Four weeks. Four-freaking-ever. That's how I'm feelin'. Tooooooo long. But pathfinding is running! It is glorious to finally see things move!
I implemented the A* algorithm which works really well for finding optimal paths. Here are some things you should consider if you are implementing A* pathfinding:
- Use a regular 2D grid for your pathfinding data. Using polygons is a whole lot of extra pain. You need to build the polygons from your world data, figure out how to optimize them and do a bunch of geometry to build your paths. Polygons do have the one big benefit of taking up a lot less storage (one big polygon can cover a whole bunch of grid squares.) For my 200,000,000 polygon world, my pathfinding data came out to just a couple of megabytes.
- Make sure all your map data is loaded all the time. If some of the map data isn't loaded, there is a solution -- you can stop pathfinding as soon as you encounter a missing block and repath when the map data becomes available. The nice thing about A* is that it first builds paths in the general direction you want to go, so partial paths will usually look alright. Occasionally you'll get units turning around when they repath, but them's the breaks.
- Don't make your searching multithreaded. You might want to put the searching on its own thread that does one search at a time just to avoid spikes in frame time on your main thread, but supporting multiple searches in parallel is questionable. It is easy enough to split the data for A* into shared read-only (static map data) and per-search read-write (open/closed lists, path data) but it is a lot of extra work and in the end, it was the most questionable decision I made. Lesson learned.
- The Cheaplist (described in AI Game Programming Wisdom section 3.4) is a big improvement over using a sorted linked list or array for your open/closed lists. It caches the N (16 works good) cheapest nodes in an array and only repopulates that array (by scanning the full cheap list) when it runs out of the cheapest nodes.
- If you need to generate your pathfinding data ahead of time, then make sure that program is fast. Having to wait 45 minutes after a bug is a huge productivity killer.
Still more to do however. I need to add path straightening which reduces the number of turns in a path generated through a bunch of map polygons by looking to see if points in the path can be removed while still keeping the path within the existing set of map polygons. That's a day of pretty easy geometry since I already have the code to find if a point is within a line.
I also need to add support for pathing around static obstacles. That'll be a bit more work.