Hello all. I have just put in a somewhat workable unit to unit collision response system for my RTS. However, now I need a good system for handling multiple units colliding. One issue that I have found is when two or three units make a 'corner' (I'll call these units B, C, and D), and unit A is trying to get to its destination, and on the way runs into this corner. Right now, with the way I have it implemented, unit A will just stay there, and won't find its way around the other two or three units. What is a good way to determine the best path for A to get around the other units to get to its destination? The way I'm determining movement after collision is by determining which quadrant unit (A) is in when it collides with another unit (B), Upper left, bottom left, etc. Then I determine where the destination is relative to B, and move A in the correct direction. The same type of thing needs to be done when unit A is colliding both with a unit and an unwalkable tile. I figured the same type of algo can be used for this as multiple units. Any suggestions on how to handle this? Jeff

Pathfinding should be done with A*

Dynamic avoidance can be done with a number of techniques: flocking, "follow the leader", can be built into the A*

If you wait until the collision happens, it's too late to do anything about it.

But start with implementing A*.

Also, in an RTS, units interpenetrate all the time. The first step is to ensure that your game is functional so disable collision between units. A little clipping here and there is not going to be noticed. But at that point the clipping is an aesthetic issue (to be handled with dynamic avoidance algorithms)..

[EDIT: also the more appropriate title for this post would be "Pathfinding and Dynamic Avoidance in an RTS" What you're trying to solve is not collision response but collision avoidance and good pathfinding.]

-me

Thanks for the quick reply Palidine.

I already have a A* pathfinding algo in place. Units will avoid any type of unwalkable tile.

But like I said, when two units collide, they will basically push each other away, in the direction that is best suited for getting to their destination. This works well in wide open spaces. However, if a unit is next to trees, and another unit collides with it, the colliding unit may be pushed into the trees, because currently I am not taking into account that there may be an unwalkable tile there. A unit needs to be able to recognize that it is colliding with both a unit and an unwalkable tile, and then go a different route.

My A* currently only takes into consideration static objects (trees, buildings, map edges, etc). I was then going to determine unit collision->response dynamically.

I'm also not setting certain destination when a unit collides, it is just pushed in the best direction. This is why it is sometimes pushed into trees.


Maybe I need to clarify how a unit moves:
1. When a destination is set for a Unit, it moves in a straight line to that destination.
2. If it hits a...
A. Unit: it is pushed in the best direction, according to where it hit the other unit, and where it's destination is.
B. Unwalkable Tile: A path is set with A*.

So basically a unit moves until it hits something, then it is handled accordingly.

Right. But what i'm saying is that you have to change how it works if you want it to work "correctly". Waiting until a collision happens is too late to get a good result.

Option1 : ignore unit-unit collision and just walk through your friend (this is actually a pretty standard solution, and it's easy as hell to implement)

Option2 : look ahead on your path, if a unit is there either (a) re-plan around him (b) tell him to move (now he'll move to a good place) (c) something else

Option3 : consider other unit locations when path planning and fail the move at the location of the other guy

Option4 : create a time-dimensional map of your tiles and path-plan through that. essentially, you know that at time=t you will be at spot x. so when someone else is path planning they look at the node state for the time they would occupy the spot. this get complicated and potentially expensive, but it has been used sucessfully before.

Option5 : bump and steer around friendly units when you're in proximity. One solution is a "follow the leader" -> when 2 units get close randomly choose a "leader". The follower walks towards a spot behind the leader, only 1 follower per leader. If you get to a case where you can't find a leader (b/c he's taken by someone else), then just stop moving for a random interval and try again to resume your move after the interval's completion.

There are lots of other options, but this should be a nice start to get your brain going.

Dynamic avoidance is "hard" so expect to spend at least a few weeks (full-time) on a solution.

-me

Quote: Dynamic avoidance is "hard" so expect to spend at least a few weeks (full-time) on a solution.

Yes I've discovered this :).

Your option 5 is similar to the one that I was interested in. I want Unit collision response to be dynamic ( as finding paths that will never intersect in an RTS would be very hard...Collisions will be inevitable) I had never considered assigning a leader. I currently treat all units equal. I remember reading in an article about setting certain units movement priority at different levels, so that one is the 'leader', and will tell the others what to do accordingly.

I think I will play with this option this weekend and see what comes out of it.

Also, Option 1 is a very simple one, yet having units in an RTS move through each other is not very realistic ( except for resource gatherers I suppose). However, it would reduce the amount of work greatly :).

Jeff

In option 5 you just roll dice to pick the leader. it's random. Also, don't wait until the moment of collision, you should detect an imminent collision at least several tiles away so that units have time to avoid eachother.

-me

When a unit is moving, to determine future collisions, do you just check to see if (UnitA->distanceFrom(UnitB)< SomeDistance), and if it is, see if their paths will come close in the next few frames? Then set leader accordingly, move, etc.?

Jeff