Sign in to follow this  
nlarooy

Arrival Steering Behaviour In a Group

Recommended Posts

Hi there,

I'm using a combination of separation, cohesion and arrival steering behaviours for units that I want to move towards a given point.

In motion, the system works fine. However, when they group reaches the target, they all start jostling and bouncing off of eachother, and only a few actually stop at the target.


Any ideas on what behaviours/techniques I should use for this situatuion?



Thanks

Share this post


Link to post
Share on other sites
[quote name='nlarooy' timestamp='1313846664' post='4851583']
Hi there,
I'm using a combination of separation, cohesion and arrival steering behaviours for units that I want to move towards a given point.
In motion, the system works fine. However, when they group reaches the target, they all start jostling and bouncing off of eachother, and only a few actually stop at the target.
Any ideas on what behaviours/techniques I should use for this situatuion?
[/quote]

I asked[url="http://www.gamedev.net/topic/598729-group-movement-and-arrival-behavior/"] the exact same question[/url] some time ago, but the good solutions are apparently a well guarded secret :). One "solution" I used was to not send every unit to the exact same position. So If units already are in a reasonable formation I'd calculate the offset of each unit from the "center of gravity" of the group and then apply the same offset to the individual unit destination. In case the units were spread out I calculated a formation and used the offsets I got from there. I wasn't entirely content with that since making reasonable formations isn't trivial.

I'm also still interested in answers.

Share this post


Link to post
Share on other sites
Yeah, I did read all of the search results I could find, but to no avail.

However, I have an idea of how it might be done!

[list][*]You create an abstract "MovementGroup" object.[*]This object provides a target for the group to head towards, and a steering which is the "arrival" from the average group position to the target.[*]It also detects when the average position of the group is on the target, at which point the group will be considered to have arrived.[*]If the group has not arrived, all of the units in the movement group behave as a flock, with "separation", "cohesion", "alignment" to the MovementGroup's steering and "arrival" towards the MovementGroup's target.[*]Otherwise, all the units perform a "braking" behaviour.[/list]
This should make the units stop scattered on top of the target.

Share this post


Link to post
Share on other sites
[quote name='nlarooy' timestamp='1313853274' post='4851615']
Yeah, I did read all of the search results I could find, but to no avail.

However, I have an idea of how it might be done!

[list][*]You create an abstract "MovementGroup" object.[*]This object provides an "arrival" steering from the average position of the group to the target.[*]It also detects when the average position of the group is on the target, at which point the group will be considered to have arrived.[*]If the group has not arrived, all of the units in the movement group behave as a flock, with separation and alignment to the MovementGroup's steering.[*] Otherwise, all the units perform a "braking" behaviour.[/list]
This should make the units stop scattered on top of the target.
[/quote]

I also considered having an abstract MoveOrder coordinating the whole group. There are a few things that scared me away though. It introduces additional "administrative" work like tracking all the members of the group, handling cases where units are given other orders/die etc. Maybe this is necessary, but I always try to find more lightweight solutions before bloating my code with additional "systems". Then there is quite some amount of cases that this approach still doesn't handle:
1. Units with different velocities/groups that get split up:
When the units end up being spread out or forming multiple groups because of different velocities or because some might get stuck on something/attacked etc. you might end up calculating an average position that is just in the middle of nowhere between your units. Without trying it out this sounds like a source of glitchy behavior.
2. Also, how do they arrive if they get separated? Will the first ones just try to arrive separately and twitch out until the average position has converged?
3. It doesn't handle "implicit" groups. Think of say starcraft where you have different controlgroups for different types of units (infantry, air, spellcaster...). If you want to move your army, you just send all those groups to the same location but wit different commands. So the different groups might get into each others way at the destination.

Share this post


Link to post
Share on other sites
[quote name='japro' timestamp='1313854965' post='4851625']
[quote name='nlarooy' timestamp='1313853274' post='4851615']
Yeah, I did read all of the search results I could find, but to no avail.

However, I have an idea of how it might be done!

[list][*]You create an abstract "MovementGroup" object.[*]This object provides an "arrival" steering from the average position of the group to the target.[*]It also detects when the average position of the group is on the target, at which point the group will be considered to have arrived.[*]If the group has not arrived, all of the units in the movement group behave as a flock, with separation and alignment to the MovementGroup's steering.[*] Otherwise, all the units perform a "braking" behaviour.[/list]
This should make the units stop scattered on top of the target.
[/quote]

I also considered having an abstract MoveOrder coordinating the whole group. There are a few things that scared me away though. It introduces additional "administrative" work like tracking all the members of the group, handling cases where units are given other orders/die etc. Maybe this is necessary, but I always try to find more lightweight solutions before bloating my code with additional "systems". Then there is quite some amount of cases that this approach still doesn't handle:
1. Units with different velocities/groups that get split up:
When the units end up being spread out or forming multiple groups because of different velocities or because some might get stuck on something/attacked etc. you might end up calculating an average position that is just in the middle of nowhere between your units. Without trying it out this sounds like a source of glitchy behavior.
2. Also, how do they arrive if they get separated? Will the first ones just try to arrive separately and twitch out until the average position has converged?
3. It doesn't handle "implicit" groups. Think of say starcraft where you have different controlgroups for different types of units (infantry, air, spellcaster...). If you want to move your army, you just send all those groups to the same location but wit different commands. So the different groups might get into each others way at the destination.
[/quote]

Agreed... I just tested it. It works very nicely when the units are all together (close to the separation distance) and you move them to a new location. It works horribly when they start scattered around the map.

Back to the drawing board...

Share this post


Link to post
Share on other sites
Further thoughts...

I'm going to try something like this:

[code]Move(units, target)
{
groups = groupUnitsByPosition(units)

if (groups.Count > 1)
{
foreach group in groups
{
Move(group, target)
}
}
else
{
MoveUnitsLikeBefore()
}
}[/code]

Share this post


Link to post
Share on other sites
The solution I've used in the past is to add a small bubble of repulsive force around each unit. As you perform your steering update tick, add the repulsive forces from each unit to each other, preferably using a simple linear or quadratic decay curve (in distance between units). It can take some tweaking to get it perfect, but done right, you should notice that groups tend to stay separate even during movement, and then "arrive" and jostle a little bit (albeit realistically-looking) and then settle into an equilibrium.

Experiment with the decay curves, influence radius, and other factors, and you can even get crowds that mill around interestingly with very little computational effort.


[edit] I should note that the secret to making this work is [i]arrival thresholds.[/i] Don't expect every steering force to place the unit directly on the target coordinates. Instead, have each force stop being active once it reaches a [i]minimum distance [/i]from the target. This is how you disable the arrival and cohesion forces and have the mill-around-the-target force take over. For bonus points, don't make the threshold a boolean flag, but instead offer support for decay curves that in turn adjust the influence of a force based on how close you are to a given target point.

Share this post


Link to post
Share on other sites
[quote name='ApochPiQ' timestamp='1313920111' post='4851837']
I should note that the secret to making this work is [i]arrival thresholds.[/i] Don't expect every steering force to place the unit directly on the target coordinates. Instead, have each force stop being active once it reaches a [i]minimum distance [/i]from the target. This is how you disable the arrival and cohesion forces and have the mill-around-the-target force take over. For bonus points, don't make the threshold a boolean flag, but instead offer support for decay curves that in turn adjust the influence of a force based on how close you are to a given target point.
[/quote]
Good idea, but this method assumes that there is enough room to "mill around the target", clearing the path before slower groups arrive and forming a well shaped front around objectives.
If units are going through a narrow choke point and/or into an enclosed place, they might pile up beyond their arrival threshold distance, pushing hard without moving much (as if they had no threshold).
Scaling down forces mainly according to crowding in front of each individual unit (e.g. distance to the closest obstacle straight ahead), irrespective of location, might be more reliable: regardless of who is "arrived" or not, if my companions are slow pushing them to get ahead slows them down even more, and I should match their speed or take a detour around them instead.

Share this post


Link to post
Share on other sites
The solution to chokepoints is to have introspection capabilities in your pathfinding. If you notice a comparatively large number of path queries moving through a narrow geographical area in a short time window (i.e. you have a bottleneck), select some agents to drop their speeds temporarily near the choke, or find alternate routes, or whatever.

This is going to be highly dependent on the particular game and even the particular level geometry coming into play, though.


A poor-man's solution is to stop local steering entirely if you spend more than N ticks without making observable progress towards your next waypoint. Pause momentarily (this needs tuning depending on the game) and then re-issue a fresh path query.

Share this post


Link to post
Share on other sites
[quote name='ApochPiQ' timestamp='1313920111' post='4851837']
The solution I've used in the past is to add a small bubble of repulsive force around each unit. As you perform your steering update tick, add the repulsive forces from each unit to each other, preferably using a simple linear or quadratic decay curve (in distance between units). It can take some tweaking to get it perfect, but done right, you should notice that groups tend to stay separate even during movement, and then "arrive" and jostle a little bit (albeit realistically-looking) and then settle into an equilibrium.

Experiment with the decay curves, influence radius, and other factors, and you can even get crowds that mill around interestingly with very little computational effort.


[edit] I should note that the secret to making this work is [i]arrival thresholds.[/i] Don't expect every steering force to place the unit directly on the target coordinates. Instead, have each force stop being active once it reaches a [i]minimum distance [/i]from the target. This is how you disable the arrival and cohesion forces and have the mill-around-the-target force take over. For bonus points, don't make the threshold a boolean flag, but instead offer support for decay curves that in turn adjust the influence of a force based on how close you are to a given target point.
[/quote]

This makes sense, but suppose you have a behaviour which you want performed after the unit arrives?

You need to be able to decide when a unit has arrived at the target, and this will differ based on whether other units are in the way etc.

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