Cellular Automata | Procedural Generation | Game Development Tutorial

In this video, I explain what cellular automata is, how it works, and how to implement it.
0:00 Introduction
0:12 What are cellular automata?
1:44 How do they work?
6:16 Implementation
11:50 Demo
🔗 Demo:
whiteboxdev.github.io/bundles...
🔗 Source:
github.com/whiteboxdev/exampl...
🎬 Game Development Tutorial Playlist:
• Game Development Tutorial
#gamedev #tutorial #defold

[@WhiteBoxDev]

Errors in this video: 1. At 2:10, I state that there are four neighboring white tiles. Obviously, there are actually five neighboring white tiles. 2. At 7:40, the random number generation is placed on line three. This should instead be inside of the for() loop on line four so that each value in the noise grid is randomized independently.

[@clasherz_gut328]

deserves more attention, the way you explained this video makes it so useful. thanks a lot, i just implemented this into my 2d scrolling game and it is very cool

[@survival_man7746]

yeah I knew the caves shouldn't look spiky

[@LineOfThy]

@@survival_man7746 uuuuuh that's not the problem here

[@survival_man7746]

@@LineOfThy yes it is, maybe we just don't see the same way what I call spikey cave because I did "cave"/"island"/"whatever you use it for" generation more than one time and I know what it is supposed to look like under normal circumstances

[@LineOfThy]

@@survival_man7746 I don't know what you mean by spiky cave but I'll take your word for it.

[@svenskazengrodan]

I really appreciated all your map generation videos. Very pedagogical.

[@GbyP]

I really needed this so I can finally understand my CS projects for class

[@NikoKun]

Neato. The maps this generates remind me a little of the level design from the old Sega Genesis game Sub Terrania.

[@123a169]

This was super informative! I never realised how simple implementing CA could be. Definitely going to give this a try to smooth out my maps.

[@DrCaesarsPalace_MD]

So cool!! In the pseudo code at 8min you would want to regenerate the random number for each (i,j) cell in the grid 👍

[@DaveDude323]

Thank you so much Klayton. This video has really helped me understand how cellular automata works, and it is by far the easiest to follow tutorial on this subject on youtube. I like how rather than just writing actual code and talking about it as you do it, you use pseudo-code and break it down to explain in detail what each step is actually doing. Now that I understand how Noise generation and Cellular Automata works, I'm confident that I can work on making my own script in Unity based upon your information in this video for use in the Cave -crawling game I'm making.

[@sushismitcher225]

It's really cool, but I'm having performance issues. I'm probably going to create a chunk system so that the tiles only have to check nearby tiles, but I'd love to learn about other optimisation methods. Great video!!

[@chasehorton2324]

Extremely high quality video, you deserve many more subscribers

[@andisarifi5805]

great video!

[@mattzrsimon]

Dude. Great video! High quality explanations, editing and content. Keep it up.

[@NathoSteveo]

Awesome video mate thanks

[@spartianaleck]

Really good video and really nice explanation of cellular automata! I even realised an error I made in a game of life type of game I created a while ago! Thank you and keep up the good work!

[@axellacce1470]

Really nice video. Your voice is clear and audible and your explanation are detailed an quite easy to understand 👌

[@shenshaw5345]

Great explanation! Surprising how simple it is.

[@jahveen]

Nicely done tutorial

[@felipecruz9567]

nice explanation

[@nonameprojects1156]

Wow, such high Quality! i also used a different Ruleset that worked better for me... if neighbour Count > 4, updated Cell is alive if neighbour Count < 3, updated Cell is dead else updated Cell is last Cell For me it makes the generation much Smoother, but great Video after all.

[@paschalasobirionwu1183]

What do u mean by last cell?

[@nonameprojects1156]

@@paschalasobirionwu1183 the Last state of the cell that you are calculating. It means basicly: nothing Changes with the cell.

[@user-oh6jx7pl5k]

Thank you! This video so much helpful to me, that was simple but strong enough!

[@atjoo5375]

Omg, your explanations are so good. Even I can understand it.

[@WhiteBoxDev]

Thank you!

[@monkey7218]

Hi! Great video :D I know this is quite an old video by now but, do you know why you get quite "jagged" walls a lot of the time? Any clues on how to fix that?

[@sdbadik]

For every wall cell, try to apply this: If the wall has 0 neighbors to the left or right, destroy it. If the wall has 0 neighbors to up or down, destroy it as well.

[@daka.notatp]

i followed the tutorial... and it works! but my maps are mirrored diagonaly, from upper left to bottom right, anyone knows why?

[@marcuthdev]

14:00 como você fez aquele ruído ficar assim? Estou há alguns dias tentando fazer algo parecido em TypeScript, mas sem sucesso. É para gerar cavernas em um jogo como Minecraft 2D

[@emmaccode]

Nice. Well explained, good code. Thanks. This will be easy to reinterpret and implement :p

[@darkfrei2]

Thanks, it was very useful!

[@WhiteBoxDev]

No problem!

[@porcelainface7809]

Great video, I have a question hope it's not too dumb but how would a dynamic size of the caves be implemented, like some are smaller some are bigger

[@WhiteBoxDev]

The caves will naturally be different sizes, as demonstrated in the demo project. If you want to be able to have more control over the sizes, perhaps you could get a little creative and do something like: (1) Run the algorithm with a low wall density, which would result in a few large caves. We will call this gA. (2) Run the algorithm with a high wall density, which would result in several small caves. We will call this gB. (3) Using a flood fill algorithm, "erase" a few of the large caves from gA. Then, copy and paste those same areas from gB into gA. This would basically be replacing some of the large caves with several small caves, so you would have a mixture of both. That's just one method off the top of my head, I'm sure there are plenty other ways of going about it.

[@FacuDuck]

Hi, nice video, you know how to implement some kind of island gradient later on the generation?

[@diligencehumility6971]

Really helpful

[@calumlindsay]

Hey super simple way to get this to run faster would be to use a double buffer instead of creating a new array on each iteration if possible! Not sure if that would be optimised out if this is being compiled but if not might give a decent boost!

[@dualbladedtvrecords4383]

Unless you have huge maps (10k x 10k, or even more) then this boost is going to be negligible. And in those cases, the boost it gives would be far too low than the computation itself. And if you do get to the big numbers, then I think holding the whole map itself in memory is your next problem.

[@piercenathanlopez6285]

I recently got in touch with this topic in my elective class, and found it exciting! Although, can I ask you about your thoughts regarding cellular automata in a polar grid? I recently want to implement a CA of that liking. :)

[@WhiteBoxDev]

I don't have any thoughts about it because I've never thought about it! :) It would be an interesting project, though. Implementing CA on a polar grid looks like it would be more difficult than a cartesian grid. I glanced through a paper that talked about generating a model of a spinning hurricane from a top-down perspective. Pretty neat stuff.

[@piercenathanlopez6285]

@@WhiteBoxDev Can I get to know what paper you're talking about? Currently finding papers that have been using polar CAs as well to start with my project! :)

[@umtbmt2395]

Thank you for your tutorial, but i don't quite get it what's the difference between step and iteration?

[@WhiteBoxDev]

I use the two terms interchangeably.

[@LKamodon]

Great video! At 8:55 it was a bit confusing seeing the whole grid being re-generated from scratch as you narrated "you will notice as the iterations increases", maybe you could have increased the iteration counter by pressing 6 multiple times instead. I don't mean to be rude, just trying to provide a bit of constructive feedback. Thank you for making the video.

[@WhiteBoxDev]

Thanks for the feedback! Since the demos are not scripted like the rest of the video, my error-ridden brain takes over and thus we see some explanation quirks.

[@Microbex]

Thanks a lot mate. :)

[@spectrecular9721]

Any chance to get a tutorial on how to remove unconnected islands of a certain volume, and/or connect islands of a certain volume?

