There is a finite 2D world consisting of chunks, each of which contains 16x16 tiles. The size of the world is up to 32k x 16k tiles. To generate using perling noise. The world is not generated all at once, but as the player moves. There are different biomes, each of which has a certain set of tiles. For example: tundra soil, desert sand and so on.

Sample biome map: enter image description here

And it is necessary to place objects on certain tiles (upd: trees, stones) with some minimum distance between each other, so that in certain areas specified by a special density map (upd: humidity for trees, distance to mountains for stones) , this distance could be changed. For these purposes, the Poisson Disk algorithm may well suit itself, and I even implemented it: enter image description here

However, there is a problem. For the algorithm to work, it is necessary to set the width and height of the working area, and I cannot afford to generate a poisson disk for the entire card, because it is large enough and it will take an unforgivably long time to generate. I also need to generate small pieces of the map, so that when re-generating one piece, the result does not change, and there are no noticeable seams between this piece and the rest. Is it possible to modify the Poisson Disk algorithm to solve this problem, or is it necessary to look for another option? If so, which one?

UPD: An example of what I want to achieve enter image description here

Here the points are trees. As you can see, in different places the density of trees varies. It is in this example that the density depends only on the biome. I would like to be able to introduce some element of chance, as in the example with the Poisson Disk above. That is, having in one biome glade with a small number of trees, dense forests and so on.

A source

The source algorithm is extremely inefficient, and the author himself speaks about it.

  • I may not be driving in any details, but it seems to me that there is something superfluous ... your map is a three-dimensional array of 2000x1000x16, a density map is 2000x1000x1. When an object is placed on the map (something is recorded in the world [i1] [i2] [i3] cell), the density array increases by 1 correspondingly to the density [i1] [i2] cell. It can be developed - when moving an object between tiles, one density cell decreases and the other increases - and so on. - Eugene Bartosh
  • By the way, it is convenient to store such data in game engines in the format of textures - Eugene Bartosh
  • I need this algorithm for placing trees, stones and so on in the world. For trees, the density map will be, for example, a moisture map. For stones - proximity to the mountains. I don't have an array of the whole world, instead I have a dictionary with chunks. Each chunk contains 16x16 tiles. This approach allows you to generate only part of the world near the player, which has a good effect on performance - grenqa
  • but you need to save what you generated, because just a part of the array can remain empty for the time being - in the array it’s just much more convenient to address. and the density limit map can be generated 1 time during the first start of the game, for example - Eugene Bartosh
  • I wrote something like three months ago. I will look at source codes, I will try to describe to you how approximately I did there. Only tell me the approximate size of the chunk, the minimum area that you generate at a time. - selya

1 answer 1

A few months ago I was implementing something similar for one of my toys. The screenshot shows the orange dots of trees:

map

They are arranged with different densities. The algorithm itself has complexity commensurate with the number of trees generated. I do not know whether this method will suit you or not, since trees are generated for each chunk separately ( per-chunk ).

A small preface. In my algorithm, I generated different structures in different ways, but as for the landscape and trees, they were generated for each chunk separately.

Each chunk had its own seed , according to which this chunk was generated. I took the Sid from the noise of the pearl according to the coordinates of the chunk, for example: seed = getPerlin(chunkX, chunkY) . Next, using this seed, I generated all the structures on the chunk.

And now to the trees. To begin, I chose an algorithm that can pseudo-randomly arrange trees. The choice fell on the halton sequence . Everything is simple:

 getHalton(index, base) { var result = 0; var f = 1 / base; var i = index; while(i > 0) { result = result + f * (i % base); i = Math.floor(i / base); f = f / base; } return result; }

index is the number in the sequence, base is the base. In order to arrange the points in two-dimensional space, I used the bases 2 and 3 . Something like this:

 var x = getHalton(index, 2) * chunkSize; var y = getHalton(index, 3) * chunkSize;

Here chunkSize is the size of the chunk (because the getHalton values getHalton in the interval [0, 1] ). In order to receive, depending on the sid, different variations of the arrangement of trees, I introduced the variable indexShift . This is just an integer generated by a seed . And we just add it to index 'y.

For clarity, we introduce a certain function setTree(x, y) , which will set the trees at the point of the chunk in which we need. Then the generation of trees will look like this:

 for (var i = 0; i < treesCount; ++i) { var x = getHalton(i + indexShift, 2) * chunkSize; var y = getHalton(i + indexShift, 3) * chunkSize; setTree(x, y); }

Good. Now we have pseudo-randomly arranged trees. But this is not enough for us, right?

And then the same pearl noise comes to the rescue. Since I used noise in my project, which returned values ​​in the range [-1, 1] , and I wanted to get values ​​between [0, 1] , I took the value like this:

 var value = getPerlin(x * noiseScale, y * noiseScale) * 0.5 + 0.5;

The variable noiseScale used to adjust the noise scale. Well, now we have a value in the range [0; 1] [0; 1] . But how will this help us? And let's modify the code for generating trees like this !:

 for (var i = 0; i < treesCount; ++i) { var x = getHalton(i + indexShift, 2) * chunkSize; var y = getHalton(i + indexShift, 3) * chunkSize; var densityInPoint = getPerlin(x * noiseScale, y * noiseScale) * 0.5 + 0.5; if (i < treesCount * densityInPoint) setTree(x, y); }

Thus, we sift out some of the trees in places where the noise of the pearl is low.

So, what we have: some algorithm. The result of his work depends on three variables:

  1. treesCount - the more, the greater the overall density of the trees.
  2. noiseScale - the more, the faster the density changes per unit of distance (the less homogeneous the density).
  3. densityInPoint - different values ​​give a generally different result.

PS: by the way, it seemed to me that the linear densityInPoint value gives not a very good result, so I additionally squared it.

PPS: different density of trees in different biomes is visible on the map. For this result, I just set different treesCount values ​​for each biome.

PPPS: if your trees are set in a matrix, then the x and y values ​​must be integer. Then just take the whole part of them:

 setTree(Math.floor(x), Math.floor(y));

PPPPS: I'm not saying that this solution is the best and most correct. However, it is much faster than the method you found in the article, and for me it gave acceptable results.

  • Thanks for the answer! This seems to be what I need. How to test - accomplish your goal - grenqa