Skynet/Skynet/PathFinder.cpp

Go to the documentation of this file.

#include "PathFinder.h"
#include "Heap.h"
#include "BuildingPlacer.h"
#include "TerrainAnaysis.h"
#include "DrawBuffer.h"
#include "Logger.h"

BuildTilePath PathFinderClass::CreateTilePath(TilePosition start, TilePosition target, std::tr1::function<bool (TilePosition)> tileTest, std::tr1::function<int (TilePosition, TilePosition, int)> gFunction, std::tr1::function<int (TilePosition, TilePosition)> hFunction, int maxGValue, bool diaganol)
{
        BuildTilePath path;

        Heap<TilePosition, int> openTiles(true);
        std::map<TilePosition, int> gmap;
        std::map<TilePosition, TilePosition> parent;
        std::set<TilePosition> closedTiles;

        openTiles.push(std::make_pair(start, 0));
        gmap[start] = 0;
        parent[start] = start;

        while(!openTiles.empty())
        {
                TilePosition p = openTiles.top().first;
                int gvalue = gmap[p];

                if(p == target || (maxGValue != 0 && gvalue >= maxGValue))
                        break;

                int fvalue = openTiles.top().second;
                
                openTiles.pop();
                closedTiles.insert(p);

                int minx = std::max(p.x() - 1, 0);
                int maxx = std::min(p.x() + 1, BWAPI::Broodwar->mapWidth());
                int miny = std::max(p.y() - 1, 0);
                int maxy = std::min(p.y() + 1, BWAPI::Broodwar->mapHeight());

                for(int x = minx; x <= maxx; x++)
                {
                        for(int y = miny; y <= maxy; y++)
                        {
                                if (x != p.x() && y != p.y() && !diaganol)
                                        continue;

                                TilePosition t(x, y);

                                if (closedTiles.find(t) != closedTiles.end())
                                        continue;

                                if(!tileTest(t))
                                        continue;

                                int g = gFunction(t, p, gvalue);

                                int f = g + hFunction(t, target);
                                if (gmap.find(t) == gmap.end() || g < gmap.find(t)->second)
                                {
                                        gmap[t] = g;
                                        openTiles.set(t, f);
                                        parent[t] = p;
                                }
                        }
                }
        }

        if(!openTiles.empty())
        {
                TilePosition p = openTiles.top().first;
                while(p != parent[p])
                {
                        path.addNode(p);
                        p = parent[p];
                }
                path.addNode(start);
                path.isComplete = true;
        }

        return path;
}

class FleeGValue
{
public:
        int operator()(TilePosition currentTile, TilePosition previousTile, int gTotal)
        {
                return gTotal + 1;
        }
};

class FleeHValue
{
public:
        FleeHValue(const UnitGroup &enemies)
                : mEnemies(enemies)
        {
                mMmaxHValue = std::max(BWAPI::Broodwar->mapHeight(), BWAPI::Broodwar->mapWidth());
        }

        int operator()(TilePosition position, TilePosition target)
        {
                int h = 0;

                for each(Unit enemy in mEnemies)
                {
                        h += mMmaxHValue - (int)position.getDistance(enemy->getTilePosition());
                }

                h /= mEnemies.size();

                return h;
        }

        const UnitGroup &mEnemies;
        int mMmaxHValue;
};

class FleeTileTest
{
public:
        FleeTileTest(bool stickToRegion, TilePosition start)
                : mStickToRegion(stickToRegion)
                , mStart(start)
        {}

        bool operator()(TilePosition position)
        {
                if(!BuildingPlacer::Instance().isTileWalkable(position))
                        return false;

                return !mStickToRegion || TerrainAnaysis::Instance().getRegion(position) == TerrainAnaysis::Instance().getRegion(mStart);
        }

        bool mStickToRegion;
        TilePosition mStart;
};

BuildTilePath PathFinderClass::CreateAdvancedFleePath(TilePosition start, const UnitGroup &enemies, bool stickToRegion)
{
        return CreateTilePath(start, BWAPI::TilePositions::None, FleeTileTest(stickToRegion, start), FleeGValue(), FleeHValue(enemies), 20, false);
}

