By Rex, Co-Founder | NnsDAO Labs

We have an interesting idea to procedural generate NFT(non-fungible token), and we will use these NFTs created to build an NFT metaverse in NnsDAO.

Why do we need Procedural Content Generation?
The Ideal Procedural Content Generation is pressing a button and generating a complete game world: terrain, vegetation, roads, cities, people, creatures, tasks, knowledge, dialogue, objects, vehicles, graphics, texture, text. We want to build a world made up of NFTs and we call it NFT Metaverse. We need to generate many different NFTs. When the number is large enough and the type is complex enough, manual implementation will become impossible. So we need Procedural Content Generation and we find a useful algorithm named Wave Collapse Function.

What is Wave Collapse Function
Before we talk about Wave Collapse Function(WFC), let’s discuss the concept of quantum mechanics first. In this field, there is a very famous experiment called the double-slit experiment. The result of the experiment is that when there is no observation, the photon exhibits the nature of a wave. When observing, photons take on the properties of particles. This is a well-known experiment in which human beings formally encountered a supernatural encounter in a scientific experiment.

There is also a famous experiment called Schrodinger’s cat. When the cat in the box is observed, the state of the cat is either dead or alive and can only choose between the two. If there is no observation, then the state of the cat is neither dead nor alive, but in a state of 50% dead + 50% alive. This state is not in line with reality, but quantum mechanics does define it this way.

The above two experiments both show that a substance may exist in multiple states in quantum mechanics.

Photons: waves, particles;

Cats: dead, alive, 50% dead + 50% alive.

When the matter is observed, its state is determined. This "state is determined" process is called "Wave Collapse Function".

Entropy in Quantum Mechanics

Entropy is a thermodynamic parameter that represents the state of matter. Its physical meaning represents the degree of disorder of matter. The greater the entropy, the more disordered matter is. The smaller the entropy, the more stable the matter.

For example, when water is heated to become fog, the entropy value increases (entropy increase) in this process. When the water cools and turns into ice, the entropy value decreases (entropy reduction) in this process.

Introducing this concept into quantum mechanics can mean that when a substance collapses from a superposition state to a certain state, the entropy decreases, and vice versa.

Taking Schrödinger’s cat experiment as an example, it can be understood that when the cat is not observed, the cat is in the immortal inactive superposition state. At this time, the probability of death of the cat is 50%, the probability of being alive is also 50%, and the entropy value is the largest. When the box is opened to observe the cat, the cat's state is never dead or alive collapsed to a dead or alive state, and the entropy value is the smallest after the collapse.

Since entropy is a measure, there is a formula for seeking entropy. For the probability of an event, the standard formula for seeking entropy (also called information entropy) is

Wave Collapse Function Today

Wave Collapse Function is mostly used in randomly generating map algorithms in the field of games and artificial intelligence. We can generate random maps according to our own customized rules. This will greatly reduce the workload of the art and generate as many scene assets as possible.

Generate noise map, Generate pipeline diagram, Generate maze...

Build an infinity city is also possible.

The Game Bad North uses this algorithm to make many beautiful scenes.

Compared with the map stitching algorithm like the Warcraft3 terrain stitching algorithm, the effect achieved by this algorithm is more flexible and richer, and it is more adaptable to various needs. However, this algorithm is more complex and difficult to quantify. It requires the computer to try and make mistakes and then backtrack... (can be calculated by multi-threading). And there is no mature production specification for the time being, and it is difficult to consider all possible situations in the production of module prototypes. The production progress is not well controlled.

From Wave Collapse Function To NFT

In the construction of NFT, there are many attributes. When we design, we will prescribe certain rules. There are certain rules between two or more attributes.

According to the rules, when we determine the specific value of an attribute, the probability of another attribute being determined greatly increases. This phenomenon from chaos to determinism is called wave function collapse in one term.

So the core principle of the algorithm is to dynamically make the selection range of each attribute become smaller and smaller until all the NFT attributes can be selected to the appropriate value. And how to dynamically make the range of candidates smaller? It is through constraint rules, propagation and backtracking.

Some points worth noting, once the rule is determined, it means that the number of NFTs is determined. This ensures the controllability of the number of NFTs.

Take the Sudoku game generated by WFC as an example. The number arrangement in Sudoku is ever-changing, but the number combination of the final game generated by WFC is 6,670,903,752,021,072,936,960 (approximately 6.67×10 to the 21st power) combinations. Bertram Felgenhauer and Frazer Jarvis calculated this number in 2005 and published the calculation method on their website. Lines swapping, number swapping, and other deformations) do not count, there are 5,472,730,538 combinations. The number of combinations in the Sudoku final game is so amazing, so the number of Sudoku questions is even more countless because each Sudoku final game can produce countless qualified Sudoku problems. This shows that the number of NFTs will change when the rules change, so the formulation of the rules needs to be very rigorous.

Generally speaking, if you want to make WFC NFT, take 2D NFT as an example, the various patterns corresponding to the wave function need to be processed in advance, and the constraint relationship between Pattern and Pattern also needs to be processed in advance. So this WFC process has three steps:

1.Cut out the pattern from the picture

2.Establish the constraint relationship between Pattern and Pattern

3.Collapse and circulate

Of course, We can extend to the three-dimensional situation. In general, the initial state of each level is a voxel composed of all possible modules. As the algorithm continues to advance according to the constraints, the possibilities in the grid become less and less, the grid becomes more and more sparse, the modules in each slot are gradually determined, and finally, a usable level is generated.

The advancement of this restriction is the key to NFT production. Here we use probability to simulate and enumerate. Using this parameter, we can also calculate the rarity attribute of NFT.

In this way, 2D and 3D NFT assets can be easily produced, which can be rendered more conveniently in the game. Allow players to stand personally on this meta-universe land composed of NFTs.

Read More

Part of the picture above comes from these links.

https://en.wikipedia.org/wiki/Wave_function_collapse

https://github.com/mxgmn/WaveFunctionCollapse

https://store.steampowered.com/app/1291340/Townscaper/

http://oskarstalberg.com/game/planet/planet.html

http://oskarstalberg.com/game/house/index.html

https://subspace.com/resources/nft-key-metaverse

https://www.forbes.com/sites/mnunez/2020/01/23/this-startup-thinks-blockchain-is-the-only-thing-that-can-save-social-media/