I Made a Wave Function Collapse Castle Generator in Godot

[@RachelfTech]

This was another fun project! If you'd like to support the channel and get access to project source code, I just made a Patreon: www.patreon.com/RachelfTech. Thank you in advance for any support over there, but also just for being here and watching my videos, I really appreciate it! 🙌

[@sonOfLiberty100]

I wanted to suggest you CNN or GAN's, but it takes to long time to train them. What you can use pretty quickly are Markov Chains. You have then to provide examples or have the transition weights. In my opinion with this approach you would avoid to build in the middle of the grass or have empty space like her 23:02

[@beastbomber2316]

Ive spent a lot of time programming procedural algorithms in the past for games. I would suggest combine Wave Function Collapse with another algorithm to automatically generate a floorplan on the castle. Then set the bottom objects to those rooms. This will make a more organized castle generation. Look up dungeon generation algorithm to find a good one if this is a path you want to take.

[@MrHaggyy]

I was tinking similar. When engineering a building you also build a hirachy of constraints and requirements. Like how many people will live in the castle. Then you derive what rooms they need and how big those needs to be. Then alignment etc. By making this hirarchy you eliminate design choices that would be possible, but not what people want. Like butting the bathroom as a connecting room between your door and your kitchen.

[@jackturner7814]

Game dev (Tech artist) here: What is the wave function collapse algorithm? I only know the term from beginning quantum mechanics...

[@b3agz]

The eternal problem. "This works and I have no idea why... do I leave it?" 😂 Great video.

[@MacronLacrom]

sometimes it seems like it only works when you type random things that have nothing to do with anything

[@Pallerim]

The joy you exude explaining your projects is super contagious and inspirational. I am currently working on my own desktop pet, inspired by your previous project (mine is a squirrel).

[@RachelfTech]

Thanks so much! That's awesome to hear! 🐿️

[@rmt3589]

I hope you make a tutorial. Any advice? Wanna make one myself.

[@Saitir942]

I do appreciate the tight but not miniscule scoping you use for these projects. Enough so that it's not just 'wow, look at this cool algorithm' (although depending on who you talk to some of that sort of thing might work well for the youtube algo gods), but not so much that you only release one video every 3 years. Hope you can remain excited about things!

[@jtw-r]

100% and I love that she recognises that she has done enough in a day, and should come back with a fresh set of eyes.

[@RachelfTech]

Thank you! I'm still figuring out what scope works best for these videos, but I do like how they've been turning out so far! I'll probably continue doing a mix of projects around this size and a bit smaller; aiming to post around once per month :)

[@Saitir942]

@@jtw-r Yeah, that's a great additional point. It's soooo easy to burn out all that early enthusiasm just pushing for one more feature/bug fix... "Morning" brain is a much better investment!

[@Saitir942]

​@@RachelfTechI'm sure you've looked into this way now than a casual viewer has, but if I've learnt anything about KZbin channel growth from people's 100k,1 million retrospectives is mainly that it's never quite what you thought it would be, but as long as you can bring the same enthusiasm to the the idea that works, you can at least keep the mental health in decent shape. I'm sure you learnt a lot of those lessons from your guitar channel though!

[@Fubes]

I love that you show all those struggles, imperfections and "I have no clue what I'm doing" situations of game design. You are super smart about the algorithm part but when it came to Blender I had to laugh because so many of us "techies" with no art background came across those same problems. Like when you said "I had to UV-unwrap my tiles but had no idea how to do" and then proceeded to do everything wrong, I just felt that so much :D

[@Nikrobaby]

Next project: Ok..I was not done with the Castle Generator... Amazing project! I understood like 5% but it was really entertaining to watch!

[@RachelfTech]

😄, thank you!

[@Groufi]

Love to see this project growing and you growing along

[@RachelfTech]

Thank you! :)

[@MaximumAxiom]

I appreciate your videos, you do a good job of keeping it entertaining without really hiding your debugging journey. I also like how you go about troubleshooting. For instance, your approach to visualize the algorithm isn't something I almost ever do but it seems really wise to figure out what's going on.

[@RachelfTech]

Thanks so much!

[@JamieBainbridge]

"It doesn't work and I don't understand why". "It works and i don't understand why". The programmer's dichotomy 😅

[@CoryTheSimmons]

This is such a great project. Thanks for sharing your process and it looks great!

[@itsduno0001]

I'm starting to notice a pattern in your love for squishy birds. I absolutely love these projects and the progress you are making on them. Keep up the great and inspiring work, it's so exciting to see.🐥

[@RachelfTech]

Thanks so much! 🐔

[@MatthewDempsky]

Great video. I appreciate the part about pop_back vs pop_front, and that you returned to it rather than just letting it be. I've seen too many engineers who just accept the "seems to work solution," when they can't explain why alternatives fail. The name "wave function collapse" is quite silly though. I know you didn't name it, but I hadn't heard of it before, and the first few times this video showed up in my feed I assumed it involved quantum mechanics somehow and skipped over it, figuring it wasn't a practical technique.

[@DavidLindes]

Neat! Fun to see both your process and your result. And the click-on-bird thing is totes adorbs. :) Subscribed!

[@sonodrome]

Great video! Love the project, the result turned out beautiful!!! When you were dealing with all the tall towers and thinking about how to reduce their frequency, it immediately made me think about weighted randomness, which is ultimately what you implemented. A real simple way I often go about this, is by generating two random values and always picking the lower of the two values, this will give you a linear distribution where the higher the value, the lower its frequency. If you need more of an extreme, you can just do the lowest of 3, 4 or more values, and that will give you more control over it. Anywho, love your work, especially all of the generative stuff, keep em coming!

[@RachelfTech]

Thanks so much! That's a cool way of handling weighted randomness, thanks for sharing!

[@superparadox]

ive had this in my watch later for weeks and im glad i finally watched it this is dope im subbing

[@galathiil]

New to Godot but a developer with some experience, I discovered your channel today and I'm already a fan! I devoured all your videos. I like your way of seeing things, solving problems and explaining concepts, it all speaks to me a lot. You seem to be a curious person, who gives 200%, who does not hesitate to rush headlong even into an area that you do not master, to search again and again to find THE solution and then share it. A true soul of a developer, rare, precious, never lose that. Unfortunately, my financial situation does not allow me to help you but know that my heart is in it! PS: Sorry for the quality of the English, it's not my original language. Google helps a lot but I don't know if I managed to transcribe all the expressions of my language.

[@RachelfTech]

Thanks so much for the kind words, I really appreciate it! It's great to hear people are enjoying the format of the videos :)

[@Lazdinger]

This is so freaking cool. I think the most interesting part for me was the bug hunting.. the visualizer you made to see exactly what the algo was doing. So satisfying, so cool.

[@stuaxo]

This looks great fun, it's really good having something like this + just building and building.

[@evanandrews8858]

This was a dope experiment to try out. Learned a lot without having to struggle to sort it out myself hahaha. More! More!

[@Frank_G_Finster]

This wasnt only fun to watch, but also very inspiring. Thank you very much for sharing! 🙂

[@RachelfTech]

I'm so happy to hear that, thank you!

[@juanurdaneta9844]

woah! really interesting surprise to see this channel after I followed your other guitar channel, I had to come into the video and see the guitars to really be sure haha, your channel was an inspiration for me to get back to guitar playing and I've been getting back into gamedev so it's really cool to see this!

[@RachelfTech]

Glad to hear people are randomly finding me here too! So cool to hear, thanks for watching :)

[@jlmonolith]

This was the first time I've seen wave function collapse, so thanks for the explanation!

[@michaelschlachter8865]

I tried to do some WFC stuff before and hit all the same things you did, and then I gave up! Your video is inspiring me to take another crack at it. you rock!

