Maze Runman is an action game in which the main character, referred to as the hero, races through a maze attempting to collect all the coins before being captured by a ghost. The ghost is somewhat slower than the hero but always follows the shortest path to reach the player, even if that requires suddenly changing directions as the hero moves about the maze. Each time the player starts the game, a new maze is generated, and some maze layouts may be more difficult than others: there may be long, dead-end corridors that the hero needs to navigate. One strategy for dealing with situations like this is for the hero to lead the ghost to the opposite end of the maze to give themselves enough time to make it in and out of the corridor before being trapped or cornered by the ghost . If the ghost makes contact with the hero, the player instantly loses, but if the hero collects all the coins, the ghost disappears and the player wins.

The game features a top-down perspective , and the player uses the arrow keys to walk north, south, east, and west. By holding down multiple arrow keys, it is possible for the hero to move diagonally, which may provide a small advantage depending on the layout of the maze. The user interface consists of a label across the top of the screen (above the maze area) that displays the number of coins remaining, as well as a large text message that appears in the middle of the screen when the game ends, displaying a message that depends on whether the player won or lost the game.

The game uses simple graphics for the game world, four-directional walking animations for the hero (similar to those used in the Treasure Quest game in Chapter 12), and a translucent animation for the ghost. When a coin is collected, a sound effect plays. In addition, there is a quiet ambient wind sound that plays in the background that gets louder as the ghost gets closer to the hero.

Beginning this project requires similar steps as in previous projects. In BlueJ , create a new project called Maze Runman. In the project folder, create an assets folder and a +libs folder containing the LibGDX JAR files (the latter not being necessary if you have set up the userlib directory). Add the custom framework files you created in the first part of this book (BaseGame.java, BaseScreen.java, BaseActor.java). In addition, you should download the source files for this chapter and copy the contents of the downloaded assets folder into your project’s assets folder.

The first and most important task in this project is to create the maze that the hero and the ghost will navigate. While in theory you could create a maze using level-design software such as the Tiled map editor, in this chapter you will instead write an algorithm that generates a new maze every time the player starts the game. One benefit to this approach is that it greatly adds to the replay value of the game; each new play session will be a brand-new experience. Techniques such as this fall under the category of procedural content generation : the creation of structured game content with algorithms. It can also incorporate techniques such as creating entire textures from code (rather than loading them from image files), but typically does not include techniques such as randomly initializing game-character parameters (such as enemy size or speed) or background scenery elements that have no effect on gameplay.

The overall process you will use for maze generation is as follows: first, you will create a rectangular grid of rooms (each 64 by 64 pixels large), where walls are placed on each of the edges. Second, you will remove walls between rooms in such a way as to create a maze: starting from any room in the maze, there should be a path the player can follow to reach any other room. Third, you will remove some additional walls at random to create multiple paths between rooms.

To implement the first step in this process, you will create a Wall class , followed by a Room class (which will contain four Wall objects and store references to the adjacent Room objects), and then a Maze class that will create the grid of rooms. To test it out, you will then create a LevelScreen class that extends BaseScreen, a MazeGame class that extents BaseGame, and a Launcher class to run the game.

Next, create a class called Room as follows. Note that there are arrays to store the walls and references to adjacent rooms (called neighbors), as well as a set of named constants to more easily identify which direction each array index represents. There are also methods for accessing and altering the data in these arrays.

Next, you will set up a class that will construct the maze, although at this point it will only set up the grid of rooms and set the neighbor data for each room in each direction, when one exists (rooms along the edges of the grid will only have three neighbors, while rooms at the corners of the grid only have two neighbors). Create a new class called Maze with the following code:

Next, you will extend the BaseScreen class to set up the screen that displays the game. The size of the background image is derived from the size of the maze, with an additional area on the top where the number of coins left will be displayed. Since the rooms are 64 by 64 pixels, and the maze is 12 rooms horizontally and 10 rooms vertically, this accounts for a region that is 768 by 640 pixels; an additional 60 pixels of height will be saved for the user interface. In addition, you will add the ability for the player to restart the game (by pressing the R key), which will be useful later on when the player wants to generate a new maze, or if the game ends and the player wants to try again. Create a class called LevelScreen as follows:

Next, you need an extension of the BaseGame class to load this screen . Create a new class called MazeGame as follows:

Finally, to run the game, you need a launcher-style class. Recalling the size of the background object from the LevelScreen class, create a new class named Launcher with the following code:

At this point, your project is ready to test. Run the main function in the Launcher class, and you should see the screen displayed in Figure 14-2.

The second step will be to remove a sequence of walls so that you can reach any room from any other room . One algorithm that can be used is called depth-first search . In this algorithm, one room is chosen as a starting location, and a room is called connected when it there is a path from the starting location to that room. The algorithm also maintains a list of connected rooms that have neighboring rooms that are not connected. The algorithm, in pseudocode , is as follows:

