Sign in to follow this  
Geron

Moving in formation

Recommended Posts

I'm experimenting with flocking behaviour and formation movment. So far each individual are given a offset to the flocks center. This makes each individual in the flock seek its position in the formation. I do however have a problem. If one member in the flock is removed (dies or otherwise). I have no real good way of rearanging the formation. What I want to do is to make indivuduals close to the, now vacant, position to take its place. Anyone here who have a good suggestion on how to do this? I've considered araging the individuals in a tree structure, if one individual die, I'll just pass a child and its subtree up one level in the tree. This doesnt solve everthing though. As I want the replacement to be a bit more intelligent. The formation must always be compact, no holes.. Nor do i want a formation to look like this:
.  Front
.  xxxxx
.  x xxx
.  x x x
.    x

the abouve should rearange to
.  xxxxx
.  xxxxx
.   xxx

And it would be nice if its done in a intelligent way. I could ofcourse just rearange the whole group. This would however cause a formation to fall appart each time a member is lost. So, any ideas for a good solution to my problem?

Share this post


Link to post
Share on other sites
As I started reading the post, I was thinking the same thing you went ahead and mentioned - the idea of using a tree structure of some sort. That seems to make sense, but there are a lot of ways you could arrange it - each having pros and cons.

Based on your example, I assume that you want to have rigid, preprogrammed positions and not just the flocking rule of "get close but don't step on me"?

Share this post


Link to post
Share on other sites
Quote:
Original post by Geron
I'm experimenting with flocking behaviour and formation movment. So far each individual are given a offset to the flocks center. This makes each individual in the flock seek its position in the formation.



Do individuals have specific positions within the formation, or do you just want them all to clump together? Do individuals move only on a grid?

-Predictor
http://will.dwinnell.com

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Each individual has its own position within the flock. Though this position is only a offset to the flocks center
ASCII-art:


^
| This vector represents the flocks direction and center
x

1 2 3 4 The numbers are offsets to the flock center
5 6 7 8



Each individual are given a position in the flock (or offset to flock center).. The flock center is the average position of each individual.. This makes the flock behave as a flock, but gradualy the take their place in the formation.

Controlling the flock direction is done manualy, thus giving the user the ability to control where the formation will point (or move).

The problem is how to rearange the flock in a fast and somewhat intelligent way when a individual is removed. For example if the individual whos assigned position 3 in the example above dies. Whos gonna take its place. As I want the formation to be compact, and they should all want to be near the front of the formation.

Share this post


Link to post
Share on other sites
Gah, forgot to log in.. post continued here:

Thus in the example above, if number 3 dies, number 7 should step forward.. Then either number 6 and 5 move one step to the right or number 8 should move to the left.

In order to do this efficiently, I need help designing the logic and/or structure to make this happen.

Share this post


Link to post
Share on other sites
This sounds a bit like the 8 puzzle.

Depending on the number of units in your flock, you could do a search for the least number of 'moves' to get to a particular shape (or to any valid formation shape).

Share this post


Link to post
Share on other sites
Quote:
Original post by BrianL
This sounds a bit like the 8 puzzle.

Depending on the number of units in your flock, you could do a search for the least number of 'moves' to get to a particular shape (or to any valid formation shape).


Guess I could.. But I want this to run in real time, when using about 200-500 individuals per flock. So I need something that is rather fast..

Share this post


Link to post
Share on other sites
Flocking and rigid formation movement are quite different (imo).

In a rigid formation the position of each individual is governed by a master plan. There is an objective for individuals to achieve this master plan. Individuals move to accomplish this plan. An example of this is formations in military drills.

In flocking there is no objective. The position of each individual is not governed by any master plan, instead it is controlled by the behaviour of the individual. Flocking emerges as a result of the combined behaviour of all individuals. An example of this is shoals of fish flocking.

