Log In  

Cart #pck404_wfc_stm-0 | 2022-10-25 | Code ▽ | Embed ▽ | License: CC4-BY-NC-SA
13

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

P#119553 2022-10-25 20:12 ( Edited 2022-10-26 15:34)

Cool!

P#119556 2022-10-25 20:31

The Desert Village I am especially interested in, @pck404.

Can all points be reached ?

P#119561 2022-10-25 21:23 ( Edited 2022-10-25 22:21)

@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).

P#119562 2022-10-25 21:35

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:

https://www.lexaloffle.com/bbs/?tid=32278

P#119565 2022-10-25 22:22

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.

P#119710 2022-10-28 01:19

I keep getting pink tiles. Not sure if that's a bug or the web version doesn't entirely work, i don't know.

P#119795 2022-10-28 22:25

@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.

P#119802 2022-10-28 23:53

[Please log in to post a comment]

Follow Lexaloffle:          
Generated 2024-03-28 13:23:59 | 0.078s | Q:31