Infinite procedurally-generated city with the Wave Function Collapse algorithm | Hacker News Reader

Infinite procedurally-generated city with the Wave Function Collapse algorithm

marian42.itch.io

764 pointsguessmyname141 comments

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?

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.

I'm too lazy to click the link, please explain what is happening if I clicked them

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.

While a clever interpretation, that's not what copypasta means. It's literally a permutation of the phrase 'copy and paste'; popularized on 4chan, as a term for posts that would be repeatedly copy/pasted.

There's something special about it when applied to code though. Spaghetti code that's been copy/pasted is, in particular, quite worthy of being called "copypasta".

I have never seen the term being used in programming (for code) this way to refer to spaghetti code. Unless your definition caught on, using it that way would just confuse people, because copypasta already means something else.

I concur that this is an interpretation I encountered, that is bad copy/paste of possibly good code (often from stackoverflow) that results in spaghetti/pasta code, due to pasted code not being reformatted/refactored to fit surrounding code.

To be clear: specifically when copy-pasting, just particularly when the code is already spaghetti. (Because who commits just one sin?) The copy/pasting is the critical element.

Actually the previous assertion predates 4chan. Anecdotally I recall using "copypasta" in the late 90's when working with code that had obviously been copied from another source and turned into a a spaghetti code mess. I don't doubt that it has taken on many other meanings, but I know for a fact that it means what naikrovek is not alone with that definition.

Yes. My exposure to the term is from slashdot and IRC in the late 1990s.

Can't believe I got downvoted for having more time on the internet than some others here, learning during that time, then making a statement based on what I learned.

What the fuck did you just fucking post about me, you absolute beginner? I'll have you know I worked for ten of the biggest silicon-valley industry companies, and I've been involved in over two hundred top secret projects including NodeJS. I am trained in refactoring the most fucked up code, and I'm the top C++er in the entire fucking internet-connected universe. You are nothing to me, but just another IP. I will fucking revoke your commits from your gitlab account with absolute dedication using only one Rasperry Pi client. Mark my fucking words. You think you can get away with posting that shit on one of my numerous very personal blogs? Your devices are fucking bricked, kid. My attack software can be anywhere, anytime, and it is tasked to remove your entire git contributions from planet earth. Not only am I extensively trained in remote cross-firewall device-hacking, but I have access to over 100 of the United States CIA and NSA git repositories. If only you could have known what doom-bringing C-one-liner you have raised from my fucking hands, maybe you would have held your fingers. But you could not. You did not. And now you're paying the price, noob. I will hail havoc upon your puny online-presence and you will drown in your own badly designed software. You're fucking offline, kiddo.

(I think the Navy Seal copypasta and it's variations is the most popular example: https://knowyourmeme.com/memes/navy-seal-copypasta )

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 track of a probability distribution over the tiles. This distribution is influenced by the neighboring tiles (exactly how is probably the most interesting bit of the algorithm; I don't know).

The algorithm proceeds by repeatedly (i) picking a tile on the boundary that has a very skewed probability distribution, and fixing it to be the most likely tile; and (ii) updating the probability distributions of the neighboring tiles in the boundary.

It's possible that you end up making poor tile placements at the beginning that gets you stuck later, so the algorithm must sometimes backtrack to undo past decisions. You want to pick a set of tiles such that the algorithm doesn't need to backtrack too often, or it will take too long.

Note that the distribution is an ordinary probability distribution, not a sum of complex amplitudes like the name "Wave Function Collapse" would make you think.

https://news.ycombinator.com/item?id=18322770

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.

Two additions to this: - AFAIK, the probability distribution is based on how common any particular adjacency is in the input. If the input is just rules rather than a small sample map, they'd all be equal, but if the input is an image that shows (for example) that only one in ten roads dead-end, that would carry over to generated stuff. - It can also do an "overlapping" model, where it sets one pixel at a time but considers overlapping tiles of 2x2 or 3x3 pixels. This breaks away from the grid structure, but requires a full sample image, not just a list of tiles.

In my case, the probabilites for each block are supplied manually.

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.

It seems like it would work very well in a horror game. Though random generation doesn’t lend itself too well to horror.

This sounds like standard procedures for sampling from a Markov random field.

https://en.wikipedia.org/wiki/Markov_random_field

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.

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

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...

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.

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.

There kind of is entanglement though!

You 'measure' one cell, and then all the other ones 'collapse' to values consistent with the result, because they have a hidden relationship with the cell you measured.

That's what happens in quantum mechanics. When you measure one thing, all the other things its entangled with collapse somewhat too - but not necessarily completely, it depends on the entanglement they had with the measured system.

It's a metaphor, I'm just saying it's very apt, not that it's mathematically equivalent.

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.

How is that different from regular constraint propagation?

It's not.

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

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/

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?!

Are the combatants channelled into the same area? If not you end up with a game of “needle in the (forever growing) haystack”.

It would have to work somewhat like PUBG - people caught outside a given area slowly start to bleed health. (Or for bonus fun, are catapulted towards the center of the current combat area.)

Careful design of the "tiles" and some restriction to the play area could go a long way to make a "fun" map that is still hugely random.

You could throw in some magnets there, like a flag whose position is known and has to be captured before the other team does it.

Doesn't have to be a stationart target. Just mark the position of the leader in a deathmatch scoreboard on the map and tge problem solves itself while the game can keep moving over the map.

As someone who already has an abysmal sense of direction (I basically never play 3D games because I'm just always lost), this is my nightmare.

If the playable area was small enough, this could actually reduce your disadvantage: nobody else would know what the map looked like, either.

Minecraft in survival mode is probably the worst. You can very easily get hopelessly lost - especially in the Nether world. Very easy to lose track of your portal which is not fun.

It can be fun. It can also be fun to come up with some sort of breadcrumb system and movement planning.

Exploration in proc gen worlds is mostly pointless anyway. Build roads to everywhere you want to go and you'll never get lost.

Yes, solved that by making big arrows out of bright coloured blocks pointing back the way I came. Once you find one arrow you're fine.

I also carried a lot of dirt around for those times when a bridge or stairs were needed to keep moving.

Pointless yes, but you could say that for most games.

I actually do play a lot of Minecraft, but my play style is probably unusual.

I almost never explore caverns. I strongly prefer to dig my own systematic mines to get underground resources, even though it's more work.

On the surface, I never explore without a map. I take copious notes of the coordinates of my home and interesting features.

I tend to spend most of my time building and acquiring, and very little time exploring (even though I love the procedural generator Minecraft uses).

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?

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.

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.

Peer to peer greatly complicated multiplayer architecture- you _can_ build it like that, but it will be 10 times more difficult.

You kind of have to have the server doing the collapse anyway, or clients can cheat by biasing the collapse towards tiles that are beneficial to them in some way.

You can partially work around this by requiring the client to use a server-provided PRNG seed, although even then a kind of aim bot could help the player decide which path to explore to get favourable tiles.

So your best bet to avoid cheating is to do the collapse on the server using a hidden RNG.

either you have a server doing the collapse or you could send explored tiles as constraints to the other clients (this also reveals your position, but oh well).

of course tiles would need to be large enough to keep latency reasonable.

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

> generates the same numbers so that it is deterministic.

The problem is, that the algorithm is path-dependent, deterministic PRNG is most likely already used, and doesn't help.

So if 2 players started at (x0, y0, z0) and went to (x1, y1, z1), but took different paths to get there - they would see a different tile :)

couple that with some mirrors edge like free running mechanic. maybe a team vs 1 chase so all players would be running toward the same thing. reminiscent of a chase scene from a movie through an unfamiliar city, where a dead end could be just around the corner.

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.

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.

"Guided by human actions" isn't exactly random; chaotic and unpredictable, sure!

On big budget games like Call of Duty, some of the multiplayer maps would be very finely tuned over thousands of hours of testing. A friend and I play regularly (just us against bots) and not a session would go past without either of us remarking that they'd nailed the maps. There's nowhere you can truly dominate a map. Everything has been tweaked to balance it all.

You kow what would be more fun - is a game with a squad that needs to advance along a path to a goal co-op style taking out hoardes coming in the opposite direction - and the prize goes to longest life of the team.

Left4Dead?

I can't tell if you're trolling by commenting with a basic summary of Left4Dead versus mode, a 10-year-old game.

You could design to have repetitive features, ex. you know that any tunnel will always have stairs to a higher level next to a lamp.

Oh yeah. I remember modding Quake and Unreal and such back in the day--after a lot of practice and experimentation, one learns to read a map like a book. Gameplay is built right into the structure of the world. When the map is made by an expert, players can still enjoy it without directly understanding it or even noticing it. It's an incredible example of intuitive design.

Not to say there isn't a way to make some form of satisfying gameplay out of a randomized sandbox, but it certainly won't be the same as an FPS map designed with experienced intent. That aside, it would probably produce a spot with excellent gameplay every so often out of pure serendipity, which would be fun to hunt for! I'd try it.

> 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 you're just memorizing the layout. Has anyone seriously attempted that in a multiplayer game? Obviously there's a lot of ways it could fail, but I feel like it could be spectacular if done well.

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

If the level was ever changing and expansive it wouldn't matter if one side has a major advantage. Balance is important for small amounts of limited maps, balance is not so important when you have infinite maps and someone might never encounter that same setup as before after hundreds of games. Plus it will be way harder to find advantageous points to utilize when you have to find that spot through observational skills, rather than seeing somebody else use it or kill you from it and copying them.

It is definitely a different play style this way, but im sure many people would have a preference for it.

> but im sure many people would have a preference for it.

hardly, for shooters it will become very frustrating very fast, because a lot of the time you're going to get outrandomed rather then outskilled.

I mean I don't get why everyone is focusing on shooter style games, this would be really great instead for assassination games or hide&seek games, including path findings, runners, treasure hunt etc.

I think Arma is proof against it not working. Sure the maps are static in Arma and not random, but they are also large enough that I might utilize a same spot twice over hundreds of hours of play, while in something like CS or CoD I use the same spots hundreds if not thousands of times. Plus with the larger maps without artificially small arena limits there is very rarely a 'safe' area to camp anyways. In CS or CoD you can block off two lanes and be immune from a surprise flank, but when somebody can literally go 1km circle around you and your team without you ever knowing about it there really isn't a safe area.

If you want a more direct comparison on how map limits effects playstyles, compare Insurgency with Arma, they both have similar weapon deadliness and player types where running and gunning isn't really possible, but the overall game strategy players use and rely on is very different. You regularly see players in Insurgency using the map limits to their advantage and can just assume they won't get shot from certain directions because of it, in Arma you might try and utilize a similar area but there is no guarantee someone might not take the time to completely flank you or pop out of the sea or just take pot shots from 2km out on a hill top.

Something like this I think would be better suited to something like an infinite roguelike or even an idle game perhaps.

It's not infinite or procedurally generated, but the basis sounds a little like the Battlefield Rush modes present in the Bad Company 2 (my fav), BF3 and BF4 games. Haven't played the newer games. Maps have only 4-5 "sections" where conflict occurs each with different design, layout and challenges.

I knew if I scrolled enough I would find a comment about gaming. I have often wonder if well balanced, authentic looking, fun maps can be generated. This type of research looks to be part of the solution.

Would be fascinating to see if key BF maps concepts can be incorporated.

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 on perlin/simplex noise and random number generator seeded with the world coordinates of the chunk

- fill the chunks basing on 2d markov chains trained on hand-crafted map, starting with the edges going inwards

It needed a lot of training data to produce something that makes sense with even small number of possible tiles, so in the end I just generated everything with simplex/perlin noise and some heuristics.

I guess instead of markov chains I could use explicit rules to fill the chunks, like this seems to do.

But it had the advantage that it was very fast - because you didn't need to remember everything from the starting place of the player. You could teleport 1000 screens left, and then back, and everything worked fast and regenerated everything the exact same way.

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.

> 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 ;)

You'd use something like Perlin noise to seed whatever makes the decision about which tile to pick. Perlin noise is deterministic, so it's perfect to generate from the (x,y,z) of the tile & you can be certain that the location will resolve to the same tile if you recalculated the area from scratch. Divide up your world into areas, and force the centre of the area you're in and adjacent areas before filling out the area the player is in.

If you have two adjacent chunks, collapsing one will impose constraints on the other one. Even if the RNG part is deterministic, as you suggested, the result will be different depending on which chunk you collapse first.

I don’t get it. If you have some location between two regions, and you fill it in starting from some regular point (say, centre of the south-west region), you will get the same tiling every time.

If you randomly choose a point to start at (like the player avatar’s current position), then I see that you might get different tilings when regenerating the location.

If you divide world into chunks and specify order of collapsing inside each chunk, and use deterministic random number generator seeded with the same thing for given chunk - then the result will be the same each time.

It's strange, but for many, many years (40 at least?), I have had dreams that are in places like this. Endless halls, rooms, corridors, and so forth with no exit.

It is really oddly triggering to run around in this thing.

I came here to find your comment. All the vivid dreams I have are either 1) resitting an exam from 20 years ago and being completely unprepared for it or 2) running around in an endless dreamscape that is created by taking a known familiar area like a university, my local neighbourhood or a shopping centre and then scaling it up by using exactly this Wave Function Collapse algorithm. Funny thing is I can't backtrack in my dreams either.

