Random labyrinths and third-person minesweeper, alien bugs, and the Bresenham's line algorithm

Hello! I've been developing video games for over 30 years and like to experiment with different game mechanics. As a result, I came up with the idea to create a third-person minesweeper-like roguelike game.

In the game, players explore large maps to collect treasures while dealing with monsters and security systems. They must also avoid traps by estimating their positions through numbers. Like in Minesweeper.

The game turned out to be surprisingly fun! An interesting mix of action/arcade and puzzle/adventure. It's based on a few simple algorithms, but applying them was sometimes tricky. I'd like to share some of my experiences with you here!

While I was writing this article, I created animated illustrations and a test level that I inserted into the game. So, the result of this article can be played. It would be great if you find the article interesting, fun, and/or useful.

Mechanics

I have been developing a text-mode style open-world puzzle platformer for several years. All over the game, there are computer consoles and players can run on them various programs and games available there. One such game is ASCIILL. This animation demonstrates the mechanics of the game:

There are traps on the field. Each number shows the number of traps in the eight squares around it. Traps can be calculated, as in the Minesweeper game. But unlike the Minesweeper, you don't need (and cannot) mark any traps. The main thing is not to fall into a trap! The goal of each level can be different: collect all the coins, kill all the alien bugs, destroy all the lasers, etc. Thus, traps are just part of the landscape, terrain that must be taken into account when you explore the levels of the alien temple.

Generation of traps and coins

What happens if you just accidentally scatter traps and coins around the field? Like this, for example:

Notes: "@" - the hero, "$" - coin, "x" - trap. You need to collect all the coins by moving the hero around the field. But the random placement of the traps blocked the passage to the right side of the field. The level is impossible to complete.

The generation algorithm must provide a passage to each coin, regardless of the field configuration. How would you do it? I'm sure there are many ways. My choice can be summed up in one sentence:

We generate a random maze. We randomly place traps on the walls, and coins in the aisles.

This method guarantees access to all coins, bypassing the traps. At the same time, the maze itself is not visible to the player. He is not required to walk the paths. In the picture above, for example, you can immediately take a coin by moving two cells to the right.

Maze passages help solve the most difficult situations, providing a 100% chance to complete the level. What kind of maze is needed and how to generate it?

Maze

So, to distinguish the cells in which we must generate traps and coins, we need a maze. Therefore, both walls and passages must be cells. Mazes, where boundaries of the cells serve as walls, won't do.

The main requirement for the structure of the labyrinth is that it must be connected. Each cell on the passage must be accessible from any other cell on the passage.

Among the many algorithms for constructing such a random maze inside a given shape, the following one seemed to be the most suitable:

1. We start from the cell in which the cursor is placed at the start of the game. We fill it. The filled cells will be the passage of the maze.

At every step:

2. Choose a random direction (up, down, right, left) in which two consecutive cells are free.

3. If such a direction is found, then move to these two cells, filling them.

4. If there is a dead end, then we roll back until we find a cell from which there are still options for movement.

5. If there are no more options - that's it, the maze is built!

This animation illustrates the construction algorithm:

In this illustration, the passages are marked with filled cells, because they are placed by the algorithm. This may seem weird because usually cells with walls are painted over. Sorry!

After I figured out this random arrangement of objects in the level to illustrate the algorithm, I wanted to see how the level would look in the game. Here's the result:

Now let's add bugs to the level!

The Bugs

Bugs are micro-bosses that move along their own trajectories. They are blind unlike the big boss. Bugs do not see where the player is. However, if you stumble upon them, you lose.

The trajectory of the bugs consists of segments. Each segment is a straight line at a certain angle. Since the game is strongly tied to the cells, the bugs must move through the cells. The player must clearly understand in which cell the bug is currently located.

Thus, moving around the playing field, the bugs fill the cells of a two-dimensional raster.

It's funny, but to calculate the cells through which the bugs move, you can use the Bresenham algorithm. Wikipedia explains it perfectly with examples:

Bresenham's line algorithm

So, computer graphics algorithms from the 70s were used. It seems, by the way, very authentic in a text-mode styled game.

Well, we've added the bugs and now we can play the level. Below is a video with a level walkthrough. The level is small and simple - good for learning at the beginning of the game!

As you can see, I also added TNT to get rid of the alien bugs moving according to Bresenham's algorithm.

Conclusion

The algorithm for generating traps and coins starts over after each loss. The landscape of the level, visible as numbers on the field, is different each time.

However, you can also generate a random shape of the level, as well as the presence and location of bugs, lasers, water, objects, etc. I made a "Challenge" mode in the game, in which a new random level is generated every day. Moreover, this level is the same for all players around the world.

We can say that the random level generation parameters are a hash of the current date. The date uniquely determines the parameters of the random number generator, which guarantees the same random levels on any device.

If you are interested, I'll be happy to share later the method that I chose to implement such generation, since this is a separate story.

I took the game out of the main game and made it a separate project. It seems to be very cool. You can watch the game here:

ASCIILL on Steam

The algorithm works perfectly even for very large levels.

Thanks for reading. Bye!