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.

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.

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.

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.

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.

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.

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!

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!

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.

-"In this case, make it so that you connect the ends of the entrance back to the walls at a
-somewhat shallow angle."
Can you explain that?
Thanks.