So I just implemented a rudimentary A* pathfinding for my game. It works fine for a couple dozen units in a 80x80 tiles map, a couple of delay spikes. When I try it in a 100x1000 it gets horrendously slow. This doesn't surprise all that much though. I was wondering how, say, blizzard did it in warcraft 1,2, starcraft 1. Managing pathfinding for hundreds of units in customizable maps.

Any info is much appreciated.

Here's a couple tips that might help you out...

#1 - don't calculate pathfinding every frame. do it once then remember that units path until something significan changes it to cause it to need to re-calculate it's path.

#2 - if you have a lot of units that need path finding, you can limit it to how many can do it in one frame. Like basically everyone who wants a path calculated puts their request into a queue, and maybe your game only processes one or two path requests per frame. The units can just sit around and wait til their pathing request has been fulfilled. This will make it so (in theory) pathing will never take up a huge amount of time in a single frame.

#3 - if you can get away with it, try and calculate a path once for multiple units all headed to the same place. Basically like if you had 4 bad guys spawning near the same spot and they all want to run to the same place, you only really NEED one path right? (:

#4 - you can do hierarchical path finding. That is... if you have some kind of navmesh that you do A* searching on for the entire map, you can have a higher level, rougher navmesh that has far fewer nodes to do a preliminary A* on. That will tell you what sectors your path falls in and then you can do A* within those sectors to find the specific path on the high res nav mesh. Make sense?

#5 - if you have certain choke points, or a situation where a lot of enemies will all want to go the same way (such as in a tower defense game) it might make more sense to calculate the path and instead of storing the path PER UNIT, store the path data on the map itself so AI's generally know the way to walk at any given spot.

(:

That makes a lot of sense, thanks!

Oh and something else you can do is set up a pathing request Queue like #2, but you make it so that you can do PARTIAL pathing per frame.

What i mean is you know how A* has an open and closed list etc?

What you do is make it so your code can stop somewhere in the middle of processing one path - with all the necesary variables being member variables so it can start up where it left off the next frame.

Then what you do is do something like decide "I'm going to spend 3 miliseconds maximum every frame on path finding" and then make it so after those 3 miliseconds are up, it stops processing until the next frame.

Whenever it finishes a pathing request, it can notify the object with the path data, and use whatever remains of the 3ms on the next job in the pathing queue if one exists.

Basically this way you ensure pathing doesnt take more than a specific amount of time on your frames so you are garaunteed not to have bad FPS due to pathing.

The downside of course is that if you have a lot of pathing requests and it takes a long time to calculate each request, it might take a lot of time before AI's get their path requests fulfilled.

So its kinda a trade off...

but yeah thats another technique (:

Quote:

Original post by Atrix256 Oh and something else you can do is set up a pathing request Queue like #2, but you make it so that you can do PARTIAL pathing per frame. What i mean is you know how A* has an open and closed list etc? What you do is make it so your code can stop somewhere in the middle of processing one path - with all the necesary variables being member variables so it can start up where it left off the next frame. Then what you do is do something like decide "I'm going to spend 3 miliseconds maximum every frame on path finding" and then make it so after those 3 miliseconds are up, it stops processing until the next frame. Whenever it finishes a pathing request, it can notify the object with the path data, and use whatever remains of the 3ms on the next job in the pathing queue if one exists. Basically this way you ensure pathing doesnt take more than a specific amount of time on your frames so you are garaunteed not to have bad FPS due to pathing. The downside of course is that if you have a lot of pathing requests and it takes a long time to calculate each request, it might take a lot of time before AI's get their path requests fulfilled. So its kinda a trade off... but yeah thats another technique (:

Perhaps implement this for each single unit? Queued pathfinding is unfair.

- the first unit added to the map is first on the logic queue
- if multiple units try to path find at the same time, the one which is first on the logic queue requests first
- 'older' units arbitrarily get priority

True, this may be unnoticeable for most applications, but it guarantees that the game isn't truly balanced