I''ve reached a point where i need to write my RTS engine a "go-to" function, now this question is made out of two: i completly understood A*, Bfs and Dfs and simple search. but my problem is as follows: when i move one unit, there is no problem, i calculate (and sucessfuly) its path and send it for her way. problems arise when i have more units. each time a unit moves, it affects the course of other units, in a way that each "turn" i need to calculate the whole route all over again. 1. i have no problem keeping EVERY units calculoations, but doing it each turn for like 200 units, isnt that alot? i''m afraid it will be a HUGE disadvantage in Framerate. the other option is doing a simple search, but it has big disadvantage in path-finding. 2. AI-wise, when a thought of finding a way is completed, does the perfect AI thinks of a way around the obstacle, or find a new path all over again? (just getting philosofical, 1st question is more important for me). 10x alot Gil

have a system with multiple layers. Break up the map into sections that aren''t that small. Do A* for that, keep that route and don''t change it. Now when the unit gets to a square it looks for the next square to go to on the main path. It can use A* or some other method to get there. Recalculate every turn if you have to, since it is just for a very small path it shouldn''t be too much of a problem.

The basic method of moving a unit as a whole is to work out the pathing for the leader and then have all other units play "follow the leader". If a unit gets stuck (possibly because of a collision or because it chose a wrong path to get to the leader) the most basic fix is to 'warp' the offending unit back to where it should be (near the leader).

Another method is to use movement formations. Just as armies do when marching or driving long distances, so your units can take on a formation. Then, simply plan a path that the formation as a whole can travel (ie, the path should be wide enough so that the formation doesn't have to change). If it does need to change - for instance going through a doorway - then deal with that scenario separately. Eg., move the formation to the door. Move each unit through the door to the other side, then move the formation to the next location.

Finally, here is a reasonably fast, accurate and appealing method.

For each unit, designate it a movement priority (something like the integers 1...N if you have N units). Plan the full path to the goal for the highest priority unit. At each waypoint on the path and for each unit, sample a point close to the waypoint that the unit will pass through. You can use a simple 2-d Gaussian distribution centered on the waypoint of the highest priority unit. Given each starting point for each unit, verify that the path to the next waypoint is clear. If it is not, then use the leaders path and add a small section at the start to take the unit to the leaders location and a small section at the end to move from the leaders waypoint to the units waypoint. Move units along the first segment. While moving along the first segment, continue to perform the path finding for all of the extra units using the method above and assuming that the first waypoints are the new starting points.

Finally, handle collisions in the following manner. If two units collide, stop the unit with the lower movement priority. If this doesn't allow the higher priority unit to move, then back the lower priority unit up a small distance to clear the way. Continue to move the higher priority unit for a few frames, then start moving the lower priority unit again.


As for the dynamic replanning (which might be necessary say if something blocks the leader units path after it has been found) then you can deal with this while finding the segments for each unit, which is done one segment ahead of time. Simply check first that the leaders path is still open (not blocked). If it is blocked, do a new search to find an open path and then continue to plan for the other units as described above.

Hope this helps,

Timkin

Edited by - Timkin on July 25, 2001 12:44:43 AM

Gamasutra has some great articles on this.
Coordinated Unit Movement - My personal favorite. Nothing like professional armies!

Realistic Pathfinding - While not completely on topic to your question, its nice if you have cars or ships in your RTS!

I hope these 2 links help.


Edited by - Elixir on July 26, 2001 1:14:11 AM

WHoa, I''ve found even a better solution,
something that reminds yours.

k, at the time that the usit is given an
order to move, it''ll calculate the path to
a linked list of moves. once.

now, in pseudo code:

  void turn(){     if next_move_on_path_is_blocked(path_list) {        calculate_new_path(path_list, destx, desty);     } else {        walk_move_on_original_list(path_list);     }};  

now, in a more simple words, if you wanna go to the mall
from your house, you dont care when you leave the house if
someone is blocking you path (momentarily). you only care
when you are blocked in the next couple of moves (lets
call that a range of view). so youll cross a and b street,
pass through this corner, and only when youll see that someone
is blocking your way in, only then you calculate a new path.

or as timkin suggested, wait (if he has higher priority) for him
to move. which isnt that useful if, lets say, a new constructed
building is blocking the way. you cant wait for THAT to move.

thanks you all guys,
and if you have better ideas,
i''m all ears

Gil

Hey forget all the advice you''ve been given its too much work.
Find some articles on Steering Behaviours. I did and I had
it working in a week. I tried to get that Coodinated Movement
rubbish working and wasted months of work. Don''t do it to your self. I can''t remember the link but the most useful article was written by

Robin Green (rgreen@eaeurope.com)
R&D Programmer, Bullfrog Productions Ltd


The name of the zip file that contains the notes is

S2000Course39DemoGreen.zip

Its great because it includes source code.

I don''t know if they have a link to it on this site but they should put one up if they don''t.

Good Luck