How can I create procedurally placed points in an infinite world?

Question

My issue is that I need to create consistently placed points in an open world. This means that optimally, I would have some function that takes an area as an input and outputs all the points that exist in that area. It would also be great if it was possible to specify the minimum distance between points.

Something like the following would be great:

What is a good way to achieve this?

Answer 1

I don't have a complete answer for you but I have some things that may be useful.

Blue noise produces points that are "evenly spread" with some distance between them.

Typically an algorithm such as Poisson Disc will generate a set of blue noise points that have a given spacing. However, you want a varying spacing. For this you can use a blue noise algorithm that gives you a number (such as 0-255) at each pixel location. When that number is in a certain range, you place an object there. If your range is small (e.g. 0-1) you will get points with large spacing; if the range is large (e.g. 0-20) you will get points with small spacing. This technique is used for dithering images. The best article I've found for this is Christoph's precomputed blue noise, which includes downloadable textures with the output of the "void and cluster" algorithm.

Variants: 1 - if you need to place different kinds of objects with different spacing, and have them respect each others' positions, see multi-class poisson disk sampling; 2 - if you need to vary the density as you zoom in, see recursive wang tiles (video is cool!). Also worth a read: Casey Muratori's blog post The Nebraska Problem.

I don't have a complete answer for you, especially for an infinite world, but keywords blue noise, dithering, and poisson disc may help you find papers/algorithms for this.

Answer 2

What you want to do is take advantage of the fact that a pseudo-random number generator that uses a seed will reproduce the same "random" set of numbers every time. You can read a bit about them at https://en.wikipedia.org/wiki/Random_seed

Given an area for input, find a way to create a seed from that area's information that gives you a unique seed for each area. It might be based on the area's coordinate for example.

Given a seed, when you want to generate your procedural points for the area you set the seed, and create your set of point coordinates from a sequence of random numbers made from the seed.

The only thing to be careful with is that you must use the random generator to generate your sequence the same time every time to ensure repeatability.

A nice twist of this is that you can have a "master seed" for your world that is used to generate each area seed. So given a "master seed", you can recreate an entire unique world in a reproduce-able way. I assume this is how Minecraft works with world seeds.

I just saw the image you uploaded, which sort of clarifies a few things. My answer isn't necessarily answering exactly how you will generate those points, but how you will ensure that procedurally generated points will be reproduceable every time you need to generate them.

Answer 3

I managed to get a solution with the following function:

    public List<Vector3> GetPoints(Vector2Int center, Vector2Int size)
    {
        List<Vector3> points = new List<Vector3>();

        float probabilityScale = 0.2f;
        int gridDist = 150;
        string seed = "a";
        float noiseScale = 4000f;

        Vector2Int topLeft = center - new Vector2Int(size.x / 2, size.y / 2);
        Vector2Int topLeftGridAligned = new Vector2Int(topLeft.x - topLeft.x % gridDist, topLeft.y - topLeft.y % gridDist);

        for (int x = 0; x < size.x; x+= gridDist)
        {
            for (int y = 0; y < size.y; y+= gridDist)
            {
                Vector2 samplePoint = topLeftGridAligned + new Vector2Int(x, y);

                System.Random random = new System.Random((seed + samplePoint.x.ToString() + ":" + samplePoint.y.ToString()).GetHashCode());
                float noiseVal = Mathf.PerlinNoise(samplePoint.x/noiseScale, samplePoint.y/noiseScale);
                float randomNum = (float)random.NextDouble();
                if (randomNum < noiseVal * probabiltyScale)
                {                    
                    points.Add(new Vector3(samplePoint.x, 0, samplePoint.y));
                }                
            }            
        }
        return points;
    }

Notice that I am using the UnityEngine library containing the Vector2Int, Vector3 and Mathf classes. It works even when the center vector is moved around, consistently returning a location to either have a point or not have one.

In the future I will be adding jitter to the noise so it doesn't look as grid-aligned.