Unleash the Adventure: Dungeon Generation in Gun Game

Table of Contents

1. Introduction
2. Initial Attempt at Dungeon Generation
3. The Walker Algorithm
4. Issues with the Walker Algorithm
5. Points of Interest Algorithm
6. Drawbacks of the Points of Interest Algorithm
7. The Search for a New Algorithm
8. The Tiny Keep Algorithm
9. Overview of the Tiny Keep Algorithm
10. Customization Options
11. Adding Handmade Rooms
12. Conclusion

Introduction

In this dev vlog series, we will be exploring the dungeon generation algorithm for a roguelike game called Gun Game. This game allows players to craft their own guns and use them to clear bullet hell levels. Developed in the Godot engine with C#, the initial attempt at dungeon generation was done using a modified version of the Walker algorithm. However, this algorithm posed certain challenges in terms of enemy placement and the positioning of start and exit points. This led to the exploration of the Tiny Keep algorithm, which offers a more efficient and effective solution. In this article, we will delve into the details of both algorithms and analyze their pros and cons.

Initial Attempt at Dungeon Generation

The dungeon generation process for Gun Game started with a modified version of the Walker algorithm, as explained by Heartbeast in a video tutorial. This algorithm involves a square that moves around the tile map, changing direction after a certain number of steps. To create a more organic look, the algorithm was adapted to use a circular brush. While this initial attempt produced visually appealing levels, it lacked the ability to easily segment the levels into different areas. Furthermore, placing enemies and defining points of interest proved to be challenging.

The Walker Algorithm

The Walker algorithm operates by marching a square around the tile map. Parameters such as direction change frequency, minimum and maximum step counts, and total step count can be adjusted. The algorithm paints tiles within the range of the walker, creating a rough layout for the dungeon. The circular brush modification adds softer and more organic edges to the generated tiles.

Issues with the Walker Algorithm

Despite the pleasing visual appearance, the Walker algorithm fell short in terms of practicality. It was difficult to determine suitable placements for enemies, and identifying logical start and exit positions proved to be a challenge. To address these issues, a new approach was needed in order to create more interesting and diverse dungeons.

Points of Interest Algorithm

To tackle the problems of enemy and point of interest placement, a custom algorithm was developed. This algorithm identified average tile positions and selected the most distant tiles as points of interest. These points were then clustered together while ensuring a minimum degree of separation. While this approach initially seemed promising, the resulting points of interest felt lacking and failed to add much interest to the levels. The algorithm provided a mediocre solution that did not meet the desired expectations.

Drawbacks of the Points of Interest Algorithm

Although the points of interest algorithm achieved a certain level of success in terms of spacing, it lacked the ability to create truly engaging areas. The points of interest felt arbitrary and failed to offer meaningful gameplay opportunities. As a result, this algorithm was deemed unsuitable for the dungeon generation needs of Gun Game.

The Search for a New Algorithm

In light of the shortcomings of the previous algorithms, a new algorithm was sought to overcome the challenges faced in dungeon generation. The ideal algorithm needed to address issues related to enemy placement, the definition of points of interest, and the segmentation of the dungeon into logical chunks. After thorough research, the Tiny Keep algorithm was identified as a potential solution.

The Tiny Keep Algorithm

The Tiny Keep algorithm, developed by the creator of a game called TinyKeep, offered a fresh perspective on dungeon generation. With the help of a visually appealing Reddit visualization and insights from the Gamma Sutra article, it became evident that this algorithm could provide the desired functionality for Gun Game. The Tiny Keep algorithm employs graph theory to connect rooms, creating a structure that facilitates the designation of special areas and points of interest.

Overview of the Tiny Keep Algorithm

The Tiny Keep algorithm follows a series of steps to generate the dungeon layout. Firstly, random rectangles representing rooms are placed within a certain radius of the origin. These rooms can be customized in terms of radius, number, and dimensions. A separation steering behavior is then applied to ensure that no rooms overlap with each other.

Next, the main rooms, which are the most suitable for gameplay, are determined based on their area. A Delaunay triangulation is performed between all the main rooms, which serves as the foundation for the graph structure of the dungeon. This graph contains information about how the main rooms are connected to each other.

To enhance the dungeon's structure and encourage exploration, a minimum spanning tree is created from the graph. This ensures that each room is connected either directly or indirectly to every other room without loops. To introduce some nonlinear paths, a random selection of edges from the Delaunay triangulation is added back to the minimum spanning tree.

After constructing the overall structure, hallway representations are generated. These hallways can consist of single straight lines or dual lines forming a 90-degree angle. Non-main rooms are checked for intersections with the hallway lines, and any colliding rooms are retained to be drawn on the tile map later. Finally, the remaining tiles are painted to create at least one block-wide hallway connecting the rooms.

Customization Options

The Tiny Keep algorithm offers several customization options. By adjusting the radius, number of rooms, and dimensions, the layout can be tailored to fit the desired gameplay experience. Additionally, the algorithm supports the inclusion of handmade rooms, allowing developers to combine randomly generated rectangles with pre-designed rooms. This provides additional creative possibilities and further diversifies the dungeon layout.

Adding Handmade Rooms

Incorporating pre-made rooms into the Tiny Keep algorithm is relatively straightforward. Instead of generating a random rectangle, a pre-designed room is used in its place. To ensure the room is considered a main room and not lost during generation, it needs to be appropriately categorized. This flexibility allows for the seamless integration of unique and carefully crafted room designs within the dungeon.

Conclusion

The Tiny Keep algorithm offers a robust and efficient solution to the challenges of dungeon generation in Gun Game. The ability to segment rooms into logical chunks and designate points of interest provides a solid foundation for diverse gameplay experiences. With the option to customize the layout and incorporate handmade rooms, developers have the flexibility to create engaging and visually captivating dungeons. As the development of Gun Game progresses, the algorithm will be refined and tuned to ensure the best possible player experience.