Pathfinding

Summary

Hello!I've recently been working on the pathfinding for NPCs in my game, which is something I've been looking forward to for a while now since it's a nice chunky problem to solve. I thought I'd write up this post about how I went about it all. I had a few extra requirements of my pathfinding, due to how my game plays: Must deal with a dynamic physical environment (objects can move freely and are destructible)Have paths that prefer to keep their distance from objects but still get close when neededAllow for wrapping around the borders of the game area (Asteroids style) General Approach My first thought was that I wanted detailed paths so that they could thread through messy arrangements of objects quite easily. This would mean a longer search time, so the simple choice of search algorithm is A*. And since I need to query the world for each node to see whether it's blocked, I thought I'd use space partitioning with the queries to cut down on the number required for each path. I ended up sticking to this plan, and figuring out the more detailed stuff along the way. Space Partitioned Queries I built a space partitioning tree where each node covers a specific area of the game, and then each of that node's children covers a specific area of their parent's area (with the tree's root covering the whole game area). I do this to a depth of 6 and then the leaf nodes effectively make up the navigation grid for path finding. Now when I check if a node is blocked it will first check its parent. If its parent is not blocked, then none of its children are blocked. If the parent is blocked, then the child node needs to run its own query to see whether its own area is blocked. This allows us to know whether large areas of the game are not blocked in very few queries, which is useful because these queries are expensive. A* Search The actual search is a pretty standard A* search. Each node has 8 neighbours, with nodes on the edge having wrapped neighbours, which are cached along with t...