RegionPath PathFinderClass::CreateRegionPath(Region start, Region target)
{
        RegionPath path;

        Heap<Region, int> openRegions(true);
        std::map<Region, int> gmap;
        std::map<Region, Region> parent;
        std::set<Region> closedRegions;

        openRegions.push(std::make_pair(start, 0));
        gmap[start] = 0;
        parent[start] = start;

        while(!openRegions.empty())
        {
                Region region = openRegions.top().first;

                if(region == target)
                {
                        while(region != parent[region])
                        {
                                path.addNode(region);
                                region = parent[region];
                        }
                        path.addNode(start);
                        path.isComplete = true;
                        return path;
                }

                int gvalue = gmap[region];
                int fvalue = openRegions.top().second;

                openRegions.pop();
                closedRegions.insert(region);

                for each(Chokepoint choke in region->getChokepoints())
                {
                        Region other = choke->getRegions().first;
                        if(other == region)
                                other = choke->getRegions().second;

                        int g = gvalue + region->getCenter().getApproxDistance(other->getCenter());
                        int h = other->getCenter().getApproxDistance(target->getCenter());

                        int f = g + h;
                        if(gmap.count(other) == 0 || g < gmap.find(other)->second)
                        {
                                gmap[other] = g;
                                openRegions.set(other, f);
                                parent[other] = region;
                        }
                }
        }

        return path;
}

PositionPath PathFinderClass::CreateCheapWalkPath(Position start, Position target)
{
        if(!BWAPI::Broodwar->hasPath(start, target))
                return PositionPath();

        Region startRegion = TerrainAnaysis::Instance().getRegion(TilePosition(start));
        Region endRegion = TerrainAnaysis::Instance().getRegion(TilePosition(target));

        PositionPath path;

        if(startRegion == endRegion)
        {
                path.addNode(target);
                path.addNode(start);
                path.isComplete = true;

                return path;
        }

        RegionPath regionPath = CreateRegionPath(startRegion, endRegion);

        if(!regionPath.isComplete)
                return path;

        regionPath.drawPath();

        path.path.push_back(start);

        Region previousRegion;
        for each(Region region in regionPath.path)
        {
                if(previousRegion)
                {
                        for each(Chokepoint choke in region->getChokepoints())
                        {
                                if(choke->getRegions().first == previousRegion || choke->getRegions().second == previousRegion)
                                {
                                        path.path.push_back(choke->getCenter());
                                        break;
                                }
                        }
                }

                previousRegion = region;
        }

        path.path.push_back(target);
        path.isComplete = true;

        return path;
}

WalkPositionPath PathFinderClass::CreateWalkPath(WalkPosition start, WalkPosition target, std::tr1::function<bool (WalkPosition)> tileTest, std::tr1::function<int (WalkPosition, WalkPosition, int)> gFunction, std::tr1::function<int (WalkPosition, WalkPosition)> hFunction, int maxGValue, bool diaganol)
{
        WalkPositionPath path;

        Heap<WalkPosition, int> openTiles(false);
        std::map<WalkPosition, int> gmap;
        std::map<WalkPosition, WalkPosition> parent;
        std::set<WalkPosition> closedTiles;

        int mapWidth = BWAPI::Broodwar->mapWidth() * 4;
        int mapHeight = BWAPI::Broodwar->mapHeight() * 4;

        openTiles.push(std::make_pair(start, 0));
        gmap[start] = 0;
        parent[start] = start;

        while(!openTiles.empty())
        {
                WalkPosition p = openTiles.top().first;
                int gvalue = gmap[p];

                if(p == target || (maxGValue != 0 && gvalue >= maxGValue))
                        break;

                int fvalue = openTiles.top().second;

                openTiles.pop();
                closedTiles.insert(p);

                int minx = std::max(p.x - 1, 0);
                int maxx = std::min(p.x + 1, mapWidth);
                int miny = std::max(p.y - 1, 0);
                int maxy = std::min(p.y + 1, mapHeight);

                for(int x = minx; x <= maxx; x++)
                {
                        for(int y = miny; y <= maxy; y++)
                        {
                                if (x != p.x && y != p.y && !diaganol)
                                        continue;

                                WalkPosition t(x, y);

                                if(closedTiles.find(t) != closedTiles.end())
                                        continue;

                                if(!tileTest(t))
                                        continue;

                                int g = gFunction(t, p, gvalue);

                                int f = g + hFunction(t, target);
                                if (gmap.find(t) == gmap.end() || g < gmap.find(t)->second)
                                {
                                        gmap[t] = g;
                                        openTiles.set(t, f);
                                        parent[t] = p;
                                }
                        }
                }
        }

        for each(std::pair<WalkPosition, int> pos in gmap)
        {
//              DrawBuffer::Instance().drawBufferedLine(BWAPI::CoordinateType::Map, pos.first.x*8, pos.first.y*8, parent[pos.first].x*8, parent[pos.first].y*8, 999999);
//              String_Builder string;
//              string << pos.second;
//              DrawBuffer::Instance().drawBufferedText(BWAPI::CoordinateType::Map, pos.first.x * 8, pos.first.y * 8, string, 999999);
        }

        if(!openTiles.empty())
        {
                WalkPosition p = openTiles.top().first;
                while(p != parent[p])
                {
                        path.addNode(p);
                        p = parent[p];
                }
                path.addNode(start);
                path.isComplete = true;
        }

        return path;
}