Replicating Minecraft World Generation in Python | by Bilal Himite | Nov, 2021

Written by Marechal Laurent - 01 december 2021

Classified in : Links, Python - Tags : none

Site d'origine : https://towardsdatascience.com/replicating-minecraft-world-generation-in-python-1b491bc9b9a4

Minecraft, the best-selling game of all time, best known for its pixelated building blocks and infinite worlds, has an amazing procedurally generated terrain with caves, waters, and even different biomes.

Procedural generation is an important part of computer graphics. It is used mostly in video games or in movies. It helps generate random structures that do not have a “machine-like” feeling to them.

Similarly, procedural generation plays an important role in machine learning. It can help generate data that is hard to collect. Training machine learning models requires huge datasets that can be difficult and costly to gather and process. Generating data procedurally can be easily adapted to the exact type of data needed.

I used to play Minecraft as a kid and I always wondered how does it generate never-ending worlds. In this article, I am going to try to replicate this in Python.

We first have to define how our world will be generated.

  • The world is 3-dimensional, discrete (comprised of blocks of unit size), bounded in the z-axis by 0 and 255, and unbounded is the x and y-axis.
  • The world contains biomes, each spanning large horizontal areas, that define the nature of the space that the biome occupies.
  • The world contains rivers, lakes, and oceans.

Every world is defined by a seed. The same seed will always generate the same world.

A chunk. Image by Author.

To make the generation process easy, we will divide our world into chunks. Every chunk will occupy a space of 1024×1024×256 blocks.

Every chunk is generated separately. This will help us save, load the world, and generate more parts of the world easily.

The first thing we have to do is divide our world into cells on the x and y-axis, each of a certain biome. We will assign to every cell a point representing its center.

Voronoi Diagram

A Voronoi diagram will help us divide our world into cells given a set of points. The main idea behind Voronoi diagrams is that the cell a point belongs to is the cell whose center is the closest.

The moving point is colored by the color of the closest point to it. Image by Author.

We can do this for every point in the xy-plane to get the Voronoi diagram of these 3 points.

Voronoi diagram of 3 points, animated. Image by Author

Altough this method works, it is painfully slow, especially when the number of points is large.

Voronoi diagram of 20 points, animated. Image by Author.

In Python, scipy.spatial has a class called Voronoi that calculates Voronoi diagrams more efficiently and provides us with more information about the diagram.

Voronoi diagram calculated using scipy.spatial. Image by Author.

scipy.spatial ‘s Voronoi returns a list of vertices, regions, and ridges, which are going to be useful later on.

A region and a ridge in a Voronoi diagram. Image by Author.

These additional points help form what is called the Delaunay tessellation.

Delaunay tessellation on top of the Voronoi tesselation. Image by Author.

Lloyd’s Relaxation Algorithm

Now, we have to generate random points where cells will be.

If we use a function like random from numpy.random to generate multiple points and calculate its Voronoi diagram, we get these results:

Voronoi diagram of random points. Image by Author.

You may have noticed that some points are too close to each other. This is known as clustering. Cells are supposed to be distributed uniformly.

This is more noticeable when we zoom out (or increase the number of points):

Notice how some points are clustered together while other areas are empty. Image by Author.

To solve this problem, we have to space the points apart.

One way to solve this problem is to use Lloyd’s relaxation algorithm, which takes advantage of the Voronoi diagram of the points.

The idea behind Lloyd’s algorithm is to calculate the Voronoi diagram of our points, then move every point to the centroid of its cell. And repeat the process a certain number of times

The centroid of a polygon is the average of its vertices.

This is a Voronoi diagram with cell points in blue and cell centroids in red.

Voronoi diagram with cell points (blue) and cell centroids (red). Image by Author.

We can then, replace cell points (blue) with cell centroids (red) over and over again.

Lloyd’s relaxation algorithm animation. Image by Author.

This yields better looking random points.

In order to generate random terrain, we have to generate properties that vary randomly through space, properties like elevation, temperature, or precipitation.

One could think of using random , and that would make sense.

We are going to generate a random number, between 0 to 255, for every block on the xy-plane in our world.

This yields the following result:

This is too random. Image by Author.

Well, that looks more like a QR code than a Minecraft world.

The problem is that our random values have no coherent structure. Every value is individually generated and has nothing to do with its neighboring ones.

To overcome this problem, we are going to use Perlin noise.

Perlin noise. Image by Author.

Perlin noise was invented by Ken Perlin in 1983. Unlike regular random noise, it has a structure to it. It looks closer to random patterns found in nature (clouds, forest distribution).

Simplex noise was also created by Ken Perlin himself. It has many advantages over Perlin noise. Perlin noise and Simplex noise are being used today in almost all of procedural generation.

We will use an implementation of Simplex noise in Python called noise. (Python module).

We have 4 variables to play with: scale, octaves, persistence, lacunarity. I won’t explain what each one does, but I will leave you with these GIFs I made to get a sense of it yourself.

Comments are closed.

SEARCH

Categories

Tags

Archives

Last articles

Last comments

 

Valid XHTML 1.0 Strict