AAGRINDER terrain generation (technical)

This page describes some of the details of the workings of the AAGRINDER terrain generator. For a simpler explanation, see Terrain generation.

Prerequisites

Before reading this page, you should have a basic understanding of pseudo-random number generation, Perlin noise, cellular automata and wikipedia:fractal fractals.

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.

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.

• 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 Perlin noise, to get interesting shapes. With that, matching chunk borders are guaranteed.

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. 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.

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 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

(mention flat top & bottom and draining)

Coral generation

(mention colors)

Grass

(mention grass biomes)

Trees

(with link to a separate page for more details)