Jump to content
  • Advertisement
Sign in to follow this  
daniel_i_l

Group Movement with Flocking

This topic is 4132 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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
Advertisement
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
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.

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
-"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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!