A new way to generate worlds (stitched WFC)

I've just come up with an interesting way to make terrain for the island in my game and I haven't really seen anyone do it like this before so I'm excited to share it with you right now I use noise to create islands that look like this this looks fine but noise usually looks repetitive without a ton of extra coding I want to be able to create a tiny sample and have it randomly generate terrain based on that sample maybe in little chunks since I'm concerned about borders between biomes looking straight this could help us we could place one biome next to the other and have the generator automatically figure out what the mixture should look like but how do I do this easily luckily I stumbled across the wave function collapse algorithm which is perfect for this so what is wavefunction collapse it's this fancy algorithm where you feed it an input like this and it can create similar looking outputs based on what it learned from the input this is super fancy since I can just make a little patch of forest and have it generate me a whole random Forest pretty cool stuff and it's not nearly as complicated as it may sound here's a quick overview of how it works all the algorithm does is take a list of rules of what can be next to what and make an output pattern so let's say we have these tiles water a beach a forest and a mountain and we we tell it that a water tile can only touch Beach tiles a beach tile can only touch water in forests a forest tile can only touch beaches and mountains and mountains can only touch forests you then have an output grid like this where every option is equally possible any tile can be watered a beach a forest or a mountain you pick a random one to start you'll then notice that your options nearby get reduced since only forests can be next to mountains all of the neighbors of your new Mountain have less possibilities you choose the one with the lowest amount of options and collapse it into a choice let's randomly pick Forest these new changes propagate outwards to the neighbors again and now it must be either a mountain or a beach see the idea if we keep doing this we end up with a fancy new design it's kind of like Sudoku sort of in this example I hand wrote these rules but we can instead give it an input pattern and it figures out the rules itself the results kind of look like machine learning but it only needs a single input image it's super fun to play with now this seems really fancy but it does have its limitations take this little sample with the tiny rooms here when we tell it to go and make stuff that doesn't look quite right at a large scale like here are all these parallel paths that we don't want and there's this little disjointed room here it just isn't right the algorithm is really good at repeating patterns on a small scale but that's about it you can also give it a partially completed output and it'll fill in the blanks for you I'm sure you can now see the magic for how this could be used for my sectors I can have a forced sample generate a forest sector have a desert sample generated desert sector and then we can have a special Stitcher take a look at what's already placed and fill in the gaps based on our special desert to Forest sample we made this all sounds cool but let's give it a try and see if it even works first things first I made a little thing where you can place down some objects in a grid and use it as input then spent two days coding like crazy I assume had something working here's a sample where I enter this little line pattern and it outputs something that perfectly follows my input now it's time to try making a forest I made this little sample here and got it to generate a bunch of forest tiles as you can see it left a bunch of gaps between them I like how it looks so far and they all look unique enough but similar to the sample one next up I made it use that same pattern to stitch all the boxes together I think it looks pretty good there are some places where you can tell it was stitched but overall it seems fairly seamless so all this seems great and it seems to be worth working but we have a major problem it's insanely slow when I make a big enough map say a thousand by a thousand tiles it takes five whole minutes to finish that's right it would take five minutes to create an island that honestly might even need to be bigger this is completely unacceptable and luckily I found a way to speed it up to just four seconds but before I dive into how I've got a word from our wonderful sponsor for today's video Southern New Hampshire University I personally commuted to school and had to drive an hour every day spend 30 minutes looking for parking walk up this insane Hill and sit through classes that could have been a 20-part YouTube series I would have traded my soldiers to do it online instead and that's exactly what snhu offers their online courses make it so you don't need to leave your precious cave and it's pretty affordable they have all sorts of degrees but I imagine most viewers here will be interested in computer science or game development they've got classes that cover programming physics graphics and interface design basically everything you would need for a 100 legitimate degree the classes are also taught by industry professionals so you'll get some wonderful connections to people in the industry who might be useful later on all of my engineering jobs have gone with their connections at school so I personally found networking to actually be important but yeah this sounds interesting at all there's a link in my description below so feel free to check that out anyways back to the issue at hand the algorithm was taking way too long to run since it's pretty complicated to fix this I headed to the Discord server of Boris The Brave Boris is a bit of an expert on this sort of thing and I reached out to see if he had any insight to help speed things up he recommended I try unity's burst compiler to give it some extra speed I'd hardly use the burst compiler before so this was a bit of a learning experience for me but here's what it is basically c-sharp isn't the fastest language it has lots of tools and features that make it easier to use and these make it slower Unity lets you write code that doesn't use a lot of these features so it can compile it into something that runs much quicker it also uses unity's job system which allows your entire CPU to do these tasks in parallel instead of doing them one at a time I'll show that later the only downside is you have to write code without using all the useful features this took a little while but I finally got it working and let me tell you I was blown away by the results here are some stats before using the burst compiler getting it as efficient as I could it took an average of 3.05 seconds to do a 100 by 100 map this means a full-size map would take about 5 minutes I then implemented burst and was super sad to see it took 4.3 seconds for the same test it got slower I was banging my head into a wall until I realized I was doing something incredibly stupid I was basically making a bunch of temporary variables doing the calculation then disposing of those variables then the next four sector would come along and I'd redo the same thing I should have been keeping the variables that I can reuse instead of time remaking them after taking this into account it did 100 by 100 tiles in only 250 milliseconds that means I could do the entire map in around 30 seconds since the unity editor uses a fair chunk of the CPU I exported the game and on its own it did the full map in only four seconds lightning quick here you can see it doing all these little sectors in parallel each one of these little boxes is a single run of the algorithm it's clear that doing them all at once is multitudes faster than doing them all in a straight line I'm curious to see how it does on computers with a weaker CPU I imagine the average will be around 15 to 30 seconds I may try to find some people in the Discord to help test things like this so feel free to check it out and maybe hop in I give testing priority to patrons but may occasionally ask everyone and while I'm Shilling for interaction make sure to like comment or subscribe to get the algorithm to like me so now that we've got it working it's time to try mixing different biomes I drew up some quick desert jungle and Beach assets mostly temporary and put them in the game I mapped out some samples for how a dense normal and sparse desert will look and did the same for the forest and jungle I also made samples for what the borders between regions should look like we can generate and it gives us something like this you may notice I use purlin noise to decide where to place each sector in the future I'll probably do this a bit more manually so I can have more control over the paths some places look a bit goofy but overall I think it looks natural enough the borders between zones aren't Flawless but I think tweaking my input images will help a bit I'm also not in love with how boxy everything is from a distance but maybe I can experiment with sectors that are a bit smaller than 10 by 10. overall I'm pretty happy with how it's turning out I shaped it into a circular Island which in the future will likely be more organic and try the beaches I think they look alright a little lumpy but that's also fixable this is super exciting because if I want to change how everything looks or how many trees there are I don't need to go into the code or hand erase a hundred trees I just have to change up this one little sample and I can add an endless amount of interchangeable sectors to spice things up now my world generation mostly involves moving around these interchangeable puzzle pieces which makes things much easier this may seem like decent progress for the four weeks since the last video but I'm not done yet I also take a stab at some simple dungeon generation I started by brainstorming what types of dungeons we'd want first off we we want some simple ones with just a bunch of rooms mostly connected by paths with maybe some branching I'd also like to be able to define a shape and have a generator that can fill it with interesting rooms maybe for like a boat or something lastly I want some that resemble Villages where it's just a bunch of separate buildings and maybe a wall around everything there are probably more ideas but that's a good start I began by making the first type since I want dungeons that don't feel very generated I'm gonna hand make most of the rooms in a simple one I'd like to maybe have a boss room that's handmade an entry that's handmade and then a pool of handmade middle rooms that can be chosen from this way every time you play The Dungeons are a bit different and contain different stuff I got it working and you can see here that the dungeons look pretty decent please ignore that it's made out of wood for now I haven't made any dungeon assets yet and of course if I get lazy I can use wave function collapse to maybe create some variety in the rooms this type of structure will mostly be found underground so it looks a bit out of place on the surface but I'm still pretty happy with it now I've decided to save the other two dungeon types for later to focus more on important gameplay type stuff it's just nice to know that it works and it helps me set up some other important code my plan is to focus next on Armor farming live livestock fishing trapping pollution power-ups character customizations skill trees and boss fights then all the core bones of the game will be present and I can make all sorts of tweaks and play tests before adding in the actual content I also want to announce that my brother Mike is unfortunately too busy with school and work these days to continue helping with the music stuff so for now it's just me I searched a bit for some composers including those who've reached out and decided to commission something from Ricardo from rmd compositions he did a fantastic job with a general Goblin e Forest theme and I wanted to play a bit for you guys I asked for something that had tinges of goblin new Vibes without being overwhelming a very subtle 8-bit influence and similarities to things like Terraria and stardew I also wanted an air of optimism but with a bit of weariness towards a looming thread of human Invasion lastly I didn't want it to be too melodic and rigid here's a bit of what he ended up with [Music] thank you [Music] thank you [Music] you get the idea overall I really like it and I'm curious to hear what you all think as well I put his links in my bio so feel free to check out some of his stuff he's very talented but without everyone we reached the end of this month's changes don't forget to check out the seriously outdated steam page for the game clean up an aisle Goblin and wishlist if you want to get notified when the game releases and of course do all the YouTube stuff to make the algorithm like me if you leave a comment I get a notification on my phone no matter what so make sure you make my pants vibrate thanks everyone for dropping by and I will see you all next time hello everyone the time has come to shout out our Eternal and gracious patrons I'd like to give a super special shout out to our Goblin deity patrons for March of 2023 namely Zachary niece Zach Fox Sarah Kraken fall Brett Hudson Jackson Singleton Matthew Spencer bertiti Joseph scabi Megan Palmer Samantha fallen and random8408 you're all amazing and I appreciate all of the support

Channel: Watt Designs

Views: 515,107

Keywords: devlog, development log, indie gamedev, indie game, developer, unity, programming, making games, procedural generation, perlin noise, indie, goblin game, cute goblin game, goblin stardew, cleanup on isle goblin, isle goblin, goblin, wave function collapse, wfc, dungeon generation, multiplayer, algorithm, wfc algorithm, constraint solving algorithm, sudoku

Id: dFYMOzoSDNE

Length: 10min 51sec (651 seconds)

Published: Tue Mar 21 2023