AAGRINDER terrain generation (technical) - Revision history

Maze: /* Generating an infinite world */ update with new information from today's update

2024-05-25T17:49:58Z

Generating an infinite world: update with new information from today's update

Maze: /* Generating an infinite world */ added description of old generator, and improved wording

2024-05-16T07:40:10Z

Generating an infinite world: added description of old generator, and improved wording

imported>Maze: Maze moved page AAGRINDER terrain generation (deep) to AAGRINDER terrain generation (technical): more understandable name

2019-11-14T23:04:57Z

Maze moved page AAGRINDER terrain generation (deep) to AAGRINDER terrain generation (technical): more understandable name

imported>Maze: /* Prerequisites */

2019-10-27T23:16:55Z

Prerequisites

86.58.42.133: /* Generating an infinite world */

2019-10-14T13:53:23Z

Generating an infinite world

86.58.42.133: /* Stone generation */

2019-10-14T13:52:37Z

Stone generation

164.8.160.229: /* Generating an infinite world */

2019-10-14T11:12:33Z

Generating an infinite world

164.8.163.165 at 11:05, 14 October 2019

2019-10-14T11:05:20Z

164.8.163.165: /* Stone generation */

2019-10-14T10:31:39Z

Stone generation

imported>Maze at 07:26, 13 October 2019

2019-10-13T07:26:53Z

@@ Line 14: / Line 14: @@
 Unfortunately, it's not that simple. We don't want the final product to look exactly like Perlin noise, and we also want to add additional features to the terrain, such as trees. These features can be bigger than 1 block and can stretch from one chunk into another. Because of this, we need to generate some additional area around the current chunk, just to see if there are any trees there and if they maybe stretch into the space of the chunk we're supposed to generate. The amount of the extra generated edge around the chunk should be the same as the size of the largest possible tree.
-Unfortunately, it's not that simple. Trees can interact with each other, prevent each other from growing depending on which ones of them grow first, so you might get a chain of strange events which brings changes all the way from the edge of the generated area into the actual chunk. And suddenly, there's inconsistency at the border. By increasing the size of the extra generated edge, you can make this less likely, but before you know it, that extra edge is bigger than the chunk itself, and you are spending most of the precious processor time generating this imaginary terrain which is then thrown away. The true solution, which is also used in Minecraft, would be to generate only the ground, and call it an ''unpopulated chunk''. Then, once the surrounding chunks have also been generated as unpopulated chunks, the chunk in question would be sent back to the generator, this time with all the information about the surrounding chunks. Trees can be added reliably in this step, along with structures and other bigger features.
+Unfortunately, it's not that simple. Trees can interact with each other, prevent each other from growing depending on which ones of them grow first, so you might get a chain of strange events which brings changes all the way from the edge of the generated area into the actual chunk. And suddenly, there's inconsistency at the border. By increasing the size of the extra generated edge, you can make this less likely, but before you know it, that extra edge is bigger than the chunk itself, and you are spending most of the precious processor time generating this imaginary terrain which is then thrown away. The true solution, which is implemented in AAGRINDER as of 25th May 2024, is to first pre-generate only the ground / general shape, before adding any larger decorations. This information is then shared between the different chunks while they are being finalized. This way, we can mostly avoid generating duplicate terrain around each chunk. Ideally, the in-between results would be cached for future use, so they never need to be re-generated. But this is not implemented yet.
 AAGRINDER does not use the concept of unpopulated chunks. Instead, I do actually generate a very large border around the chunk. I hope the admins and the players won't mind if it takes 1 second to generate a chunk instead of 0.2. The server and the terrain generator are different programs in different languages, so caching intermediate results would be particularly difficult.

@@ Line 7: / Line 7: @@
 In AAGRINDER, I wanted the world to be generated in smaller sections (called ''chunks''), while it is explored. This way, one can keep exploring as far as they want, and it will always be possible to generate more terrain. At the same time, I wanted the world to be predetermined by the world seed. This means that even though we are allowing the player to explore chunks in any order, the resulting terrain must be identical regardless of the exploration order. Because of this, the world generator must be a program which generates a chunk at specific coordinates, without knowing which surrounding chunks already exist and what is in those surrounding chunks.
-I also wanted the borders of chunks to always match up nicely with surrounding chunks, which makes the world look continuous and consistent. There are two ways of achieving that: the boring way, and the awesome way.
+I also wanted the borders of chunks to always match up nicely with surrounding chunks, which makes the world look continuous and consistent. There are a few ways of achieving continuous world generation.
 * The boring way of making chunk borders match is to make all chunk borders the same. So make them either all full of stone or all full of air. The world would look like a giant grid, it would be very obvious where the chunk borders are.
-* The better way of achieving matching chunk borders is by sampling noise. Here, noise is some mathematical function with which we can calculate a value for any specific position in the world. We of course know the world coordinates of each block in the chunk. The generated world will then reflect the qualities of the noise function that was used. We would use a type of coherent noise, such as [[wikipedia:perlin noise|Perlin noise]], to get interesting shapes. With that, matching chunk borders are guaranteed.
+* A better alternative with better results is to generate floating islands which are randomly placed into the world. This can be done consistently and locally, even when the island appears on the chunk border. Sometimes two or more generated islands may overlap, in which case we can either drop all of them, or assign them deterministic priorities to decide which one will stay. This is how AAGRINDER worked back in 2018, but not any more.
-Unfortunately, it's not that simple. We don't want the final product to look exactly like Perlin noise, and we also want to add additional features to the terrain, such as trees. These features can be bigger than 1 block and can stretch from one chunk into another. Because of this, we need to generate an additional area around the current chunk, just to see if there are any trees there and if they maybe stretch into the space of the chunk we're supposed to generate. The amount of the extra generated edge around the chunk should be the same as the size of the largest possible tree.
+Unfortunately, it's not that simple. We don't want the final product to look exactly like Perlin noise, and we also want to add additional features to the terrain, such as trees. These features can be bigger than 1 block and can stretch from one chunk into another. Because of this, we need to generate some additional area around the current chunk, just to see if there are any trees there and if they maybe stretch into the space of the chunk we're supposed to generate. The amount of the extra generated edge around the chunk should be the same as the size of the largest possible tree.
 Unfortunately, it's not that simple. Trees can interact with each other, prevent each other from growing depending on which ones of them grow first, so you might get a chain of strange events which brings changes all the way from the edge of the generated area into the actual chunk. And suddenly, there's inconsistency at the border. By increasing the size of the extra generated edge, you can make this less likely, but before you know it, that extra edge is bigger than the chunk itself, and you are spending most of the precious processor time generating this imaginary terrain which is then thrown away. The true solution, which is also used in Minecraft, would be to generate only the ground, and call it an ''unpopulated chunk''. Then, once the surrounding chunks have also been generated as unpopulated chunks, the chunk in question would be sent back to the generator, this time with all the information about the surrounding chunks. Trees can be added reliably in this step, along with structures and other bigger features.
-AAGRINDER does not use the concept of unpopulated chunks. Instead, I do actually generate a very large border around the chunk. I hope the admins and the players won't mind if it takes 1 second to generate a chunk instead of 0.2. The server and the terrain generator are different programs in different languages, so generating in multiple passes would be particularly difficult.
+AAGRINDER does not use the concept of unpopulated chunks. Instead, I do actually generate a very large border around the chunk. I hope the admins and the players won't mind if it takes 1 second to generate a chunk instead of 0.2. The server and the terrain generator are different programs in different languages, so caching intermediate results would be particularly difficult.
 == Stone generation ==

@@ Line 2: / Line 2: @@
 == Prerequisites ==
-Before reading this page, you should have a basic understanding of [[wikipedia:Pseudorandomness|pseudo-random number generation]], [[wikipedia:perlin noise|Perlin noise]], [[wikipedia:cellular automata|cellular automata]] and [[wikipedia:fractal fractals]].
+Before reading this page, you should have a basic understanding of [[wikipedia:Pseudorandomness|pseudo-random number generation]], [[wikipedia:perlin noise|Perlin noise]], [[wikipedia:cellular automata|cellular automata]] and [[wikipedia:fractal|fractals]].
 == Generating an infinite world ==

@@ Line 5: / Line 5: @@
 == Generating an infinite world ==
-In AAGRINDER, I wanted the world to be generated in smaller sections called chunks, while it is explored. This way, one can keep exploring as far as they want, and it will always be possible to generate more terrain. At the same time, I wanted the world to be predetermined by the world seed. This means that even though we are allowing the player to explore chunks in any order, the resulting terrain must be identical regardless of the exploration order. Because of this, the world generator must be a program which generates a chunk at specific coordinates, without knowing which surrounding chunks already exist and what is in those surrounding chunks.
+In AAGRINDER, I wanted the world to be generated in smaller sections (called ''chunks''), while it is explored. This way, one can keep exploring as far as they want, and it will always be possible to generate more terrain. At the same time, I wanted the world to be predetermined by the world seed. This means that even though we are allowing the player to explore chunks in any order, the resulting terrain must be identical regardless of the exploration order. Because of this, the world generator must be a program which generates a chunk at specific coordinates, without knowing which surrounding chunks already exist and what is in those surrounding chunks.
 I also wanted the borders of chunks to always match up nicely with surrounding chunks, which makes the world look continuous and consistent. There are two ways of achieving that: the boring way, and the awesome way.

@@ Line 18: / Line 18: @@
 == Stone generation ==
-Stone generation is the first part in world generation and the most important part for giving the AAGRINDER world its shape, as everything else depends on where stone was placed. Stone is generated as a fractal-like
+Stone generation is the first part in world generation and the most important part for giving the AAGRINDER world its shape, as everything else depends on where stone was placed. Stone is generated as a 3-level fractal-like structure. Although calling it a fractal is not mathematically correct, because the third level is generated differently than the first two.
 == Water generation ==

← Older revision	Revision as of 23:04, 14 November 2019
(No difference)

← Older revision		Revision as of 10:31, 14 October 2019
Line 5:		Line 5:

	== Stone generation ==		== Stone generation ==
		+	Stone generation is the first part in world generation and the most important part for giving the AAGRINDER world its shape, as everything else depends on where stone was placed.

	== Water generation ==		== Water generation ==

← Older revision		Revision as of 07:26, 13 October 2019
Line 1:		Line 1:
−	This page describes some of the details of the workings of the [https://gitlab.com/MRAAGH/aagrinder-terrain AAGRINDER terrain generator].	+	This page describes some of the details of the workings of the [https://gitlab.com/MRAAGH/aagrinder-terrain AAGRINDER terrain generator]. For a simpler explanation, see [[Terrain generation]].

	== Prerequisites ==		== Prerequisites ==