koobas.hobune.stream
A* Pathfinding, multiple enemies, moving target. Efficiency advice
Hi,
Ive been playing with Aron Granberg's A* pathfinding project to have some simple enemies chase the player.
At the moment I have 20 enemies with character controllers and an invoke repeating call (1second repeat) to create a new path from themselves to the player since it will be moving constantly. (I am using a grid graph that is fairly spread, from memory of the logs I haven't seen a path found longer than 15 to find the player)
After adding a system so that they can be killed by the player it seems to work pretty nicely. But I am interested in extending this to a lot more enemies and I expect a lot of lag incoming and in some of my tests it drops from 60+FPS right down at seemingly random times.
So what im looking for is some advice on how to handle multiple enemies who need constant pathing updates of the location of their target. Such as increasing the delay between path updates, or only updating if the player has moved a decent amount in that delay? Increasing spacing on graph nodes and adding more smoothing? [edit: Just thought of making the update delay based on distance from player?]
Im assuming A* is similar to a BFS in complexity so doing it once every second per enemy seems like it will never scale well. Ive seen another thread mention rigidbody to control enemy movement over a charactercontroller to increase performance so if anyone is familiar with that relationship thatd be helpful.
Cheers!
Here are some ways you could make it more efficient:
First, don't make the enemies update their path over time. In reality, their path only needs to be updated when your player changes its closest "node" by moving. Do it when that happens, and limit its frequency to something like every 0.25 seconds.
However, if you were to keep those enemies update every 1 second, do it at random times, not all at the same time. 60 path calculations are better laid out over the whole second of time you have than in a single render.
Also, when the player changes node, you might want to consider simply adding this new node to your existing enemies path, therefore just expanding their path instead or re-computing it.
Finally, you could also introduce some sort of follower system. In a game I made, units would look for units next to them, check their path, and steal it if the unit had the same closest node. You could even just try to follow a nearby unit that has a path, closely. Some sort of "guide". That limits the amount of "intelligent" units that have to calculate paths, and reduces your calculations by a lot.
Check out the game I made using these tricks in the past, you can see a lot of units and it runs well even on Flash Player: http://armorgames.com/play/5766/planet-noevo
Thanks a lot Louissi. I think I was hoping for some quick and easy way to go about this but you have a lot of good ideas. Thanks! I did a lot of things to improve performance, most notably the not doing all path findings at the same time which helped a lot. The adding your changes to the node was also a good idea, but if I stopped it from extending too far and just make a fresh route, otherwise they would start following your zig zagged walking. Thanks again!
Thanks so much the bug I was working on for the last few weeks fixed!
@Louissi has a great answer. To elaborate on his post:
In general, you have to consider when MUST the path for each actor be updated. Generally update pathfind on events, not on a frequency. However, limit your updates by a frequency. That is, ignore update events that are more frequent than your constraints or queue the most important update event to occur at the next interval. Spread your expensive updates out so they don't all hit on the same frame.
Some considerations for update events:
target move orders changed
target was moved / deleted / added
unit reached the end of its path or is at final node - N
nav mesh changed
dynamic obstacle was added / deleted / moved
unit found / lost target within weapon / sight range
unit lost line of sight on target
Another optimization that might apply is to pathfind units as a group, with offsets or perturbations from the pathfinding object. For example, if you spawn 10 tanks that are to move in formation anyway, they might be able to pathfind as a group.
If you can pathfind over a simpler domain, it will be less expensive. For example, an RTS might only need to pathfind in 2d, even though there is a visual 3d environment.
As you mention, if your pathfind can use a simpler object, such as a sphere or character collider capsule, it will be a faster calculation than dealing with a cube or a mesh.
A* does work best with a fairly coarse node graph. You can have reactionary code deal with incidentals between nodes.
Yeah, making the new path as a response rather than proactively is a good idea
That's some great advice by Louissi,
Also, you could consider using a simple AI that uses basic heuristics to determine it's path, and only the pathfinder when a certain condition is met (basic AI leads the agent into a wall, distance to the player is above or below a certain threshold, etc).
Another optimization is to make your pathfinder asynchronous and limit it's execution time. Agents will put path requests in a queue and the pathfinder will respond with paths as long as it's execution time has not exceeded. Again, in this case too you would probably want a simpler AI pathing fallback.
Swapping between using a simpler 'pathfinder' and fully fledged A* was a good idea if you can deter$$anonymous$$e which situation you should use either. Thanks!
