UEFI News and Commentary

Tuesday, November 22, 2016

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.

No comments: