Adventures in Procedural Generation

Hi there! Saishy here again, today I will be talking about our work on procedural generation for TinyAttack.

If you played the prototype available for patrons you might have noticed the map is always the same, initially I decided that maps would be hand-made as to allow them to be aesthetic pleasing and interesting. While only randomizing location for chests, goals, start point etc.

What I would find later is that I’m actually horrible at level design… And TinyBird Games don’t make enough to be able to hire one.
The map ended up being too big and empty, nothing interesting, people would walk to one corner and away and forget where they were. The empty feeling would make them complain about the slow moving speed. It was a train wreck.

So, being a horrible level designer, a barely passable artist… The only thing left being a programmer I decided to finally go ProcGen!

So first was researching, I’ve received great help from Eniko (Creator of MidBoss, another RogueLike), and the following links:

Reading tons of articles and tutorials was a key point in choosing and implementing an algorithm.
And after pondering for a while I decided to go with the Cellular Automata for the first level, the GrassLands.

The initial attempts weren’t going well tho:

Considering blue is non-walkable area and green is the walkable one, you can see that those are not playable maps.

That was a result of somewhat confusing tutorials and me not really understanding what was going on. A few tweaks to the Cellular Automata algorithm and we get:

… It does look better tho! I mean, it’s actually playable, I think.

Reducing a little the map size and increasing the number of iterations done on the Cellular Automata eventually left me with those results:

I think those are the first good results I got, but I still thought it was too big for TinyAttack. Besides you can see it still generates isolated islands, which I will explain later how I dealt with them.

A little more tweaking on the size and iterations got me to the second batch of results:

Those looks much better! But I still think they were a tad too big and a lot of big open spaces with nothing ended up appearing.

For third batch I didn’t reduce the map size, but I did make it generate the horizontal and vertical sizes apart, adding a little of variety:

I think that really helped with the variety and interesting shapes, but it was still too random, a square map with big open areas would still be generated with a high chance.

To fix that was basically just playing around with map size and number of walls generated at the start of the Cellular Automata. It might still not be perfect but I think it’s good enough.

Then the next thing I wanted was to make some portion of the map into water, because the Grasslands map is a grassy area that ends into a portion of water.
For that I tried making a sphere and checking if a non-walkable tile was inside it, if it is turn it into water and Flood Fill the area (Flood Fill is another algorithm very useful for procedural generated stuff).

Also this is when blue starts to actually represent water:

So, the problem is obvious here, the Flood Fill is not working! But why?

Fixing it was very easy, let’s get this over already:

So now I got my attention into fixing the isolated islands problem.
Remember the Flood Fill thing? This is it now, feel old yet? I basically just got the first portion of walkable area nearest to the center of the map, once I got it I applied the flood fill to a full non-walkable map, changing the non-walkable tiles into walkable ones.

And done! Since the flood fill only traversed in the X and Y axis that means the result was assured to be fully connected, never having non connected areas.

Of course that is not perfect, and I found a fairly low chance of it generating extremely small maps due to the initial tile being actually inside an isolated place or the map having too many isolated places to begin with.
To fix that I just got the percentage of non-walkable tiles and if it passed a threshold I dropped the map and regenerated it. Remember that at this point the map is just a bunch of 0 and 1 on an array, not too heavy to regenerate again and again.

Here one resulting image for your entertainment:

It generated a duck: So that means it’s perfect already.

I wish! The next problem is that the walls of TinyAttack are composed of two vertical tiles together, but putting them in some places would actually block the player path!

Oops, so how do we solve that? My first idea was a way to check if putting a wall in that area would actually block the path. That was fast dismissed by Eniko on grounds of being too difficult, which I agreed after thinking a little.

Next idea was something I thought it was ingenious, clear the 3 tiles bellow a wall so the path is always walkable!

I’m a frigging genius! Is what I would like to say… Again reality shows that there are no easy ways out:

Damn, there is no way for it to known when digging is not necessary! So a single curve for either side can eat into it’s own area…

How the hell do I solve that now?

A lot more thinking, and I end up with the conclusion that I shouldn’t solve that, I shouldn’t even use that at all.
I’m already wasting too much time on this, let’s just brute force the solution!

So what I came up with is that all non-walkable areas will be extruded two tiles down, and those two tiles will be converted to walls later on.
Since at this part the Flood Fill check and percentage of walls check would still run after, I was guaranteed to get a playable map!

Dirty? Yes. Functional? Heck yes:

 

 

 

So now we put everything we did together and what we get?

Yeah that is starting to look like an actual playable map!

The next steps are mostly aesthetic ones, putting the borders on the high areas, putting the walls on the water areas, putting decorations etc…
Then selecting areas for the starting point, chests, shrines, portal, but those are much more game specific.

I hope you have liked following into what happens behind TinyAttack.
Please come back for the next article, and maybe support us on Patreon too!

Bye bye.

Liked it? Take a second to support TinyBird Games on Patreon!

Leave a Reply

Your email address will not be published. Required fields are marked *