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

61–70 of 145 posts

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

#61

Post by madhadron »

doubleunplussed wrote: post #56
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…

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.

As an ex-physicist, I would say "Markov random field sampling" would be the right name.

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

#63

Post by ozmbie »

yters wrote: post #9

I imagine a counter strike scenario where the area of engagement is constantly moving throughout this infinite city, so the fight is waged over a constantly changing landscape. Hecka fun or hecka confusing?!

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!

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

#64

Post by a_t48 »

marian42 wrote: post #57
mlonkibjuyhv wrote: post #52

Earlier quoted context omitted.

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.

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.

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

#65

Post by colecut »

MrStonedOne wrote: post #38
delinka wrote: post #37

Earlier quoted context omitted.

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

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

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

#66

Post by BorisTheBrave »

doubleunplussed wrote: post #56
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…

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.

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

#67

Post by J253 »

Anyone have any experience applying this to the generation of time series data?

It's easy enough to generate random time series data but this looks like a promising way to generate interesting signals with prescribed shapes or features while still being "random".

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

#68

Post by matuszeg »

marian42 wrote: post #59
mcphage wrote: post #42

Earlier quoted context omitted.

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.

I have a vive, but I don't have a mac. I could throw the SteamVR plugin in and get it up on windows, but someone would have to test it on mac

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

#69

Post by ajuc »

marian42 wrote: post #50
ajuc wrote: post #34

So, does this algorithm need to remember all already decided tiles forever to be consistent? Or to recalculate everything from the start each time you teleport? I've been working on similar (but much simpler and 2d) algorithm, and the gist of it was: - divide infinite world into 2d chunks of constant size that easily fit in memory - when player is nearby - deterministicaly generate edges of the visible chunks basing…

My implementation keeps the entire world in memory, forever. This is obviously not desirable, but I didn't figure out a way around it. You can't generate a place again that you have been to because the result would be different. If you do chunks and generate the edges first, you could run into a situation where it's impossible to fill the chunk based on it's edges. For generating terrain, using noise functions makes…

> If you do chunks and generate the edges first, you could run into a situation where it's impossible to fill the chunk based on it's edges.

Yes, to solve that I generated world in 2 stages - first decided which tiles are solid (using simplex noise so it was consistent), then decided "decorations" (what exact thing is in each solid tile - tree, building part, roof, stairs, etc). Most tiles were empty, tiles with nothing beneath were platforms, tiles with nothing above and something below were roofs or tree tops, etc. Where there were decisions to be made I sampled random number generator in constant order for given chunk. That, combined with seeding the generator basing on chunk coordinates meant it always generated same stuff for a given chunk, no matter which path you took to arrive to this chunk.

The problem was - there were a lot of such rules to specify, and if I only specified the few rules that were needed for consistent world - then the generated worlds were very repetative. When I added more tiles specifying rules for all combinations were too much, so I wanted it to learn rules by itself by analysing handmade maps and then tryign to use that in 2d markov chains, but I never got it to work well, and it was my master's thesis, so I just wanted to be done with it at this point ;)

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

#70

Post by tikhonj »

ozmbie wrote: post #63
yters wrote: post #9

I imagine a counter strike scenario where the area of engagement is constantly moving throughout this infinite city, so the fight is waged over a constantly changing landscape. Hecka fun or hecka confusing?!

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 proportions to give cover on one side while being open on the other, letting players choose when to engage.

In a well-designed map, every part has to play well with everything else, at least within line of sight. Even small changes to the layout result in unbalanced maps that lead to frustrating play. Randomly generated maps might be fun out of novelty, but they won't play well in the long run, at least for games like Counterstrike.

Post reply on HN