Implementing A* algorithm using C++ templates

While developing my game, blades of the righteous, I’ve decided to make better pathfinding both for AI and for the player (the units can be given orders to move through multiple tiles – we need to find the optimal path). As I’m probably going to encounter the problem quite often in my next games, I’ve decided to make a universal function for pathfinding that returns the tile path through the generic field. The use of C++ template comes to mind.

Used this article as a reference: http://www.gamedev.net/page/resources/_/technical/artificial-intelligence/a-pathfinding-for-beginners-r2003

 

A bit of a background: I usually make 2d game maps as 2d array of pointers to units. If tile is empty, it contains nullptr. Otherwise it points to the unit.

Unit* field[FIELD_W][FIELD_H]
field[0][0] = nullptr; // field with coordinates 0,0 is empty
field[1][1] = myUnit; // field with coordinates 1,1 contains myUnit

Seems pretty straightforward, but the problems began when I’ve introduced the units that take two tiles. The Unit class still has only one coordinate pair (x and y), but now the width has been added into the equation. That adds lots of border cases, like:

  • What happens, if our unit of length 2 tries to reach unit to the right of it? For the sake of example, let’s say that our unit is on tile (1,1), the unit that we need to reach is on (7, 1). In that case, the final destination is going to be (1,5) – because our unit occupies both (1,5) and (1,6) and therefore stands near by (1,7)
  • What happens if both units have the length of 2 tiles? What happens if our target is to the right? Then we’d have to approach (targetX – 2, targetY) coordinates.
  • What if our destination tile is empty, but is on the border of the map? That means our unit would not be able to stand there because he lacks length.

Additional data structures/functions are introduced:

// tile, == operator needed to use it with std::find
struct TileCoords
{
    int x;
    int y;
    bool operator==(const TileCoords& other) const
    {
        return x == other.x && y == other.y;
    }
};

// inner tile info, necessary for use within algorithm:
struct TileInfo
{
    TileCoords comeFrom;
    bool isStartingTile;
    bool isVisited;
    int G; // in my case - basically distance from starting tile if you follow 
           // the chosen path (in more generic case: how expensive is it to get here)
    int H; // our guess how much we need to move to reach destination from 
           // that time (it's inaccurate most of the time, but we need to use something as a prediction)
};

using tile_list = std::vector; // define a variable type name for better code readability

// do given x and y coordinates belong to the field with width w and height h?
bool areValidCoordinates(int x, int y, int w, int h) 
{
    return (x >= 0 && y >= 0 && x < w && y < h);
}

// prediction function for H value, basically calculates the distance between two points
int HFunc(int xStart, int yStart, int xDest, int yDest) 
{
    return std::abs(xStart - xDest) + std::abs(yStart - yDest);
}

Therefore, to make A* as generic as possible, we will need a function template:

template <typename T> tile_list Astar(T*** field, // link to the battlefield
                          size_t w, // battlefield width
                          size_t h, // battlefield height
                          bool(*checkFunc)(const T*), // function that checks whether 
                                                      // the given field is available
                                                      // to be moved on
                          int xStart, // starting tile x (where the units stands at)
                          int yStart, // starting tile y (where the unit stands at)
                          int xDest,  // destination tile x
                          int yDest, // destination tile y
                          bool include_destination, // do return destination tile 
                                                    // in the resulting final path?
                          int unit_w) //unit width
{
    if (areValidCoordinates(xStart, yStart, w, h) == false)
    {
        return {}; //empty list
    }

    // check if unit can actually fit in destination
    if (include_destination)
    {
        for (int newX = xDest + 1; newX < xDest + unit_w; newX++)
        {
            if (areValidCoordinates(newX, yDest, w, h) == false)
            {
                return{}; // empty list, one of the destination tiles is out of bounds
            }

            if (checkFunc(field[newX][yDest]) == false)
            {
                return{}; // empty list, one of the destination tiles is occupied
            }
        }
    }

    tile_list closed_set;
    tile_list open_set;

    std::vector<std::vector> evaluatedCoords(w); // array of array

    // initialize values, calculate initial predictions:
    for (size_t x = 0; x < w; x++)
    {
        evaluatedCoords[x] = std::vector(h);
        for (size_t y = 0; y < h; y++)
        {
            evaluatedCoords[x][y].isVisited = false;
            evaluatedCoords[x][y].G = 0;
            evaluatedCoords[x][y].H = HFunc(x, y, xDest, yDest);
        }
    }

    bool destinationReached = false;
    // add starting tile to open list
    evaluatedCoords[xStart][yStart].G = 0;
    evaluatedCoords[xStart][yStart].isStartingTile = true;
    evaluatedCoords[xStart][yStart].isVisited = true;

    if (areValidCoordinates(xStart, yStart, w, h))
    {
        open_set.push_back({ xStart, yStart });
    }

    // while we have not reached destination
    // and there are tiles that can still be evaluated
    while (open_set.empty() == false && destinationReached == false)
    {
        TileCoords currentTile;
        int minF = w * h; // minimum cost that is required to reach destination
        size_t tileNum;   // tile index number
        // select assumed lowest-cost path
        for (size_t i = 0; i < open_set.size(); i++)
        {
            int F = evaluatedCoords[xStart][yStart].G + evaluatedCoords[xStart][yStart].H;
            if (F < minF)
            {
                tileNum = i;
                currentTile = open_set[tileNum];
                minF = F;
            }
        }

        // make an array of adjacent coordinates
        TileCoords adjacentCoordinates[] = { { currentTile.x - 1, currentTile.y }, 
                                                { currentTile.x + 1, currentTile.y },
                                                { currentTile.x, currentTile.y - 1 },
                                                { currentTile.x, currentTile.y + 1 } };

        // ... then go through it and check the new possible tiles
        for (int i = 0; i < sizeof(adjacentCoordinates) / sizeof(*adjacentCoordinates); i++)
        {
            if (areValidCoordinates(adjacentCoordinates[i].x, adjacentCoordinates[i].y, w, h))
            {
                if (std::find(closed_set.begin(), closed_set.end(), adjacentCoordinates[i]) == closed_set.end())
                {
                    int adjX = adjacentCoordinates[i].x; // to make code look cleaner
                    int adjY = adjacentCoordinates[i].y; 
                    // if this tile has not been visited:
                    if (std::find(open_set.begin(), open_set.end(), adjacentCoordinates[i]) == open_set.end())
                    {
                        // we found are destination
                        if (adjX == xDest && adjY == yDest)
                        {
                            evaluatedCoords[xDest][yDest].comeFrom.x = currentTile.x;
                            evaluatedCoords[adjX][adjY].comeFrom.y = currentTile.y;
                            destinationReached = true;
                            break;
                        }

                        // see if found tiles are valid through the whole unit width
                        bool validTiles = true;
                        for (int newX = adjX; newX < adjX + unit_w; newX++)
                        {
                            // coordinates are valid?
                            if (areValidCoordinates(newX, adjY, w, h) == false)
                            {
                                validTiles = false;
                                break;
                            }

                            // field can be visited?
                            if (checkFunc(field[newX][adjY]) == false)
                            {
                                validTiles = false;
                                break;
                            }
                        }
                        
                        // if newfound tile is OK:
                        // we have an unocupied field
                        if (validTiles)
                        {
                            // say that we've came to evaluated coordinates from the current tile
                            evaluatedCoords[adjX][adjY].comeFrom.x = currentTile.x;
                            evaluatedCoords[adjX][adjY].comeFrom.y = currentTile.y;
                            evaluatedCoords[adjX][adjY].G = evaluatedCoords[currentTile.x][currentTile.y].G + 1;
                            open_set.push_back(adjacentCoordinates[i]);
                        }
                    }
                    else
                    {
                        // if we visited this tile already
                        if (evaluatedCoords[adjX][adjY].G > evaluatedCoords[currentTile.x][currentTile.y].G + 1)
                        {
                            // but the path would be shorter if we moved to this tile
                            // from the other one
                            evaluatedCoords[adjX][adjY].comeFrom.x = currentTile.x;
                            evaluatedCoords[adjX][adjY].comeFrom.y = currentTile.y;
                            evaluatedCoords[adjX][adjY].G = evaluatedCoords[currentTile.x][currentTile.y].G + 1;
                        }
                    }
                }
            }
        }

        // move the current tile to visited
        closed_set.push_back(currentTile);
        // remove it from unvisited tiles
        open_set.erase(open_set.begin() + tileNum);
    }

    if (destinationReached)
    {
        // let's make a path
        // go backwards from destination
        tile_list path;
        if (include_destination)
        {
            path.push_back({ xDest, yDest });
        }

        TileCoords currentTile = evaluatedCoords[xDest][yDest].comeFrom;

        // ... until we reach the starting tile
        while (currentTile.x != xStart || currentTile.y != yStart)
        {
            path.push_back(currentTile);
            currentTile = evaluatedCoords[currentTile.x][currentTile.y].comeFrom;
        }

        return path;
    }
    else
    {
        // could not find a way - return nothing
        return {};
    }
}

 

 

As a bonus, here’s the episode from the reworked battle system:

Leave a Reply

Your email address will not be published. Required fields are marked *