How do you generate an Infinite Voronoi diagram?

Questions & Answers
1

Hello there!

I’ve been dabbling in procedural world generation for a little while now, and I’ve gotten a decent understanding of some parts. I can create height maps, temperature and moisture maps.
It seems usually people generate biomes based on various factors, eg. temperature and moisture maps.

Now what I want to do is to generate a heightmap, then add biomes, and then modify each biome based on whatever parameters I come up with.

So… to the point - I was looking into the Voronoi diagram and implemented that. My problem is, I have a hard time understanding how I implement this for an infinite world. For a heightmap, I can simply offset it by whatever distance on the x/y axis, and all is good (And deterministic based on seed, which is important)

What I’ve gathered so far during my research is this:

When generating the Voronoi diagram for a chunk, you take the eight adjacent chunks into account. Now as I’m writing this, my understanding seems to become a bit better, but I’m still not entirely sure exactly how to do this. I guess this means, assuming chunk 1 - 9 where 5 is the center chunk; if I generate my Voronoi diagram for chunk 5, then if I do the same approach for, say chunk 4 (Left of 5), then it will seamlessly fit together with chunk 5? Is this assumption correct?

Assuming I’m correct in my sudden mid-text epiphany; I’m not really sure how to take the adjacent chunks into account when generating the Voronoi.
My current implementation looks like this:

public static Color[] GenerateVoronoidDiagram(int width, int height, int numberOfRegions)
    {
        var centroids = new Vector2Int[numberOfRegions];
        var regions = new Color[numberOfRegions];

        for (int i = 0; i < numberOfRegions; i++)
        {
            centroids *= new Vector2Int(_rand.Next(0, width), _rand.Next(0, height));*

regions = new Color((float)_rand.NextDouble(), (float)_rand.NextDouble(), (float)_rand.NextDouble());
}

var colorDiagram = new Color[width * height];
for (int y = 0; y < width; y++)
{
for (int x = 0; x < height; x++)
{
colorDiagram[y * height + x] = regions[GetClosestCentroidIndex(new Vector2Int(x, y), centroids)];
}
}

return colorDiagram;
}

private static int GetClosestCentroidIndex(Vector2Int pixelPos, Vector2Int[] centroids)
{
var smallestDstSqr = float.MaxValue;
var index = 0;
for (int i = 0; i < centroids.Length; i++)
{
var distanceSqr = (pixelPos - centroids*).sqrMagnitude;*
if (distanceSqr < smallestDstSqr)
{
smallestDstSqr = distanceSqr;
index = i;
}
}
return index;
}
What I’m struggling with is how do I take the other chunks into account?
Simply multiplying width and height with 3 (3*3=9 chunks) and multiplying numberOfRegions with 9, will just result in the exact same generation, no matter where I generate it.
Initially I thought I could simply offset the centroids by width and height multiplied by the chunks x and y coordinate respectively, but that did not give me the desired result.
Sorry for the wall of text, but wanted to include as much of the info I gathered as possible, and to clarify what I do not understand. - Any help is greatly appreciated :slight_smile:

2

Well, the only thing you need are the additional “centroids” positions around the edges of the chunk you’re generating. So for each adjacent chunk you just need to generate the centroids for those chunks as well and simply include them in your array when you do your distance calculation. Since this would effectively multiply your centroid count by 9, the GetClosestCentroidIndex becomes much more expensive. Though what you can do to optimise the distance calculation is to build a quadtree out of all the points. However this only make sense if your number of regions / centroids is kinda high.

Of course currently you generate your centroids in local space of each chunk. So of course you need to have all the centroids in the same space. So the centroids generated from the chunk left of the current chunk needs to be offset to the left. So you end up with a list of positions of all those chunks combined.

So I would recommend to outsource the generation of the centroids into a method and you just pass a List<Vector2Int> and a relative offset to it and it fills in the centroids for that chunk into that list. That way you can simply gather all the centroids necessary into one list. Currently you have your region color and the position seperate. I would recommend to combine those into a single struct so you have a single list. That makes the handling much easier.

Keep in mind that you would still just generate the same map, only for your middle chunk. So your “x” and “y” loops stay exactly the same. However having the neigboring centroids in the array / list the transition into the next chunk will be correct.

3

Hey @Bunny83

Thanks a lot for your detailed answer, this was exactly what I needed.
I’ll look into how bad the performance is after implementations, first iteration will just be to get results-then optimization :wink: Since I’m planning to use the regions as biomes on my terrain, I wouldn’t expect the region numbers to get too high, as each chunk will likely ever only contain/be part of 2-5 biomes, thus the same amount of regions.
Great tip about combining position and region color, much appreciated.

All in all, awesome feedback - Again thanks a lot for the helpful input, especially in such a timely manner :wink: