Sign in to follow this  
unsigned short

Conflicts between steering behaviors

Recommended Posts

I have a group of units which I'd like to order to a specific position. So for unit movement I chose a combination of the path follow and the arrival behavior (see steering behaviors by Craig Reynolds). To prevent units from crowding together I also added a separation behavior. But there seem to be a conflict between the arrival and the separation behavior. Because when multiple units try to arrive at a specific position, the separation behavior wants to separate them again and an annoying jittering effect comes up. Does anyone know how to somehow smooth the steering forces in a way that the units stand still when they can't go nearer to their target position?

Share this post


Link to post
Share on other sites
If you have multiple units, place them in a formation. A formation would assign different target points for each unit, e.g. V formation, circle formation, etc.

Then you wouldn't have any "conflicts" as each unit would have its own location...

Share this post


Link to post
Share on other sites
Put a floor on your movement so that if it is below a small value then there is no change at all. Once they get near to that equilibrium, they will simply stand still.

But, formations are cool too - if your design calls for that.

Share this post


Link to post
Share on other sites
Yeah these are possibilities I've already thought about. Formations are a certain problem with my design. Setting a threshold might be a consideration. However, because during the jittering effect the velocity is quite high, the threshold would have to be high too (first arrival behavior with high velocity, next frame separation with high velocity). So both don't really work well:(

Share this post


Link to post
Share on other sites
I think if you've got a group of units trying to "arrive" at a single point as well as separate then you're always going to lose out. Perhaps change your arrival behaviour to bring them to a rest within a certain radius of the target point? I suspect alexjc has the better solution though - proper handling of formations (where every unit has their own destination) would be a better way of handling things.

Share this post


Link to post
Share on other sites
Quote:
Original post by unsigned short
However, because during the jittering effect the velocity is quite high, the threshold would have to be high too (first arrival behavior with high velocity, next frame separation with high velocity). So both don't really work well:(


This implies sharp discontinuities at the edges of the separation and arrival effects, which doesn't sound good to me. At the furthest extent of the separation effect, you'd expect the magnitude of the separation force to approach zero. At some point as you approach the destination, the arrival and separation forces should be roughly equivalent and your jittering would reduce to a level below your threshold.

Another idea is to give each of the units randomised positions near the destination. Pick random places within a certain radius of the target, where the radius is proportional to the number of people you're sending there.

You might also consider some sort of 'step aside' behaviour for units that have already reached their arrival destination, but who end up blocking friends that haven't. The idea would be to move you out of a friend's path, wait for them to pass, and then re-do the arrival behaviour to move back. This could help prevent bottlenecks.

Share this post


Link to post
Share on other sites
You could always add some code that detects that a unit is stuck by simply storing a small history of positions, and checking to see how much the unit has moved over the last few updates. If it's not gone very far consider it stuck and stop trying to move (and maybe recalculate the route if it's not close enough to the destination).

Formations will work well for open maps, but are much more complicated in enclosed areas. For example consider a corridor that is only wide enough for a single unit, if a group arrives in the wrong order some of them will never get to their assigned positions without a lot more work.

Share this post


Link to post
Share on other sites
If unit A is trying to arrive at point P, check if a another unit is sitting on point P. If so, then calculate a new arrival point somewhere near point P.

Or if it is a group of units, do a leader-follow routine. Designate unit A as a leader and make it arrive at point P. Make the other units follow unit A.

Or, as suggested above do formation.

Share this post


Link to post
Share on other sites
The point of using behaviour based methods is to avoid excessive deliberative checking of entity states against constraints. If you choose a behavioural approach for movement (such as the popular steering behaviours) then it is defeating the purpose to then add state checks to avoid undesirable side effects. Clearly your behaviours aren't working as you had hoped or intended if you find yourself in this position.

It should be mentioned though (as Kylotan implicitly pointed out) that steering behaviours are functionally equivalent to potential field methods. Implementing these in discrete time dynamic programming algorithms leads (in general) to systems with oscillatory transient errors. In simple terms... the system state will not settle to an equilibrium point due to the discretisation of time (and/or space) without the addition of an additional damping term.

What you are witnessing in the jitter is the algorithms attempt to optimise the position of all entities with respect to the steering forces applied to them. This suggests a solution...

Since you are already computing distances to the arrival target it is trivial for you to compute the mean squared distance from all units to the target (sum up the squared distance and divide by the number of units). This represents your position error (w.r.t the arrival behaviour) at the current iteration. You are trying to drive error to zero. Monitor this error over time. If it's magnitude does not change by much over several iterations then it is likely that your system has settled into an optima. If the magnitude is also close to zero then you have settled around the global optima and you can turn off the arrive behaviour.