When this algorithm finishes, there are no more connected rooms with unconnected neighbors; all the rooms are connected! This algorithm produces mazes such as those shown in Figure 14-3.

As the name indicates, the depth-first algorithm creates paths that move randomly throughout the grid for as long (or as deep) as possible until the path reaches a dead end (a room with no adjacent unconnected rooms). At that point, another path will be generated, branching off from the room most recently added to the list. As you can see from the sample mazes in Figure 14-3, this typically creates mazes that contain only a few paths that are very long and have few branching points. In order to create more branching points , you could change the first line in the while loop to let currentRoom be a random room in the list. This will have the opposite effect: instead of only a few long paths, mazes will be produced that have very many short paths and lots of dead ends; some examples are shown in Figure 14-4.

The approach you will use in this chapter is a hybrid of these two methods : with probability 0.50, the algorithm will return to a random earlier room in the list. This generates mazes with medium-length corridors and more branching paths than the depth-first algorithm. Some sample mazes generated using this technique are shown in Figure 14-5.

In the constructor, initialize this variable to false:

Then, add the following methods, which will be used to set and check the value of connected, determine if any neighboring rooms are connected, and randomly select one of the neighboring unconnected rooms :

The final addition you will make to the maze-generation algorithm is the removal of a random number of walls . This is important to create looping paths, which will give the player multiple options to maneuver the hero around the maze and avoid the ghost that is constantly approaching. The results will be similar to the mazes pictured in Figure 14-6.

To accomplish this task, at the end of the constructor method in the Maze class, add the following code. The value of wallsToRemove may be adjusted as you wish.

At this point, the maze generation is complete, and you are ready to add the hero: the character controlled by the player.

The next addition to the Maze Runman game is the hero character , who will navigate the maze. The character will feature walking animations in each of the four compass directions (north, south, east, and west), seen in the spritesheet shown in Figure 14-7.¹

The code for setting up the animations and the logic for determining which animation should be used (based on the angle of motion) is identical to the code from the Treasure Quest game in Chapter 12. For further details, you can review the explanations in the corresponding section. Create a new class named Hero as follows:

At this point, you can test the program and press the arrow keys to move the hero throughout the maze.

Next, you will create a ghost character that will chase the hero around the maze. The key feature of the algorithm used to determine the path the ghost will follow is that it is the shortest path between the room occupied by the ghost (called startRoom) and the room occupied by the hero (called targetRoom). In this algorithm, the order in which the rooms are visited is very important: rooms closer to startRoom should be considered before rooms that are farther away. All the rooms that are one square away from startRoom will be checked first, followed by all the rooms that are two squares away from startRoom, then all those that are three squares away, and so forth. An algorithm that considers rooms in this order is called a breadth-first search algorithm , in contrast to the approach used for initially generating the maze, which used a depth-first algorithm. There are two additional practical considerations to take into account when searching for the path. First, since there are looping paths in the maze, you will need to keep track of which rooms have already been considered by the algorithm to avoid needlessly considering them additional times. This will be tracked by a Boolean variable called visited . Second, you will need to keep track of the sequence in which the rooms are considered when searching for a path: each of the rooms that are n+1 squares away from startRoom were arrived at after considering a room that was n squares away from startRoom. This information will be stored in a Room variable named previousRoom . This algorithm, in pseudocode, is as follows:

Once this algorithm finishes, the path can be retrieved as follows: set currentRoom to targetRoom and add it to a new list of rooms. Then, set currentRoom to its previous room and add this to the front of the list. Repeat this process until currentRoom has no previous room (previousRoom is null; this will only be true for startRoom). At this point, the list contains a sequence of rooms that form a shortest path from startRoom to targetRoom.

An example of this algorithm in practice is illustrated in Figure 14-8. The upper-right corner room, occupied by the ghost, is startRoom, and the room near the lower-left corner, occupied by the hero, is targetRoom . The rooms are labeled with numbers indicating the order in which they are visited by the algorithm and with arrows illustrating the previous room of each room. In the illustration, rooms 1 and 2 are one room away from the ghost, rooms 3 and 4 are two rooms away, 5 and 6 are three rooms away, 7 and 8 are four rooms away, 9, 10, 11, and 12 are five rooms away, and 13, 14, and targetRoom are six rooms away. Once the target room is located, following the sequence of previous rooms yields the path consisting of startRoom, 1, 3, 5, 7, 10, targetRoom—this is one of the shortest possible paths to the hero .

To implement this algorithm, each room needs to keep track of whether it has been visited in the algorithm and what the previously visited room was. To this end, in the Room class, add the following variables :

