So imagine an RTS game, with ~150 units all cramped together, just staying chill. What I would like is to "space them out" so that they d form a grid. This is useful for example when a large area attack is about to happen so Player would like to minimize damage.
Naive solution is simple: find the middle of all units, calculate side of the grid (~sq root of number of units) and make it larger than current mess. For each point of the grid, find the nearest unit among "units to place" and give him order to move to that grid point. Remove that unit from total list of "units to place", proceed with next grid point. Stop when no more units to place.
Naive solution is obvious and I have implemented it, but I think there might be a less expensive solution, which would not require me to calculate distances for every point?
I am not asking for implementation, just some pointers, if any, or links to resources.