[@Katzenha]

I barly understand a word, but I love what I see (generators are SO awesome!) and your happy energy. :)

[@thedeadman6171]

YOU are my favourite youtuber ever sooo helpful

[@BrianHaddad]

You are quickly becoming one of my favorite game programming channels. Keep up the great work and thank you!

[@RachelfTech]

Thank you so much, I really appreciate it!

[@SeanStClair-cr9jl]

This video is so relatable and awesome. I was obsessed with the idea of a WFC castle a while ago, and I am glad there are non-lazy people like you to actually put ideas like that into action

[@Gijontin]

Okay, just found this channel with this video, love it, subscribed!

[@R4venshore]

That looked like fun! Well done! I've done a ton of procedural generation, for no good reason really. One thing I recently did which was a lot of fun and really challenging, was generating whole cities, with streets and buildings. Especially if you want to streets to not be a perfectly square grid.

[@RachelfTech]

Thank you! That definitely sounds like a fun project as well, something I'd like to experiment with in the future too!

[@cashewolddew]

Such an exciting project! Well done 🥜

[@RachelfTech]

Thanks so much! :)

[@barrystan3682]

Another excellent video. I've always been fascinated by procedural generation. Reading Notch's devlogs of creating Minecraft map generation was inspiring. I never understood exactly how it worked, but I do understand how to solve Sudoku (made my own solver years ago). I could follow what you were doing, but tackling something like that is way beyond me atm. Still struggling with TileMaps. Was fun to watch you get it working. Learning of EditorScript will help out in duplicating all my TileMapLayers while trying to create a season transition using tileset crossfades in my current project. Probably a dumb way to do it, but I don't know of a better one yet. Seeing the tools you use helps us beginners out.

[@HansMilling]

Cool project. The thing is, when doing these PoC’s or small demo projects, you learn so much that will make you even better at the next project. I’ve been coding software for many, many years, and it’s funny how we all struggle with the same problems solving the code. I hope, whoever build these AI tools will focus on AI that can spot these mistakes we make, so coding will be a lot faster in the future. Right now AI is only good for making boiler plate code. I use Blender for Isometric tile sets. I use a sun ray instead of a point light to ensure that light fall equally on the models to not have the shading on a flat surface change. I also put all tiles into the same Blender files in different groups and build a script that will show, rotate and render all tiles from four angles.

[@DapperDilanzo]

Youre a huge inspiration for a godot game developer like myself!! Keep making awesome stuff

[@RachelfTech]

Thanks so much, I really appreciate it!

[@quentinarrius]

That was fantastic to watch! :D

[@whizzie3928]

"but I was struggling with this and decided to take a break" is so relatable lmao

[@ReasonMakesMusic]

This is so cool! I remember when Townscaper first came out I was so impressed by this kind of algorithm. Super fun to see more of this!

[@JacobJustice2141]

I didn't really understand the algorithm itself until I saw the "debug" visualizer with the red blue and green blocks, then it all clicked for me instantly. Great video!

[@RachelfTech]

That's awesome to hear, I'm glad the visualizer helped!

[@DJMankiewicz]

This is an awesome walk through for something I've wanted to grok for a long time. Thanks!

[@platibyte]

I ran into the same problem with WFC not being able to finish the generation. I used a red symbol with no constraints that was placed when no solution to the existing WFC state could be found. Then created new tiles to fill the gaps for these cases. It was like 15% more tiles i needed in the end.

[@derBartzer]

Nice video which I enjoyed watching!

[@ChrisBrown-si1vg]

Very cool video. I've just started using godot and am really impressed with what can be done in it.

[@BoredDeveloper]

I love your videos, keep it up!

[@RachelfTech]

Thank you!

[@iamsushi1056]

Another WFC video, what a good day

[@sketchonk]

narrator rachel: now I decided for real I am done devlog rachel: now for real I am done these cuts make me chuckle

[@Illusion-clock]

your smile is contagious, I keep smiling I dunno why

[@rafikR85]

Wow ❤ this project is so cool - hats off girl 😊👏❤️ Im not in game dev thats random pop probably 😅 but your passion speak for themselve - very inspiring 😊

[@ashishnair97]

Saw Townscaper and wanted to know how to and your video was the best learning experience... Thanks for you work 👍

[@RachelfTech]

Awesome to hear, glad it was helpful!

[@_mickmccarthy]

Awesome work! WFC is such a cool algorithm for procedural level generation, never used it myself but always looked like a very fun thing to create. Well, a full thing to have created, I always imagined it being a frustrating thing to actually create/debug due to all sorts of weird edge case possibilities!

[@RachelfTech]

Definitely ran into some frustrating debugging moments 😅, but it's really cool when it comes together!

[@BananaftRu]

Thing hovering on top of grass is the grass texture wrapping around and showing bottom row of pixels on very top, you can fix that by switching texture sampling from wrap to clamp.

[@gametail]

respect, I tried to implement this aswell and failed miserably on the constraint generation. You made it look so easy lol.

[@GreySectoid]

As a fan of procedural generation this was very enjoyable to watch, seeing so much progress in half an hour feels like programming with super powers :)

[@josh2878]

Your videos are so entertaining. I love how happy you are talking about programming, it reminds me of The Coding Train.

[@RachelfTech]

Thanks so much!

[@KasperFrandsen]

This was lovely!

[@RachelfTech]

Thank you! :)

[@Kry0000]

This was a very fun and informative video, thanks for sharing.

[@RachelfTech]

Thank you! 😁

[@mtrxishere]

How are you so talented at everything!??

[@Mark73]

There was a company called Subversion that build a city generator, all the way down to the insides of buildings. Looked really good. The only problem was that they couldn't figure out a way to build a game around it.

[@Haakkon]

Great video! Pretty sure the normal map for your bricks is flipped in the Y direction. The depth might be inverted as a whole but I think the Y direction is just flipped which is why they look odd.

[@merthyr1831]

I WILL LAY DOWN MY LIFE FOR SQUISHY BIRD

[@janikarkkainen3904]

Great project! My only nitpick is that seems to me like the brick texture has the seams going out instead of in - so either the normal map or the normals themselves should be inverted. A great spot to see this is at 24:13

[@badsamaritan8223]

I think you could add more rules/constraints that could make more castle-looking structures. Things like, requiring it to create an enclosed geometric shape, walls on the outside are always shorter than walls on the inside, corners always have a tower, etc.

[@jakebrooks3415]

This is sick! I tried to implement a wave function collapse map generator myself and like you said i totally overcomplicated it. I was trying to generate constraints using a python script in blender that would identify vertices along the edges of some very low poly pieces and would calculate if it lined up. Looking back it was definitely a failure on my part to understand that WFC should generate constraints from an example output lol

[@JoshGVarg]

worked on something similar in college but much simpler definitely was a fun challenge translating the high level algo into actual code

[@_Draven]

Absolutely gorgeous😦

[@Fighka303]

You make games now! Awesome!

[@sammysofa1511]

woooweeeee very impressive! nice project

[@neogoo123]

Really cool stuff! The final product looks really nice, and it was interesting to see some of your findings! I have to say, I'm quite confused as to why it was faster to pop off the front of the array rather than the back... makes me think it was implemented as a queue instead of an array. I also feel like there's gotta be a faster way to propagate those constraints, but don't know what the algorithm would be off the top of my head. I feel like it'd be something related to adding the tiles around a changed tile to a stack and see if any of their constraints change, adding the tiles around *that* to the stack if it indeed did get more constrained. Edit: Just remembered doubly-linked lists, couldn't have been implemented that way

[@RachelfTech]

