2
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

Don't search every tile-path. Most of your data is going to be redundant. If there is a solution for tile a, going through tiles b,c,d,e,f - goal then the solution for tile b is by definition c,d,e,f - goal. Your goal shouldn't be solving for which path from tile X is the best. But rather, assigning directional vectors to all tiles and the direction each of them should go for the optimal path. If I am on tile X, which direction do I go. The answer to that is always the same, regardless where you came from.

So you want to actually solve from the goal, outward painting every spot with an optimal direction vector. Basically you can do this by what amounts to Dijkstra's, giving each node you see traveling backwards from the goal with an optimum amount you can offer with that direction, and if it currently has a better option, pass, else give that tile that direction. Until all tiles have been visited and have the optimal path. It should take a few milliseconds to complete.

\$\endgroup\$
  • 1
    \$\begingroup\$ Ah ha! Yes that makes perfect sense, I did not think from this perspective and had greatly overcomplicated the problem. I re-wrote my code to just perform the search once from the destination, updating the directional vector within the next neighbor loop. Working fantastic now...many thanks \$\endgroup\$ – Zugdud Oct 30 '16 at 21:29
3
\$\begingroup\$

Dijkstra's Algorithm uses a priority queue as its main data structure. In your code it's WeightedQueue.

A priority queue can be implemented with O(log N) insert and O(log N) remove. Your queue has O(N log N) insert and O(N) remove. This doesn't matter for small N but as you've found, as N increases, it's too slow.

I suggest using std::priority_queue<WeightedNode> instead of std::vector<WeightedNode>; I have some code here you can look at.

\$\endgroup\$
  • 1
    \$\begingroup\$ So it turns out I had a massive fundamental problem with my implementation due to a misunderstanding on my part, as pointed out by Tatarize. In addition to resolving that, which solved the problem (performing the search once rather than N ^2 times), I also replaced my WeightedQueue implementation with std::priority_queue and a custom object comparator. That cleaned up my code, so my thanks! Also your website looks great, I love the interactive examples, I'm going to spend some time there \$\endgroup\$ – Zugdud Oct 30 '16 at 21:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.