A short story on solving fair random distribution without complicated math.
I’m working on a little multi-player 4X space game, think MOO2. There is a galaxy with stars. Each player (AI or human) starts on a home world; each in another solar system.
For fairness all home worlds should be surrounded by about the same number of other stars in about the same average distance. Also the home worlds should be distributed in the galaxy so that the closest distance between two of them is as large as we can make it so players get to develop before they are confronted with potential enemies.
The galaxy should look “natural” and random: No arrangement of stars in uniform shapes or groups. Takes fun out of the game.
?
First the galaxy is divided into a grid of rectangular cells of equal size. The number of grid rows and columns (and thereby the number and size of the cells) are a function of the player count and the galaxy size so that we get some more cells than players. Division, multiplication and rounding get you there.
For each player pick a random cell from remaining set and remove it from that set.
The picked cell’s rectangular area is filled: Pick a random point within the cell. Check that is has at least a certain minimum distance to all points (stars in galaxy) picked so far (green). Otherwise (red) pick another point until the minimum number of stars close to each player is reached for that cell.
The home world is the point of the cell that is closest to the center of the cell (cyan). Pick next cell until there is a filled cell for each player. Some might still be empty.
Finally add some additional random points/stars within the bounds of the whole galaxy that still have the quality of not being to close to any of the points/stars picked before.
We are done. Only math required is basic arithmetic and distance between two points in a 2D plane.
The result is a natural looking galaxy where home worlds are distributed in no particular shape but still each home world has about the same quality. The grid made sure the home worlds are not to close to each other. The computational complexity is linear with the number of players. By sizing cells appropriate it can be made sure there is enough space for the number of random points we want to place in each cell without failing too often.
Also the algorithm naturally allows for the kind of parameters we want to have:
How the grid is divided can easily be tweaked to these parameters.
While the problem looks for a combination of minima and maxima this simple approximation solves it with very little math, code and complexity.