Is the process of finding the path from A to B for an agent typically done in one call? If the path to be determined was riddled with obstructions, the pathfinding algorithm may require a significant amount of time. How is this issue handled in games today? I can think of two solutions: 1. The pathfinding procedure is parameterized with a timeout value that, once reached, will force the algorithm to return a partial path (producing a sort of 'iterative deepening' algorithmic behavior). This would allow the agent to immediately start moving towards it's destination and not sit there "thinking", waiting for a path to be determined. 2. Spawn a thread to find the complete path and force the agent to either sit and wait (and probably give the user an impression of a lack of intelligence) or send the agent towards its destination via a straight-line path and then adjust accordingly when the pathfinding algorithm completes. Maybe there are other solutions that I haven't thought of, but solution 1 seems to make the most sense to me. Solution 2 is probably very evil: if I sent 100 units to go to a location, 100 threads would be spawned which would be very bad. My Questions: a. Is there a scenario where solution 1 would not be sufficient? Or is there a better solution to this problem all together? b. Assuming you have a 'busy world' where possibly 100 units may be moving simultaneously, is solution 1 practical? c. How much time is too much time to spend on path finding, terms of CPU? 10%, 30%, 50%?

If you're talking about grid maps, for 100 units even if the map goes up to 256x256 tiles, you can still easily make them process their paths using only 5% CPU, on a say... P4 at 1Ghz. Not optimal paths(from my experience), but you can. So i don't think you'll need either solution.

If you can gives us a bit more information, like the type of map, the max size, the minimum CPU you're aiming for, and the CPU% of time you're aiming for, relative precision of the paths(optimal, non-optimal), maybe we can give you more accurate numbers.

Well, I was thinking in terms of a 2d tile based map, but potentially very large ones (1024x1024 tiles or possibly even larger). Optimality isn't necessary, but surely I'd hope for paths that were near optimal. Actually, that is something that I hadn't thought of -- if optimality isn't a requirement, is it possible that A* isn't the best choice with regards to speed?

In terms of CPU percentage, I'm not really sure. I was trying to get a feel for what game developers regarded as an acceptable window (i.e., maybe most people feel 0-10% is fine, but 20% and over is just totally unacceptable?).

Abou the CPU %, the numbers i've come across are allways between 10%-15%, less if possible, then there are AI oriented games that can use much more(like Sims), and games with no AI at all. I guess it just depends on how smart you want your game(if this is a game we're talking about) to be.

The map size is tricky. If this is for some kind of MMORPG, you'll probably just have the players on the map, and each one makes it's own computations, and the server would just need to handle the npc's and the creatures, the npc's wouldn't move that much and the creatures wouldn't need precise path's, random would do. So you won't have 100 units to calculate paths for.

If this is for a strategy game, it's totally unrealistic. Warcraft3 biggest maps IIRC we're 160x160. With that map size with 5% CPU on a P4 at 1Ghz you'll have trouble processing a single path per second(not per frame).

You can divide the map in smaller maps, with gateways connection them, use another algorithm other then A* much less precise but faster, use waypoints through the intire map, implement hierarchical pathfinding, and will still be hard. You'll either end up with very fast very ugly pathfinding. Or very slow, not quite so ugly pathfinding.

IIRC, the largest Warcraft 3 map may have been 160x160 texture tiles, but the world space (i.e., the nodes available for agents to move around in) had a resolution of about 4 times that per tile. It may not have been 4 but there was definitely not a 1 to 1 ratio between the agents' world space and the texture tiles. So, now we're talking about about 640x640 tiles. It's possible that my size of 1024x1024 is totally unrealistic -- if that's the case, I definitely want to know about it :) I'm attempting to create an RTS game with 256x256 texture tiles and I increased the resolution 4 fold for the world space, so a 1024x1024 coordinate space, if you will. If that is indeed totally unrealistic, I could reduce it to a 2 fold resolution increase, which would yield a 512x512 coordinate space.

Assuming I choose a tangible map size, what algorithm would you recommend, since I don't require optimal paths? And, is returning partial paths an acceptable solution?

