Hi! I'm working on a simple 2D RTS game. I have almost finished, but I have problems with pathfinding. I mean I have one, but there are problems when I want a big number of 'soldiers' to go somewhere - game runs much slower then (about 30FPS where 60FPS is normal speed). I don't see any place to improve code... I'm using the square grid; there can not be two units at the same time on one square. Have You ever fight with such problem? How did You solved that? Any advice? Regards, Pszemsza

Are you describing a situation involving groups of soldiers, in which the actions of the group are similar (each group has its own destination), or where soldiers are basically going every which way?

If it's the former, then reduce the complexity of the search task by finding a path for only one member of the group and have the other members path relative to the 'leader', so as to maintain separation or formation.

If it's the latter, then you have a more difficult problem, because the 'optimal' answer for each unit must take into account the path that every other unit is going to follow. Since this is impractical for real time pathing, you need to find an acceptable suboptimal solution, such as creating a path that ignores other units and then react to dynamic obstructions that occur to the path by circumventing them.

There are a variety of solution techniques applicable for whichever scenario you face... but before one can be offered up as appropriate, we need more information about the specifics of your pathfinding problem.

Cheers,

Timkin

Quote:

Original post by Timkin If it's the former, then reduce the complexity of the search task by finding a path for only one member of the group and have the other members path relative to the 'leader', so as to maintain separation or formation.

Hmmm... So I'm looking for 'general path' and then I can use it for other units, right? I thought about that, but I haven't good idea how to implement that. I think it's good for games like Age of Empires, when there is no grid (I mean soldiers have global position keeping by float, not int ) and there are a lot of free space &#111;n the map. In my game there's a lot of bottlenecks.<br><br><!–QUOTE–><blockquote><span class=smallfont>Quote:</span><table border=0 cellpadding=4 cellspacing=0 width=95%><tr><td class=quote><!–/QUOTE–><!–STARTQUOTE–><i>Original post by Timkin</i><br>If it's the latter, then you have a more difficult problem, because the 'optimal' answer for each unit must take into account the path that every other unit is going to follow. Since this is impractical for real time pathing, you need to find an acceptable suboptimal solution, such as creating a path that ignores other units and then react to dynamic obstructions that occur to the path by circumventing them.<!–QUOTE–></td></tr></table></blockquote><!–/QUOTE–><!–ENDQUOTE–><br>Now I'm doing something like that. I'm looking for path always, when the soldier stands directly &#111;n the square and that square is not his goal. So I have a lot of pathfinding function executions. In finding the path I ignore other units that are moving, unless they are very near given soldier. In such situation I'm treating squares occupied by them (the &#111;ne soldier is travelling from and the square soldier is getting to) as unwalkable. But this is too slow…<br><br>I'm thinking about making a queue of pathfinding. It will prevent the situation, when in &#111;ne frame I'm executing pathfinding function 30 times. But I'm not sure… Isn't it the same to calculate 30 paths per frame what to calculate 5 paths in 6 frames (I mean the influence &#111;n FPS)?<br><br>I don't know what more I can say… The maps are 60x60 to 100x100. There is a lot of obstacles like rivers, trees, buildings, rocks and so &#111;n…<br><br>Pszemsza<br><br>Ohh… Sorry for my English… I hope it's readable :)

These might help...
Coordinated Movement
Implementing Coordinated Movement

Quote:

Original post by tonyg These might help... Coordinated Movement Implementing Coordinated Movement

Yes, I already know that, but it's not the case. As I said, it's good for games like AoE (BTW: Author of these tutorials, Dave C. Pottinger, was working on AoE :)). It will be difficult to implement things like formations at my project...
The problem is that I know (more or less...) what I should to do (after all I wrote that :)), but I want to know if there is a smart way to do that, which allow us to solve that a bit faster. I know the general rule, but I'm intersted rather in specyfic implementation or pseudo-code...

