Pathfinding optimization.

Newbie & Debugging Questions
#1

I have some hand made pathfinding code and I wonder if it could be more performant.

Currently I’m finding a path on a 200x200 (40000) grid map in approximatively 50 ms in worst case scenario. Does anyone get better result with pathfinding? Would really like to improve my code.

Of course, I have a lot of otimization where I can reduce the number of cell in the map and get the same result but I would like to see if I can improve the size of the map and get the same result.

N.B. : For comparison, I benchmark the difference in speed between my implementation and the one that come in Slick and mine is faster by 64 times. (Maybe I did something wrong with slick one but that’s what I got)

N.B2 : An early version of my code can be see here. I currently swap the arrayList of open nodes by a MinHeap to get a boost in speed by 10 times.

#2

Why don’t you post the current code? Hard to tell whether it can be improved without seeing it.

#3

http://code.google.com/p/protectcastle/source/browse/pathfinding/pathfinding/grid/astar/GridAstar.java

#4

I optimize my A* with a lookup table that is filled in after each path. This method assumes static obstacles and not to many cells/nodes since the algorithm uses N^2 space.
After one A* search, each subsequent search (involving any of the nodes in the found path) only takes linear time in number of nodes on the optimal path.

The lookuptable[fromId][toId] contains the ID (or index/reference) of the next node on the optimal path from fromId to toId. When you get an optimal path, you can update the table for each node on that path in L^2 time where L is the number of nodes on the path.

When you want a path from A to B you check the lookuptable[A][B]
If the ID exists you get that A’ and continue with A' = lookuptable[A'][B] until you get A’ == B and you collect all the node IDs during the search.

#5

I guess lookup table could work since the world is not changing that often. Only placing a couple of building some times.

#6

The problem with a changing world is that you have to invalidate all stored paths in the lookup that involve the newly occupied cells or do something more fancy :slight_smile:

#7

Thanks for the idea krasse.

I guess I should have thought about it sooner but since my game is a tower defense all unit go to the same point so I can precalculate easily the path for each node.

Before : 50 ms for a 200x200 map
Now : 0.04 ms for a 200x200 map

The only draw back is that it takes around 50 ms to precalculate every path and you must do it everytime that you place or remove a building. But that is a lot faster :slight_smile:

#8

Krasse, that is not correct. You have to recalculate the paths every time you place or destroy/sell a building, as that could give a shorter path to the target.

#9

Some fancy way would be find all paths that include edited cell and only update those paths. Bad thing is that the worst case scenario is then even heavier and that can happen very often.

#10

Yes, you are right when it comes to destroying/selling buildings but you can still do this when you place a new building (unless it is a bridge or something that opens up new travel paths). It might be very expensive though as pitbuller pointed out :slight_smile:

BTW, I am happy that you were able to optimize your pathfinding Gudradain!

#11

yeah, tower defense is a very specific type of pathfinding were your end destination almost never change so this optimization was possible here.

But I’m thinking another place where this sort of optimization would be really usefull : RTS with gathering unit. Those unit almost always come back to the same base to bring back their resources. So for each resource base you can precalculate a distance map and then use this pathfinding method. The resource bases almost never change their location once placed so you don’t need to calculate the distance map very often and after that pathfinding for the unit bringing back their ressources to that base is almost instant (0.3 ms on a 1000X1000 map from the testing I did so far).

This way the only sort of pathfinding that is still expensive are the attacking unit that you control. That should make it lot easier to deal with pathfinding performance in an RTS or similar game.

#12

How could you even do this? Just solving one single time with A* shouldn’t be very expensive (50ms seems very expensive, btw, unless you have a massive grid, I’d double check your heuristic is working correctly). And once you change the grid in any way whatsoever you need to recalculate absolutely every path that may involve that space… and I can’t think of any way to know for sure whether a path involves it.

The only things you could do, as far as I can think of, is do a partial A*, that is if the full path is from A to Z and you remove a building a M, do a pathfind between J and Q, and replace that portion of the path. The drawback is that this might not get the best solution, though. Another option is to make “mipmap” equivalents for your grid, and pathfinding within that. i.e. divide your grid into several different-sized grids. So like if you have a 100x100 maze, have a 10x10 representation of it, a 25x25, a 50x50, and finally the actual 100x100 grid. Each grid space in the 10x10 actually represents 100 grid spaces, in the 25x25 16 spaces, in the 50x50 4 spaces. As entities are built or removed, you not only update the 100x100 grid, you also update the larger grids. If anything at all exists in those 100 spaces for the 10x10, it’s considered a full space. So what you do is try to pathfind on each level, starting with the 10x10 down to the 100x100. You can extrapolate what an empty space means in any one of the grids, even if you can’t compute a full path with it. Like if there is an empty space in the 10x10, that means everything in that 100 space area in the 100x100 is empty so you don’t need to pathfind through the whole thing. It’s pretty complicated and easy to mess up, but can help in certain situations. Still, if you’re doing tower defense, I imagine that when you really need to get the pathfinding fast (when the whole screen is filled) it’s actually going to slow you down because you’ll start doing a bunch of redundant checks…

So in conclusion I’d just figure out why your algorithm is slow and rerun it whenever a building is plopped down. :stuck_out_tongue:

#13

I always have the same destination since it is a tower defense game. So I just need to calculate every paths for one cell. It’s fast. In fact, it’s as fast as the calculation of normal A* in worst case scenario (where you iterate through all the cell in the map).

I don’t think that my code is slow, in fact I couldn’t find one that is faster for now. Still, I would gladly have an example of faster code so I can improve. Your Ah!Maze example seems to take forever to run even when you try to reduce the draw delay to 0. Didn’t check the source code to see if it has speed limitation in it to help for example purpose though.

I thought a long time about mipmap but those seems pretty complicated to get right. The problem is that removing or adding a building in one mipmap cell doesn’t affect only that mipmap but the whole map as that would create new possible path or remove previous one.

#14

Gudradain have done wonders with pathfinding. Our game run now almoust full fps at cell phone(crappy one) before any optimizations to rendering or other game logic.

#15

Thx for frustrating me Eli.

To calculate the distance map on a 200X200 map it takes 15 ms instead of 40 ms now.

#16

If all weights are equal, you’re probably using a floodfill that tags each cell with an age and call it a day :slight_smile:

#17

Could you explain more? I did’t quite understand.

#18

Use a pathfinder without a target: it will flood the entire area. Using the data in the nodes, you can then backtrack from every cell.

To optimize the end result, you can make a byte[] that holds a value ‘pointing’ to the neighbouring cell that is closer to the ‘target’ (tower?).

To backtrack, you can simple lookup the value in the grid, and jump through it, without any logic for finding the optimal backtracking path.

#19

That’s exactly what I’m using right now Riven. It’s pretty fast. It never take more than a few micro seconds.

But my old pathfinding code was also using backtrack but without a flood fill. Since the destination change each time I need to calculate enough of the distance map to reach my destination. Than I was backtracking from my destination toward my current location to get the path.

Currently, the code only work for one destination but I could probably change it so it work for many destination. I would have to store a list of distanceMap (one for every cell) it could be pretty long :S. But if I calculate only the map that are required it could be faster.

EDIT : Although it doesn’t matter if the node are not weighted equal. My floodfill algorithm is A star where the heuristic always return 0.

#20

It’s extremely easy. Just start your search from multiple sources. I use a strategy like that to enable quickly finding the shortest route between N start points and M end points. (which lumberjack is closest to a tree)