Random map generation - strategies for scattering/clustering random nodes

Question

I am doing a simple 4X strategy game in space where each node is a point-of-interest (a planet, an asteroid and etc.).

To randomly generate a map, I would follow the steps below

1. Decide how many type of each nodes the map will have (perhaps, say, 5 Earth-like planets, 10 barren planets etc.)

2. Place each type of node on the map.

For step 2 I would like to have an even spread of each node type. So for example, I would start by placing all the earth-like planets. If I simply do a rand(map.width, map.height) to determine the position, I may end up all the earth-like planets clustering together, which will give advantage to the player who starts in that area.

Are there any methods, such as using different graph functions or noise function, which could generate a sequence of (x,y) coordinates which are spread out from each other. Likewise, are there any ways to generates coordinates which are close to each other?

Answer 1

The problem you're facing is that random selection doesn't discriminate, and that can mean that it's a less-than-ideal fit for what you need to do. But, there is at least one easy way to work around this:

1. Split up your space into sectors (e.g., if you have an area of 100 by 100, and you need to generate 100 of these solar systems, then split your area into a 10 by 10 grid of sectors)

2. Loop through each Sector and repeat step 3 (which will, in turn, repeat step 4 multiple times)

3. Randomly determine the number of planets for the current solar system (e.g., for a range of 3 to 7 planets, just acquire a random number ranging from 0 to 4, and add 3) in the current Sector (if you have more than one solar system in a sector, this is where you'd set up another loop)

4. Randomly assign your planets within the current Solar System identified by your loop (you can also use random numbers to increase the minimum distances between the planets); this is where you'd decide the types of planets, which could also be randomly determined with a variety of weights or whatever method you prefer to use

You may also wish to define an "out of bounds" area around the edge of each sector to prevent planets from neighbouring sectors from making direct contact with each other (just in case they were effectively randomly located side-by-side), or...

Another solution could be at the point of deciding the location of each solar system and/or each planet, to just run a quick proximity check against neighbouring sectors and adjust accordingly (e.g., move away from the edge by a minimum distance plus a random distance).

Answer 2

The best way to ensure even distribution is to treat each node as a sort of physical particle. First do a random distribution across a continous (floating point) xy plane. By applying forces of repulsion between each distinct pair of individual particles on the plane, you'll find they slowly spread apart. In a sense it's like collision resolution, only there is no actual contact to speak of. It's then a simple matter to convert that plane ("rasterize" it) back into an integer-indexed grid. You can simply do this from a integer-indexed grid to start with, but it might be a little more difficult to get things "nice" -- this depends on how high the resolution of your grid is... the higher, the better, in this case.

Obviously you may want to apply some sort of forces from the edges of the square plane as well, or else you may find a lot of particles "washing up on the shores". Alternatively you can create a field much larger than you need, then take a snapshot of a small area of that -- this avoids the aforementioned problem.

When you want to ensure the opposite, i.e. that clustering does occur, then look into "standard" or "gaussian" distribution. This is why randomly generated starfields often look fake; they use pure random distribution rather than a more naturalistic distribution model.

Answer 3

You can use a simple Poisson-disk distribution algorithm to get a "blue noise" distribution. This results in points in the plane which are roughly spaced equally apart from each other. This works not only in your 2D example but in 3D as well, and also in non-Euclidean spaces, but the calculations can quickly become unwieldy.

The basic idea of those algorithms is that you start with a first "seed" point, then work yourself outwards adding random or pseudo-random points in the annulus between the max and min distances you'd like to have from the point onward and eliminate those which lie too near to each other. Your algorithm then works outwards in such a manner, until either the amount of points needed is added (which gives you a roughly circular point cloud), or the space available is filled.

A fast and elegant alternative algorithm for generation of 2D such noise, as well as a short discussion of the properties thereof, can be found in "A Spatial Data Structure for Fast Poisson-Disk Sample Generation" by Daniel Dunbar and Greg Humphreys of the University of Virginia.