Map Generator
2024 · Team of 1
Tool for creating random-generated 2D maps using the Wave-Function-Collapse algorithm
Description
This is a personal project I did during my free time as a challenge and to learn more about procedurally generated content.
It is divided into two parts, the first one is the implementation of the Wave-Function-Collapse algorithm, and the second is the creation of a tool to help create the tileset and adjacency rules in a more efficient manner.
Features
Wave-Function-Collapse Algorithm
The algorithm operates by iteratively collapsing possibilities based on a set of adjacency rules for each possible tile. During each iteration, the algorithm analyzes the neighboring patterns around each grid cell, considering their compatibility and enforcing constraints. The collapse process continues until the entire output grid is filled, adhering to the specified rules and constraints. This iterative approach allows the WFC algorithm to generate intricate and complex patterns.
The algorithm itself is divided in three parts:
- An heuristic pick to select the tile to collapse based on the total number of possibilites available, the grid cell with the lowest available possibilities will be the first to be collapsed. If there are more than one with the same number of possibilites, it is randomly chosen between them.
- The collapse of the cell, basically choosing randomly from the available tiles.
- The propagation to the neighbouring tiles, updating their possible tiles. If a neighbour has reduced its possible tiles, it continues the propagation to its neighbours until there are no changed neighbours.
- Repeat until the map is completed.
Tileset Manager
The main disadvantage of the algorithm is the need to set the adjacency rules for each tile. If we had to do it manually it would take too much time, as there has to be a rule for each side of the tile: top, bottom, left and right. If the number of tiles is relatively big it can be very time consuming and prone to error to set the rules manually.
In order to make this process more efficient, I created the tool to manage the tileset and its rules. It allows the user to easily import and modify the adjacency rules for each tile in a visual manner.
There is also the possibility to see all the tiles' combinations at the same time to check for errors and correct them.
Custom Data Structures
I decided to not use the standard template library data structures and instead use my own as a way of practicing and learning more about their inner functionings.
The data structures used for this project were a static array, a dynamic array, a doubly-linked list, a bitset or bitarray and a string class.
Map Generator
The map generator scene shows the grid where the map will be created and it lets you preset cells if you want to have predefined tiles. The algorithm will respect this preset cells and propagate from them.
There are UI buttons for each cell of the grid and you can multiselect or deselect them.
The camera can be panned and zoomed. For the zoom, I made it so that the mouse position is the center of the zoom operation, in this way the zoom will keep this position static making it more responsive and easy to use.
Debug Features
There is a UI panel in the map generator scene to give the user some debug functionalities. They are the following:
- Play, Step and Stop buttons to control the state of the generation.
- Time elapsed: step time and total time to generate the map.
- Changing the map size.
- Presetting and clearing cells.
- Inspection of cells during runtime, if the map is generated with the step button.
- Showing or hiding the separation between grid cells.
