In the senior year of my Software Engineering degree, I was excited to take on the challenge of making a large-scale game application. After hours of brainstorming, we came up with a very interesting game idea, but little we knew about the opportunities for learning this project is going offer. After eight months of hard working with a team of five talented students, we didn't only finish the project with a very high grade, but we also ended up being introduced to a variety of interesting problems in computer science. In this post, I am going to discuss how we used L-Systems to generate the dungeons of our 3D Roguelike game: Kastle.
Since our game was a roguelike, the first challenge we had to face was how to generate a variety of dungeons at run-time that not only look different but adhere to our game design specification. Before I introduce them, let me first define the types of rooms in our game Kastle:
Each dungeon generated had to follow the following four rules:
After some researching, we found that the best method to implement our specification is to use L-Systems.
According to Wikipedia, An L-system or Lindenmayer system is a parallel rewriting system and a type of formal grammar. An L-system consists of an alphabet of symbols that can be used to make strings, a collection of production rules that expand each symbol into some larger string of symbols, an initial "axiom" string from which to begin construction, and a mechanism for translating the generated strings into geometric structures.
To apply L-Systems in Kastle's dungeon generation, we are going to treat the first rule as our axiom or initiator. (Letters represent the rooms defined previously). Naturally, our terminal symbol is B.
Although our game is 3D, we can treat the generation space as a 2D Grid. So, each room can be connected in four directions: up, down, left, and right. Consequently, we will have the following production rules: (C* is a symbol for challenge rooms that are not on the main path).
Now, we can execute the following algorithm to generate our dungeon:
Here is an example of using the above algorithm:
Using L-Systems to generate our dungeons has proved to be both efficient and easy. I really liked how L-Systems elegantly captured our requirements, and I am really interested in researching how L-Systems could be used to create a framework that can be utilized by game designers to specify their rules and requirements for dungeon generation. Additionally, this framework could allow for the rules to adapt at runtime to the player's behavior and reactions, resulting in a more customized experience.