1
\$\begingroup\$

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?

\$\endgroup\$
4
  • \$\begingroup\$ I think the big question here is how to use probability in procedural generation. I recommend randomizing with the coordinates of the smallest loading unit (chunk) as the random seed, which will give a fixed result. \$\endgroup\$
    – Mangata
    Feb 18, 2023 at 15:58
  • 1
    \$\begingroup\$ What kind of falloff rates are you looking for: Log, Linear, Sinusoidal (quarter circle)? Do you want to allow distant islands with higher local densities (gives variation if sparsely applied)? \$\endgroup\$
    – user122973
    Feb 18, 2023 at 23:00
  • \$\begingroup\$ @Strom Something akin to Log or Linear the fall-off rate would never cause the density to increase again, it would always go down with distance. \$\endgroup\$ Feb 19, 2023 at 12:24
  • \$\begingroup\$ Lots of great answers here! I would like to add a more holistic note that spawn/origin bias is a design factor I like to either commit hard to, or leave out entirely. Either the player should expect similar options no matter how far they travel to set up base, or they should be immersed in gameplay deeply molded around spawn distance. In-betweens can be a bit awkward (see: Minecraft Java Stronghold placement vs. everything else). It's trickier, too, with "infinite" worlds, because at some point someone might ask why such a large world should have such a small relevant center. \$\endgroup\$
    – KdotJPG
    Feb 23, 2023 at 2:11

2 Answers 2

4
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ Ah, I was always under the impression that I would have to generate some circular noise map to make this work, but technically its a square noise map with a fall-off where I adjust the brightness threshold depending on the distance of the input point from the center correct? Cause the same can be done with any noise, but blue noise in addition has the properties of Poisson disc sampling? As when I look for more sources on how to generate blue noise textures, I always end up at Poisson disc sampling but the former is not the same as blue noise correct, but can be used to generate them? \$\endgroup\$ Feb 19, 2023 at 12:10
  • 1
    \$\begingroup\$ Yes, you can tile a square or rectangular image then apply a radial gradient as your threshold. "Blue" is a description of noise that has variation at small scales but is uniform at large scales, and Poisson disc sampling is one way to get a point set with that property. But not every greyscale image with a blue noise property can be thresholded to get a Poisson-like point distribution at various densities — the images linked above are specifically designed for that. \$\endgroup\$
    – DMGregory
    Feb 19, 2023 at 13:11
2
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ Thanks for adding this! I'm not fluent in Python, but should x and y appear in the inputs to either repr() or sha1()? \$\endgroup\$
    – DMGregory
    Feb 18, 2023 at 23:04

You must log in to answer this question.

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