Sign in to follow this  
daniel_i_l

Group Movement with Flocking

Recommended Posts

I was wondering how groups of units were implemented in RTS games so that they could move together around a map with obstacles. One option that i read about was to find a path (with A* or something) from one unit in the group to the target position and then use craig's flocking to make them all move together. But there was one thing i didn't understand, let's say that the units get into the following position:
    |   |
    |   |  
----| * |----
  * |* *| *
  * * * * *

where the '|' and '-' are walls and '*' are troops. In this case the path goes inbetween the walls and the units are flocking together and following the path, but soon the ones in the middle will continue upwards and the ones on the sides will be hopelessly stranded in the corners, trying to go in the same direction as the rest of the group! I thought that maybe i should constantly check all the units to see if one of them gets stuck and if they do - break of the unit that got stuck from the group and find a new path for it - but with this method, if the group is navigating a tight enviroment it'll quickly become divided into lots of subgroups thus losing any advantage that the flocking gave. Are there any better methods? Thanks.

Share this post


Link to post
Share on other sites
One method I have seen (can't remember where) is to only have A* return paths that allow a width equal to that of the formation. Your situation above would not have happened.

More practically is to not use "flocking" to stay around the leader but rather "station keeping". In that case, each member is specifically trying to keep a certain offset from the leader (e.g. back 10, left 10). Then you have the unit steer toward that point. If you detect that he doesn't have a direct line to it (i.e. obstacle), you can run a quick pathfind to see if he needs to jump through hoops to get there.

There are always going to be situations that pose challenges. It's hard to solve for them all.

Share this post


Link to post
Share on other sites
InnocuousFox's "Station Keeping" is a good start. You can apply cooperative pathfinding methods to move each unit to their individual positions relative to the leader. Because its a much smaller path, the cost of doing a cooperative pathfinding is not so bad.

Share this post


Link to post
Share on other sites
Thanks for the advice.
But i might have thought of a way to solve the problem i mentioned above. Inorder to keep the "flock" from going dangerously straying from the trail you construct "virtual fences" around the trail that only stop the units in the flock. In order to construct the fence a mimimum distance would be calculated for each segment of the path - the minimum distance is the longest line prependicular to the segment that doesn't touch any obstacle. In addition, mindis of one segment wouldn't be able to get bigger than the previous one within a certain threshold. For example, the virtual fence of the walls above would look like this:

| |
| |
----| |----
| |
/ --- \
/ ----- \
|---------|
| |




where the added fence is in the last four lines. (all the '-'s are just so that it'd align properly)
This way, the flock would grow and shrink in a natural way according to the size of the path as wall avoidence in a trivial steering behaviour?
What do you think?
Thanks.

Share this post


Link to post
Share on other sites
Quote:
Original post by daniel_i_l
What do you think?
Thanks.


Honestly, too complex. It would be *much* simpler to detect when individual units get astray from the flock, and then activate pathfinding for those units until they find the way back.

Share this post


Link to post
Share on other sites
InnocuousFox:
-And it doesn't take into account non-perpendicular approaches to the opening. If they come at
-a 45 degree angle, half the group will miss your inviso-fences.
If they come at a 45 deg. angle then the path will also have come at that angle. Since the inviso-fences are built along the path the units can never "miss" the fences.

Steadtler:
-Honestly, too complex. It would be *much* simpler to detect when individual units get astray from the flock,
-and then activate pathfinding for those units until they find the way back.
yeah i guess you're right... i just liked the fence idea because it allowed me to keep from firing up the pathfinder everytime a unit gets stuck.
But don't you think that it's an advantage to only let the "group class" work with the pathfinder and have the individual units go according to relativly simple rules? Sorry if i seem like i'm stubbornly sticking to a bad idea, it just seems like having each unit following it's own path is more complicated than having one "fenced off path". and what's complex about the fences? It seems like it'd be relativly simple to implement:
-to find the "min-dis" of a segment is trivial raytracing.
-to construct walls just make lines prependicular to the segments, each one with the lenght of the min-dis of the respective segment, then connect all the endpoints on the "left" and all the ones on the "right" to make the fences.
Could you guys please convince me that this is a bad idea before i start a pointless project?
Thanks!

Share this post


Link to post
Share on other sites
Quote:
Original post by daniel_i_l
yeah i guess you're right... i just liked the fence idea because it allowed me to keep from firing up the pathfinder everytime a unit gets stuck.
But don't you think that it's an advantage to only let the "group class" work with the pathfinder and have the individual units go according to relativly simple rules?


That depends on the complexity of your environment. Flocking was originally designed in a totally free environnement, and tough I love steering behaviors and frequently use them, they work best when there is few obstacles, or at least when the obstacles are convex. According to your original post, your environments can get pretty complex.

Quote:
Original post by daniel_i_l
Sorry if i seem like i'm stubbornly sticking to a bad idea, it just seems like having each unit following it's own path is more complicated than having one "fenced off path".


Remember that individual units dont need to find a path to the destination, but only to their relative position from the leader, or only back to the flock. Since such paths should always be rather short, the cost should be minimal, and it also allows you to introduce cooperative pathfinding if you want. As for the complexity of implementation; detecting when a unit is astray from the group is trivial (distance from leader, threshold depend on group size), and you already have the pathfinding implemented anyway, for the group/leader.


Quote:
Original post by daniel_i_l
and what's complex about the fences? It seems like it'd be relativly simple to implement:
-to find the "min-dis" of a segment is trivial raytracing.
-to construct walls just make lines prependicular to the segments, each one with the lenght of the min-dis of the respective segment, then connect all the endpoints on the "left" and all the ones on the "right" to make the fences.
Could you guys please convince me that this is a bad idea before i start a pointless project?
Thanks!


Intuition, experience, spider sense, call it what you want, tells me this is the kind of idea where you could get stuck in an endless list of problematic cases, and numerical problems. I could be wrong. But imagine your units moving in a room full of pillars. Where simple flocking would have the units move elegantly and naturaly around the pillars, "fenced" flocking would have all of them trying to get between the same two pillars. That solution is simply too specialized and restrictive, in my opinion.

Good luck!

Share this post


Link to post
Share on other sites
Heck, if you are going to all the programatical work to make your "fences", just make invisible convexities on your obstacles... in this case, make it so that you connect the ends of the entrance back to the walls at a somewhat shallow angle. It doesn't make it completely convex, but combined with a gentle system of trying vectors towards the center of the group (or leader), they would be more inclined to slide off those invisible walls and into the doorway than in the original situation where they would have to actually back up.

Share this post


Link to post
Share on other sites
Gosh, everything just gets more complex and you start losing the essence of flocking. I would say that you don't need anything too complex, something like a modified evacuation simulation will work, especially since you're working in real space.

Yes, a leader is a good way to do it, but the problem is the behavior of the others in the group, which can be controlled very simply. Just have them try moving towards the leader, while not stepping on each other and hit walls. This can be done with gradients. The leader exerts an attractive force on all units in the group, while everyone else in the group exerts a small repulsive force on its surrounding group members to keep from being trampled. Then have the walls exert a repulsive force in a specific direction. This way, the only problem you might run into is if you have walls that are less than 90 degrees, like a sharp split in the path, which may cause the group to split up, but those can also be handled with by messing with the repulsive forces or having the leader drop attractive waypoints as he goes, which disappear in attractive strength over time.

You might find that this will create some varied interesting results. This is basically the social interaction model used by most evacuation simulations, whcih have been shown to be quite accurate.

Share this post


Link to post
Share on other sites

| |
| |
-\--| |--/-
\_| |_/

Make the angled lines twice as shallow, though. (Hard to do with ANSI art)
Also, the repulsive forces mentioned above can be used in the same way as my invisible walls. Set a repulsor in those corners so that the agents don't go there:

| |
| |
----| |----
*| |*



* is a repulsor point on the map

Share this post


Link to post
Share on other sites
I would recommend personally firing off a small pathfinding task to catchup with the leader. Small search space (especially breadth first).

Its also the generic solution to 'getting stuck'. Your corridor idea could end up working for this 1 solution but then you may have to think up another specific solution for another specific solution.

The generic solution if you set up a 'stuck flag' could end up magically fixing other problems :)

Share this post


Link to post
Share on other sites
Just as a variation to everything mentioned thus far. If you the leader is always front and center you can just have all units try to maintain the least relative distance between them and the leader moving towards the nearest unit to the leader if they can't move adjacent to the leader. This could be done by giving the leader a weight of 0 and increasing it by 1 for each space away a unit is from the leader and units always moving towards the unit with the lowest weight.

Or a buddy scheme. Where units always follow their buddy and buddies are assigned based on distance from the leader.

Share this post


Link to post
Share on other sites
Or you could simply have the leader act as a formation oracle, ordering the unit to temporarily change formation when it notices the constriction. Think of the formation's current shape as a state of a formation object. Generally, you want to allow it to be a fluid shape, but sometimes you want to enforce a shape on it.

How does the leader notice the constriction? I can think of several ways, but the easiest might be to cast out a ray in either direction along the front of the formation, but offset a distance in front of the leader, equal to the expected distance covered to the next AI iteration. If the ray intersects a wall then you know the world is about to get narrow! This will also give you the width of the constriction for selecting a new formation shape. This is a kind of collision detection between the environment and a 'formation object'.


Share this post


Link to post
Share on other sites
Quote:
Original post by Timkin
Or you could simply have the leader act as a formation oracle, ordering the unit to temporarily change formation when it notices the constriction. Think of the formation's current shape as a state of a formation object. Generally, you want to allow it to be a fluid shape, but sometimes you want to enforce a shape on it.

How does the leader notice the constriction? I can think of several ways, but the easiest might be to cast out a ray in either direction along the front of the formation, but offset a distance in front of the leader, equal to the expected distance covered to the next AI iteration. If the ray intersects a wall then you know the world is about to get narrow! This will also give you the width of the constriction for selecting a new formation shape. This is a kind of collision detection between the environment and a 'formation object'.


I like it! Simple and elegent, but more then that it open up other possiblities as well. If you don't limit a squad leader's ability to reshape a squad to just moving past obstacles then you could then you could have squads reshape base on the situation and objective. Being Attacked by an area effect weapon? The squad leader automatically reforms the squad into a disperesed formation to eliminate or reduce the effects of splash damage.

Share this post


Link to post
Share on other sites
Quote:
Original post by Timkin
Or you could simply have the leader act as a formation oracle, ordering the unit to temporarily change formation when it notices the constriction. Think of the formation's current shape as a state of a formation object. Generally, you want to allow it to be a fluid shape, but sometimes you want to enforce a shape on it.

How does the leader notice the constriction? I can think of several ways, but the easiest might be to cast out a ray in either direction along the front of the formation, but offset a distance in front of the leader, equal to the expected distance covered to the next AI iteration. If the ray intersects a wall then you know the world is about to get narrow! This will also give you the width of the constriction for selecting a new formation shape. This is a kind of collision detection between the environment and a 'formation object'.


Wont this have the same problem that the OP's solution in regards of simple obstacles? If moving in a large area with some small obstacles, the leader will force every one to go in between the same obstacles as him, when it would be more efficient to have most of them go around. I still tihnk this kind of method remove the benefits of flocking.

Share this post


Link to post
Share on other sites
Quote:
Original post by Steadtler
Quote:
Original post by Timkin
Or you could simply have the leader act as a formation oracle, ordering the unit to temporarily change formation when it notices the constriction. Think of the formation's current shape as a state of a formation object. Generally, you want to allow it to be a fluid shape, but sometimes you want to enforce a shape on it.

How does the leader notice the constriction? I can think of several ways, but the easiest might be to cast out a ray in either direction along the front of the formation, but offset a distance in front of the leader, equal to the expected distance covered to the next AI iteration. If the ray intersects a wall then you know the world is about to get narrow! This will also give you the width of the constriction for selecting a new formation shape. This is a kind of collision detection between the environment and a 'formation object'.


Wont this have the same problem that the OP's solution in regards of simple obstacles? If moving in a large area with some small obstacles, the leader will force every one to go in between the same obstacles as him, when it would be more efficient to have most of them go around. I still tihnk this kind of method remove the benefits of flocking.


Throw a local area check in to tell if it is a 'big' object, or a 'small' object. Small ones can be walked around, large ones that split paths to points that would be too far away from each other are then trigger the tighter single path group.

Share this post


Link to post
Share on other sites
I hate this topic :) I have found that the steering behaviors look really good on paper and that's about it. Most of it falls apart when you are actually trying to get a unit to go to a specific spot. Also as mentioned, they don't do well with obstacles.
What I ended up using in a shipping game, The Warriors, was formations.

