EPC2018 - Oskar Stalberg - Wave Function Collapse in Bad North

Presentation from Oskar Stalberg (Bad North) at the Breda University of Applied Sciences Everything Procedural Conference 2018.
Bad North is a procedurally generated strategy game about fighting Vikings. Oskar Stalberg will talk about how the Wave Function Collapse algorithm is employed to magically assemble idyllic island dioramas from handcrafted tilesets. You'll learn about the theory behind WFC, its implementation and further development in Bad North, as well as the tools and pipeline surrounding it. Lastly, Oskar will cover how he approaches the integration of art and tech aesthetically.

[@SirFloIII]

at 32:00 he foreshadows Townscaper. neat.

[@SkyArcherDev]

Oskar is a true professional, I am amazed by the effort he puts in Bad North, and not only for the things discussed in this presentation. Can't wait to play it!

[@arjuntyler1317]

instablaster.

[@MarcusRound]

It reminds me of the board game Carcassonne - like a competitive wave function collapse :)

[@Kufunninapuh]

Man I got taught Carcassonne wrong and have sort of hated it ever since. But looking at it as a wave function collapse makes me kinda wanna play it right now. Thanks for the perspective!

[@revimfadli4666]

Ah so that's the secret. Why do Eurogames somehow keep exploiting maths? :P

[@hi-im-kerri]

I've been following Bad North for a while, I've briefly come upon the Wave Function Collapse algorithm in my search for intelligent procedural generation for the use in dungeon crawlers. so this talk has been really interesting and how you demonstrated the algorithm has made it so much clearer than the existing documentation I've read. Sad the Cat game didn't pan out but Bad North looks super promising. Also, I'm a born and bred Manx gal, so seeing "Isle of Man" show up in your demo.... that makes me unnaturally happy.

[@lobrundell4264]

A thousand thank-yous for this amazing display of generosity with your knowledge! Even an interactive demo omg! I now got it working in Unity myself! :D

[@oddixgames6704]

This is insanely beautiful! Both aesthetics and tech level. Good job!

[@GriffinWiebel]

Great presentation. I only wish the camera would have switched to the screen only during his initial explanation of the collapse.

[@Grimthe]

Incase you are wondering, the presenter, Oskar Stälberg, made an a game based on his game “Brick Block” Called Townscaper. It launched into early access on June 1, and is $5.99 USD.

[@CatFish107]

Ha thank you. I was watching the looping vid at the start and thought it looked like townscaper. I was wondering if he worked on that one too. Lovely chill builder toy.

[@user-lf8yz8ze1v]

我超愛bad north 裡的建模的 超讚

[@t.m.1593]

Maybe I missed it, but can the bigger objects be cut at any mesh line and be recombined(if matching options exist)? Or are the objects finished and only the outside(?) mesh lines are considered?

[@cornuArietis]

Very cool!!!

[@remram44]

My understanding of WFC is that it's more general than this, it can look at arbitrary NxM cells, while this is just the 1x1 case ("simple tiled model" in the original repo). I still can't quite wrap my head around the general case...

[@KnitterX]

Correct. This version of WFC only takes into consideration which tiles can be directly adjacent. There’s also a more complex one that looks beyond direct neighbors and follows patterns. I’m still trying to wrap my head around how it works and how to implement that in 3D space.

[@sgbench]

In the most general sense, WFC is a constraint solving algorithm that's best suited for discrete-valued parameters. WFC consists of the following phases, which alternate until the entire parameter space is fully determined: 1. Collapse (choose a parameter and set its value) 2. Propagate (evaluate the implications of the parameter setting) Some considerations for the collapse phase: - How to choose the parameter (heuristics, weighting, etc.) - How to choose the value (ditto) Some considerations for the propagate phase: - How to represent the possibility space (whitelisted/blacklisted values for each parameter, global state, etc.) - How to handle constraint violations (backtracking, depth-first/breadth-first search, etc.)

[@raikitanaka1140]

Could anyone tell me what he said at 4:24-5:20? I've been trying to write the subtitles for this great video and translate that into Japanese. However, I am not a native English speaker, it is very difficult for me to listen English accurately from sound sources. I'd appreciate it if you could help me. Thank you for reading.

[@jaapstam]

"So, this is another early example of what I did there, so you see it's like building a little sort of city block, something like that . These to the left there, that's actually all the input modules being used, so it's not too many, it's quite quick to get started with it . It figures out how to put it together into different things . And this... since the algorithm is content-agnostic, fundamentally, it doesn't know that it's building a house, it's just knows that it needs to fit things together. It makes it, like, as an artist, you can build all these nice little, sort-of, transitions between things, and you can build extra little things, useless things, like you can build a chimney, and you can build a... Like, I have some larger features, of like, things going up here, this little, sort-of, divider here . So, yeah... you can build things like that, and then it will create larger structures from it"

[@raikitanaka1140]

@@jaapstam It was very helpful! Thank you so much!

[@Linck192]

@@raikitanaka1140 did the video you talked about happen? Do you have a link?

[@bagboybrown]

Doesn't matter what he said, this isn't even WFC it's Model Synthesis.

[@alphablender]

WOW. I MEAN WOW. AMAZING

[@DylanBurke]

Anyone know if this WFC example app is still available?

[@anonymoussloth6687]

Is the demo at 6:19 available somewhere or open source?

