Pathfinding is a large topic as it takes up a large amount of CPU so I wanted to just talk about some things I’ve been doing to speed up pathfinding for an RTS game I am making.
We all know and love A*, but we do not love its speed. We know that A* is n^2 over the number of nodes that it expands. The only thing you can do at this point is seek to reduce the n.
I began with Jump Point search, looking carefully at what points were jump points and which were not. I found that tiles next to convex corners became my jump points. My tiles use 4 borders passage (tiles are not just open-closed but have open or closed openings on each of the 4 sides), so some other points also became jump points. I wrote a function to calculate when a tile gains and loses jump point status based on which of its borders are open. Now instead of a graph consisting of every tile it just consisted of these jump points. I built a navmesh of these, which is updated every time a tile gains or loses jump point status.
For a faster jump point search, all tiles have a distance value in all 8 directions to either a wall or a jump point. Testing adjacency involves dividing the path into diagonal and straight line components and comparing distances (as opposed to walking to each tile and seeing if you hit a wall). This required me to write methods to update each tile distance whenever a wall or jump point was placed and/or removed.
At this point pathfinding has 2 major costs: finding the isovist (which is the list of jump points that the starting location is adjacent to), and finding the path. I started with a bi-directional search but I found that finding the isovist was about the same cost as finding the path, so I went back to single direction. Also, I often have a situation where the starting point is adjacent to hundreds of other points but only few of them actually yield a good path.
To improve the starting point situation, I divided each point’s list of adjacent points into 8 wedges, like a pie. Every time I expand a node, instead of fully expanding it, I just expand the wedge that contains the best angle to the end point. As I ran out of nodes in that wedge, I would move around to surrounding wedges. Now, the A* algorithm works by costing each adjacent node, putting each node into the open list, and selecting the best to expand. I found that wedging didn’t get better performance until I only costed the nodes in the wedge. This means that I won’t always get the best path. However, my testing shows that the deviance from the best path is usually very small on sparse graphs (0.04 tiles on average) while cutting pathfinding time by a factor of 4.
I also did try to tackle finding the isovist faster. The naive approach is to just test the adjacency of each jump point to the starting point. I also began this other, more involved approach using Formations.
Each jump point on the map is next to a formation (which is an obstacle - think of a rock formation). To get the formation that a jump point is next to you need to trace out the formation from the navmesh. To do that you start at a point and use the 8 distance markers in each tile to trace around the edges of the formation until you return to your starting point.
Now that you have all the formations traced out, you can draw a box around them. This formation list is updated every time you update your graph.
To get the staring point’s isovist, cast a beam in all 8 directions. To cast a beam up, for example, you need the up-right and up-left distances in the tile. The start of the beam is the tile’s x minus the up-right distance, and the beam’s width is the up-right distance plus the up-left distance. Cast this beam up to the top edge of the map (draw a box). Find all formations that lie in that box, then sort them according to their bottom edges. Create a bit field containing the visibility lanes in the beam, then eliminate the visibility lanes of each formation in the list. Record the formations that did hit (and eliminate) visibility lanes.
Repeat the above process for all 8 directions, adding only unique formations. Then test the adjacency of each point in only the formations you found.
My initial run of this process was quite slow, namely because I was testing the beam against each formation. My CS program didn’t have a class in computational geometry. After further research I have read about using interval trees, which could be a promising approach to test the collisions between each formation and beam.
Congratualtions for reading this far. Perhaps you can benefit from my journey in climbing the pathfinding Mt. Everest.