Distributing objects on an infinite map with density decreasing with distance from the center

Question

I'm working on a game that has a procedurally generated world akin to Minecraft, but in 2D. I'm generating my terrain by using Perlin noise to determine heights and type of terrain. The advantage of this is that I can input any coordinate and get a result from it. I'd like to be able to do this for objects generated on top of this terrain as well. These objects should be more frequent towards the center of the world and less frequent as the distance from the center increases.

I'm simply not sure how to achieve this, I've found a few potential solutions but they all have their caveats. The one that might work the best would be to use Poisson Sampling with variable radii as this algorithm would also allow for proper spacing between the objects, the problem here is that it has to be generated beforehand and is not useable when going towards infinity. Another idea is to utilise a Gaussian probability density function and to increase the standard deviation with the increasing distance, what I dislike here is that the generation of objects would still be up to chance, making it hard to tweak. Lastly trying to create a circular noise could be an option as well, it would not go towards infinity, but a cutoff at some large value is also alright.

How can I tackle this kind of problem?

Answer 1

You can get some of the benefits of Poisson disc sampling with variable radii and still extend out to infinite distance by using tiling blue noise textures. (That link has both source code to generate them, and free textures you can use directly)

The examples above are set up so that each colour channel (RGBA) is an independent square of blue noise that tiles with itself. Within each channel, the pixels between 0-x% brightness form a point set with an approximately Poisson disc distribution covering the area to a density of x%.

This lets you generate placements in a way similar to using Perlin-style noise: put in a pair of x, y coordinates, multiply them by some scale factor and use a modulo to wrap the result to within the bounds of the texture, then sample the pixel they land on. If the brightness of that pixel is lower than your density value at this radius, place an item there, otherwise skip it.

You can add a pseudo-random jitter at each point (eg. generated by Perlin/simplex noise) so that the regular grid of pixels doesn't induce a regular grid in the placements.

The downside is that the texture itself is tiling, and can introduce repetition as a result. But your changing density fall-off should help with that: any two repeats of the same tile will have a different density gradient running across them, and so should still produce distinct results - at least until you get so far from the origin that the density differences between adjacent tiles are only about 1/256 or less. You can add a layer of Perlin/simplex noise to your density function so it always has some non-repeating local variation, even far from the steep part of the radial gradient.

Using larger textures can help too, and will probably be enough to drown out any noticeable repetition of patterns that fit within a screen.

But if you really need to get aperiodic placements - say you can zoom so far out that you can see the tiles no matter how large a texture you choose - then there's another trick you try: upgrade from a single repeating tile to a collection of Wang tiles. These tile the plane aperiodically, so even though a single tile may repeat multiple times, it will do so in the context of different neighbouring tiles, so the pattern as a whole is non-repeating up to the largest scales.

Check out some Shadertoy examples to get a sense of this in action. The way these shaders work is, for each point in the image plane, they find which cell of the repeating tile grid that point falls within, and pseudorandomly choose one of the Wang tiles for that cell, in a way that's guaranteed to match the edges of the tiles selected at adjacent cells without actually generating all the neighbours first (so every pixel can make this decision independently in parallel, and still agree where it matters).

Here's a paper that discusses this technique in more detail, and its accompanying presentation.

Answer 2

As you're working on a discrete grid, I thought I'd offer a simpler implementation. It's potentially quite inefficient for large radius values.

The idea is we imagine ordering the infinite plane of points by a random shuffle, and looping over each point. We only add an object at a point if there isn't already an added object sufficiently nearby. This is quite similar to rejection sampling.

We don't need literally order all infinity points, we only need check the points in the immediate vicinity would have been sorted earlier given some priority function.

def variable_radius(x, y):
  # Whatever function you like
  return log(x*x+y*y+1)

def get_priority(x, y):
  # Returns a deterministic pseudo-random unique sort key
  import hashlib
  b = repr((x, y)).encode()
  return hashlib.sha1(b).digest() + b

def is_object_at_point(x, y):
  r = variable_radius(x, y):
  priority = get_priority(x, y)
  for (x2, y2) in cells_in_circle(x, y, r):
    if deterministic_rand(x2, y2) < priority:
      return False
  return True

As this is so inefficient, you may have to resort to evaluating large blocks at a time, or using a more advanced algorithm described in other answers.