The UEFI Maze Game, Part 2

This is the second article in a series describing a simple UEFI Shell game that generates a random maze and lets you navigate a character through that maze to the exit. The goal is to show how to use graphics and the UEFI Shell together, line by line.

The next step is to initialize the grid and the maze. The maze uses two-by-two sections of the grid. These sections can have one of the following configurations

Notice that in each chase, the lower-right cell is always a rock, and the upper-right cell is always empty. The only question is whether there is a pathway to the right, to the bottom, or both.

Figure 35

Lines 407-423

This function divides up the screen into cells based on the size of the loaded bitmap images. If there aren’t e

nough cells to make a reasonable maze then the function exits with an error. The maze uses a two by two section for each part of the maze. In addition, the first row and first column must be all walls. This means that the number of rows and columns must be odd. 

Lines 425-434

The function creates the buffer for the maze bitmap.

Lines 436-441

The function creates the buffer for the maze grid contents.

Figure 36

Lines 443-448

Initialize every cell in the grid to a background image.

Lines 450-451

Display the empty background grid. This is important, because the other images (rock and player) need to be drawn on to another color besides black.

Lines 454-460

Initialize the maze generation data structures, create the random maze, copy that maze over to the grid and then free up the allocated data structures.

Lines 462-469

The entrance is at a random location on the top edge. The exit is at a random location on the bottom edge.

Lines 471-475

Now move the character to the entrance and draw it on the bitmap. 

During maze initialization, we create a temporary grid.

Figure 37

Lines 231-242

The temporary two-dimensional array mMaze holds either PATH or WALL for every location.

Lines 245-259

The backtrack arrays are used so that when we get to a dead end, the maze generator can back up to the last place where a decision was made.

Lines 261-269

Since in every 2x2 section of the maze, the bottom right cell is a rock wall, set that now.

These utility functions simply make it easier.

Figure 38

Lines 195-200

These global variables hold the maze and the backtrack data structures. The maze (mMaze) is a two-dimensional array where each element is set to either a path (PATH) or wall (WALL). The backtrack arrays contain the coordinates in the maze of the last point where a decision was made.

Lines 202-207

Utility function to return what is at a specific set of coordinates in the maze.

Lines 209-214

Utility function to change what is at a specific set of coordinates in the maze.

Lines 216-226

Utility function that returns whether there are walls in all four directions.

Now there are the two functions to generate the maze and shutdown the maze.

Figure 39

Lines 380-385

This function calls the maze generation function, starting at the upper-left hand cornder of the maze. Since each maze cell requires a 2x2 section of the grid, we divide both the height and width of the grid by 2. We subtract 1 because we leave one extra for the wall on the top and left of the grid.

Lines 389-394

Free up all of the resources used by the maze generation.

Next Steps

Now we have all of the pieces we need to generate the maze and all the parts to draw it. In the next article, we'll dig in to the heart of the maze generation function.

The UEFI Maze Game, Part 1

This UEFI Shell application features a very simple maze game that uses UEFI’s Graphics Output protocol to draw a random maze and direct a character from entrance to exit using a keyboard. It will be added to the SVN repository after the last article in this series is published.

This application features a few nifty touches, including converting bitmap (.bmp) files to HII, merging bitmaps using transparency and a nifty maze generation algorithm. This application uses both the standard C library, as well as UEFI-specific libraries.

This game doesn’t have any villains or time limits, yet. Originally, I planned to integrate the thermometer application previously discussed so that the main character got hotter and hotter and little ice cubs in the maze would cool him down. You can add villains in the maze, or the animation could move smoothly from cell to cell or there could be some sort of time limit.

The source is spread over two .C files. It also uses three bitmap files, which are included in the online source code. These bitmaps are: a rock, a player, and a solid green background.

The First Source File: Game.c

Figure 1: Global Variables in Game.c

Lines 1-13

These are the include files for the standard C library, basic UEFI services and, surprise(!) bitmaps. The MdePkg\Include\IndustryStandard contains constants, data structures and file formats from many popular industry standards, including PCI, ACPI and USB.

Lines 15-41

These are the key function declarations from the other source file, Bitmap.c. Rather than create a separate header file, they are just listed here.

Figure 2: Game State Data in Game.c

Next we move on the various global variables that maintain the game state.

Lines 46-47

DisplayImageStack is the global function that refreshes the screen from the internal buffer that holds the game’s bitmap image.

Lines 50-51, 64-65

These globals hold the width of the loaded background images and other images. These should be the same.

Lines 52-54

These point to the three bitmaps used in the game: the rock, the background and the player. Each is 50 x 50 pixels.

Lines 56-58

The game maintains a pixel-for-pixel copy of what is actually going to be displayed on the maze portion of the screen.  All of the player actions are updated here before they are copied to the screen. 

Lines 60-62

The game also maintains a cell-by-cell copy of what is in each part of the grid. The array mGrid contains a two dimensional array, mGridWidth cells wide by mGridHeight cells tall. Each element in the array points to one of the bitmaps: rock, background or player. The size of the array is calculated based on the screen resolution.

Lines 67-74

These mark the coordinates (within mGrid) of the character’s position, the entrance position and the exit position. Initially, the character’s position is at the entrance position. The game ends when the character reaches the exit position.

Figure 3 Game entry point in Game.c

Now that you are thoroughly bored with the global definitions, we finally reach the entry point of the game. 

Lines 590-596

This uses the standard C-style entry point. But there are no command-line options parsed.

Line 598

The srand() function is used to initialize the random number generator with a seed value. In this case, the seed value is derived from the system time. When debugging the maze generation algorithm, it was useful to set this to a fixed value so that the maze would be the same each time, facilitation easier debugging of issues.

Line 600

Reset the console so that the screen is empty.

Lines 602-606

Load all of the bitmap images and convert them into the format used by the UEFI graphics output functions. If there is an error, it means that not all of the images could be loaded or (less likely) the system cannot switch to graphics mode.

Line 608

Initialize the game data structures, including the maze.

Line 610-614

Display the maze for the first time.

Line 616

Enter the main game loop. This loop continues until the user indicates they are finished or they have reached the maze exit.

Line 619-621

Clear the screen and exit.

Figure 4 Setup bitmap images and Graphics Output Protocol in Game.c

The first step for the game is to load all of the bitmaps out of the files.

Lines 108-110

Find the instance of the UEFI Graphics Output protocol.

Lines 112-127

Load each of the three bitmaps from external files. Each of the files is formatted using the industry standard .bmp file format. 

Next Time

In the next installment, we'll look at exactly how to initialize UEFI's Graphics Output Protocol and load a bitmap.