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.

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

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

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 :)

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.

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

"Cat's Whiskers"

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.

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.

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.

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.