Thank you! I think in my case it's not that the pop front operation itself was actually faster, just that the algorithm ended up being able to resolve constraints faster in that order compared to the other way around. And yeah, I'm sure there are optimizations you could do to speed up the propagation! It's definitely not the fastest algorithm in general, but I also didn't spend much time thinking about optimization for this project.

[@ReginaCæliLætare]

Those are some crazy looking castles

[@theagemaway]

Instead of picking a random point in the 3d space, run the WFC from the bottom layer first, then as it gets taller, eventually only the columns under the spires will be left, and they'll naturally choose a top.

[@davidmaaschdeyck]

these birds look HILARIOUS

[@NADLABS]

Going down the rabbit hole of bird click = tweet is too relatable

[@FOM_extras]

omg this is so cool!!

[@ThinkWithGames]

Cool video! Is it true that pop_front was always faster? Or did it just so happen to be the case in a few examples? (I thought pop_back was always faster, though maybe your implementation didn't make that the case)

[@RachelfTech]

pop_front as an operation should be slower than pop_back, but the way I wrote the algorithm it seemed like processing constraints in the order set up by using pop_front was still always faster than the other way around. I didn't test this extensively though!

[@CharlesVanNoland]

I've done a lot of procgen projects over the last 25 years but only recently have I started experimenting with hydraulic erosion. It seems obvious to me that the kind of mountain ranges you see in California or the northwestern coastal USA should be computable with a hydraulic erosion algorithm that's lattice-based, but I've really been struggling getting it to not just look like rock formations that have eroded into sand. Including a talus angle helped, but I still haven't been able to get those sharp angled ridges forming properly, which is what I'm going for. I assumed that IRL they form by large shallow flows eroding, and the erosion narrows as it grows deeper - but apparently the opposite is what happens. Instead, a narrow stream forms and stuff basically falls into it, while it keeps eroding deeper, resulting in the classic V-channel and angled ridges. Anyway, just thought I'd share a little bit of info about what I've been doing since you've shared your pursuits with us randos on here :]

[@ruthmoreton6975]

Hah, I ran into the exact same bug ( pop_front vs pop_back ) I mistakenly assumed that pop_front would get the last item pushed onto a stack whereas it actually gives the first. I've been procedurally generating mazes using a depth-first algorithm which seem to be similar to wave function collapse as constraints are added to adjacent cells based on the current cell.

[@AverageDrafter]

Every time I see one of your titles I think "Hell yeah you did!"

[@Imevul]

I would have constrained the algorithm to start from the bottom and work up. That way, you wouldn't have the problem of randomly selecting a top grid cell that you _have_ to place something in. Usually, that's how buildings are constructed: from the bottom up. You could even add dynamic rules such that a wall tile is only valid as long as it doesn't have 5 or more wall tiles below it, or a spire can't have 5 or more spire tiles below it. Then you could better control the different castle size parameters. Might be difficult to save those kind of rules as a resource though. The suggestion from one of the top comments to generate a floor plan first is a step up from that as well.

[@NexusBaum]

the fractured castle definitely has some appeal to it :)

[@nicklansbury3166]

Thanks. I really enjoyed watching this video.

[@RachelfTech]

So happy to hear, thanks!

[@KrytenB]

good job! keep it up!

[@Lion_McLionhead]

Good idea for a beast.

[@softgripper]

This was a great video :) Thank you.

[@RachelfTech]

Thank you!

[@veorEL]

You did good!

[@redshepard5306]

your freaking awesome.

[@isaacewing]

very nice work ***hand-clap hand-clap hand-clap***

[@needlessoptions]

Hii great work !! just wanted to feed the algorithm and also say I love that I can actually hear you smiling all the time when you talk 😆😁

[@RachelfTech]

Thanks so much!

[@multiarray2320]

are you planning to continue your computer science/godot journey or is this just temporary? id love to see more videos like this from you ❤

[@RachelfTech]

