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.
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?
Edited by Hannibal2400, Yesterday, 05:20 AM.