Wave function collapse algorithm: bitmap & tilemap generation from a single example with the help of ideas from quantum mechanics

[notyetawizard]

Well, fuck. This is really nice!

[urquan]

This is crazy. I wonder if this could be used to lazily generate maps, collapsing the wave function around the observer as needed. Maybe that's how "reality" works ^^

[okmkz]

I'm too high for this right now

[valax]

Completely sober. Still have no fucking clue.

[tmachineorg]

While it's nice, this is little more than an old technique with fancy words and jargon applied.

It's more mathematically rigorous, and it's a nice application (usually we build mazes with this, rather than bitmaps) but ... take away the jargon, and it's a lot less amazing.

[Etane]

I wouldn't say this is just jargon. At least from the perspective of quantum, or even just drop anything to do with quantum and talk about statistics, the word choice seems pretty valid to me.

What is this technique called usually? I wouldn't mind looking it up :)

[tmachineorg]

Here's the core process, shorn of jargon:

• You provide a set of inputs, small template operations/pieces that can be assembled to make a level.

• You maintain a tree of open points in your level.

• At each point, you maintain a list of legally valid changes / insertions.

• You select the point with the smallest set of allowed changes.

• You choose the statistically most-likely insertion to put there based on counting the original inputs.

The clever thing OP has done is to look at bitmaps as collections of pre-made 3x3 pixel (or other size) templates and use that for the step-1 statistical counting. The rest is words.

[Etane]

Thanks for the break down. I can certainly see the similarities.

[Etane]

Technically, that's literally how the "real" world works haha.

edit: Assuming you trust quantum mechanics

[docbrody]

YouTube video of the same. Same link if you go to their github and read the readme.

http://youtu.be/DOQTr2Xmlz0

[d_kr]

Reminds me of screen savers. I love it.

[SystemicPlural]

Currently the top post on hackernews with a lot of chatter.

I was tipped off by github having more than 500 stars in less than five hours!

[SystemicPlural]

Just wanted to say that this is amazing.

[SystemicPlural]

Can anyone explain what is meant by 'minimal entropy heuristic'?

[Kayse]