1)A leader of the group would have slots, positions relative to the leader, that group members would follow.
2)These slots would get updated when the leader has moved a certain distance, save 1m, or a timer timed out.
3)The follow slots would have their position updated relative to the leader and then a check to see if its position was a valid spot to move to.
4)Also a line of sight check from the leader to each slot was done so that slots on the other side of a wall would become invalid.
5)Next I assigned each slot to a member. Assignment was done based on who was closest to each slot.
6)Once all the slots were assigned I did a 2d line test to see if any of the assignments caused people to cross paths, if they did I would just have them switch slots.
7)I did up to 3 passes trying to resolve crosses. This might seem like a waste but I found that the best solution was to never tell people to cross paths in the first place. Instead of blindly moving units and then try and make them not collide.
8)Now if there weren't enough slots for all the units, I would have the remainder of the units trail someone who did.
9)Trailing was done by having all units in the game save their position every meter. This was useful BTW for many things.

So back to your problem :) My method would have the group follow up until the canyon. Then the leader would move through and most of his slots would become invalid. This would force everyone to line up single file until they became valid.

Share this post


Link to post
Share on other sites
Good idea, but there is still the danger in the "forest" situation that potential legit slots would be disqualified because they are temporarily on the opposite site of a tree.

There needs to be a way for the leader or followers to determine if an obstacle is a temporary (and thus tolerable) situation or if it is truly going to cause a problem.