[@MaxSMoke777]

I have an abstract art style that works similarly. I start out with one large shape, then add some medium size ones in various locations on the canvas, then fill the in the rest with smaller shapes until I run out of space.

[@Raccoon0710]

Guys, I have developed wfc algorithm, its working, but I think its not enough to make such castles which shown on 4:23. In my case its looks more chaotic, I understand that there should be probable some additional rules or combining with different algoritms, am I right? What kind of rules there could be?

[@cosmicrdt]

As soon as the demonstration starts the screen changes to a camera where you can't see anything 😡

[@doup]

Minute 32 is explaining Townscaper?

[@pixboi]

WFC is like magic. Couldn't we implement some kind of self-architecting building robot with this? Just leave a bunch of materials around, leave, and come back to a ready built house. Is there some way to limit the use of tiles, eg. make a map with these resources: 4 grass, 4 houses, 2 rocks etc.? What if you have 4 walls but only 2 ceiling tiles? Will it then make a house with half of the ceiling missing? or will it just make a smaller house and put the extra walls else where?

[@NoahHornberger]

rule based logic means you can specify how it would use the materials. if there was a rule to only build things with full roofs, then the number of ceiling tiles would limit the size of the building created. but I think one thing happens when you start to imagine actually using this kind of thing: since humans have so many preferences for 'real' things, we really don't want bots making those choices. the owner of the land wants a certain shape, the user of the building wants certain features. Other than in games, there are many reasons for every design choice unless you are making art . . . then you can be quite random and it all works out.

[@sgbench]

Limited resources can be represented as additional constraints that are evaluated on propagation. However, the main limitation of WFC is that it's poorly suited to solving constraints on continuous-valued parameters. For example, parametric CAD software lets you place various geometric constraints on part features. However, due to the continuous nature of the parameters (lengths, angles, tangencies, etc.), they don't use methods like WFC to solve the constraints. Instead, they use analytic or iterative methods.

[@LucasSoaresy]

Someone know where can I find this Brick block game that appears on the beggining?

[@Hamfrags]

oskarstalberg.com/game/house/index.html There, I did a Google Search. :)

[@ThinMint86]

look up townscaper

[@bentgg03]

Townscaper

[@xsan698]

Oskar is a damn god

[@MuradBeybalaev]

Not really a new concept, but I love the way it's presented.

[@stefano8936]

Why the f the view is switched after 7 minutes?

[@teroblepuns]

This is Sudoku

[@johnstevenson5084]

lol, yeah it actually is.

[@RikMaxSpeed]

Finite-domain constraint solving with back-tracking - this was all sorted int he early 90s. But a nice application domain & demo.

[@freyappari]

This is exceedingly based

[@TDQ_Gaming]

"Wave function collapse" looks suspiciously like elementary cellular automata. en.wikipedia.org/wiki/Cellular_automaton

[@blackdragoncool]

How? The algos are both based on adjacency rules, but only WFC works with constraints.

[@danielkrajnik3817]

15:39 urgh finally

[@danielbloom2470]

I don't feel like this algorithm is as good as people make it out to be. It doesn't really seem original, it's just someone put more time into it than others. Lots of generators had constraints. The fact that they're using a recursive algorithm over trying to take advantage of noise seems inefficient.

[@Ash_18037]

Interesting presentation but I detest the way game development still seems to feel the need to borrow impenetrable, academic terms such as "wave function collapse" from other fields, seemingly just to give more credibility or weight to the work. Oskar himself (1:41) has no idea why his entire talk has anything to do with this concept taken from quantum mechanics. It just confuses and excludes interested viewers, turning them off the video/subject before they even start. Iin fact, the actual concept Oskar presents is quite easy to understand and useful to know about, quantum mechanics is utterly irrrelevant. The sad thing is game development already has all the credibility it needs in 2020. Stop resorting to high sounding, academically focused concepts just to convince somebody that "Please believe us, this is a serious profession, it's a real job".

[@johnsmith-zr2br]

he didn't give it this name

[@sgbench]

What would you propose as an alternative term for this constraint solving method? Perhaps "pick and propagate"?

[@peppermintgal4302]

There is a connection, though it's a fairly vague one --- its about superposition. Each module has a superposition that is then collapsed by the algorithm into a specific position. Sure, its not much more analogous than that, but I mean, the big bang isn't a bang, and black holes aren't holes. So what really is the problem?

[@peppermintgal4302]

Oh, I will add --- the term is still not technically accurate, in that the algorithm has no function that defines a wave, (or, at least, not necessarily.)

[@TommyLikeTom]

I don't know why but I feel this unjustified ownership over game design and art in the way that I feel like I made everything first, and I'm being cheated out of recognition for my efforts. I know it's delusional, it's just I want to express this irrational jealousy I have for every game designer and artist in the world. I have made quite a few things but I have lost a lot and had lots stolen from me.

[@DannysGalaxyTab]

Hey, just had a peek at your channel. It's literally all dog shit.

[@DootyDuck]

could you give me an example? its okay if u just wanna keep venting im only curious

[@Raccoon0710]

Guys, I have developed wfc algorithm, its working, but I think its not enough to make such castles which shown on 4:23. In my case its looks more chaotic, I understand that there should be probable some additional rules or combining with different algoritms, am I right? What kind of rules there could be?