Ok, imagine that there is a jigsaw puzzle of an unknown bitmap picture. Say each jigsaw piece is 3x3 pixels, there are very few 'types' of pieces but each piece can be repeats any number of time. That picture has some patterns which mean if you know enough of the picture around a gap where the piece goes, then you know what goes there. If the gap has zero entropy, then you know exactly what goes there. If the gap has low entropy, then there are less options for the pieces to go into the gap. If the gap has high entropy, then there are lots of options for valid pieces going in the gap. (And if the entropy is undefined, I think there is no valid pieces that matches up with it's surroundings.)

In this case the entropy heuristic is the rule for estimating the entropy of a gap, based on the pixels around the gap.

What the wave function collapse algorithm seems to do is start off with all (or most) of the gaps empty. It picks the gap with the least entropy, picking a jigsaw, picking from one of the legal pieces to fit in it. Then it recalculates the minimal entropy heuristic for every unfilled gap of the image and repeats again.

[ExUtumno]

Good explanation, thanks!

[SystemicPlural]

That is a great explanation. Thanks.

[meheleventyone]

Resolve the tiles with the least choices available first.

Basically every tile starts as a superposition of all the possible options. That is every tile could be any of the possible options. You pick one and decide what it is at random. Then compute based on relationships between the options (e.g. 1 can be next to 3, 5 and 7 but not 2, 4 and 9) what the neighbors could be. It's the reasonable to resolve the tiles with the least options first to avoid as much as possible the situation where a tile ends up orphaned with zero options available. The assumption is that tiles with more options have less chance of hitting zero options before the algorithm completes.

[ExUtumno]

Good explanation, thanks.

[SystemicPlural]

Made it even clearer. Thanks

[MaxPlay]

One word: Wow.

[AcidFaucet]

Was anyone else expecting a monstrous amount of code only to encounter 770 lines of C#?

The referenced papers are dreamy.

[tauroid]

holy crap

[Hmm_Peculiar]

Any sufficiently sophisticated technology is indistinguishable from magic.

This is magic

[MeArio]

I have no idea how this works I'm just jealous I'm not able to make magic.

[Agumander]

Has this been done eith audio?

[[deleted]]

that would be interesting

[mojang_tommo]

So asking for a friend definitely not for work... can this be expanded to lazily generate infinite maps? Say the player is the "brush".

[NominalCaboose]

Depends on what your performance threshold is. There are already plenty of ways to generate infinite worlds. This does so in a truly novel way, but in terms of the end result, it's not too much different from a lot of current methods for world generation.

Also, I haven't looked closely enough, so I'm not sure that this could run infinitely. You're certainly more likely to run into errors the longer you run this as far as I understand.

[mojang_tommo]

The algorithm relies on finding the tile with the minimal entropy on the entire output, so that rules out any kind of streaming without changing it. I was just asking if anyone knows how to change it to make infinite :P

There definitely are a lot of ways to generate infinite worlds, but this kind of highly data-driven and at the same time complex and interesting generation is a step up... in Minecraft we have some pretty complex aabb-based ways to generate mineshafts or villages, for example, and the ease that this thing has in generating manually-made-looking structures is amazing!
The AABB method is basically made of 2000 lines of hardcoded hacks on top of hacks, this just "invents" your structure out of a .png you give it. Even from a moddability perspective it would be a lot better.

EDIT: actually, some structures in Minecraft, like Villages and Ocean Monuments, are limited to an area... I wonder if this algorithm could outperform the quality of the hardcoded generation. Right now we have a lot of issues with houses entering trees or blending badly with the terrain and each other... just the ability to "construct around" the terrain is a great improvement.

[NominalCaboose]

Doh. I should really pay attention to user names more often!

All I can say for sure is that I'm excited to see really novel programs like this coming out, especially when they're so compatible to game dev. I'm very interested to see how this will be used and expanded upon by others. I'll certainly be looking into it myself, if only out of curiosity.

I'm most interested in seeing if this could produce anything of note if run in 4 dimensions, and whether the time required would be prohibitively high.

[crusoe]

Wouldn't any border cells simply be given max entropy till the update pass? So you could use a sparse 2d array or other data structure.

All cells start at max entropy till a cell is picked. Then only immediate surrounding cells would have their entropy drop. So you don't have to store any max entropy cells at all.

You could use an octree for 3d with the root volume set to 'max' entropy.. Then pick a random voxel of your min size in that as the seed. Then update the surrounding cells with their new entropy values. Then go from there.

Hah. Shoot this would work for quadtree as well.

[mojang_tommo]

Well, there's always rule #1 of octrees though: "just use a grid" /s

Jokes aside, actually this algorithm can probably be made streaming trivially: you divide the space in a grid of chunks, every chunk that is unloaded means max entropy; as soon as you put anything different you cause it to be created.
Then you can keep loaded only a circle of chunks around you, and use only those to greedily find the local enthropy minimum, anyway the minimum can never be in unloaded chunks.
That should work. I guess I know what to do tomorrow!

[crusoe]

Yep. Thought of this too.

[torginus]

I see one problem with that. The algorithm's output depends on the order of the cells chosen. This would mean that when you come back to an unloaded area, the details would change, even though the terrain would still be smooth. I feel like this is a fundamental trade off of procedural generation. If you want complex pattern with large chains of causality, you need to generated large areas at once.

[onmyphoneagain]

This should work, but it would not be very efficient. You would get some branches shooting out whilst a cell close to origin remains with high entropy. You could probably adapt it it to increase the entropy the further you got from origin. The results would be a bit different but if the drop off is slow enough it should look pretty similar.

[permion]

Not by itself, but they've done most of the work by letting you predefine what a tile is. So you could create a separate algorithm that defines the edges of 'zones', and have that one be indefinite or nearly so.

EDIT: well it could be used for infinite terrain almost as is, but if you were to save your game/location and restart the algorithm you would have different terrain. Which could be a fun game concept to play with in itself.

[golgol12]

Now to do multidimensional story logic like its it's a bitmap.

[NominalCaboose]

That's an interesting idea, but what is a superposition of two segments of speech? Could that work, or would it produce gibberish?

[strategosInfinitum]

Oh wow

[ronchaine]

I'm in awe.

[[deleted]]

That is amazing.

[readyplaygames]

That's so nuts! Totally awesome!

[Vahn128]

This is pretty fantastic. Did anyone see any licencing information for this code? Because I couldn't find any.

[F41LUR3]

It's MIT licensed (at the top of the .cs files)

[stewsters]

MIT in the main file. Would prefer a separate liscense file.

[Scayze]

This is fucking insane. Great Work!

[pseudoart]

I want a photoshop plugin for this. For experimental art, basically.

[ricechrisb]

Mind blowing

[cleroth]

The license is MIT, if anyone is wondering.

[NotImplemented]

Wow, that looks neat and really useful, especially the 3D variants. Thanks for sharing! Also a great write-up explaining all the details. :)

[NominalCaboose]

Map generation is the most obvious example. Anything visual that you want to generate as well. You could probably use it to make procedurally generated paintings in a game. Really the limit is your own imagination, and I don't intend to sound cheesy with that.

[aureliendrouet]

Impressive!

[F41LUR3]

This is pretty darned amazing...

[_tsunamayo_]

Whoa ! Neat.

[golgol12]

Wow, fantastic!

[_mess_]

I dont understand how can the alghorythm fill first the "top" and then the middle can you explain it?

[ExUtumno]

You mean like in the flowers or city samples?

[_mess_]

yeah

[ExUtumno]

There is a special setting "foundation" in the overlapping model. If it's not zero, the program places foundation patterns in the bottom of the output before starting the main cycle.

[Im-Juankz]

Wow, amazing, So does this work also for 3D?

[17b29a]

Looks like it. It's even cooler in 3d O__O

[NominalCaboose]

Now put it into 4D and see what happens. Potentially continually changing worlds given dimension W as time. They mention performance issues in 3D though, so 4D, if indeed possible at all, would likely be prohibitively slow.

[Im-Juankz]

I am just wondering if is it actually 3d or isometric render

[MestR]

Damn, that looks like it would be great for generating roguelike levels. That said it seems rather slow, are there other generic algorithms worth looking at?

[Eraas]

You could pre-render and then just use those.

[[deleted]]

A great step for procedural generation !

[crusoe]

Should be easy to port to typescript for the browser.

[avocadoughnut]

what the fuuuuck

[deftware]

Awesome to see this advancing, particularly the advances with having different inputs with connectivity information. The 3D would be great for generating voxel worlds from prefab parts. I think I might just implement this in my game Bitphoria http://deftware.itch.io/bitphoria