News for hackers. Stuff that matters.

A comment on The Wavefunction Collapse Algorithm explained clearly.

Re:The Wavefunction Collapse Algorithm explained clearly by zzlk on Tuesday December 20, 2022 @12:20PM (#34068993)
I implemented this algorithm to generate StarCraft 1 maps and it worked quite well. The results it generates have quite a natural property to them that you don't see with similar things like perlin noise. I wrote it in rust which I compiled down to wasm, put it on a web page with an ugly UI and gave it to the community. They used to to produce some interesting maps and the results of one run even got included in a real released and finished map. One other benefit of this algorithm is that people can hand craft a map, placing tiles in certain places, and then you can ask the algorithm to complete the map. The algorithm will seemlessly blend generated content with your original tile placements (which are just more constraints). This is really nice for filling in unimportant areas with a consistent level of detail.

Unfortunately I could never really get it to be fast enough. There are an enormous number of tiles in StarCraft, 15,000+ for some tilesets, and people want to generate maps of up to 256x256 tiles. This is a huge state space and under these conditions the algorithm very often gets stuck in a local minima. I've tried so many different heuristics to get it to work but it doesn't work reliably enough to be a truly useful tool in this situation unfortunately.

There are many explanations out there about how this algorithm works, more so than many other algorithms. I think the reason for that is because from hearing the basic high level idea of this algorithm most people are able to then go and implement it and then that makes for an interesting blog post (I could do the same after implementing, I think). What almost all of these blog posts are missing is how to make it fast, and how to implement back tracking efficiently. I had to try a lot of things to get to where I am now and I don't feel like I've fully explored the space of possible implementations despite trying a lot of different approaches.

Here are some example generated maps: https://media.discordapp.net/attachments/583406212272619571/... https://i.imgur.com/LK5a6jU.jpg https://cdn.discordapp.com/attachments/583406212272619571/10... https://cdn.discordapp.com/attachments/583406212272619571/99... https://cdn.discordapp.com/attachments/583406212272619571/99...

[ Parent | on HN ]
Re:The Wavefunction Collapse Algorithm explained clearly by Doxin on Thursday December 22, 2022 @04:07AM (#34091314)
So one solution I've used in the past to get WFC unstuck from local maxima is to keep a counter for each tile location with how many times it has gotten stuck at that location. Whenever it gets stuck it'll reset all the tiles within a radius relative to that counter. First time it gets stuck it'll reset all direct neighbors. Second time it'll reset all direct neighbors and their neighbors etc. For the tilesets I was using it'd hardly ever have to reset the same spot more than twice, which kept things relatively fast. It has the nice property of eventually guaranteeing a solution, though that may involve resetting the entire map many many times if it's a sufficiently gnarly problem.
[ Parent | on HN ]
Re:The Wavefunction Collapse Algorithm explained clearly by zzlk on Thursday December 22, 2022 @04:14AM (#34091356)
This is a nice solution. I came up with something similar where once it got stuck without making much progress I would just blow away a big radius and that would often help it get unstuck. I did eventually abandon this approach though. I can't remember the exact reason why but I think my back tracking system was not compatible with it. So if it got stuck after blowing away some tiles then it would be truly stuck and could not backtrack anymore.
[ Parent | on HN ]
Re:The Wavefunction Collapse Algorithm explained clearly by Doxin on Friday December 23, 2022 @03:08AM (#34103405)
Mine didn't even have any backtracking at all. It'd just keep blowing stuff up until it happened to stumble on a solution. Obviously that only works if your tileset allows for many solutions, if there's only a single solution to an area it'll take a long while to stumble on it.
[ Parent | on HN ]