Your current strategy is looks kind of rigid formation rather than flocking. You are assigning each individual a position relative to the centre. You can simulate flocking like this, but as you are finding it is problematic.

If instead you give each individual the same rules to follow then you can achieve flock behaviour, and automatic resolution of the problem you are currently facing.

Even simple flocking can be accomplished with simple rules. For example just considering the nearest individual:

If too far away from nearest individual -> turn towards
If too close to nearest individual -> turn away
If blocked -> brake
If not blocked -> accel to max speed

That will just produce random flock movement though, there won't be any sort of overall direction. So there is the problem with that one.

Share this post


Link to post
Share on other sites
Im quite aware of the diffrence..
Though I'm using normal flocking rules, i.e avoid, align, center.. its just that instead of moving towards the flocks center, each individual moves to a offset of the center.. this creates the look of flocking, but the flock always asume their formation even if there is some kind of disturbance (lika obstacles or other)

Share this post


Link to post
Share on other sites
I'm curious and I'm having trouble visualizing the system you describe... how does your "flock" formation differ from a standard formation (visually)? What advantages does it offer over the usual method of offset pursuit (which requires less processing).?

(Do you have an executable we can see?)



Share this post


Link to post
Share on other sites
As I'm have some issues with my own version of this implementation. All I can provide is the source of my insperation.. Which can be found at:

http://www.riversoftavg.com/formation_flocking.htm

This does what I'm after, to some degre. It dont support removing a random induvidual from the flock.. If you increase/decrease the number of individuals in the flock. The others just "shift" one step left.. This makes square formations behave kind of strange. If one individual on the far left is removed, one individual of every row will move from the far left to the far right (one row closer to the front).

Share this post


Link to post
Share on other sites
I've taken a look at the demo and I don't think it provides any advantages over a simple "offset pursuit" steering behavior approach (which is less costly to implement).

Here's a link to a windows demo of offset pursuit (without collision avoidance, although that would be easy to add)

www.ai-junkie.com/files/OffsetPursuit.zip

Obviously that doesn't solve your original problem but I believe implementing offset pursuit provides a better base for adding more sophistication. (There is a good article on formations in AI Game Programming Wisdom btw. Again, if I remember correctly, it doesn't address your original problem but it's definitely worth reading).

One approach to your original question is to pre-define, for each formation type in the game, the next formation the agents should assume each time one is removed. Then, when an agent is killed you assign each new offset to the closest live agent in the old formation.

I hope that last paragraph made sense!


Share this post


Link to post
Share on other sites
Guest Anonymous Poster
If you want a "balance tree" to represent the formation positions, why not use a 'balanced tree' (like an AVL tree for example)?

botman

Share this post


Link to post
Share on other sites
With the conditions you're imposing, it's impossible to solve this problem. You're asking the computer to do guess work. I'm assuming you want to keep a formation that was carefully built by the player before the units start moving, like in some RTS games (if it was just a square formation it would be really easy). For example, if the player tried to draw a circle with the units, and one of them is lost, it's obvious that they should close the circle, but try to make a computer guess that :P I hope you got my point.

If, instead, the formation emerges automatically from some simple rules (flocking behaviour), the formation will heal itself automatically.

BTW since no one gave you an example of flocking behaviour yelding interesting visual results, here's a simple set of rules for a group of soldiers to form lines. But as with all flocking behaviour rules, you have to think a bit and visualize for it to make sense:
- Move towards the nearest soldier until you're at an appropriate distance
- Chose a direction and remember it - left or right
- Rotate around the soldier until you're by his side, depending on the side you chose (relative to the orientation of the formation; a 90º angle)
- If that's not possible (the position is taken), move along the line (in the direction you chose) until you find a soldier that has a free spot by his side; or you can chose to start a new line behind the soldier (remember that you have to play around with these rules until it works like you want)
- Face the orientation of the formation and move with it, fight, etc

I also had an idea for maintaining custom formations and, now that I think about it, it might be a mistake to post it here since everyone is going to steal it :)

