Lazy Flood Fill | Procedural Generation | Game Development Tutorial

[@PolarTop6260]

bro this channel is so underated, this channel teaches you procedural generation methods you might of never heard of, that are simple to understand and looks very good, and also teaches you how to implement them

[@Sketchaphone]

what a simple yet effective tweak to generate landmasses. I was looking for different techniques for generating terrain and I'm delighted to see that a modified floodfill does the trick

[@icewizzard]

Just wanted to thank you for the video, really good and I'm using it in my project. First I set some interconnected nodes on the map. Then I colored an area around each of them to be the "safe zone", to make sure each node had its own minimum area. Next I used this algorithm to fill around each node, only adding neighbors that are already the right color or white(empty). This way, they don't "trample" over the safe areas. Finally, I check each node again for its neighbors. If at least one of the neighbors is from one the connected colors, I draw a green border between them. Otherwise, it is black. This gives me a map of countries, each with their own land and borders. Black borders are impassable terrain and green borders are passable.

[@juliendev2191]

Im not sure lazy is a proper description but it works :) great video !

[@romeo9015]

You are my FAVORITE KZbinr rn. I’ve been playing pygame recently and your videos have been instrumental for visualizations.

[@AntsanParcher]

A few changes I'd propose: 1. Have the chance variable be local to every tile on the deque. Reduce it only for the neighbors you push onto the deque. Implement it by pushing (tile, chance) tuples onto the deque. This makes the decay factor less sensitive. 2. Don't roll for pushing all neighbors onto the grid, but roll for whether to fill the current tile and recurse afterwards. As it is, the border of the filled region is made up of little crosses, which is kinda visible in the final result. Not sure whether it makes some border shapes actually impossible.

[@R.B.]

That was going to be my recommendation. I think the chance should be localized and maybe even influenced by the neighbors which have been visited. It might also be interesting if the chance were influenced by how many tiles of a biome were already laid, so that decay wasn't what governed the decision only and therfore you could keep the sizes as a constraint. It would also be an enhancement if the fill of multiple biomes were pushed to the stack to seed them all at once so that you didn't have overlapping zones, more like loosely defined voronoi. The stack would need to be able to search for existing tiles already queued, but then it would maybe give you more zones.

[@davdav4804]

Thanks man, your video is a blessing, I really look forward to try to implement this in my projects ! Thank you so much for sharing and explaining it so well because I work with Unity and I already have a vague idea of how I will try to implement it!

[@ABHISHEKSINGH-nv1se]

Simple graphics and algorithmic problem, This is what i like most. And that is why i like your videos. 😃

[@JohnMcChungus]

I love these videos, you're giving me a lot of neat ideas about alternative methods for world generation :)

[@Smarceloz]

Thank you for this. I was with my game development stopped, because I wasn't finding a solution to generate biomes on my map.

[@hamsterbyte]

Very interesting algo. I'm curious though, did you try any aside from exponential decay? Perhaps logarithmic, linear, or quadratic? I'm not suggesting there is anything wrong with this implementation as it is really quite clever, I'm really more interested in how the decay would fall off if it were implemented with another algo. Gonna throw you a sub for getting me thinking. Great job.

[@awesomegamedev]

Nice! Take 100th like:) I am surprised though, that you multiply chance by decay every single time, instead of only multiplying it when adding neighbors: deque.push_back() This would make the algorithm more symmetric (instead of biased towards the direction which you check first, and which correspondingly has the highest chance) and the value of change&decay have a more meaningful value.

[@Gandalf_Le_Dev]

Very nice tutorials I love them ! Could you tell us your approach to save procedurally generated maps ?

[@WhiteBoxDev]

No need to save them. The only thing you need to save is the seed used for the random number generator. To reproduce the same map, plug in its seed. If the world is changed for some reason (player interacting with the world), then the changed areas should be saved and reapplied when loading the map.

[@bike_n_fish]

Every time I discover a knew procedural generation algorithme I'm like a child before christmass wondering what stupid things I will do with my new toy

[@WhiteBoxDev]

The cool thing about procgen is that you can create your own quirky algorithms just by thinking of little tweaks that might align better with whatever you're making. There are many established algorithms, but what makes them really come to life are the little changes you make.

[@SyntekkTeam]

Nice video! I'm curious, in your game how would you use the black areas that are left open by the algorithm? I'd like to have my space to be completely filled, so my default is voronoi, but I like how organic yours looks, so I'm wondering if there's a way to combine both My initial thought is to execute multiple flood fills from random positions, where they each take turns stepping through the algorithm. To make it organic, flood fill would have to randomly select between the neighbors somehow (possibly biasing the select to neighbours closest to the fill origin? I'm not sure)

[@WhiteBoxDev]

In my mind, the black areas should be interpreted as flood filled areas as well. For example: if you use blue, red, and green in your flood fill which represent "ocean", "desert", and "forest" respectively, then the leftover black could be thought of as "plains" or some other type of biome. You could also do a scan of the map and perform more flood fills in the areas where black is detected until there is no black leftover. Just a few thoughts.

[@lastvirtualdomain]

im doing something wrong, the edges are great... but at large scales.. it looks mostly square.

[@disdis6127]

Great video

[@disdis6127]

Btw please make a video on A* pathfinding algorithm.

[@homelessdorito2263]

What did you do in your demo to get the generation to have more irregular shapes rather than tend towards circles? More irregular shapes would be ideal for my project

[@WhiteBoxDev]

The implementation I explained in the video is exactly what I wrote in the demo project.

[@homelessdorito2263]

@@WhiteBoxDev Thank you for the quick response! I am certain that I implemented it correctly; I suspect it might be due to a difference in math.random implementation in the engine i'm using. Looks like i'll need to find a different generation method