SeaBomb – Flow Map Inspired Path Finding
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.
Premature Optimization
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:
- Quadtree – Quadtrees by Jonathan Ferraris
- Octree – Coding a simple Octree by Brandon Pelfrey
- Spatial Hash Map – Spatial Hasing by Tristam MacDonald
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.
Constructing the graph
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.
Go with the flow
Now, finally that I have all the preparations completed, I can start to muck around with the path finding.
The idea is pretty simple:
- Every node has a value stored. They default to float max.
- Every frame these values are increased.
- Every frame the navigation system can be impulsed with 1 or more positions (representing any players locations).
- This reduces the nodes stored value to 0.
- Every frame the nodes check each of their neighbours for a smaller value.
- If one is found the distance squared to that node is added to the value of the neighbour, and then stored in the current node.
- Over time, this creates a gradient with the smallest value at player locations, and the largest values being the furthest from the player.
- The node also stores the index of the neighbour it used.
When an enemy needs to know what direction to travel towards the player, it does the following:
- Looks up the closest navigation triangle.
- Checks for the one with the smallest value.
- Gets the direction that node is pointing towards, and travels in that direction.
- If no direction is returned the enemy travels straight towards the player.
- This happens if the triangle has any nodes that are from the same triangle the player is currently on.
- It also happens if the triangle has all nodes at float max.
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.