# Random mazes and third-person sapper, alien bugs and the Bresenham algorithm

Hello! I have been developing video games for over 30 years and regularly experiment with different game mechanics. As a result, I came up with the idea to create a game like a sapper, but from a third person and on a roguelike level.

Exploring a large space, you need to collect treasures, deal with the inhabitants and the security system. At the same time, it is important to avoid traps that can be calculated by numbers. Like in the game Minesweeper.

The game turned out to be surprisingly playable, sorry for the tautology. An interesting mix of action/arcade and puzzle/adventure. Let me tell you about a couple of algorithmic problems that arose when generating levels. The algorithms themselves are simple. However, it is interesting that they can be used in the game.

As the article was being written, I made animated illustrations and a test level that I inserted into the game. It turned out that you can play as a result of this article. I will be glad if you find it interesting, fun and / or useful.

## Mechanics

For several years I have been developing an open world puzzle platformer in the style of text mode. Computer consoles are placed in various places of the game, to which you can approach and run the programs and games available there. One such game is ASCIILL. The mechanics of the game can be easily understood from this animation:

There are traps on the field. Each number represents the number of traps in the eight spaces around it. Traps can be calculated, as in the Minesweeper game. However, unlike the latter, nothing needs to be cleared. The main thing is not to fall into the trap! The goals of each level can be different: collect all the coins, kill all the alien bugs, destroy all the lasers, etc. Thus, traps are part of the landscape, terrain that must be taken into account when exploring the levels of the alien temple.

## Traps and coins generation

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

Designations on the diagram: “@” – character, “\$” – coin, “x” – trap. Moving the character around the field, at this level you need to collect all the coins. But the random location of the traps blocked the passage to the right side of the field. The level is impossible to pass.

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.

Labyrinth 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?

## labyrinth

So, the maze is needed in order to mark in which cells to generate traps, and in which – coins. Therefore, both walls and passages must be cages. Labyrinths, where the walls are the boundaries of the cells, are not suitable.

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

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 on which the cursor is at the beginning of the game. We paint it. The filled cells will be the path of the maze.

At every step:

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

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

4. If there is a dead end, then we roll back until we stand on a cell where there are still options for directions of movement.

5. If there are no more options – that’s it, the labyrinth is built!

This animation well illustrates the construction algorithm:

In this illustration, the passages are marked with filled cells, because they are placed by the algorithm. Perhaps this is unusual, since walls are usually 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 what happened:

Now let’s add bugs to the level!

## beetles

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

The trajectory of the beetles consists of segments. Each segment is a line segment at a certain angle. Since the game is strongly tied to the cells, the bugs must move through the cells. The player must clearly represent the cell where the beetle is currently located.

Thus, moving around the playing field, the beetles, as it were, paint over the cells of a two-dimensional raster.

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

https://ru.wikipedia.org/wiki/Bresenham_algorithm

Such is the use of computer graphics algorithms from the 70s. The application seems, by the way, very authentic in a game stylized as a text mode.

Well, they added bugs, and you can play the level. Below is a 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

With each loss, the algorithm for generating traps and coins starts again. 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 such 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 will be happy to share later the method that I chose to implement such generation, since this is a separate story.

ASCIILL took the game out of the main game and designed it as a separate project. It turned out very cool. You can watch the game here: https://store.steampowered.com/app/1878770/ASCIILL/

The algorithm works quietly and at very large levels in several screens.