Hey guys,

I'm working on an RTS and trying to find a fast way to let a group of up to 256 units change formation. Units new positions should be assigned in a smart way to avoid units bumping into eachother and large discrepancies between the marching distances of every single unit. To illustrate this I made a small graphic with 3 different cases.

[attachment=26858:g4819.png]

The top row shows the desired formations while the bottom row shows the current ones. In the first case the units simply take the new positions in the order they are stored in their container. This is of course the fastest way but also very impracticle as units in large numbers get into eachothers way and occupy near positions that other units with higher marching distances should be taking.

The second and third case show the desired results.

I found a way to solve this problem. However I'm worried that it is too slow. I can't think of a better way, though. This is basically what I'm doing:

1. calculate new positions depending on group destination and formation

2. calculate the distance between every unit and every position

3. save the positions in descending order of the distance for every unit

4. grant the unit with the highest minimum distance the choice of its preferred position

5. remove the now occupied position from the choice pool of the remaining units and repeat 4. until all units are assigned a new position

It's step 2 and especially step 5 that take the most time. The time increases exponentially with the unit number. For 128 units it takes 0ms in release mode and 200ms in debug mode of VS C++. With 256 units it already takes about 30ms in release mode and over 1 whole second in debug mode.

Now the results aren't that bad in release mode but of course this is only for one group and in the game there might be several groups that need reassignment at once. I can go with this solution but of course would like a better one. Do you have any ideas?

1. Seems, instead of calculating path for each agent to each point of destination formation you can calculate path for each agent to the centroid of a destination formation. This solution is approximate and when distance between source and destination points is small (it depends on group size) you have to use some other approach.

2. Split group into subgroups and use your algorithm for subgroups. Individual units inside subgroup then may take any position available to its subgroup.

3. Make main algorithm async and move group to closest point/centroid while waiting for main algorithm results

4. Instead of solving the problem at once for a whole group, treat each unit in a group as an agent with a set of rules which it constantly follows. For example, agents dont immediately stop when they reach nodes, instead they analyze closest environment: if there are empty nodes ahead and alof of agents behind them - they continue to move forward.

Or you can move agent to the closest point. Other agents arriving later may "ask" to move an agent a little bit further (in direction of a free space).

Thank you very much for your answer.

I think I'll try the first and the second approach first. Splitting into subgroups should probably be enough as anything under 100 units gets calculated very fast. If I use the first approach on each subgroup it would even be more accurate than using it on the whole group.

I don't think the fourth approach would work very well in my game but the first three should suffice anyway. Thanks for your help. I'll report back as soon as I get it done.