[@WhiteBoxDev]

Unlikely, however thinking on my feet, I might do the following: 1. Use flood fill algorithm to scan all areas on the map and keep track of their volumes. 2. Average the position of each tile in each volume to get the "center tile" of each volume (or somewhat close to it). 3. If any volume is less than some threshold, then it should be either filled (eliminate it) or connected to the nearest volume. Hope this gives you an idea of how to go about doing this. I'm sure there are plenty of alternative ways, but this would be my first approach.

[@spectrecular9721]

@@WhiteBoxDev ​Thanks for the advice! I assume after performing a flood fill (but before actually filling in the cells), the volume would simply be how many elements were to be filled? That's a lot simpler than I thought it would be

[@WhiteBoxDev]

@@spectrecular9721 Based on your term "volume", yes I figured you meant "group of similar cells". The actual connecting of distinct volumes would be up to your creativity. Glad to help. :)

[@TheOneWithComments]

Maybe someone can help me with this... after implementing the cellular automaton my grid looks like the end of a game of snake. It looks very square compared to what it is supposed to be. The noise part seems to be working fine but its the cellular automaton part that seems to mess up. The only part of the algorithm i don't fully understand is the "temp_grid" part so I'm guessing that may be part of the problem.

[@radiance_37k]

pseudo code: (hope this clarifies it) repeat for each iteration copy grid to temp_grid loop through each cell in temp_grid count number of walls surrounding cell if walls are less than 4, make this cell in grid floor else make it a wall Basically you are checking the neighbours in temp_grid and changing the original grid accordingly.

[@zephguo145]

I have a question here that in apply_celullar_automoton function: If I do not count the type of the current tile itself in. Then the neighbor_wall_count should be 0 to 8. And that's 9 status, an odd number. If the thershold is N_W_C > 4, 0，1，2，3, 4 -> Floor 5，6，7，8 -> Wall The chance of a tile becoming FLOOR or WALL seems not ot be 50 : 50. Becasue of that, as the iteration goes, I get less Wall and more Floor. Within 10 times, they are most Floor. But if we count the tile itself in. Then 0，1，2，3, 4 -> Floor 5，6，7，8 , 9-> Wall the generating chances are the same. And I got the correct map by doing so. Or did i misunderstand something in the algorithm? (I apologize for my poor English level)

[@WhiteBoxDev]

Whatever works for you, there is no strictly correct answer. If you count the tile itself and you like the result more for your particular use case, then feel free to do that. :)

[@FungIsSquish]

I had no idea dwarf fortress used cellular automata!

[@willculpepper9637]

The nested loops will continue until morale improves

[@vaibhavpandey6640]

hey u explained better than sebastin lague! hope I can implement something like this for my survival game made with pygame in python

[@ankanroy2931]

hey in line 7 and 8 what are the ...(3 dots) doing

[@shenshaw5345]

you're checking the previous & next value of both width & height

[@noahbrunner3431]

in what coding language is it written

[@WhiteBoxDev]

The demo in the video is written in Lua.

[@noahbrunner3431]

how to use it in godot

[@pbthroggy]

​@@noahbrunner3431 The code in the video is psuedocode, you just need to know how to code in GDScript. Take a Computer Science class for the basics of code logic.

[@pbthroggy]

​@@noahbrunner3431 You can also try teaching yourself, I would recommend Crash Course in Python as a starter.

[@piago1457]

what are i and j?

[@stormfath3r754]

I don't know if you still need an answer to this but, for anyone who does it's the initialization value of the for loop. i=1 in the for loop means your loop starts at 1. Any time you call i in the for loop it will return the value the loop is on. So if i=1 then it runs three loops when you call i it will return 3.

[@numero7mojeangering]

Need quantum computer to make this algorithm faster

[@haiweihe8737]

it can be gpu accelerated like neural cellular automata

[@jaxonpetersen5942]

The for loop makes no sense