Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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.

share|improve this question
add comment

4 Answers

up vote 1 down vote accepted

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).

share|improve this answer
    
Quite a novel technique. I am going to figure out if I can possibly do some pre-calculation work ahead of time (flood fills are pretty expensive). Edit: Looks like someone beat me to it –  Jonathan Dickinson Nov 16 '11 at 16:05
1  
Not allowed to edit any further :/ - the anchor system on that blog is broken. Looks for "Sean Barrett's" answer. –  Jonathan Dickinson Nov 16 '11 at 16:12
    
Ha, ha. I should have known. It did seem somewhat familiar! Well spotted (referring to the BFS-likeness). –  Nick Wiggill Nov 16 '11 at 16:27
add comment

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.

share|improve this answer
2  
Thanks for reminding me to not prematurely optimize. I'll give this a shot and see how it goes. –  Jonathan Dickinson Jun 13 '11 at 14:14
2  
+1 One move ahead hardly sounds like pathfinding at all (or if it is, the most naive kind possible) –  Jonathan Hobbs Jun 14 '11 at 2:52
    
+1 Altough 'premature' optimization on such a huge part of the game mechanic is not all that bad ;). –  Jonathan Connell Jun 14 '11 at 10:03
add comment

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.

share|improve this answer
    
Awesome idea with the grouping. Thanks! –  Jonathan Dickinson Jun 13 '11 at 12:26
add comment

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.

share|improve this answer
    
Because of the nature of the networking layer (thanks to the AOE article) the server can handle floods of the same type of messages queues within the same tick. A specialized async worker running over a queue is probably not a bad idea at all. –  Jonathan Dickinson Jun 15 '11 at 7:43
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.