Now that I have complicated levels with tonnes of places to get enemies stuck, it's probably time to tackle path finding. I read a bunch of blog posts on A*, and while it generally seems to be the default way to go, I decided I wanted to try something a little different. My main reason for deviating from the norm, was that I wanted to have bucket loads of enemies chasing the player, and I didn't really want to have to continually run A* for each of them. There had to be a faster way.
While pondering the problem I wound up thinking back to my old tests with flow maps. Basically these textures described how water was meant to get from point A to point B. I wondered if I could use a similar technique to tell every single enemy where it was meant to go. It sounded like a good idea, I was pretty sure it would work, but before I could sit down and write of the fairly simple algorithm for generating flow I had some work to do.
Throughout this process I've been fairly careful not to get too bogged down making things optimized too early. It's been an effective tactic, as it's stopped me from getting stuck on finding “the best way”. Well, this is definitely one place where I'm paying that cost now.
The whole point of trying something other than A* was so that it would be fast. So, I sat down and profiled my “closest point on navigation” function with 100 actors (I would be using this a lot more when path finding is added)... Bad news, it took 16ms just to process that many enemies. This is basically my entire frame time if I'm shooting for 60 fps.
I needed to spatially partition my data. I looked into and tried several options for organizing my navigation triangles. I won't go into how they all work, but I will link some resources I found useful:
In the end I decided to go with a 3d implementation of a spatial hash map. I figure I can always cut it back down to a 2d look-up if I don't need vertical partitioning later on, and I don't want to exclude vertical levels. Coding the spatial hashing was fairly trivial in the end, the majority of the work was in how these items are tracked when entities are added, removed, or disabled. Taking care of this wound up costing me a little bit of time.
In the end, it was absolutely worth it. The frame time was cut down from 16ms, to 1.5ms. Additionally, since I'd just coded the spatial hashing, I also used it for my inter enemy collision, saving a further 8ms.
Firstly, to look up a “flow” vector, I need something to store them in. I started by constructing a graph using the edges of all the triangles in my navigation mesh. This seemed to produce the best results (I tried triangle centres, and verts as well, they didn't help too much).
To make sure any edges that are shared by triangles do not double up, I used a temporary spatial hash map to catch matching edges. The cell size for this was pretty small, about 1cm. The navigation triangles store indexes to the edge data, so that the enemy can look up the closest triangle, and be presented with 3 nodes to choose form.
Constructing the graph only takes about 2ms for a typical level, so I just reconstruct the whole graph whenever objects are added or removed.
Now, finally that I have all the preparations completed, I can start to muck around with the path finding.
The idea is pretty simple:
When an enemy needs to know what direction to travel towards the player, it does the following:
The whole thing works really well for my current set up. My levels don't have many navigation triangles, so iterating over them all once per frame is extremely fast (I usually don't have more than 2000). Further more, I intend on having a large amount of enemies, so having the per enemy cost of the algorithm incredibly low is a huge advantage. Finally, I don't currently have a need for enemies to travel in any direction other than the player. If I ever want to have smart enemies that try do things like flank the player, then I'll have to come back and revisit A*. Hopefully, even if this is the case, most of my enemies will be dumb, and so the current system can be used.