This is my take on the wave function collapse algorithm in one of its simple variants : the simple tiled model.
Given a set of tiles and some adjancency rules, the algorithm tries to produce an image. It can be used for levels generation, pattern-like backgrounds and can also be used for non-visual data.
How does it work ?
This cart contains a few demo tilesets and rulesets that you can navigate between with the left and right arrows.
Sometimes the algorithm gets stuck (shown with red tiles). This happens when there is a contradiction : the rules won't allow any tile to be placed on a position. Press X or O to restart.
Yeah but, really, how does it work ?
I suggest you look at the links provided below for more information about the algorithm.
For this specific implementation, I used bitfields to encode adjacency rules : each tile has a list of 4 integers (for the four directions : up, right, down, left). Valid neighbors are determined by comparing (with a binary AND) the opposite bitfields of each tiles : 1 can connect with 1, 3 can connect with 2 and with 1,...
Links
- Original implementation by Maxim Gumin (@ExUtumno) : https://github.com/mxgmn/WaveFunctionCollapse
- The coding train's implementation which this cart is based on : https://youtu.be/rI_y2GAlQFM
- A nice explanatory video by Martin Donald : https://youtu.be/2SuvO4Gi7uY
- GDC Talk about wave function collapse in "Caves of Qud" : https://youtu.be/AdCgi9E90jw
@dw817, you would need to add extra logic to tell which tiles are walkable, find paths, discard dead-ends or cycles... It's hard to enforce these kind of high-level requirements with this simple approach only, but I guess more complex WFC implementations could.
I think a well-suited usage of this algorithm for level generation would be to have a few "layout" tiles that combine to form the overall shape of a room, or even a room arrangement. You could have rules like "a monster room goes next to a treasure chest room". And then you would have to turn the result of the WFC algorithm into the actual graphics (with another WFC to add semi-random textures, for example).
Hi @pck404:
It can be done. Here is an example program I wrote that literally just drops random blocks on the map yet a check is made every time to ensure all points can be reached:
Very nice. I hadn't seen a tiled version of WFC before. I've been working myself up to trying to do WFC myself and now I've got another method to try.
I keep getting pink tiles. Not sure if that's a bug or the web version doesn't entirely work, i don't know.
@Pickelrye, there are a couple tilesets that produce pink tiles quite often (1 and 3) because of the particular tiles/constraints I used for those. That's a common issue with this algorithm : it sometimes leads to contradictions. I could fix this by adding more tiles with different connections. I could also try to implement a backtracking mechanism that would undo the latest choices and try something different.
[Please log in to post a comment]