Initialize visited to false in the constructor method :

Next, you need some methods to get and set these new variables, as well as to retrieve all the adjacent neighbors of a room that have not yet been visited. This is accomplished with the following code, which should also be added to the Room class :

It is helpful to have a method that identifies the rooms in which the ghost and hero are located and resets the visited and previousRoom variables of each room, which is necessary before searching for a new path. In the Maze class , add the following methods to perform these tasks:

Next, you will create the Ghost class, which includes a method named findPath that implements the breadth-first search algorithm previously described. The method adds a sequence of actions to the actor to move it along the first few rooms of the path. The ghost does not follow the path all the way to the end, because by then the hero will have moved on to a different location. Instead, each time the ghost completes its current set of movement actions, the path to the hero is recalculated, and a new set of movement actions along this path is added to the ghost. Create a new class called Ghost with code as follows:

To integrate the ghost into the game, in the LevelScreen class , add the following variable declaration:

In the update method, check whether the ghost has finished its movements (when the ghost contains no more actions), in which case you activate its findPath method with the following code:

At this point, you can once again test your project and watch as the ghost moves around the maze, always moving closer to the hero.

Now that the maze is set up, along with a player-controller character and an intelligently programmed adversary, it is time to add a goal for the player , as well as win and lose conditions. As described at the beginning of the chapter, there will be coins for the hero to collect. If the hero collects them all, the player wins the game, but if the ghost reaches the hero first, the player loses the game. The first step will be to create the coins. Create a new class called Coin with the following code:

Next, you will add coins to the level, placing one in the center of each room. At the same time, you will set up a label to display the number of coins remaining, and while you’re at it, add a label to display a message at the end of the game. The positioning of the labels is illustrated in Figure 14-9, which shows what the screen will look like when the player loses the game .

To implement these additions, first add the following import statements to the LevelScreen class :

Next, add the following variable declarations:

In the initialize method, you will create a Coin object centered on each of the Room objects, set up the labels, and arrange them in the user interface table by adding the following code. Note the use of the toFront method so that the ghost renders above the coins, rather than below.

Next, in the update method , you need to check whether the hero overlaps any coins as well as update the label that displays the number of coins remaining. If the ghost overlaps the hero, then the player loses the game, and if there are no coins remaining, then the player wins the game . In either case, a corresponding message will be displayed. In the case of a loss, the player is removed from the stage. In the case of a win , the ghost is removed from the stage, and an infinitely-repeating delay action is added to the ghost so that its findPath method will not be invoked.

At this point, you have finished implementing all the game mechanics . Test out the game and see if you are able to win. You may find that you want to adjust the speed of the ghost or change the number of extra walls that are removed when the maze is generated in order to make the game easier or more difficult.

In this section, you will add some polish to your game in the form of sound effects . The first effect will be a quiet jingle sound that plays each time a coin is collected. Instead of background music, an ambient sound of rushing wind will play, and the volume will increase as the ghost approaches the hero to subtly build a sense of tension. To begin, in the LevelScreen class , add the following import statements. (The math-related classes being imported will be used when calculating the distance from the ghost to the hero.)

Next, add the following variables:

Also in the update method, you will adjust the volume of the wind sound. To calculate the distance from the ghost to the hero, you calculate the length of a Vector2 object from the ghost’s coordinates to the hero’s coordinates. When this distance is 64 pixels (which is as close as the ghost can get without overlapping the hero), the volume should equal 1. When the distance is 300 pixels, the volume should equal 0. Using some algebra, you can calculate a linear equation that converts distance to volume based on these values, as you will see in the code that follows. However, you also will clamp the volume level to a number between 0.10 and 1 so that the sound is always somewhat audible and never goes above the maximum possible value of 1. Finally, the audio should only be adjusted while the game is in progress, which is indicated when the message label is not visible. To accomplish these tasks, add the following code:

With this addition, you are ready to test the project once more to verify that the audio plays as expected. Congratulations on finishing the project!

In addition to the usual suggestions (adding a title screen, instructions screen, and visual and audio special effects), there are many refinements and additions you could make in this project. You could have larger mazes that are not entirely visible on screen to add to the challenge. You could add more ghosts to chase the hero, or have the ghost increase its speed as time passes (although the ghost speed should never be greater than the hero’s speed). To compensate for these additional challenges, you might want to introduce health points or extra lives, which would allow the player to be hit multiple times. You could also display a timer in the user interface so that, as a secondary goal, the player tries to collect all the coins in the shortest amount of time; this provides a more exact way for players to measure their skill and compare performance.

In the next chapter, you will shift your focus from advanced algorithms for content generation to advanced 2D graphics. In particular, you will add particle effects and image shaders and filters to improve the visuals in some of your earlier game projects.