I am using Dijkstra's for pathfinding in my 2d game, my game is similiar in style to a tower defense game which has waves of monsters trying to reach a goal. I am currently building the paths while loading the level, saving the results, so that I do not need to perform the search during gameplay.
There is only 1 goal node in each level, so for each tile I perform the search to discover the optimal path and then store the next location to move to.
Sample of my search times for building 1 set of paths for a level:
4096 Tiles
Total time taken (Milliseconds): 157789
avg time taken to find each path (Milliseconds): 38.000000
1024 Tiles
Total time taken (Milliseconds): 13499
avg time taken to find each path (Milliseconds): 13.000000
256 Tiles
Total time taken (Milliseconds): 425
avg time taken to find each path (Milliseconds): 1.000000
For added context, here is my search algorithm:
struct MatrixPosition
{
int y;
int x;
};
struct WeightedNode
{
int nodeId;
int weightValue;
};
struct orderLeastWeight
{
inline bool operator()(const WeightedNode& weightedNode1, const WeightedNode& weightedNode2)
{
return (weightedNode1.weightValue < weightedNode2.weightValue);
}
};
// The Weighted queue always returns the lowest weight value node from get()
class WeightedQueue {
public:
WeightedQueue();
int get(); // return the item with the lowest weight value and remove it from the map
void push(int weight, int NodeId); // add item
bool empty(); // is it empty
private:
std::vector <WeightedNode> mNodeVec; // nodeId
};
WeightedQueue::WeightedQueue()
{
}
void WeightedQueue::push(int weightValue, int nodeId)
{
WeightedNode weightedNode;
weightedNode.weightValue = weightValue;
weightedNode.nodeId = nodeId;
mNodeVec.push_back(weightedNode);
std::sort(mNodeVec.begin(), mNodeVec.end(), orderLeastWeight());
}
bool WeightedQueue::empty()
{
return mNodeVec.empty();
}
int WeightedQueue::get()
{
int nodeId = mNodeVec.begin()->nodeId;
mNodeVec.erase(mNodeVec.begin());
return nodeId;
}
void Board::setMatrixPositions()
{
for (int i = 0; i < mTileCount; i++)
{
MatrixPosition matrixPosition = { i / mTileRows, i % mTileRows };
mMatrixPosition[i] = matrixPosition;
}
}
int Board::getTileId(MatrixPosition matrixPosition)
{
int tileId = mTileRows * matrixPosition.y + matrixPosition.x; // left to right
return tileId;
}
int Board::getTileId(int tileIdX, int tileIdY)
{
int tileId = mTileRows * tileIdY + tileIdX; // left to right
return tileId;
}
MatrixPosition Board::getMatrixPosition(int tileId)
{
return mMatrixPosition[tileId];
}
// reconstruct the path taken
void Board::setPath(int startTileId, int endTileId, AIStrategy aiStrategy, std::map<int, int> & cameFrom)
{
std::vector<int> path;
int currentTileId = endTileId;
path.push_back(currentTileId);
while (currentTileId != startTileId)
{
currentTileId = cameFrom[currentTileId];
path.push_back(currentTileId);
}
std::reverse(path.begin(), path.end()); // invert order to be start->end
if (path.size() >= 2)
{
mTileMap[startTileId]->setPath(aiStrategy, path[1]); // set path to the first move
// printf("setPath -- %d -> %d \n", startTileId, path[1]);
}
}
// search the board for the optimal path
void Board::findPath(int startTileId, int endTileId, AIStrategy aiStrategy)
{
std::map<int, int> cameFrom; // neighborTileId, current tileId
std::map<int, int> costSoFar; // total cost so far for the path from startTileId
std::vector<int> neighbors; // vec of the neighboring tileIds
WeightedQueue weightedQueue;
weightedQueue.push(0, startTileId); // Lowest weight item moves to the front of the queue
costSoFar[startTileId] = 0;
cameFrom[startTileId] = startTileId;
while (!weightedQueue.empty())
{
// current tile we are working with
int currentTileId = weightedQueue.get();
// exit if we've reached the goal tile
if (currentTileId == endTileId)
{
break;
}
// get all the neighbors for this position
neighbors.clear();
collectNeighbors(currentTileId, neighbors);
for (size_t i = 0; i < neighbors.size(); i++)
{
int neighborTileId = neighbors[i];
Tile *neighborTile = mTileMap[neighborTileId];
int totalCost = costSoFar[currentTileId] + neighborTile->getWeight(aiStrategy);
if (!costSoFar.count(neighborTileId) || totalCost < costSoFar[neighborTileId])
{
// if we haven't been here yet, add it to the weightedQueue
weightedQueue.push(neighborTile->getWeight(aiStrategy), neighborTileId);
cameFrom[neighborTileId] = currentTileId;
costSoFar[neighborTileId] = totalCost;
}
}
}
setPath(startTileId, endTileId, aiStrategy, cameFrom);
}
// [ 0][ 1][ 2][ 3][ 4]
// [ 5][ 6][ 7][ 8][ 9]
// [10][11][12][13][14]
// [15][16][17][18][19]
// [20][21][22][23][24]
void Board::collectNeighbors(int tileId, std::vector<int> & neighbors)
{
MatrixPosition tile = getMatrixPosition(tileId);
const int x = tile.x;
const int y = tile.y;
if (y > 0) // otherwise an underflow occurred, so not a neighbour
{
int up = y - 1;
int neighborTileId = getTileId(x, up);
neighbors.push_back(neighborTileId);
// printf("up -- neighborTileId: %d y: %d x: %d\n", neighborTileId, up, x);
}
// down
if (y < mTileRows - 1)
{
int down = y + 1;
int neighborTileId = getTileId(x, down);
neighbors.push_back(neighborTileId);
// printf("down -- neighborTileId: %d y: %d x: %d\n", neighborTileId, down, x);
}
// left
if (x > 0)
{
int left = x - 1;
int neighborTileId = getTileId(left, y);
neighbors.push_back(neighborTileId);
// printf("left -- neighborTileId: %d y: %d x : %d\n", neighborTileId, y, left);
}
// right
if (x < mTileColumns - 1)
{
int right = x + 1;
int neighborTileId = getTileId(right, y);
neighbors.push_back(neighborTileId);
// printf("right -- neighborTileId: %d y: %d x: %d\n", neighborTileId, y, right);
}
}
Here is my question:
What I'm currently doing works fine if I wanted to keep my level sizes small (256) or pre-generate larger levels. However the problem is that I would really like to support large maps (4096+ tile) and I want to allow the player to change the level. However with the search taking 2-3 Minutes on a 4096 node graph that's not an option even if I did it between "waves" of monsters.
Looking for other ideas to this problem, one thing I thought of was that I could pre-generate the initial level save the complete path to the goal on every tile along with their total costs. Then, between waves of monsters I would only need to update the weight values of those tiles which changed, re-sum the weight totals for the changed paths, and re-order the paths.
Appreciate any thoughts on that, or any other suggestions.
