It’s time to get serious, or at least, as serious as a game with a mummified redneck as the main character can be. Today, I’m going to show you how we create the levels of Immortal Redneck, those spaces where you’ll be fighting all kinds of enemies with all kinds of guns. As you know, our game is an arcade FPS with roguelite elements, and what is more ‘roguelitish’ than randomly generated levels?
What we wanted
What we wanted and needed was obvious: a way of generating random maps with a lot of rooms and that didn’t repeat each time you played the game again. Sounds easy, it’s not. Seriously: it’s a damn mess. Thankfully, nowadays there are plenty of games with proceduraly generated rooms, so the technology and the development tricks are more common knowledge than a few years in the past.
Summarizing, what we are doing is designing specific rooms for the game (lava room, jumping room, trap room, chest room…) and using an algorithm to create different layouts proceduraly with them.
BSP it’s not for us
So, how do we generate the levels? We tried different ideas and programming tools, but we ended up with a very particular and a little unique one.
Each time you play Immortal Redneck you’ll get a different distribution, but the rooms that compose that map are designed by us. Think in The Binding of Issac, but with a lot more of sizes, doors position and such stuff.
We tried using Binary Space Partitioning, or BSP. Since it’s a very common technique used in dungeon generation, we gave it a try. It was great at first and we could insert our rooms into the random spaces it generated, but there was a problem: connecting them. This method required us to design corridors between each room and that’s something we didn’t like much.
To avoid this, we started dividing each space more efficiently so the room size determined how the BSP generated the spaces. This seemed like a nice solution at first because we could get rid of the corridors and just connect the rooms by doors. 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, this would prove to be a massive pain in the ass because of repeating patterns in the rooms distribution and more complicated stuff we couldn’t solve easily, so we dumped all of this and tried something different. Sorry, BSP, it’s not you: it’s us
How we solved this?
Instead, we tried another algorithm.
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. And within each new ‘generation’ of rooms, we would take the new doors and repeat the process until the floor is 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 maps without corridors. Unfortunately, as always, we had a problem: each map had really 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. Each level would be a horrible maze.
Then, we thought: ‘hey, why don’t we automatically connect those rooms that are really near in the map?’ It was a good idea, but we didn’t like the results. There were very little connections or very erratic one.
We had to go deeper and make an even more complicated algorithm. What did we do exactly? We changed how the rooms were placed by testing the connections with other rooms. So before placing a new one, the algorithm would test how it connects with those already placed in the map and then it chooses an outcome.
This way, the algorithm has a list of doors to connect and it will test a few new rooms for each one of them. Since each room can be connected through a lot of doors, the algorithm would randomly choose some of them to evaluate how well the doors connect with the previous generation of rooms. Then, it takes the best room in the best possible position available. That is, it chooses the room and the position with most connections with the previous rooms.
It’s kind of funny because if our algorithm would test all the possible room layouts, the out coming level would be always the same. After all, there’s only one ‘perfect’ combination! We made our algorithm more random by making his choices more limited, curious stuff.
Anyway, each time a new room is placed, its doors are included in that list of doors to connect, so 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.
So this was the almost final state of our algorithm. Even if this solution we made doesn’t make a difference in the first or the second generations of rooms – there would be very little doors to connect –, it’s a correction that radically changed how the map develops in the following ones.
Now, enjoy some examples of randomly generated maps! We made some isometric ones because the looked really cool!
The foundation for something great
I know this was a very techie devlog, but we thought some of you, specially those who develop games, would find it interesting. Playing with random stuff is always a pain in the ass, and we needed to share it, not only because we let off some steam but also because it might help some of you.
Immortal Redneck is going to push the player into messy situations thanks to all this stuff. The randomness of our maps would test you ability to adapt to different situations because even if you know how a room is designed, you don’t know how enemies will spawn, what kind of price is behind a door nor how much rooms are left until you reach a new floor.
We’ll talk about all of this next week so you can see the rooms themselves, so keep tuned. And follow us on Twitter and Facebook, just because.
