Long introduction.
In our last game, The Unexpected Quest, level development took about three months, including design and cinematics. Now we are making a tactical strategy game called Eternal Mist and we have over 100 levels planned for it. Naturally they will be much smaller and simpler, but even spending a few days on one level will take a long time to develop. "Better to lose a day, then to fly in five minutes!" we decided and set to work on automatic level generation. We ended up with this:
I want to point out right away that we don't plan to dynamically generate levels in the game itself. Therefore, on the one hand it became easier: there are less demands on stability of algorithms (in case of error or unsatisfactory result you can always generate the level again) and their performance. On the other hand, additional tools for the developer: debugging and visualization of bad moments, UI for the editor, etc. Right now, the process of working on the level looks like this:
From the title of the article, it is clear that after exploring the possible options we settled on the Wave Function Collapse algorithm. It is quite simple to implement and still can produce very interesting combinations. Moreover, the game we were inspired by Bad North: Jotunn Edition, also used this algorithm for generating levels. At the end of the article I added a link to a lecture by its creator about the WFC algorithm.
I'm not going to go into details of the algorithm itself, as there is a lot of material on the web on this topic. I will add some useful links at the end of this article. Just to remind you of the basic principle:
- a level is built from tiles,
- each tile is a visual representation and a list of possible neighbors for each side,
- the whole field is divided into slots, and at the beginning of work, each slot is filled with all possible tiles,
- at each step, one slot with the lowest entropy is chosen (simplistically, with the smaller number of tiles inside) and "collapsed" to a single tile,
- from the remaining slots, the tiles that cannot be adjacent to the collapsed slot or its neighbors are removed (the "wave"),
- the algorithm is repeated until all slots have collapsed or an error occurs.
Implementation features
The usual list of neighboring tiles is not enough to determine which tile may be nearby. Simply because as the number of tiles grows, these lists will also grow. And very quickly and confusingly. So instead of storing tiles, we store edges. This list is much smaller and easier to keep track of. Since the tiles can rotate, we still need to develop an agreement to dock the edges. In the video below (time-linked link), everything is explained in detail and we did the same:
In addition to the "white lists" of allowed tiles (the edges lists discussed above), it is highly recommended to have a "black list" of forbidden tiles. Already without the indication of edges. But simply as follows: on this side of the tile so-and-so cannot join. For example, in terms of joining edges, the example below is acceptable, but visually it looks unnatural.
It is highly recommended to make at least some kind of dump of already registered edges and in which tiles they are used. The visual format is ideal, but even the text format will be very useful in the later stages of development. The top flight, to think through the system of edges so that they can be generated automatically, we, unfortunately, have not reached this level. It looks like this:
One more important point about edges and tiles. The success of the WFC algorithm and the realism of the generated levels largely depends on how you implement the tiles and how you dock them. It took us about three tries to find the right fit. Our main mistake was trying hard to reduce the number of possible edge types, which resulted in a small number of variations for the algorithm and consequently ugly and unrealistic results. At first, it's best to start with a set of tiles from some examples where you like the results.
Performance. The algorithm is slow, with increasing the number of tiles, running time increases significantly, and you have to think about optimization right away. We have thought about it right away, cached something and didn't get there at all... So my advice is: you should optimize the thin places of your algorithm at the development stage, you most likely don't know about them. In our case UE4 internal profiler helped us and studied all suspicious places (everything that is called in loops). We put WFC_SCOPE_CYCLE_COUNTER around and around, and then checked what most of it costs us time. But we should definitely pay attention to handling lists of edges and tiles: merging, crossing and checking if one list contains another. This will be called a lot and often.
Error debugging. Finding a set of tiles where the algorithm can always generate a level is very difficult. For a large set of tiles, it's unrealistic. Therefore, at the stage of development, it is extremely important to understand why the level was unable to be generated and what combination of tiles led to the error. We have it like this:
The red sphere indicates a slot that has no tiles left and can't "collapse". This is most often caused by not having enough tiles to connect nearby slots. Which slots need to be connected is shown in the log below. In addition to this, the log displays the iteration number at which the error occurred. And for detailed debugging, we made it possible to stop the algorithm not only at any moment of iteration, but also at any step of the wave, i.e., when all adjacent slots update the lists of possible edges. This is the panel on the right. Without this kind of functionality, it would be extremely difficult to pick up a working set of tiles, and we recommend that you worry about it right away.
If you are planning a game with automatic level generation, in case of error, it is necessary to rethink the system of level generation (it may take a long time) or a fallback system and continue level generation, but with new random numbers (this should work faster). Fortunately, it was not needed for our tasks.
Useful Links
- You should start with this video: https://youtu.be/2SuvO4Gi7uY
- An excellent lecture by Oskar Stålberg about his game Bad North and his implementation of WFC: https://youtu.be/6JcFbivo8dQ
- An article about generating infinite 3D levels with WFC:
https://marian42.de/article/wfc/
And a link to Unity algorithm itself:
https://github.com/marian42/wavefunctioncollapse - There are ready-made plugins for Unreal Engine, but I'm not sure about their quality:
https://www.unrealengine.com/marketplace/en-US/product/easy-level-generator
https://www.unrealengine.com/marketplace/en-US/product/procedural-environment-generator-wfc - There is also an experimental WFC plugin in Unreal Engine 5:
UE5_FOLDER]\Engine\Plugins\Experimental\WaveFunctionCollapse
Unfortunately, I couldn't find any documentation on it.
Thank you for your attention!
We will be very pleased if you add our game to your wishlist and keep an eye on the project. We will be happy to answer your questions. We promise to write new articles, notes and post interesting materials about the game.
https://store.steampowered.com/app/2102300/Eternal_Mist/
And we look forward to seeing you on our Reddit page.
https://www.reddit.com/r/RionixGames/
Best wishes,
Rionix team.