Admittedly without yet reading but just looking at the pictures, I'd love to see examples of where it creates patterns of patterns. Sort of like the biomes in Minecraft: one pattern to draw out where the biomes are, one to fill them in with content. Could it be made to do patterns of patterns of patterns?

If this were used to create level design where the local view is several iterations deep of patterns of patterns but not yet all the way to the bottom, I guess a fractal, that would be a trip.

Awesome work!

Each block has a probability of being selected. You could make this probability location dependent, for example by sampling a noise function. That way you get something like biomes.

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".

Time series data is one-dimensional?

Isn't that kind of just a markov chain?

"One of the dimensions can be time. In particular, d-dimensional WFC captures the behaviour of any (d-1)-dimensional cellular automata."

Imagine creating a Tony Hawks Pro Skater course with this. Can’t learn the course ahead of time, just have to be a badass street skater.

Great minds: https://arcadia-clojure.itch.io/proc-skater-2016

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.

I assume McMansion builders use the same design process.

Honestly I think that's giving them too much credit ;-)

Someone skin this to mimic 'Dark City'! Complete with signs to Shell Beach...

Dark City is a great film, though this had me personally thinking more of Inception.

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.

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

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 :-(

I do have a Mac, I don't have Unity Editor :-(

I may be fulfilling this wish, but I have not build a unity game to Mac in a while and do not have a mac powerful enough to run VR games. Can you download mac.app from here and let me know if it runs on your machine or if it works with SteamVR.

https://drive.google.com/drive/folders/1uRP9uan3iViBddmQ5iZ3...

This is tectonic. If it's purely WFC, I'm really amazed and excited. It's not the novelty, it's the perfection of each. They remind me of the Laurentian library by Michelangelo.

https://goo.gl/images/HHQLUv https://goo.gl/images/njGNLC

Would love to see the output using Gothic architecture as the input.

Links are broken (without javascript?), direct links appear to be:

https://s.hswstatic.com/gif/michelangelo-buildings-10.jpg

http://www.perfectraveller.com/media/k2/items/cache/2cebfdae...

If this is based on wave-function collapse, what does it do when it hits an impossible/contradictory state?

(See https://github.com/mxgmn/WaveFunctionCollapse where it mentions "It may happen that during propagation all the coefficients for a certain pixel become zero. That means that the algorithm has run into a contradiction and can not continue.")

In the algorithm as it's described on that page, nothing is returned in case of a failure. I first implemented it so that single blocks would fail and a white cube would spawn at that position. Now, it uses backtracking. It keeps a history of its decisions and removes some whenever it reaches a contradiction.

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

Does it use WFC or another genration algorithm?

This is sufficiently advanced to be magic to me.

Ok, I understand a little bit more from reading this page: https://www.grendel-games.com/procedural-generation/?lang=en

This would make so many games much more fun. Imagine if every drop in PUBG was onto an island with familiar features but not like any before it. Would definitely level the playing field too.

This evokes a deep House of Leaves kind of horror in me when I play it. Similar to when I play No Man's Sky or Zoom in on the Mandelbrot set. Infinite sameness... forever...

The unity game engine and everything worked really well though. It immediately used my HOTAS controllers, which I wasn't expecting. Impressive demo!

How does the infinite part work?

The key problems with Wave Function Collapse tend to be that it gets exponentially slower as the area you need to collapse increases, and that it easily gets "stuck" (i.e. finds an combination of tiles that cannot be resolved, and has to backtrack arbitrarily far).

I assume the speed is solved by operating only on new chunks at the edge of the explored space, but backtracking across chunks seems... painful.

I can see echoes of Borges, Kafka, Euclid, Escher, Greg Egan... nice work. Some existential and strange tales to tell with an environment like this.

Pretty cool. Is everywhere reachable on foot? Are there blind interiors that are not reachable?

Does this remember what’s been generated if you come back to an area you’ve been before?

Yes, it does. However the algorithm is not deterministic. If you close the game and start it again, you will see a different world.

If you want to shoot me an email I could help port it to the vive? I might just need a few detailed instructions and I can figure it out from there.

That's why I hate being a tourist.

- "Look at this wonderful stairs!"

- "I see them. They are really uniquely same as any other stairs I've seen so far. And after all they are ... just staris."

For all those of us not running Windows, is there a video anywhere showing this off?

here is a gif: https://twitter.com/marian42_/status/1061785383057440768

It's on the page:

https://www.youtube.com/watch?v=VqGDxNsAkKE

Thanks! It wasn't before :)

I'm reminded of Greg Bear's The Way. I thought it would be cool if user generated graffiti could be used as a seed for new generative graffiti so the further 'in' you go the stranger it gets

Would it be fair to call the "Wave Function" here a case of parallel constraint satisfaction?

This is just a few ghosts and some pellets away from being awesome .. ;)

It's very unrealistic: in a real city people would have shit bricks because of the total lack of parking, and forced the planning commission to enact big parking minimums.

Reply on news.ycombinator.com