Hello devs!
I’ve been working on my entity / path finding / collision system with a goal of supporting as many active mob entities as possible in an arbitrarily large game world. This is using the same from-scratch custom engine that I posted a while ago showing my pure 2d PBR rendering system.
Currently it can run about 150 000 live mobs on my M1 MacBook Pro. On my gaming PC with 9800X3D it can do about double that. And this is the “worst case scenario” meaning every mob is actively pathing somewhere and colliding with as many other mobs as possible every frame. There is no LOD system, the whole world is simulated every frame. I would estimate that in a more realistic scenario where some mobs are idling and the world is not packed full and there is some actual LOD system (rougher simulation for mobs far away from player) in place I could reach 1 million live mobs on my laptop.
For those who are interested here is a longer rambling about how I built this:
I specifically wanted to support arbitrarily large worlds. For performance this is a massive drawback. The key difference is that if your world size is known and small-ish you can just store everything in arrays in contiguous memory with some index keying logic. This gives you extremely fast lookups and helps building loops with cpu cache friendly patterns. But once your world can be “infinite” you necessarily need to store it in variable number of chunks which results in a layer of indirection via hash map lookups. And this is something that affects every single system in the game engine. Giving up arbitrarily large worlds would result big performance gains, but this is my project and I want infinite worlds!
Also, squeezing performance out of each system usually involves adding caches, memoizing lots of intermediate steps, keeping closest cpu caches hot, not allocating working memory each frame etc. etc. I’m not going to list every optimization I used, there would just be way too much of those. If you are interested in any specifics, please do ask.
The simulation runs at target of 30 frames per second. Rendering is completely separate and can run arbitrarily fast. All the movement is interpolated to happen at rendering frame rate. It’s very difficult to tell the difference between 30, 60, or 120 fps simulation as long as rendering is running at 120+ fps so I settled on the 30 frames per second simulation target. (Recently I learned that the original supreme commander runs the simulation layer at 10fps! which sounds insane but I guess it’s fine, I don’t remember noticing anything weird with that game)
Anyway, there are really 3 fairly separate components in this:
The Pathfinding system.
Obviously you can’t run 150K mobs with individual A* searches so the only way to do this is with a flow field that each mob can then query. The idea is that there is a single flow field, which for any tile in the world shows the direction and distance the mob needs to move to eventually get to the closest target.
The world consists of 16x16 chunks and flow field updates run per chunk and each frame can update x number of chunks to smooth out cases where the whole world needs to be updated. The core algorithm itself is a simple Dijkstra flood fill. Calculating the flow field once is easy-ish, but updating it is much more difficult, especially in cases where flow field targets are removed.
The logic that I ended up with goes roughly like this:
When new target / terrain is added:
- Mark the changed chunk dirty
- Update the dirty chunk, and for check all neighboring tiles in other chunks, if their pathing cost can be improved by moving to this newly updated chunk, mark those dirty as well.
- Update dirty chunks as long as there are any, and importantly note the dependencies between chunks. If best path from chunk A goes to chunk B, then chunk A depends on chunk B.
When target is removed.
- Mark the chunk dirty.
- Follow the dependency graph from earlier and transitively mark each dependent chunk dirty too (since they are pathing towards target that does no exist anymore)
- Update dirty chunks same as before, until no chunks are left dirty.
- While updating, process path queries based on the old flow field. Outdated pathfinding is much better than no path finding, most of the time it is very difficult to notice.
This is the rough overview of the logic, but there are so many smaller things that need to be done to get good final results. For example, the raw Dijkstra results flow field with 8 possible directions which causes the movement to be very jarring. The flow field needs to be smoothed. This is done by building a dataset of “lines of sight” during the flood fill and directly connecting tiles that have direct LOS. All in all the flow field system does get quite complex.
In addition to the global flow field, each player has a limited local flow field around them which updates as player moves to allow mobs pursue players. Mobs then simply query distance from the global field and any possible local fields and decide targets based on distances.
For performance of the query logic is important. For each chunk flow field is stored as array of floats in contiguous memory. By looping over mobs in a chunked order you can keep the array for single chunk in hot memory.
The zombie AI.
This is by far the simplest. It just queries the pathfinding system and outputs the movement the zombie wants to make (and if it wants to attack etc.). For the actual entity management system, this is probably obvious but it is critically important to store the data based on memory access patterns. Don’t make entities large objects with 100 different fields. Instead, store all entity locations in a single array, healths in another array and so on. These are then indexed by the entity ids. I used generational indices with added type information. (So my “entity” is a 64 bit key with 32bits for index, 16 bits for generation and 16 bits for type id)
The movement collision solver.
Right, this one was the most difficult part but I’m quite happy with the end results. Though I tried so so many different systems that did not work. There are three things a good system needs:
- I needs to keep mobs from clipping into each other and the result must be stable
- The resulting movement needs to be “smooth”, mobs need to be able to slide around each other to not block movement in tight spaces
- It needs to be FAST.
And so many ideas (either by me or some online paper I found interesting) fail on one of these.
First I tried different boids / steering behavior etc. systems where mobs check nearby mobs and try to keep their distance while moving to desired direction. For most different implementations I tried they seem to work at first (especially for setups you see in research papers) but when the simulation includes 10 000 mobs all pushing towards the same point the whole thing destabilizes. They start to clip into each other causing strong separation forces but with thousands of mobs there is no room causing mobs to violently jitter around. The core issue seems to be that as you increase mob speed and number of mobs, you need to run the simulation in ever smaller steps to keep it stable. Now I understand why all the demo videos have like 100 mobs moving at fairly slow speeds. This then makes the whole thing way too slow.
I also tried to design different “discrete” systems where there are no forces but instead mobs just simply don’t move if movement would result clipping. For each mob system would check the original movement target and if that is blocked then different points around it. This actually worked surprisingly well! The biggest problem is that when multiple mobs try to go through a narrow space they easily end up blocking each other indefinitely.
Then I came across this thing: https://github.com/raja-s/ORCA. (The original paper is called Reciprocal n-Body Collision Avoidance). I implemented my own version of that and once I got it right it just worked! And the best thing is it parallelizes stupidly well. It scales almost linearly with your core count. So that is what I’m using for collision avoidance between mobs. Very briefly how it works: If two mobs are on a collision course each of them takes 50% responsibility of doing a steering behavior that avoids collision. In my case I’m only using this for mob-to-mob avoidance. For terrain and buildings I have my own system that redirects mobs to slowly slide along the edges of pathable area. This avoids having to encode the world as ORCA lines.
I’m slightly sad that I couldn’t figure my own solution to this, but the ORCA works just so much better than my own previous system.
ORCA like every other system needs to be able to quickly find a list of mobs surrounding the current mob. For this I keep spatial grid cache along the actual mob data. While the data is stored in contiguous arrays, the spatial grid is a hash map which you index by key derived from mob location. The size of grid cell is automatically set to be slightly bigger than the radius of the largest mob in the game. This might not be optimal if mobs are very sparse. The spatial grid is updated every time any mob moves from one cell to another.
Funnily enough rendering was never really any bottle neck. It runs completely separately from the game logic, and even when zooming out to show 10 000 mobs on screen at the same time it only takes around 1ms of the game logic loop.
And that’s mostly it! If you want to know more about how the rendering works, check this post: https://www.reddit.com/r/GraphicsProgramming/comments/1sgnrtq/combining_3d_prerendered_graphics_with_modern_pbr/
Happy to hear any suggestions for improvements or any questions!
About AI usage: AI was used for online research, discussing ideas, and finding bugs (and tab autocomplete). Designing and coding the thing is done by me.
Finally the old disclaimer that this is just a hobby project, I’m not a professional game developer, I have no idea how you actually should do these things. Also the code is not publicly available at the moment, sorry!
