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: