One Step-Ahead A-Star

Question

I am attempting to create a server-centric RTS (as opposed to usual parallel synchronised simulation route of most RTS games today) - however I am still leveraging the discreet N-turns-ahead paradigm discussed by one of the AOE developers on Gamasutra.

I have [possibly questionably?] decided that the path finding should only ever find the next cell the entity needs to move to, and was wondering if anyone has any clever ideas on how to optimize the algorithm for this specific scenario - or any other ideas on how to keep the pathfinding as lean as possible on the server.

I have investigated a few possible algorithms but could only come up with one appropriation: Tiered A-Star - Relatively large T1 tiles, work out (and cache) each cell as you enter it. Other than that: doing the full A-Star pass and caching the entire path, which might use too much memory if a large amount of units are present.

I know about the existence of naive progressive pathfinding algorithms (if you hit a block, turn in the direction closer to your target etc.) but they suffer from infinite feedback loops - and very poor pathing even if visited blocks are memorised. Not an option.

Many thanks.

Answer 1

Check out BlobMaps for something simpler, at least, than A*. Still not only one step ahead, but fine under many circumstances, according to the author (I've not tried them as yet).

Answer 2

Computing just one move sounds like a bad idea to me. If you don't compute the whole path, then you don't know that the next tile to move to is correct, so a lot of the time units will get trapped.

Caching the entire path for a unit won't take too much memory. It's just a list of node IDs. The main problem is generating the path in the first place, and how much of an issue that is depends on the complexity of your map - how many discrete nodes you have, the branching factor for each one, and whether you have a lot of large obstacles.

This is not to say that hierarchical A* won't help, and it will definitely speed things up, but you seem to be micro-optimising ahead of time. Why not just implement the simplest approach and go from there? If it turns out to be too slow, you can trivially change it later because you have a simple input interface (the source and destination nodes) and output interface (a list of nodes to travel on) - the algorithm you use to handle that is easily interchangeable.

Answer 3

Your best bet is to use Tiered A-Star and then employ various strategies for minimizing the overhead. For example, the memory footprint can be dramatically reduced by having multiple units share the same path. That is, there's no need to store a path for each individual unit; instead store all the units that started in the same area, and then calculate just one path from that area.

Answer 4

I've used the shared path idea that jhocking brought up, it works well in a situation where you're moving groups (say like infantry squads) around.

I've also used a variant of the tiered approach where paths between the higher tier(s) are pre-calculated when the map is built and cached by the server, the lowest tier is still best served by a local path of its own.

If you haven't done it already move your path finder out into an asynchronous service for your server, in this way a flood of requests on the same tick won't bog down the main simulation.

And finally, have you measured how much space/time is actually used by a path? It could be that you're worrying over nothing =) Kylotan is right about measuring before optimizing.