Share this post


Link to post
Share on other sites
Again, solve the actual problem you are trying to emulate. When we all say "let's meet over at the lamp post", we don't mean "all 25 of us need to be touching the lamp post." We are quite content to go stand within a certain reasonable distance of the lamp post until others show up. If we need to make room for people arriving, we do. If not, we just hang out near the lamp post. The actual lamp post itself is not a magical object - it is an abstract area that is defined by the lamp post for the sake of communicating the idea of "over there".

So, to emulate this...

If you know how many units are going to be at the arrival point, you can calculate an acceptable radius from the actual distinct point. The more units going there, the bigger the radius. Once a given unit is inside that radius, you turn off the arrival behavior and leave on the separation one. That way, peeps will "make room" for new arrivals to some extent.

The only tricky math will be at design time coming up with an algorithm to determine an acceptable radius based on the desired separation distances between agents. You want to make it big enough so they don't have to really jostle each other to all fit, but small enough so that it is obvious they are supposed to be meeting up there.

The only change you need to make to your code is to incorporate the radius calculation - which doesn't even really NEED to be dynamic. If it's not dynamic, then it can be a fixed value in the code. The only line change would be a simple if statement that checks the distance to the arrival point... "Am I close enough?" leads to "Do I add the arrival vector or not?"

The point is... sometimes we get so fixed on discrete, perfect solutions, that we lose sight of what sort of behavior we are actually trying to accomplish. In your example, you stated:
Quote:
I have a group of units which I'd like to order to a specific position.
You knew that by "specific position" you didn't mean that they should all stand on top of each other - that's why you were incorporating separation behaviors. However, as you proceeded, you were still locked onto the concept of the "arrival behavior" which, once you get to a certain point, becomes all but meaningless. It's much like the legendary runners paradox... where you cover half the distance, then half the remaining distance, then half the remaining distance... such that you never arrive. The paradox only holds if you assume that time is slowing down for you as well to the point where time is all but frozen. In this case, your false premise was holding onto the idea that your agents were desperate to reach that given point - despite the fact that they knew they couldn't all stand on it. At some point, the specific target point becomes irrelevant so therefore so does the arrival behavior.

The best solution for that is to put yourself in the place of your agent for a moment. In this case, if you would envision approaching the lamp post that was already crowded with people and saying "well, here's the meeting place - this is close enough." That statement, of course, is analogous to getting inside the acceptable radius. The next statement would be "it wouldn't look real good if I were to go and snuggle up to dude over there - I should keep my distance a little from each person." There's your separation behavior... still in effect.

In short, you were making your behavior model the logic of your math rather than making the logic of the math model your behavior.


Share this post


Link to post
Share on other sites
You might want to read Craig Reynolds paper again, because it doesn't sound like you implemented correctly. From what I understand, you are directly moving the agent's screen position to avoid crowding. Although the paper does mention this method, the entire idea of steering behaviors is that the agents are merely controlling their orientation and velocity, never directly altering thier x/y/z position. Please read on.

To get smooth movement you mustn't be hard-coding collision responses (ie, collision detected, move agent back 4 units). That should ideally never happen. What you want to do is simply rotate the agents facing vector away from the other agents vector. So if two agents collide (or have overlapping visibility radius) then multiply each agents vector velocity by the others vector multiplied by some constant (such as the current movement speed). Doing it like this will allow quick response for fast agents and ease back as they slow down. Also, if you are using the arrive behavior, the agents should be slowing down anyway, so their influence should be scaled down.

A quick solution would be to do as others have said and have the target position be an area like a circle, and have the agents pick random positions within that radius. You never want to have a large group of objects all arriving at the same location as you are bound to get collision issues. You can also chain agents together (have each ones target position linked to the previous agent) such that you will have a straight congo-line formation. Doing a few chains like this will make it look like there are different squads or factions all moving to the same area.

Share this post


Link to post
Share on other sites
Quote:
Original post by cyberpnk
To get smooth movement you mustn't be hard-coding collision responses (ie, collision detected, move agent back 4 units). That should ideally never happen.


Unfortunately that could still result from a typical implementation of steering if:
- the separation effect somehow has a non-zero threshold at the edges, or
- the updates are so infrequent that the discrete differences in forces between frames become large.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this