The UEFI Maze Game, Part 3

This is the third part in a series of posts about a simple game written as a UEFI Shell application. It consists of generating a random graphical maze and navigating a little man through that maze from entrance to exit.

This post gets to the actual maze generation, which is actually a recursive function. Pick a random position. Then pick a random direction and, if that cell is completely surrounded, then mark the cell as a path. If there is no such cell in any direction, then back up. This algorithm generates that there are no circular paths through the maze.

Figure 10.40  Maze generation main function, part 1 in Game.c

Lines 272-280

This function gets called once for each grid cell. The coordinates of the current cell are X and Y.

Lines 282-288

The local variables keep track of which neighbors to the current cell. The number of valid neighbors and then the direction from the current cell. 

Lines 293-299

If the neighboring cell to the left is surrounded by walls, then it is a possible cell that we could go to next. So record the cell’s coordinates and increment the number of valid neighbors.

Lines 301-307

If the neighboring cell above is surrounded by walls, then it is a possible cell that we could go to next. So record the cell’s coordinates and increment the number of valid neighbors.

Figure 10.41 Maze generation main function, part 2 in Game.c

Lines 310-315

If the neighboring cell down is surrounded by walls, then it is a possible cell that we could go to next. So record the cell’s coordinates and increment the number of valid neighbors.

Lines 301-307

If the neighboring cell to the right is surrounded by walls, then it is a possible cell that we could go to next. So record the cell’s coordinates and increment the number of valid neighbors.

Lines 328-331

If there are no valid neighbors then we need to back track to the last valid position and try again.

Figure 10.42 Maze generation main function, part 3 in Game.c

Lines 336-340

Pick a random direction and update the coordinates in that direction.

Lines 343-345

Save the coordinates in the backtrack list.

Lines 349-357

Mark the maze in that direction as a path and increment the number of cells visited.

Lines 361

Now recursively call this function, but this time start at the next location.

Next Steps

Now the finish line is nearly in sight. We have the environment, we have the bitmaps, and we have the maze. Now we just need to draw it and move the man around.

Oh, wait. We haven't seen how to read the bitmap files or draw them with transparency. These functions are not provided within UEFI itself, so we will add them in a single post!