Quote:

Assuming I choose a tangible map size, what algorithm would you recommend, since I don't require optimal paths? And, is returning partial paths an acceptable solution?

Maybe divide the map in 256x256 maps or less, create some gateways between them, like bridges, and when a large path has to be computed(origin and destiny are in diferent map sections), you just calculate the path to the gateway that is closest to the end, when he gets there you do the same, calculate the path to the gateway closest to the end, and do it until the unit is in the actual map section that it will end up, then you just calculate the path to the destiny.

This way the paths are almost allways non-optimal, and the intire map will look like it was glued together, gateways are used frequently to ease processing of paths and they can be succefully 'hidden', ocasional bridges here and there are ok, but for that map size, it's going to become obvious.

But hey, you can return partial paths, it's much faster, and the paths look ok.

You can use waypoints instead or with gateways, you have smaller maps, again 256x256 for instance, in total you get 16 of these small maps, you just create waypoints from each one to the rest. When a unit has to go from one section to another, just calculate the path to a waypoint, and the rest is already calculated.

This can also get very tricky because it's static, if a structure or unit gets in the waypoint's way, you'll have to recalculate the waypoint, or recalculate just the path of the current unit, in specific situations you can get really weird paths. And moving an intire army, the units will look like a line of ants instead of the flocky look, they will all be following that waypoint.

If you mixture waypoints with gateways you might get a good combination, but will be messy.

---

About Warcraft:
I remember in an interview a blizzard programmer saying they used "per pixel pathfinding" on Starcraft. I don't know how it works, and he didn't get into the details, what he mentioned the advantages of using such pathfinding method. The paths would be smoother, several units could partially occupy the same tile so that formations wouldn't look likes squares, it would look better.

Now if they used the same pathfinding method wich, by the way the units move, looks like they did, the fact that you can see several units partially in the same tile is just part of that pathfinding method.

But hey, don't belive me, go check out other RTS and see their map sizes.

I don't get one thing though, if you are only aiming at 100 units, why do you need 1024x1024(or bigger) sized maps?

[Edited by - xor on December 12, 2004 9:47:41 AM]

Quote:

I don't get one thing though, if you are only aiming at 100 units, why do you need 1024x1024(or bigger) sized maps?

Well, I just wanted to have a vast space for the agents to inhabit. I'm looking at 256x256 texture tile maps right now (i will quantize these into 1024x1024 coordinates spaces) and they definitely don't give the appearance of being too large. 100 units was just a blind goal -- I don't really know what kind of number I will end up with. Surely, if I could handle more units, that would be better. After I write some initial pathfinding, I do some testing and tweaking to determine what the apropriate number of units is. Developing the intricasies of gameplay seems very far off in the distance though :)

With regards to Warcraft, per-pixel pathfinding? Surely they have some kind of quantized coordinate space underneath all of the tiles. I wish there was some literature regarding this technique as it sounds very intriguing.

And about choice 1. It seems optimal only if you assume that all different paths to the destination (or at least the one it chooses before time runs out) can go all the way to the destination. It would never work if it sometimes chose the wrong path to take and your units not being able to go through that mountain that the pathfinder couldnt take into account without searching the whole depth of the path.

Quote:

After I write some initial pathfinding, I do some testing and tweaking to determine what the apropriate number of units is. Developing the intricasies of gameplay seems very far off in the distance though :)

Go for it, when you have some code working you'll understand more then you do now what i mean when i say those map sizes are unrealistic. Hey maybe you'll figure out a way to make it work.

Quote:

With regards to Warcraft, per-pixel pathfinding? Surely they have some kind of quantized coordinate space underneath all of the tiles. I wish there was some literature regarding this technique as it sounds very intriguing.

Yeah, me too!

AP(1) broken link.

AP(2) don't think you read all the posts.

wfrost:

Quote:

Well, I was thinking in terms of a 2d tile based map, but potentially very large ones (1024x1024 tiles or possibly even larger). Optimality isn't necessary, but surely I'd hope for paths that were near optimal.