Think about this: When walking through a forest, for example, or past another interposing object of some sort, if we know where the leader is going, we can realize that, despite being seperated for a brief period, we will soon be rejoined (via direct LOS) in a moment - therefore, we persist as if we were not separated at all. To model this would entail not just an idea of where our leader is at the moment but also a concept of where that leader is going and therefore our own future relative location.

Our questions become:

Is that future relative location a valid one?
Is it accessible from here?

Share this post


Link to post
Share on other sites
Ultimately the OP has to decide if they want to handle the failure when it occurs or avoid it before it occurs.

Handling it is a matter of each blocked unit backtracking to the closest state at which a valid path can be found (the same paradigm as backtracking up a search tree when you find a dead leaf). Avoiding it requires prediction (reasoning about actions/plans/behaviours) and a means of assessing whether each unit should carry on with what it is doing or change its behaviour. My earlier suggestion was in this vein, but only one unit did the reasoning (the leader) and commanded the others to change. This is one of the simplest means of doing this (and almost certainly not likely to be the best in all situations).

Steadtler: Obviously, how you reform is a matter of assessing the requirements of the situation. If you're in a forest, the leader could simply say, "I'm heading in this direction at this speed as best I can. You do your best to maintain a parallel trajectory" and then each unit manages themselves until told otherwise. This is a perfect situation for switching between steering behaviours that are primarily designed to maintain formation and those that are primarily designed to get the unit to the goal. Think of a subsumption architecture for this. Combine 'stay in formation' behaviours with 'move to goal' behaviours. When you find lots of objects that are making it hard to stay in formation, relax that behaviour and give more weight to 'move to goal' behaviours.


Share this post


Link to post
Share on other sites
Timkin brings up a great point: Why one architecture to solve all contingencies? Certainly a macro-state over this issue can be used to set what sort of approach you will need to use at any one time. All it takes, then, is a diagnostic analysis of the environment to see which state you are in (as a leader) and give an entire set (or type) of orders accordingly.

Sometimes if you can't solve the problem, you need to back up one layer of assumptions.

Share this post


Link to post
Share on other sites
A neat trick to use whenever doing any sort of formation movement based on a formation of distance-based offsets: use pathfinding to validate that the spot is roughly the same distance to walk to as it is to fly to in a straight line. Do a search with a node count limit related to the square of the distance (A* search node count is sort of an area, so the relationship to distance is ^2). If your search succeeds, use the spot. If your search fails, a really good fallback spot is the nearest point to the goal you reached in your search (the lowest H point touched that isn't occupied). This worked really well for us in Company of Heroes, since guys can go on the opposite side of very small obstacles like trees/dead vehicles, but they won't go on the opposite side of large obstacles like long walls.

Cheers,
Chris

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