This channel is going to be my main focus for the foreseeable future! Will be trying to do at least one project/video a month :)

[@multiarray2320]

@RachelfTech thank you so much. i really appreciate this a lot!

[@weaponizedemoticon1131]

Man, that orientation problem in Blender is so familiar. :P Cool project!

[@DanielLCarrier]

Add floating islands. Preferably with lakes and waterfalls.

[@morgan0]

if you generate the tiles from bottom to top, you’d probably get a more realistic set of tower heights

[@RachelfTech]

That is probably true! I was selecting cells to collapse based on which had the current fewest possible allowed tile options, which must have led to higher up locations being chosen more often. Could definitely be worth investigating changing how the collapsing order works or implementing some sort of more complex probability system.

[@tom-sawyer-999]

Wow, impressive!

[@Kavukamari]

maybe im projecting my own tendencies, but in the timelapses i can't help but imagine some of the faces you make as just "i can't believe this... why won't you just work"

[@mattmmilli8287]

Bucket list item to learn this 😭 so many ideas forever. No time tho

[@fokeyjo]

I wondered about doing generated castles after seeing Townscape. It certainly looks fun to try, but I think the constraints of wave function collapse possibly aren't enough, in that they're great for filling in smaller details, but the bigger picture isn't working. E.g. you need castle walls to form contiguous enclosements. So as others say, there's another algorithm needed somewhere, or maybe several iterations of the WFC algorithm run at different scales of the structure. Maybe you can achieve it with components collapsing that aren't visible, like "inside-of-wall air" blocks?

[@RachelfTech]

Yeah you could definitely do more with it/modify the algorithm to make things more traditionally castle like! Would be interesting to explore further :)

[@EmbeddedSorcery]

Ok this is cool. Imagine a Minecraft-like game with a megalopolis biome.

[@lunerjuice1832]

It would be so cool if the generative castles were a maze players could try and solve. They could either start from the outside trying to make their way to the center or from the center trying to make their way out. Adding more birds of varying colors could also be a fun way to earn points, it would be super cool if the birds only generated along paths that "could" lead to the end. Oh! And if it needs a story element it could be a Kind or Queen player looking for their missing crown. Or a little Knight character searching for it on their Majesties request. Each play through would be different keeping it interesting with a near limitless number of unique levels for one to go through! Okay now to step away from my own head for a moment lol, this was so much fun to watch. I felt like I learned something, I won't lie and say I'm gonna try this myself but I definitely wan to give it a try sometime in the near future. Just need to figure out where to start before diving in head first. Love the concept, 11/10 bird design, look forward to the next vid. :)

[@Serhii_Volchetskyi]

You can try using a SAT solver for wave function collapse. It’s a bit of overkill though.

[@Serhii_Volchetskyi]

1) Google already implemented the algorithm in C/C++, BTW. 2) With the algo, you might implement way more complicated collapsing algorithms like multiple conditionals, physics corrections, etc.

[@Serhii_Volchetskyi]

To understand it, see video from AlphaPhoenix about Game of Life.

[@troligtvisme]

Fun! :D You could add a "Hide and seek" mode where you have to look around the castle to find the bird, once found/clicked the bird will find a new hiding spot :))

[@RachelfTech]

That would be fun! 😁

[@Tapsin]

Quick advise: Your normal maps are inverted by the end of the video, you just need to invert the green channel in photoshop or anything similar. I think Godot uses open gl normal map format and yours were maybe done for direct X :D

[@RachelfTech]

Interesting, will take a look, thanks!

[@RachelfTech]

@@Tapsin Looks like my normal map was indeed for Direct X, good catch! I'll just leave as is for now but good to know for future projects! Thanks :)

[@Tapsin]

@ oh yes it was just a tip for future Rachel. Amazing videos by the way

[@RachelfTech]

@@Tapsin Thank you! :)

[@MattHudsonAtx]

you had me at perlin noise