Jump to content
  • Advertisement
Sign in to follow this  
euroq

Easy (maybe?) grid pathfinding question

This topic is 2901 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi everyone. I have a question, and I think it's probably an easy question. In fact, I already know how to do it myself inefficiently, but what I'm going for is the BEST solution.

I am independently making a game to sell on iPhone/Android. It's a tile-based game. The map never changes, and is relatively small (max is 64x64), but there are many monsters moving through the map (possibly more than 100). Since the map never changes, I originally computed a path between the entrance and exit (there can be multiples of these), and assigned that path to the monsters. The problem is, though, that the monsters will occasionally have to change paths, for some reason or another. When I say "occasionally" I mean that it happens less than 1% of the monster's life cycle. So I thought the path recalculations didn't need to be that efficient, considering it's only 1%.

The problem is, though, that when you have 100 monsters, recalculating each of their paths, even for that mere 1% tick, will make a huge frame rate blip. So, I realized that a smarter thing to do would be, instead of assigning the paths to the monsters, assign the paths to the TILES themselves. When you have to recalculate the paths, you only do it once, instead of 100 times.

Sorry for being too pedantic. Basically, each tile will have an integer value, which is the distance from that tile to the exit (actually, each tile will have multiple integers, depending on which exit, but don't worry about that, let's just deal with one exit). A monster simply has to look at adjacent passable tiles to find the which tile has the lowest number, and that tile will be its destination.

Example with a 7x2 grid... from START to END, each tile has a number which defines its distance to the END, and "x" denotes an unpassable tile:
START 9 8 x x 3 2 1 END
x 7 6 5 4 x x

Here's a bad algorithm for calculating the distance values of each tile. The problem with this algorithm is that I was trying to avoid 100 path calculations, but now I'm doing potentially up to 64x64=4096 path calculations.
for (int x = 0; x < map.width; x++)
for (int y = 0; y < map.height; y++)
tile.distanceValue = CalculateDistanceTo(tile, target);

So here's the real meat of the question: the above algorithm is really inefficient, because, in worst case, it's O(n^2), which is technically (width*height)^2, or (64*64)^2=16,777,217. The fact of the matter is, in the above algorithm's CalculateDistanceTo(), you are implicitly finding the values for other tiles too during its calculations. Can someone point me in the direction of a good algorithm to use that could assign the distance values of each tile, all at the same time (in the same search), instead of separately calculating it for up to 64x64 tiles?

I have one thought (note that this is pseudocode off the top of my head):
1. // Calculate path between start and end
Array path = CalculatePath(start, end);
2. // Assign distance values for each point in that path, and tiles for checking the adjacent tiles later
for (int i = 0; i < path.size; i++) {
tile = path.get(i);
tile.distanceValue = path.size - i - 1;
tilesToCheck.add(tile);
}
3. // Now, for each tile that we already know the distance for it, find all adjacent tiles and assign them a value of tile.distance + 1:
while (tilesToCheck.size() > 0) {
Tile tile = tilesToCheck.removeFirst();
for each adjTile in adjacentTiles {
adjTile.distanceValue = tile.distanceValue + 1;
tilesToCheck.add(getPassableAdjacentTilesTo(tile));
}
}
4. // Continue until there are no more adjacent paths that have not been assigned a value

Basically the above algorithm finds the optimal path between start and end, and then finds each tile next to the found path and gives it a value + 1, and then continues like a BFS search to all adjacent tiles that haven't been dealt with until all tiles have a value. (Yes I know I would need avoid adding tiles that have already been checked)

I may have answered my own question in writing this :), but I'm just curious to see what everyone says about this.

Thanks!

Share this post


Link to post
Share on other sites
Advertisement
As fas as I understand your problem is quite easy to solve. You can view your grid as graph with 4 or 8 edges (=allowed movement direction). Then you have one node (exit) and want to calculate the shortest path from any node(=tile) to the exit. In this case you could use the dijkstra algorithm with the exit as input node. As a result each node(=tile) contains only the next node you have to take to reach the exit. With this approach you can easily find the shortest path from any tile to the exit and you have to use the dijkstra algo only once.

Share this post


Link to post
Share on other sites
Ashaman is correct. If you'd like more information on the topic you should be looking for single source pathfinding algorithms, as opposed to single pair pathfinding algorithms like A*.

Share this post


Link to post
Share on other sites
The algorithm that does what you describe is commonly called the "brushfire algorithm" in robotics and the "distance transform" in image processing. What it computes is more generally called the "cost to go" function or "Bellman Value Function."

Here's the brushfire algorithm:

--- Pseudocode:

Initialization:
V -- 2d array, initialized to -1 everywhere except the goal,
which is initialized to 0. This will be the Value Function.
Q -- FIFO queue, contains one node, the goal node

Algorithm:

while(Q is not empty)
{
x := dequeue(Q)

for y in neighbors(x)
{
if(V(y) == -1) // The -1 indicates that we haven't been here yet
{
V(y) := V(x) + 1;
Q.enqueue(y)
}
}
}


Note however that you don't actually have to store the distances as I did here. All you really need to store is a direction (N, S, E, or W) at each node that tells you which of its neighbors is closest; this can be better because this only requires 2 bits per tile instead of log(largest distance) bits. FYI, a function that, given a tile, returns the direction to go, is called a policy.

Share this post


Link to post
Share on other sites
Ahh perfect, thank you!

I basically was doing that algorithm, except unnecessarily finding the shortest path separately and then finding the neighbors of each point on the path and assigning distance values. Really all I need to do was start at the target tile and start assigning distance values starting from there.

Thanks for jarring my head!

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!