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.

  • \$\begingroup\$ What if the grid pushes an unit into the enemy range? \$\endgroup\$ Jun 30, 2021 at 15:47
  • \$\begingroup\$ @ShadowsInRain doesn't matter \$\endgroup\$
    – dgan
    Jun 30, 2021 at 18:42
  • 1
    \$\begingroup\$ "calculate distances for every point" - sounds like something CPU would do in nanoseconds. Are you sure performance is your problem? As for assigning items to positions - look up the Hungarian algorithm - it may come in handy. \$\endgroup\$
    – Kromster
    Oct 3, 2021 at 18:09
  • \$\begingroup\$ thanks @Kromster, never heard about that! looks indeed interesting \$\endgroup\$
    – dgan
    Oct 3, 2021 at 18:33

1 Answer 1


This is useful for example when a large area attack is about to happen so Player would like to minimize damage.

Sounds like you're thinking of giving the player the option to specify formations, so other spacing options (like boids) won't work.

I have two ideas for you.

Manhattan distance from origin

What you have sounds good, but you could also try a less-precise method of placing the units that only finds distances relative to one point:

  1. determine the bounds of the grid
  2. sort a list of the units by their distance from the top left of the grid (the grid origin)
  3. pop off units from the list and assign them to grid spaces that get gradually farther from the grid origin (instead of iterating row by row, you iterate by an L shape)

Truncate position to int

Another method to find grid candidates would be to truncate the unit's floating point position into an integer grid position: take grid, rotate to align to world axes, translate into world coordinate space, round values of unit positions into grid cell buckets and subtract the grid offset. Some cells may have multiple units, but you can resolve that by tracking the grid occupancy (as a 2d array of bool or unit pointers) and looking in nearby cells instead of doing more distance comparisons.

  • \$\begingroup\$ ha! Thanks for Manhattan distance idea. I ll give it a try! \$\endgroup\$
    – dgan
    Jul 22, 2021 at 17:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .