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

91–100 of 145 posts

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

#91

Post by gus_massa »

BorisTheBrave wrote: post #66
doubleunplussed wrote: post #56

Earlier quoted context omitted.

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.

It's really not. There's no probability field (unless you count booleans as a scalar), no complex numbers, and no entanglement. It's just constraint propogation, optimized for certain conditions and given a fancy name. I guess you could call it a markov random field, but I don't think it does unbiased sampling.

I agree. My main objection of the QM metaphor is that in QM you can have interference. For example in version more similar to QM if you have a 2x2 map like this

  1) X ?    2) X Y    3) X ?    4) X Y
     ? ?       ? ?       Z ?       Z ?
The probability of some particular tile in the bottom right corner may be bigger in 2) and 3) because somehow Y and Z make this tile more probable, but perhaps in 4) the probability decrease.

The trick is that you must calculate amplitudes, not probabilities. For example, Y may contribute an amplitude of .5 to the bottom right corner , and the probability is (.5)^2=.25. And Z may contribute an amplitude of -.3 to the bottom right corner , and the probability is (-.3)^2=.09. But when both are there the amplitudes must be added and the probability is (.5-.3)^2=.04.

This is a case of destructive interference that reduces the probability of a particular tile when both are present, but if both have the same sign it can be a constructive interference and increase the probability of that tile.

This type of interference is what produce the weird interference lines in the double slit experiment (and even in the single slit experiment).

This project just add probabilities, without squaring the numbers, so it's more difficult to have quantum-like weird things.

Anyway, I like the result very much. Nice project. Nice name.

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

#92

Post by JazzXP »

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…

Thank you. This description is what cleared it all up for me. I totally understand how this works now.

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

#93

Post by dkural »

srtjstjsj wrote: post #84
BorisTheBrave wrote: post #54

Earlier quoted context omitted.

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…

How is that different from regular constraint propagation?

It's not.

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

#94

Post by MisterTea »

colecut wrote: post #65
MrStonedOne wrote: post #38

Earlier quoted context omitted.

Animated gif https://twitter.com/marian42_/status/1061785383057440768 GitHub page (demo in Unity) https://github.com/marian42/wavefunctioncollapse Original Wave Function Collapse Algorithm https://github.com/mxgmn/WaveFunctionCollapse

and they call you people lazy

We're focused.

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

#95

Post by a_t48 »

PhasmaFelis wrote: post #87
ozmbie wrote: post #63

Earlier quoted context omitted.

I’ve worked as a level designer on FPS games. Dynamic generation might suit certain types of games (or something like an event mode), but a huge amount of design work and iteration goes into the layout of multiplayer game levels to make them enjoyable. It’s also important that players/teams can memorise the level layouts in order to form strategies. Still a cool idea though!

> It’s also important that players/teams can memorise the level layouts in order to form strategies. I'd like to see someone challenge that notion. I mean, that's certainly a known and reliable model for multiplayer play, but we see single-player games like Spelunky where familiarity means being able to recognize how common elements interact and construct your strategy on the fly, as opposed to a Super Mario where yo…

Look for blind races of Super Mario Maker at Games Done Quick.

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

#96

Post by bryced »

Minecraft has an add on that does this called “The Lost Cities”

“There are highways, bridges, tunnels, a subway system, tons of dungeons with spawners and loot and so on. ”

https://minecraft.curseforge.com/projects/the-lost-cities https://youtu.be/OZYZ0kV7Uw0

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

#97

Post by namibj »

a_t48 wrote: post #64
marian42 wrote: post #57

Earlier quoted context omitted.

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.

The server can establish an ordering for the collapse events, and send back to the client that ordering. Edit: depending on how complex the world is, the server could probably just send out the world changes itself, rather than relying on each client to correctly (deterministically) apply the changes. It needs to do so anyhow for late joiners.

Just keep some buffer of generated tiles around the players, and either use a server to asynchronously decide on when which player moved to cause which tile to be generated. You can also use something distributed if you go for peer-to-peer communication. fix the seed and ensure everyone aggrees on the order in which they tell the generatoe that a certain chunk needs yo be fixed or should be freed from memory. Consider just aggreeing on added/deleted blocks inside fixed intervals, and then process the list in e.g. coordinate order. Consider Raft for peer-to-peer aggreement of the exact diff for the most recent period. Consider chunks of like 0.5 seconds per diff. Don't apply the diff tk the generator until a moment later. You can interleave the cknsensus process of successive blocks a bit.

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

#98

Post by nrb »

tikhonj wrote: post #70
ozmbie wrote: post #63

Earlier quoted context omitted.

I’ve worked as a level designer on FPS games. Dynamic generation might suit certain types of games (or something like an event mode), but a huge amount of design work and iteration goes into the layout of multiplayer game levels to make them enjoyable. It’s also important that players/teams can memorise the level layouts in order to form strategies. Still a cool idea though!

I haven't designed levels, but playing maps across a few games, I'm constantly amazed at how well small details are thought out. A seemingly random crate actually blocks off a line of fire that would give one team a major positional advantage; a tree breaks up the line of sight between two objectives; a decorative fire provides visual cover in an otherwise overly open lane; a curved passage has exactly the right prop…

Compared to Fortnite, where every match is a unique experience with the addition of player-crafted buildings, and the static game map is under constant transformation each season.

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

#99

Post by naikrovek »

delinka wrote: post #37
abetusk wrote: post #20

Here's a collection of relevant links for the lazy: * Animated gif: https://twitter.com/marian42_/status/1061785383057440768 * GitHub page (demo in Unity): https://github.com/marian42/wavefunctioncollapse * Original Wave Function Collapse Algorithm: https://github.com/mxgmn/WaveFunctionCollapse

I’m too lazy to copypasta the links. Can you please reformat to make them clickable?

That's not what "copypasta" means, you're thinking of "copy and paste."

"Copypasta" is when you copy sections of code from one or more program's source code and paste it into another, trying to pluck specific functionality from them, and create a mess in the destination program doing it.

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

#100

Post by mrfusion »

matuszeg wrote: post #81
mrfusion wrote: post #79

Earlier quoted context omitted.

I’d love to try it on windows if you can do it.

I'm at work and my Vive is at home, threw together a build that "in theory" works but I have yet to test it. If you wanna take a stab it you can download it here. https://drive.google.com/drive/folders/1uRP9uan3iViBddmQ5iZ3... or check out the source here https://github.com/matuszeg/wavefunctioncollapse I'll update the build (and this comment) and make sure it works later when I get back to my Vive.

Awesome! I’m going to fire up the vive Pc tomorrow morning and try it out. I’ll provably have to sit through an hour of updates :-(
Post reply on HN