How did we use L-Systems to generate dungeons in our senior game project: Kastle.
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:
Start (S): The room where the player starts.
Challenge(C): A room where the player endures a challenge: Kill all enemies, collect all shards, etc.
Loot (L): A room where the player gets to collect a reward: New gun, magical spell, boss key, etc.
Boss (B): The room where the player faces the final boss of the dungeon.
Each dungeon generated had to follow the following four rules:
The Existence of a constant main path as follows: S - C - C - B
Total of 10 Rooms: 3 Loot Rooms, 5 Challenge Rooms, 1 Start and 1 Boss.
Every Loot Room must be preceded by a challenge room that is not on the main path (The design reasoning behind this is to reward the player for exploring more rooms).
Not a circular dungeon (Subpaths don't merge)
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:
Start with the initiator: S-C-C-B.
Choose any non-terminal symbol.
Apply any valid production rule. (Make sure you don't choose a rule that causes two rooms to overlap).
If (Challenge Rooms == 5 AND Loot Rooms == 3) GOTO 5 ELSE GOTO 2
END
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.
Read more about:
BlogsYou May Also Like