When a player creates a formation, keep a small grid where each cell represents how many soldiers should be in that position. This is relative, so a cell can hold 10% of the soldiers, another 20%, etc. The soldiers will try to distribute amongst these cells as evenly as possible (this is not hard to implement), so you will always keep the initial formation even if you used the soldiers to draw a smiley face, and have nice effects like soldiers rushing to replace their fallen comrades in the left flank, etc ;)

Share this post


Link to post
Share on other sites
I thought about a recursive bubble method.

You have the average of all the positions, that's the 'center' of the formation, and you have each individual's coordenates.

When someone dies, you remove their coordenates from the average, in effect calculating a new average. Now you have an empty space, and a corrected average.

You caculate wich one of the units surrouding the hole is the one most appart from the average, and move it to the hole. Now there is another hole. You do it again, calculate wich unit surrounding that hole is more appart from the average, and move it there. And do it again and again until the coordenates of the hole created are more appart from the average then ALL of the units surrounding it.

I'm not sure about the performance on this one, and there are probably better ways of doing this, but i think this will work. =)

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
I think the solution your looking for is to have the actual positions in the formation have ranks... so if you were to define a phalanx formation in ascii it might look like:

2 1 1 1 2
3 2 2 2 3
4 4 3 4 4

Then, every time a guy dies or leaves, if there is a full position ranked lower than the one he vacated, choose the nearest lower ranked guy to move over. This could be done recursively so that an even lower ranked guy would take the moving guy's place, and so on. I am not sure this would work for all formations, but it's worth a try.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Arg.. i misformatted that last one, the formation was supposed to be in three rows of 5 guys (the 1's all in the front)

Share this post


Link to post
Share on other sites
See, I'd think this is a simple problem if you approach it in a different way. Instead of thinking about filling the hole, and getting into various permutations of which unit moves over and so on, I just defined the formation algorithmically. If the 7th unit of 20 dies, then typically the 8th moves into position 7, the 9th moves into position 8, and position 20 becomes vacant. The key then is to ensure that subsequent positions are less and less important, and that the ordering of positions leaves no gaps. This was implemented in terms of a function that takes a unit and that unit's current ranking in the formation, and returns the x,y coordinates for where that unit needs to be, given the current formation.

Share this post


Link to post
Share on other sites
Thanks for all the feedback. I feel that I need to replie to some of the suggestions given.

First, fup, Youre right, offsetpursiut is what i'm doing but i'm also incorporating flocking behaviour so that the offset is alway in relation with the flocks center.

Jotaf - Actually I was thinking of using strictly mathematical formations so that each formation is easy to maintain. Possible formation would be line, square, quadratic, triangle. These should be easy to maintain.

White Rabbit - Sound like a good approach, might try it (if I understand your idea that is =)

Kylotan - I've been thinking about this method. It creates some strange behaviour thouhg. But I think I can do a work around. Might try it later.

Ah, well... back to coding, must get this to work soon..

Share this post


Link to post
Share on other sites
The problem with Kylotan's solution is that you would end up with people potentially running across the formation to fill a slot. In fact, if you numbered the box in sequence across rows and down columns, if one person in the front row goes down, then every person on the left edge of the box now has to run over to the right side and up a row. That is why it is better to define it as a tree structure so that there is some sense of "who is most suited to fill a slot".

Share this post


Link to post
Share on other sites
if you are modelling men, a more realistic approach might have the men lined up in columns, eg

**********
**********
**********
**********
**********
**********

and if one in the front died, x representing nothing

****xxx***
**********
**********
**********
**********
**********

they would move up like so:
**********
**********
**********
**********
**********
****xxx***

then if to many died on one column,

**********
*********x
*********x
*********x
*********x
*********x

guys from the back would see, eg

**********
**********
**********
*********x
********xx
********xx

those at the back who could see might move in

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