Friday! New devlog! This one is goddamn cool because it's about really technical stuff and such, and more precisely, about how we create our randomly generated levels.
First thing: we mean levels, not individual rooms. Like The Binding of Isaac and other games, our rooms are not randomly created, they are designed by our team, but the way they are placed on the map each time you play the game is random.
That said, let's talk about algorithms!
BSP it’s not for usWe tried using Binary Space Partitioning, or BSP. It was great at first and we could fit our rooms into the random spaces it generated, but there was a problem: connecting them. Initially, this method required us to design corridors between each room and that’s something we didn’t like much, so we started dividing each space more efficiently.
We got rid of the corridors thanks to this, but another problem appeared: the more room sizes we inserted, the more unused spaces appeared. This was just a geometry problem: if we had one space with a certain size to divided in and three room to insert into it, placing one of them would determine the others two.
At the end, BSP was a pain in the ass and the layout were not good enough for us, so we dumped all of this and tried something different.
A new, better algorithmWe tried another algorithm, obviously.
Given an initial room with ‘x’ number of doors, this new level generation algorithm would connect those doors to new ones that are randomly chosen from new rooms. And within each new ‘generation’ of rooms, we would take the new doors and repeat the process until the floor was filled. This left some unused spaced, but nothing really problematic.
It was a rather easy process and we loved it because we were able to create great, random maps without corridors. Unfortunately, as always, we had a problem: each map had very fixed courses. For instance, in an ‘initial’ room with four doors, you would go only north, south, east or west. And once you went all the way in one direction, you would have to backtrack and take another course.
That's when we thought: ‘hey, why don’t we automatically connect the doors on those rooms that are really near?’ Didn't work out. Instead, we changed how the rooms were placed by testing the connections with other rooms before placing a new one.
This way, the algorithm always has a list of doors to connect and will test a few new rooms for each one of those. Since each room can be connected through a lot of doors, the algorithm would randomly choose some of them to evaluate how well they would connect with the previous generation. When it has the best room with the best position with the most connection with previous rooms, it place it.
Each time a new room is placed, its doors are included in that list of doors to connect and the algorithm keeps going and going until it fills all the given space. Yes, this would have a exponential impact on performance, but we solved this issues and now it doesn’t take that much processing time.
Now, enjoy some examples of randomly generated maps! We made some isometric ones because the looked really cool!
A gif of the map generation. This is the algorithm when it didn't connect the rooms properly and there was a lot of backtracking.
This is the final algorithm working. Rooms connect properly, there are a lot of paths to follow and the layour is great.
More layout tests
Isometric view! Looks like and old spectrum game :__)
Now, two examples of the room generation with lighting and stuff. Didn't insert them as gif because they were really heavy. Oh, and this rooms are a little more repetitive because we only have four final rooms yet
Community
