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

41–50 of 145 posts

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

#41

Post by mcphage »

dev_dull wrote: post #21

This is a really good example of an uncanny valley. Things like two staircases side-by-side of different sizes just looks... strange, even though there’s technically nothing wrong with it.

There's a book called "Possible Palladian Villas" which gets into procedurally generated houses (in the style of Palladio), and that kind of thing came up—they'd run their algorithm to generate some houses, and then notice details in what was generated that were just... off. Not impossible, just... not quite right, either. Things you wouldn't think about unless you saw plans for a house that didn't consider it. So they'd tweak their algorithm, and re-run it, finding new details to fix. It's a cool book.

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

#42

Post by mcphage »

marian42 wrote: post #31
mrfusion wrote: post #23

This is great. Can you Please and thank you port it to the vive? Edit: this might not be too hard. It’s open source and has instructions for loading it into unity. You might just have to add the vive camera and toolkit.

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.

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

#43

Post by pgruenbacher »

marian42 wrote: post #35
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?!

Since the algorithm is not deterministic I imagine it would be a nightmare to make all clients see the same world. But I agree it would be fun!

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

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

#44

Post by rickycook »

marian42 wrote: post #35
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?!

Since the algorithm is not deterministic I imagine it would be a nightmare to make all clients see the same world. But I agree it would be fun!

someone explained above that it’s just a bunch of “tiles” (assume they’re premade), so it’s a fairly simple matrix. it would be much less to transfer than custom maps for example, where clients download a large payload at the start of the game.

or, you don’t really care about tiles except that are directly around the players, as long as there’s a reasonable path between them. the city between them can regenerate and it wouldn’t matter; it’s not like they’d compare notes (and if they did, it’d be an odd coincidence rather than broken)

or, you can always use a map seed so the PRNG that makes it non deterministic (assuming that’s the only thing that does) generates the same numbers so that it is deterministic. the age of empires (old yes, but still relevant!) team wrote a great little piece about their multiplayer, and how they kept all their PRNGs in sync so that the games remained the same across hosts

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

#45

Post by rickycook »

pgruenbacher wrote: post #43
marian42 wrote: post #35

Earlier quoted context omitted.

Since the algorithm is not deterministic I imagine it would be a nightmare to make all clients see the same world. But I agree it would be fun!

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?

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

#46

Post by [deleted] »

[deleted] wrote: post #30
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

[deleted]

[deleted]

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

#47

Post by yoklov »

marian42 wrote: post #28
vokep wrote: post #22

Earlier quoted context omitted.

Oh my....perhaps this backtracking to fix past inconsistencies could allow for a game environment in which "Mandela effect" events happen naturally from time to time. Could make for an interesting game mechanic.

You're right. There is backtracking in the demo and when it happens it looks quite eerie. The world around you just decides it wants to look different and changes.

That sounds like it could be mechanically cool. Or at least lead to a cool setting.

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

#48

Post by teddyknox »

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…

I wonder if machine learning could be used to model the probability distributions at a greater capacity, and thus reduce backtracking.

One might also consider placing the algorithm in the context of a generative adversarial network (GAN) to adapt the tile probability modeling ML component towards a pattern that is less distinguishable from a real city.

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

#50

Post by marian42 »

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 a lot of sense since they are local (= don't need to know nearby values to evaluate) and deterministic.

Post reply on HN