1 line of code to generate random maze, this probabilistic programming language is on the GitHub hot list, the author has developed the famous WFC algorithm

Exploring the mazes in the game is fun, but it’s not “fresh” after playing too much?

That’s right, if the game mazes are not very different, it will be easy to become familiar with the map over time, reducing the fun of exploration.

Now, a probabilistic programming language “turned out”, MarkovJunior, solves this problem:

Using the Markov algorithm, a batch of mazes are randomly generated, none of which is repeated, and you never know what the next maze will look like:

Not only 2D mazes , but also 3D mazes that require several layers of maps can be randomly generated:

As soon as this project came out, it was immediately listed on the GitHub hot list, and it has already gained 2.6k Stars in less than a week.

Some netizens lamented that this programming language can directly generate buildings for RPG games or action games.

The authors of Keras are also interested in this probabilistic programming language:

Let’s see what its principle is and how it randomly generates various mazes.

based on Markov algorithm

According to the author, this probabilistic programming language draws on Markov algorithms .

(The name MarkovJunior is also named after the mathematician Andrey Markov who proposed the Markov algorithm)

Specifically, this set of probabilistic programming languages ​​consists of a series of specific rules (Rewrite Rules) , which are an ordered list.

In the process of generating a (maze) model, it will use the Markov algorithm to achieve ” random generation “, and then formulate a series of specific rules to determine the type of the generated model, such as a maze, a topographic map, or a circuit diagram.

The Markov chain has the “memoryless” property, that is, the probability distribution of the next state can only be determined by the current state, and the events preceding it in the time series have nothing to do with it.

So, what exactly do these specific rules look like?

For example, one of the simplest rules is to rewrite the “black” patch to a “white” patch until it eventually fills the entire model:

For another example, by implementing the rule of rewriting the “white-black” color block into a “white-white” color block, combined with the Markov algorithm, a probability generation model can be obtained:

For another example, based on the rules of the “Shoko box game” ,

△ Sokoban game

You can use this batch of small red dots to randomly “carry” the white squares to the designated location:

There are many more specific rules like this, all contained in MarkovJunior.

So, how exactly do we use these rules to generate a random (maze, circuit diagram, etc.) model?

2D/3D mazes, topographic maps and circuit diagrams can be drawn

Let’s take a random 2D maze as an example:

From the picture, this maze algorithm will automatically generate a “starting point” red dot, randomly explore and rewrite the path in a black map, and finally fill the entire map, completing a “maze” with a beginning, an end, and a fork.

MarkovJunior can make a lot of random mazes like this, just based on two rules:

The first rule rewrites the “red-black-black” patch randomly into a “green-green-red” patch.

The second rule , when the first rule is “stuck”, that is, there is no matching option, automatically executes the “red-green-green” color block randomly rewrites to “white-white-red” color piece.

In this way, the algorithm can generate a random path through the first rule, backtrack the untraveled path through the second rule, generate a fork in the road, and finally traverse the entire black map to generate a set of “2D mazes”.

There is also a simpler idea to replace all “white-black-black” with “white-A-white”, where A is an intermediate state, which is not used as a starting point, and is replaced with white after the maze is generated.

According to the authors, using this rule, 1 line of code can randomly generate 2D or 3D mazes.

△ 3D maze looks like this

Based on this idea, a random topographic map can also be generated by changing the rule combination method.

For example, trying to generate a topographic map of a river, just use the above method of generating models and add some other rewrite rules to create a random river map:

In addition to topographic maps and simple 2D/3D mazes, more complex 3D buildings can also be done, just generate a batch of “stairs” at random positions between the two 2D “mazes”:

Well, I can even draw circuit diagrams …

According to the author, as long as these rules are used flexibly, MarkovJunior can be used to randomly generate a variety of buildings and drawings.

It can be said to be very useful.

He is also the author of the famous WFC algorithm.

The author of this probabilistic programming language, Maxim Gumin, is an independent game developer.

The most famous project he has worked on should be a set of things called ” WaveFunctionCollapse” (WFC) , which currently has 18.7k Stars on GitHub.

This set of WFC algorithm is inspired by the concept of “wave function collapse” in quantum mechanics, and it has been applied to some games, such as ” Townscaper” and so on.

△ Source: Steam

Maxim Gumin did not disclose more information about himself, but we can see on his homepage that this old man calls himself “the king of probability models, the procedurally generated messiah, the one who tames the Markov chain… ” (manual dog head)

From GitHub, he has been focusing on applying various mathematical algorithms to procedural generation over the years to make various interesting models.

Maybe some of the games you’ve played have already used the algorithm he developed.

project address:

https://ift.tt/bQ0nflO

Reference link:

[1] https://twitter.com/ExUtumno

[2] https://ift.tt/avSnP9A

[3] https://www.youtube.com/watch?v=DOQTr2Xmlz0

[4] https://twitter.com/fchollet/status/1532019171038355456

-End-

The text and pictures in this article are from qubits