Hi, I finished my Pathfinding algo in a Isometric World, a player finds the nearest way to a given point. So now it would be great to implement group movement, i read a article on gamasutra but didnt think it's what im looking for. Whats the easiest way to implement group movement, there are these Steering behaviours but i just want to move a formation of figures over the world. Does each figure has to find its own Path or should the group find its path? If I have to find the path only once what bindings do i use, of the biggest figure and if theres not enough place for the formation theres a ranking who goes first and the other wait? Maybe someone knows a Link or any tips hope someone can help me. broom

This is something I have thought about recently too.
I'm sure there are other/better ways of doing it, but here are a couple techniques I've seen and/or attempted.

I assume your game is an rts, or something similar...

1. When moving a group of units, put them all into a Group, and assign a Leader. Find the path for the Leader, then have all the other units follow their Leader. I implemented a simple 'Move in formation' technique, where all followers try to stay at a certain position relative to their leader. Doing this allows for a 3x3, 4x4, 1,2,3 pyramid, etc formations. If a follower hits an obstruction, get around it, and either have them play catch up, or tell the group to wait for that unit to get back in position.
Things to take into consideration are how to handle things like bottle necks, or an obstruction that splits the group.
In some situations the formation may not be viable, and a single file line would be needed...

2. I haven't tried this method, but it seems like a logical way to do it. Put the units into a Group, and determine the size of that group (height and width). Make an abstract Rectangle from these dimensions, and modify your pathfinding algo to take this rectangle and find a path for it. Like I said I haven't tried this, so not sure if its a viable way.

Not sure if this is helpful, or close to what you need, but it might give you a few ideas.

Geo

I just finished group movement with option 1. above. It works.

The way I did it, only the leader makes path requests. Every time the leader reaches a waypoint in the path, he assigns new waypoints to the followers. So each follower only knows his immediate waypoint. He moves directly towards it without requesting a path. Only if he is blocked, does he request a path. I don't have collisions between entities, which simplifies things.
The assigned waypoints are the relative formation positions, rotated by the leader's heading. If there is no room at the spot where a waypoint should have been, you can assign the closest one via a limited A* search from the leader's waypoint. "AI Wisdom 4" explains all this.

In my implementation, there is some relatively complicated messaging logic going on to get the group to wait for stragglers and so on. I have had plenty of deadlock bugs to iron out, where the group members were waiting for each other.

You might want to check Coordinated Unit Movement and the follow-up Implementing Coordinated Movement .

Yeah... option 1 is the standard way of approaching this. Path a leader (real or virtual) and run everyone else on offsets. You can either do this loose (i.e. a general grouping) or rigid (i.e. formations).

Hi,

I'll implement that Option 1.

But i want to have group collision, so the followers follow the leader and if they collide with a movable object, they just wait and try to follow their waypoint later?

Thank you
broom

You can certainly overlay local steering behaviors onto the follower's movements as well. That is, treat them just as if they are a normal entity doing some pathfinding (like the leader). Allow them to move around obstacles in their desire to get to the (moving) goal.

A lovely method I've seen for solving this problem involves building corridors annotated with clearance values. The group moves within the corridor and maintains coherence through the use of potential fields (so the units don't bump into each other). To keep the group together, there is a maximum veritcal and horizontal dispersion, a sliding window of sorts inside which the units always have to remain.

It's pretty cool because your groups always stay together, they can avoid dynamic obstacles along the way (each group is effectively a single "unit" with a deformable shape). The solution does require more work than the simple method presented earlier in this thread (you need to create a roadmap and a system for local planning) but it appears pretty robust.

Anyway, I'm probably doing a poor job describing it. Read the paper for yourself.

Hi,
The thing done in a group is really effecting. The group can do many things which the alone person can't even think of.


Joe

Simplest is single file lockstep movement with pathfinding only by the leader.
(assuming you dont have dynamic scenery that might invalidate the path for the followers).

Each object follows the path were they are spaced out (maybe tiny pathfind to get them 'into line'.. to 'fall in' to the initial line ordering) all movement is at the same rate so there would be no collisions.

If the line isnt too long (object count low) it can look reasonable but funny if too long (conga line).


On roads its very natural.

Variations would be two/thre/many abreast. Depending on your terrain system and object sizing scheme you may have to do the 'fit between things' processing anyway and the formation would just be a fixed width spacing.