You're going to need to reduce the number of pathfinding queries each frame if you want to increase your frame rate. If you're not reducing the number of units, then you need to have them share a reduced amount of information that's available to all units. This is where pre-computed information can be used.

Alternatively, information found by one unit at run-time can be shared with other units. For example, one unit discovers a path through a bottleneck. Rather than having all other units search for their own path through that bottleneck, that path is communicated to other units that might need it. Alternatively, convey not the path but rather a region of the map through which the path traverses that is free from static obstacles, so that all other units that need to travel in that area need not worry about static obstacles and can use a straight line path.

As for dealing with the dynamics of units, you're facing a fundamental problem in multi-agent environments... there's no simple solution (as I'm sure you understand). My best advice for improving efficiency is to bias each agents path away from areas of higher unit density unless there is a need to stay close to other units for tactical reasons. This will reduce the number of interactions per frame and improve your frame rate.

Cheers,

Timkin

Hmmm... I think I need a little bit of time (university, arghh...) to read something about that and to play around with the code... Thanks for advices. I will consider some of them and try to add to my project... Additional questions may appear later :)
Greets,
Pszemsza

I know this thread should be closed by now, but I have a couple of questions for you Timkin that popped up while reading your post (BTW, Viktor -- mip-maps are a great idea, and I can see how they will increase the framerate enormously).

Ok, here it goes: You talked about storing some paths for later use. But there's the whole issue that computer algorythms aren't very good at generalizing things. How do you suggest this could be done? Storing a good deal of paths, recognizing when 2 very similar paths could be aproximated by only one of them, and integrating this knowlege in a real pathfinding algorythm?
About your suggestion of biasing units away from high-density areas, I can see this being done by increasing the cost of traversing these areas, good idea.

[Edited by - Jotaf on February 22, 2006 7:45:39 AM]

Quote:

Original post by Jotaf Ok, here it goes: You talked about storing some paths for later use. But there's the whole issue that computer algorythms aren't very good at generalizing things. How do you suggest this could be done?

If the start and end of a stored path is close to the start and end of a path you are about to calculate, you can probably use the stored path with a little modification.

If you use a hierarchical system you can probably find an exact match with the higher-level paths. On the other hand, in such a system you can precompute a lot of the higher-level paths anyway.

I've been toying with path storage architectures for some years now, with the notion that an agent could reuse knowledge of previous pathing to assist in finding paths (or first guess paths) more efficiently... which also has practical use in multi-agent systems where agents can share knowledge.

Consider first that you merely want to store exact paths that have been found so that an agent (the same agent or another agent) can use this information later. You need a path representation. If you know the domain isn't going to change, then this can be achieved using the sequence of actions (or ordered references into a set of actions) that will recreate the path when executed. This is essentially plan storage and reuse. Alternatively, you can store waypoints that demarcate linear segements of the path and deduce the appropriate linear operator (action) to translate the agent between waypoints.

I've also played around with more complex graph building architectures. What I'm more interested in though is abstraction of pathing information and storage of this abstract path representation. I've been looking at tree decompositions and at the moment I'm looking into tree decompositions of composite spline curves (essentially B-spline trees). I don't really have anything conclusive to say on such methods yet, but they certainly offer some interesting possibilities and are fun to play with.

On the issue of path similarity (which is an aspect of the abstraction problem), you can measure similarity in a variety of ways: average separation, volume of space encompassing both curves, comparitive cost, etc. Once you have a measure of similarity then you have a means of deciding how well one curve can represent another. What is a tougher problem is for an agent to be able to determine when an abstraction of a previously found path is appropriate for its current problem. A first attempt at this is to compare the abstraction to a hypothetical straight line path between start and end waypoints. There are plenty of other ways to tackle this problem... I'd be happy to discuss this further, but perhaps we should do so in another thread dedicated to such issues, rather than derail this one further away from the issue of handling collisions.

Cheers,

Timkin