Skynet/Skynet/MapHelper.cpp

Go to the documentation of this file.

#include "MapHelper.h"

#include <regex>

#include "UnitTracker.h"
#include "Heap.h"
#include "BaseTracker.h"
#include "PathFinder.h"

TilePosition MapHelper::spiralSearch(TilePosition startLocation, std::tr1::function<bool (TilePosition)> testFunction, int maxRadius)
{
        int x = startLocation.x();
        int y = startLocation.y();

        int length = 1;
        int j      = 0;
        bool first = true;
        int dx     = 0;
        int dy     = 1;

        if(maxRadius == 0)
                maxRadius = std::max(BWAPI::Broodwar->mapWidth(), BWAPI::Broodwar->mapHeight());

        while(length < maxRadius)
        {
                if(x >= 0 && x < BWAPI::Broodwar->mapWidth() && y >= 0 && y < BWAPI::Broodwar->mapHeight())
                {
                        TilePosition location(x, y);
                        if(testFunction(location))
                                return location;
                }

                x = x + dx;
                y = y + dy;

                //count how many steps we take in this direction
                ++j;
                if(j == length) //if we've reached the end, its time to turn
                {
                        //reset step counter
                        j = 0;

                        //Spiral out. Keep going.
                        if(!first)
                                ++length; //increment step counter if needed

                        //first=true for every other turn so we spiral out at the right rate
                        first = !first;

                        //turn counter clockwise 90 degrees:
                        if (dx == 0)
                        {
                                dx = dy;
                                dy = 0;
                        }
                        else
                        {
                                dy = -dx;
                                dx = 0;
                        }
                }
                //Spiral out. Keep going.
        }

        return BWAPI::TilePositions::None;
}

std::set<TilePosition> MapHelper::floodFill(TilePosition start, std::tr1::function<bool (TilePosition)> testFunction, std::set<TilePosition> targets, std::set<TilePosition> ignoreTiles)
{
        bool noTargets = targets.empty();

        std::set<TilePosition> remainingTiles;
        remainingTiles.insert(start);

        while(!remainingTiles.empty())
        {
                if(!noTargets && targets.empty())
                        return targets;

                TilePosition tile = *remainingTiles.begin();

                ignoreTiles.insert(tile);
                remainingTiles.erase(tile);

                if(!tile.isValid())
                        continue;

                if(!testFunction(tile))
                        continue;

                if(noTargets)
                        targets.insert(tile);
                else
                        targets.erase(tile);

                if(ignoreTiles.count(TilePosition(tile.x() + 1, tile.y())) == 0)
                        remainingTiles.insert(TilePosition(tile.x() + 1, tile.y()));
                if(ignoreTiles.count(TilePosition(tile.x() - 1, tile.y())) == 0)
                        remainingTiles.insert(TilePosition(tile.x() - 1, tile.y()));
                if(ignoreTiles.count(TilePosition(tile.x(), tile.y() + 1)) == 0)
                        remainingTiles.insert(TilePosition(tile.x(), tile.y() + 1));
                if(ignoreTiles.count(TilePosition(tile.x(), tile.y() - 1)) == 0)
                        remainingTiles.insert(TilePosition(tile.x(), tile.y() - 1));
        }

        return targets;
}

std::map<WalkPosition, int> MapHelper::walkSearch(WalkPosition start, std::tr1::function<bool (WalkPosition)> testFunction, std::set<WalkPosition> targets, std::set<WalkPosition> ignoreTiles)
{
        std::map<WalkPosition, int> returnDistances;

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

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

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

        int maxhvalue = std::max(mapHeight, mapWidth);

        while(!openTiles.empty())
        {
                WalkPosition p = openTiles.top().first;

                int fvalue = openTiles.top().second;
                int gvalue = gmap[p];

                openTiles.pop();
                closedTiles.insert(p);
                returnDistances[p] = gvalue;

                for(int i = 0; i < 4; ++i)
                {
                        int x = i == 0 ? 1 : i == 1 ? -1 : 0;
                        int y = i == 2 ? 1 : i == 3 ? -1 : 0;
                        WalkPosition tile(p.x + x, p.y + y);

                        if(tile.x < 0 || tile.y < 0 || tile.x >= mapWidth || tile.y >= mapHeight)
                                continue;

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

                        if(!testFunction(tile))
                                continue;

                        int g = gvalue + 1;

                        int f = g;
                        if(gmap.find(tile) == gmap.end() || gmap[tile] > g)
                        {
                                gmap[tile] = g;
                                openTiles.set(tile, f);
                        }
                }
        }

        return returnDistances;
}

bool MapHelper::isAnyVisible(TilePosition location, BWAPI::UnitType type)
{
        for(int x = location.x(); x < location.x() + type.tileWidth(); ++x)
        {
                for(int y = location.y(); y < location.y() + type.tileHeight(); ++y)
                {
                        if(BWAPI::Broodwar->isVisible(x, y))
                                return true;
                }
        }

        return false;
}

bool MapHelper::isAllVisible(TilePosition location, BWAPI::UnitType type)
{
        for(int x = location.x(); x < location.x() + type.tileWidth(); ++x)
        {
                for(int y = location.y(); y < location.y() + type.tileHeight(); ++y)
                {
                        if(!BWAPI::Broodwar->isVisible(x, y))
                                return false;
                }
        }

        return true;
}

bool MapHelper::isTileWalkable(TilePosition location)
{
        return isTileWalkable(location.x(), location.y());
}

bool MapHelper::isTileWalkable(int x, int y)
{
        for(int nx = x * 4; nx < x * 4 + 4; ++nx)
        {
                for(int ny = y * 4; ny < y * 4 + 4; ++ny)
                {
                        if(!BWAPI::Broodwar->isWalkable(nx, ny))
                                return false;
                }
        }

        return true;
}

bool MapHelper::mapIs(std::string name)
{
        std::string mapName = BWAPI::Broodwar->mapName();
        std::transform(mapName.begin(), mapName.end(), mapName.begin(), tolower);

        std::string mapFileName = BWAPI::Broodwar->mapFileName();
        std::transform(mapFileName.begin(), mapFileName.end(), mapFileName.begin(), tolower);

        std::transform(name.begin(), name.end(), name.begin(), tolower);

        return std::tr1::regex_search(mapName.begin(), mapName.end(), std::tr1::regex(name)) || std::tr1::regex_search(mapFileName.begin(), mapFileName.end(), std::tr1::regex(name));
}

int MapHelper::getGroundDistance(Position start, Position end)
{
        if(!BWAPI::Broodwar->hasPath(start, end))
                return std::numeric_limits<int>::max();

        int groundDistance = PathFinder::Instance().CreateCheapWalkPath(start, end).getLength();
        int linearDistance = start.getApproxDistance(end);

        if(groundDistance < linearDistance)
                return linearDistance;

        return groundDistance;
}