Pathfinding for tons of creatures

Performance Tuning
#1

Hey everyone, so for the past month I’ve been working on a game that will feature hundreds (probably around 500 - 800) of individual animals controlled by AI on a purely tile based world. They all need to eat, drink, stay away from predators (such as the player) etc. All of this requires a metric ton of pathfinding. Now I’ve achieved what I wanted from the pathfinding without many issues. Animals are able to navigate through the world without running into each other, they won’t freak out if their path is blocked, it’s all working smoothly. Except for the fact that the sheer performance drop, once there are more than 40 animals on the map, is substantial. If I have 60 animals on the board, it can take up to 8 seconds per frame! (with 40 I get around 90 fps).
All of these animals not only have to search for food, water, and other resources, but they also wander around when they have nothing to do. This means that at almost all times, an animal is having to path to its destination. This is the reason my computer is having such a difficult time keeping up.

I’ve run various performance tests and improved the system, but it doesn’t really make a big difference. I tried only updating 30 animals per frame, but naturally this caused every animal to slow down considerably.

So my question is. Is it even possible to process so many entities? The game revolves around the fact that entities never spawn or despawn. This is to provide the realistic world where even the smallest change to the environment can cause a chain reaction. Such as an oasis drying up that causes all the animals nearby to migrate to a new source of water. It also allows for natural consequences if the player makes a mistake (such as accidentally killing too many squirrels causing them to go completely extinct).

Thanks :slight_smile:

#2

Some thoughts:

  1. Have you tried to eliminate object creation and reuse objects like arrays whenever possible?

  2. I have read some stuff (not much) about alternatives like navigation meshes and jump point search that might be interesting to look into performance-wise.

#3

It is very possible. Thousands at once are quite possible.

First off: I hope you aren’t computing every entity’s path each frame. Cache them. Only recompute paths when required (such as the entity reached it’s destination and needs a new one, or something stepped in front of it, etc). Only allow up to a certain number of paths to be computed per frame, others will simply have to wait until next frame. This smooths out lag spikes.
Also: what algorithm are you using? Is it a known one or homebrewed?

#4

I use the typical A* pathfinding algorithm (without a library but it should be exactly the same).
And yea, I’m caching the path and I only recalculate if the tile immediately in front of the entity is blocked. I am computing the paths of every entity each frame, however, I tried to do just 30 per frame. The problem was that the more entities I had, the slower each one would move around.
Saying that out loud actually revealed a possible fix to me. When I tested this idea out, I made it so that the game literally only updated 30 animals every frame, I don’t think I should be limiting how often the entire animal is updating. Instead, I should be limiting how often an animal updates its path, not how often it updates as a whole. So that’s one possible solution :).

So I guess I would have something like a master list of paths that need to be processed, and each frame my Pathfinder class would go through 30 of them. I’ll try that.

#5

[quote]Instead, I should be limiting how often an animal updates its path
[/quote]
That is exactly the point of caching, which it doesn’t sound like you’re doing if you’re recalculating on each frame.

#6

Trust me, I don’t recalculate the paths every single frame. That would be crazy xD. What I was saying I should do, is that whenever an animal does reach its goal and it needs a new path, it would basically send a request form saying, “hey, I need a path from point A to point B”. This request would be added to the back of a master list that would eventually be fulfilled by the pathfinder a few frames later after it fulfills the path requests in front of it.
Currently, every animal determines its path and stores that path into a “Path” object. It only calculates a new path if it reaches its goal, or if something blocks its movement. I think the problem is that currently, whenever an animal wants a path from point A to point B, it always calculates that path in the same frame. It doesn’t spread them out. And when you have 50 animals with semi short paths, they reach their goals quickly and will need a new path pretty often.

#7

I’ll take a look into navigation meshes, it would probably be a great thing to learn.

#8

Nav-mesh=good idea. Take a 256x256 map. That’s up to 65536 cells to “consider” for the search method. It’ll be common for the equivalent nav-mesh to be something like a dozen.

#9

Revenge of the Titans does basically exactly this and it works well. I didn’t go so far as bothering with navmeshes because of the highly dynamic nature of the map.

Cas :slight_smile:

#10

Although I don’t handle nowhere near that many creatures, this is what I do.

First, each GamEntity has an AI that ticks once every 2 seconds, this of course may be adjusted to more or less often depending on your game. Never do it per frame.

Second, I first check for a straight path being available, this actually covers 90% of the cases. Then, if no straight path is available, I check for a single “turn” being efficient enough (i.e, I generate a few nodes making a grid in between point A and B, and I evaluate if for each node N, distance A-N + B-N is not bigger than straight line distance +10%. This covers many cases in which there is a single obstacle in the way, not an intrincate path.

Finally, if the above fails, I fire the A*pathfinder.

#11

Another consideration is: Does each “thing” need to think for itself. Or can some of the follow the leader most of the time. Also depending on the look of the game…do creatures block one-another or not (friendly creatures that is).

#12

Grid based A* isn’t really suitable for multi-unit pathfinding. You’ll have to implement lots of hacks just to get it working nicely and even then unit movement often looks unnatural.

For less than a hundred or so units, a much nicer algorithm is Cooperative Pathfinding, which is similar to A* but with the addition of time (where position of other units a number of time steps ahead is considered as part of the pathfinding).

For thousands of units, you’ll want to go for one of the pathfinding algorithms that use flocking with a combination of either a navmesh or a flowfield. Such as those seen in games like Supreme Commander, Planetary Annihilation and Starcraft 2. These calculate the path just once for a whole group, scale well and allow you to implement various types of group formations and movement patterns much more easily then with more rigid algorithms such as A* for each unit.

#13

I think, yes. Many will jsut follow the path, while others are pathfinding, so the number of parallell pathfinding activities isn’t that big. I’m using a thread pool, 16 pathfinders can run in parallel. If more creatures need a new path, there will be delays.

With this I copuld move 50 creatures and there was still plenty of CPU time left. I’d assume if one uses a highly optimised pathfinder (which i did not), one can have at least 500 creatures running around simulataneously on a modern PC (4 cores).

#14

I’ve had 6,000 robots running under A* on a 256x256 map at 60Hz :slight_smile: They ebb and flow in very pleasingly emergent ways.
Here’s a Youtube of a 2,000 robot battle:

qObkxxxjyFI

Cas :slight_smile:

#15

Heres a comparison of a flowfield algorithm vs an old A* style one (a rather crappy implemenation by the looks of it but demonstrates the point)

bovlsENv1g4

#16

Hmmm… Massive phalanxes neatly interleaving? Sorry the a* variant in the video is much more realistic.

#17

I like the idea of making unit movements appear more natural, however because each animal is an individual and won’t move in herds, I’m not particularly worried about making sure they can move as a large group. Nonetheless, cooperative pathfinding might still be a good thing to implement, especially if it helps with performance.
Is flowfield still viable even if the animals don’t move in herds? Or is it kind of unnecessary if they are acting as individuals.

#18

What did you do to avoid the performance issues I’m running into? Because that’s a huge number of robots.

#19

Mostly just using simple internal queues to schedule only a certain amount of work per tick. Also not doing all the work, every tick - robots only scan for targets once per second. That sort of thing. The end result is almost completely imperceptibly different to the observer. We are the masters of cheapass effects :slight_smile:

Cas :slight_smile:

#20

I agree… I find the mixed up skirmish look far more aesthetically pleasing and realistic. Even though the fancy stuff is impressive - but who cares? Does it make a better game? Probably not.

Cas :slight_smile: