Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Infinite procedurally-generated city with the Wave Function Collapse algorithm

marian42.itch.io

Post reply on HN
Print view View original

51–60 of 145 posts

Re: Infinite procedurally-generated city with the Wave Function Collapse algorithm

#51

Post by c3534l »

jbattle wrote: post #6
justinpombrio wrote: post #3

Earlier quoted context omitted.

Here's my high-level understanding. You're going to tile (say) the plane with a set of tiles you've chosen beforehand. (In this example, it looks like the tiles are 3d.) There are rules for which tiles can go next to each other---the edges must match. As you go, there are two regions: a region in which you've settled on which tiles to use, and a boundary region in which you haven't. In the boundary region, you keep t…

Maybe this is a dumb comparison, but it sounds like an algorithm for solving minesweeper. The big difference is there's no "right" answer, the puzzle emerges from the outplaying of probabilities.

Basically.

Re: Infinite procedurally-generated city with the Wave Function Collapse algorithm

#52

Post by mlonkibjuyhv »

rickycook wrote: post #45
pgruenbacher wrote: post #43

Earlier quoted context omitted.

oh it's not? is it at least deterministic on the same architecture (ignore float precision) or is just inherent to the implementation?

someone mentioned that it’s random, but i feel like a PRNG seed would make it deterministic?

I get the feeling it's path-dependent. If I start uptown and you start downtown the algorithm could potentially show us two different cities. So we would have to agree on a city beforehand.

Re: Infinite procedurally-generated city with the Wave Function Collapse algorithm

#53

Post by tobr »

justinpombrio wrote: post #3
mrspeaker wrote: post #2

Amazing work! I've been excited about this technique since I first saw the original demos of it ( https://github.com/mxgmn/WaveFunctionCollapse ) - but can someone explain (at a very high level) how Wave Function Collapse works? I've read through some of the documentation on various repos - it starts with the nitty-gritty details, and I haven't been able to grasp the concepts.

Here's my high-level understanding. You're going to tile (say) the plane with a set of tiles you've chosen beforehand. (In this example, it looks like the tiles are 3d.) There are rules for which tiles can go next to each other---the edges must match. As you go, there are two regions: a region in which you've settled on which tiles to use, and a boundary region in which you haven't. In the boundary region, you keep t…

A while back I hacked together a crossword generator that works almost exactly like this, but using a wordlist to provide probabilities.

Re: Infinite procedurally-generated city with the Wave Function Collapse algorithm

#54

Post by BorisTheBrave »

mrspeaker wrote: post #2

Amazing work! I've been excited about this technique since I first saw the original demos of it ( https://github.com/mxgmn/WaveFunctionCollapse ) - but can someone explain (at a very high level) how Wave Function Collapse works? I've read through some of the documentation on various repos - it starts with the nitty-gritty details, and I haven't been able to grasp the concepts.

Have you ever written a Sudoku solver. It works like that.

You start with an array where every tile is possible in every location. Then you pick a random cell and assign a tile to it. That tile implies some choices are impossible, so you set those possibilities to false. That further implies some other possibilities are false and so on. You propogate that as far as it goes, and when you are done, pick another random cell and assign a random possible tile to it.

Because you are propogating information as much as possible before making the next choice, the algorithm very rarely needs to backtrack. You can run WFC without any backtracking at all and it'll still find a solution most of the time.

Some animated examples I put together might illustrate things more: https://boristhebrave.github.io/DeBroglie/articles/gallery.h...

Re: Infinite procedurally-generated city with the Wave Function Collapse algorithm

#55

Post by BorisTheBrave »

WFC collapse is an awesome algorithm, but I think this demo really illustrates that to get nice looking output with procedural generation also requires an excellent eye for design.

I've played around a bit with WFC and wrote a library for using it[1], but I've never made anything as pretty as this.

[1]: https://boristhebrave.github.io/DeBroglie/

Re: Infinite procedurally-generated city with the Wave Function Collapse algorithm

#56

Post by doubleunplussed »

BorisTheBrave wrote: post #54
mrspeaker wrote: post #2

Amazing work! I've been excited about this technique since I first saw the original demos of it ( https://github.com/mxgmn/WaveFunctionCollapse ) - but can someone explain (at a very high level) how Wave Function Collapse works? I've read through some of the documentation on various repos - it starts with the nitty-gritty details, and I haven't been able to grasp the concepts.

Have you ever written a Sudoku solver. It works like that. You start with an array where every tile is possible in every location. Then you pick a random cell and assign a tile to it. That tile implies some choices are impossible, so you set those possibilities to false. That further implies some other possibilities are false and so on. You propogate that as far as it goes, and when you are done, pick another random…

As a physicist who works with quantum mechanics, I have to say, "wave function collapse", is an extremely apt name for what you're describing. Usually when quantumy things are used in names of things it's just 'cause it sounds cool, but this is spot-on.

Re: Infinite procedurally-generated city with the Wave Function Collapse algorithm

#57

Post by marian42 »

mlonkibjuyhv wrote: post #52
rickycook wrote: post #45

Earlier quoted context omitted.

someone mentioned that it’s random, but i feel like a PRNG seed would make it deterministic?

I get the feeling it's path-dependent. If I start uptown and you start downtown the algorithm could potentially show us two different cities. So we would have to agree on a city beforehand.

This is exacly it. Collapsing one area changes the possible blocks for nearby areas. If you use the same seed, you can still get different results by exploring places in a different order. Maybe there is a way to get around this though.

Re: Infinite procedurally-generated city with the Wave Function Collapse algorithm

#59

Post by marian42 »

mcphage wrote: post #42
marian42 wrote: post #31

Earlier quoted context omitted.

I don't currently have access to a Vive, but I worked with it earlier. All that needs to be done is add SteamVR to the project and hook up teleportation. That's it.

If possible, I'd love to be able to run it on a Mac, too.

If you (or someone with a Mac) wants to create a build with the Unity Editor, I'll add it to the itch.io page.
Post reply on HN