CC Blog Projects Research & Design Hub

Build a Maze Generator and Game

Using a PIC32 MCU

During the pandemic, many project designers met the challenge of doing team designs remotely. In this article, learn how these three Cornell students remotely designed and built a maze generator and game running on a PIC32 MCU. They focus on the hardware that enabled their remote setup, as well as the software architecture of the system.

  • How to design games

  • PIC32 for building games

  • How to write software for game design

  • What is involved in programming your own game

  • PIC32 MCU

  • Python

  • Prim’s Algorithm

The COVID-19 pandemic created a demand for remote development configurations for embedded systems. At Cornell University, the course staff for Digital Systems Design Using Microcontrollers (ECE 4760) created a system for working remotely, allowing the course to be run in the midst of the pandemic. To facilitate this remote development, our group utilized a Remote Desktop connection to an in-laboratory PC; in turn, this PC communicated with a Microchip PIC32 target board [1] via a serial connection. The PIC32 board then communicated with various hardware peripherals, including a DAC and a TFT display screen, via SPI connections. Two cameras pointed at the setup allowed us to observe both the lab bench and the TFT display via a Zoom video call joined from the lab PC.

Our project creates a maze game anyone can enjoy. The objective of the game is to solve mazes of various difficulty levels at leisure or in the fastest time. To play it, the user opens the Python program that launches a GUI to control the game on the lab PC (Figure 1). From the GUI, players can select options for three parameters of the game:

  1. Desired difficulty level (Easy, Medium or Hard), with harder difficulties corresponding to higher-density mazes.
  2. To play alone (One-Player mode), or race a friend in Two-Player mode.
  3. Toggle Time-Trial mode on or off (Free Play), allowing players to compete against the current fastest solve times for each level of difficulty.
Figure 1 The Python GUI used to interact with the game. The GUI enables users to change the game difficulty and mode. It also shows the current fastest times for each level of maze-solving difficulty.
Figure 1
The Python GUI used to interact with the game. The GUI enables users to change the game difficulty and mode. It also shows the current fastest times for each level of maze-solving difficulty.

After selecting a game mode, clicking the “New Game” button on the GUI will generate a maze on the PIC32 microcontroller’s (MCU’s) connected TFT display. When the maze is generated, a user icon appears within a red square at the top left of the screen. Getting to the green square in the bottom right corner is how the user completes the maze and wins the game.

To advance the icon, Player 1, uses the WASD keys to move up, left, down and right, respectively. In two-player mode, the arrow keys are used to move the icon of Player 2. The different game-play modes allow players to solve the maze game in different ways. For example, one could relax in Free-Play mode, not worried about time trials or beating another player. Alternatively, more competitive players can choose to race the clock or each other, and beat high scores to establish a legacy as the fastest maze solver.

HIGH-LEVEL DESIGN

We used an implementation of Prim’s Algorithm to generate the different mazes. A visualization of this algorithm is shown in Figure 2. The algorithm runs on a grid of nodes, with each node representing a portion of the maze. The algorithm starts on a given node, which can be any of the nodes in the grid. In our implementation, the starting node is selected randomly, because we found that a fixed starting node generated similar mazes.

Figure 2 How maze generation works, using Prim’s Algorithm. The white cells have already been added to the maze, and have had walls knocked down in the generation process. The yellow cells represent the frontier nodes, and the purple cells are untouched by the algorithm thus far.
Figure 2
How maze generation works, using Prim’s Algorithm. The white cells have already been added to the maze, and have had walls knocked down in the generation process. The yellow cells represent the frontier nodes, and the purple cells are untouched by the algorithm thus far.

The next step is to add nodes that border the starting node to the “frontier set,” or the set of nodes that are on the outermost boundary of the current maze. When a node is added to the frontier set, a backpointer is saved, pointing to the maze node that it borders. For example, when the starting node adds its bordering nodes to the frontier set, the backpointer for each bordering node is the starting node.

— ADVERTISMENT—

Advertise Here

To grow the maze, a new node is randomly selected from the frontier set. The wall between the selected frontier node and its backpointer node is knocked down, adding the selected node to the maze. Once the selected node has been added to the maze, the bordering nodes are checked to see if they are eligible to be added to the frontier set. A node is eligible to be added if it has all of its walls and is not already in the frontier set. This prevents loops from being created in the maze.

The algorithm repeats the process of selecting nodes from the frontier set, knocking down a wall to add it to the maze, and adding its eligible bordering nodes to the frontier set until the frontier set is empty. The frontier set will only be empty after every node has been added to the maze, meaning the user is able to access every part of the maze. At this point, the maze generation is complete and an arbitrary exit can be added to the maze. We selected the bottom right corner of the maze as the exit. The generated maze is displayed by the PIC32 on a connected TFT display. Examples of “Easy” and “Hard” mazes are shown in Figure 3 and Figure 4, respectively.

The Python interface configures the difficulty of the generated maze and the play mode. After the maze is generated, users can start moving through the maze. Keystroke data is sent to the PIC32 using a serial connection, and the display is updated accordingly.

Figure 3 An “Easy” maze displayed on the TFT. The user begins in the red square and must navigate the maze to reach the green square. This photo was taken through a webcam that enabled remote development.
Figure 3
An “Easy” maze displayed on the TFT. The user begins in the red square and must navigate the maze to reach the green square. This photo was taken through a webcam that enabled remote development.
Figure 4 The winning screen of a Player 1 victory in Time-Trial mode on a “Hard” maze. The victory message remains on the screen until the PIC32 is reset or a new game begins. This photo was taken through a webcam that enabled remote development.
Figure 4
The winning screen of a Player 1 victory in Time-Trial mode on a “Hard” maze. The victory message remains on the screen until the PIC32 is reset or a new game begins. This photo was taken through a webcam that enabled remote development.
SOFTWARE DESIGN

The software for this project generates and displays the maze and the movement of users through the maze. Maze generation begins with drawing a grid to the TFT. The user-selected maze difficulty determines the dimensions of the grid and, by extension, the number of nodes. To create the entrance and exit, the left wall of the top left grid cell and the right wall of the bottom right grid cell are erased. To make these cells more obvious, the entire cell in the top left is colored red and the exit cell on the bottom right is colored green.

After the grid is drawn on the TFT, the maze is generated and drawn on the TFT by removing grid lines. Before the maze is generated, the node modules are instantiated and placed in a 2D array. To eliminate the need for dynamically allocating and deallocating memory, the maximum number of supported nodes are instantiated and reused with each new maze. Since the number of nodes in our remotely played game was limited by the visibility of the TFT in the Zoom video call, the maximum number of support nodes is the number used in the Hard difficulty level (432 total nodes).

The nodes are arranged into a 24×18 2D array, such that nodes can be indexed by their position in the grid. Each node object contains a value for its X and Y coordinates, plus four values to represent if the node has its north, south, east and west walls. It also contains two values for the X and Y coordinates of its backpointer node, and one to represent if it was in the frontier set or not. Each node starts with all of its walls and a backpointer of NULL.

To create the maze, a node is randomly selected from the nodes array. A function is then called to find which bordering nodes are eligible to be added to the frontier set. To determine if a bordering node is eligible, the node is first checked to see if it has all of its walls. The frontier attribute of the node is also checked to ensure the node is not already in the frontier set. The backpointer values of the node are set to point to the current node, and the frontier attribute is set to 1. A node is then randomly selected from the frontier array, and is added to the maze by eliminating the wall between the selected node and the node that added it to the frontier. The wall is “erased” from the TFT by coloring a black line over the wall segment.

Once the maze has been generated and displayed, the protothreads library [2] is used to control the game. Protothreads are lightweight stackless threads that are designed for memory-constrained systems, such as small, embedded systems. The serial protothread parses serial data sent from Python and uses it to set the proper flag, so that the handler thread for that particular event will be scheduled. If a button event occurs, we raise a button flag. If the user sends a string, we raise a string flag and so forth. These flags signal the thread that corresponds to that particular event. The Python string thread handles specific messages from the user command line, and can write a response to the Python GUI text box. This thread was used only for debugging when necessary, and was not actually used in the final version of our code. The code for the project is available for download at Circuit Cellar’s article code and files webpage.

The serial protothread is an important link to the Python/user input side of this project. This thread allows us to encode various messages from Python to key events as part of the maze game. A New Game thread is called at the beginning of every new game initiated by the user. Before pressing the New Game button, the user would have configured a preferred game difficulty level and mode, and this thread simply captures that information and uses it to generate a maze.

— ADVERTISMENT—

Advertise Here

For example, if the user selected Easy mode, a “new game” protothread sets the node dimensions of the maze to 12×9 by setting the X dimension of the 2D array to 12 and the Y dimension to 9. At this point, the game is initialized by drawing the grid, creating a random seed, generating the maze, and drawing the player(s). If Time-Trial mode is enabled, we start the PIC’s internal timer. At this point, the game is ready to begin!

THREADS IN ACTION

The player protothread drives player-icon movement during the game. The “key push” thread sets the user direction, which is used in this thread to update the user position. This thread yields for 10ms between iterations to ensure that user icons do not move too quickly. If Two-Player mode is not enabled, the second user icon is not drawn or updated. This thread also determines a winner and signals the endgame thread, by checking whether either player’s icon has entered the winning grid square.

Importantly, this thread is also responsible for ensuring that user icons stay on the midline between grid walls. It does so via the movement function illustrated in Figure 5. Based on the existing walls of a particular grid cell, we can determine to which locations movements are legal. The red lines show where a player is allowed to move. If the player is not centered left and right on a cell, but would like to move down, we snap them to the center of their current cell if it is legal to move down, and then move them down. This ensures a player always stays along the red line without having to be perfectly centered when changing directions.

Figure 5 Visualization of the user movement algorithm used in the program. The user begins in the red square and attempts to reach the green square. The red lines show in which directions a user can move at each node.
Figure 5
Visualization of the user movement algorithm used in the program. The user begins in the red square and attempts to reach the green square. The red lines show in which directions a user can move at each node.

The Endgame protothread is signaled by a “game-over” flag whenever a player enters the ending node. The game-over flag is first cleared, then the timer is disabled. If the winner has not yet been displayed, the phrase “Player X Wins!” is written to the TFT, where X is either 1 or 2, depending on which player finished the maze first. If Time-Trial mode is enabled, the message will read “Player X Wins! Time: ss.hh” where ss is the number of seconds and hh is the number of hundredths of seconds taken to complete the maze.

The time and maze difficulty are also written back to the Python GUI. When the GUI receives the time and difficulty, it compares the time to the current fastest time for the given difficulty. If there is no current fastest time, or this time is the new fastest time, the received time is set as the new high score and is displayed on the GUI. To store the fastest times more permanently, the fastest time for each difficulty is written to a text file. This file is written to and read by the Python program, and the data is stored until it is overwritten or the file is deleted.

HARDWARE DESIGN

Let’s take a deeper look into the hardware that makes this project possible. We created this project using a PIC32MX256F128B MCU [3] with a serial interface to the lab PC. These connections were facilitated using Sean Carroll’s Big Board (SECABB) [1], which was designed for this course by a former student. The schematic and layout for this board are shown in Figure 6. This lab also utilizes some key hardware from the remote development board developed by Hunter Adams for this course. The schematic and layout for the remote development board are shown in Figure 7. This board enables us to reset the PIC32 remotely from the Python interface by filtering a serial break condition using the reset hardware shown in Figure 7. A block diagram of the overall hardware setup is shown in Figure 8.

Figure 8 The high-level hardware setup that enabled the remote development of this project. A user could program the PIC32 by remotely connecting to a laboratory computer that was connected to the PIC32 via the Remote Learning Board and Sean Carroll’s Big Board.
Figure 8
The high-level hardware setup that enabled the remote development of this project. A user could program the PIC32 by remotely connecting to a laboratory computer that was connected to the PIC32 via the Remote Learning Board and Sean Carroll’s Big Board.

We use both the TFT display and a hardware timer in this project. The TFT display is the screen on which the game is displayed, so this is core to the functionality of our game. We include control and graphics libraries to configure and update the TFT, setting the orientation such that the origin is in the top left of the screen, the X-axis grows to the right, and the Y-axis grows down.

One of the PIC32’s internal 16-bit timers was utilized to implement the time trial functionality of our code. In main, we configure this timer to interrupt every 10ms, and we also reconfigure it to do the same in our New Game thread, as long as Time-Trial mode is enabled. This allows us to increment a counter every 0.01 seconds, which allows us to keep track of how long the user(s) take to complete the maze. We close this timer in our Endgame thread, which captures the time it takes to complete the maze accurate to 0.01 seconds.

It is also worth noting that the protothreads library utilizes a timer behind the scenes, so as a result of our use of the protothreads library, we use two timers in this project. One interesting protothread call that we make in our code is to get the current protothread running time at the beginning of a new game. We use this time to seed the random number generator used for maze generation. Since this call is triggered by user input, we can expect the random seed generation to be adequately random, such that different mazes should be generated each time a user tries to play.

TESTS AND RESULTS

To complete the project, we added functionality incrementally, and tested each feature extensively before moving on to the next one. We began our project by generating a maze using Prim’s algorithm. The first iteration of our maze was built using Python and was based on an implementation by Christian Hill [4]. This allowed us to code and debug using high-level functions, and to abstract away memory management that would eventually be required on the MCU. We then printed out an ASCII representation of our maze (Figure 9) to verify that the maze had a beginning, an end and a path connecting them together. We also used this representation to make sure that our maze contained no loops.

Figure 9 ASCII representation of a generated maze. While not used in the final product, printing out the generated maze greatly simplified the algorithm debugging process.
Figure 9
ASCII representation of a generated maze. While not used in the final product, printing out the generated maze greatly simplified the algorithm debugging process.

Once we were able to verify that our high-level algorithm was correct, we ported our code over to C. Unlike Python, C does not contain simple array-manipulating functions such as len() and append(). For this reason, we had to expand on many of the abstract Python functions to create the same functionality in C. Testing our C maze-generation code was a little tricky, because we had not written any code to display the maze on the TFT. Thus, we used the same ASCII representation as before, and printed the output to the Python GUI. With this method, we tested the maze generation code in isolation to verify its correctness.

The next feature that we added was drawing the maze on the TFT display. We began by testing the Easy level of difficulty, which generates a simple maze that is easy to debug. Initially we ran into a problem where, if the node sizes did not divide evenly into the TFT screen’s dimensions, the nodes got cut off. We amended this issue by filling in the extra space on the TFT with black and modifying the dimensions that the maze-generating function used to calculate node sizes. Effectively, this caused all the nodes to fit within the given bounds and cleaned up the display. Once the Easy maze worked, we extended the generate maze function to handle a Medium and Hard maze.

KEYBOARD CONTROL

An important feature of our game is the ability to move the player with the WASD keys. This required us to import a keyboard module into our Python GUI to register key presses. Testing the module had several components. First, we tested that the Python to PIC serial communication worked correctly by printing the key presses to PuTTY. Once we got this working, we tested moving the player cursor within the defined lines of the maze.

Initially, the player would sometimes get separated from the middle of a node, causing it to move over and through walls. We could see this when testing, since the player would overwrite and delete portions of walls when it passed over them. As described earlier, we remedied this issue by moving the player to the center of a node whenever a player wanted to change directions within that node. This forces the player to move within the lines, and makes it easier for the user to control the player through the maze.

Our final design features a maze game with Single-Player or Two-Player modes, three levels of difficulty, and an optional Time-Trial mode. Figure 4 is a view of the victory screen on the final version of the project. Additionally, it has a high score tracker for fastest maze completion time at each difficulty level.

— ADVERTISMENT—

Advertise Here

One thing we were worried about during the design stage of the project was the smoothness of player movement. Our program context switches between threads. If the player thread takes too long to be rescheduled, it would look like the player dots were jumping around. However, it turned out that all our threads executed quickly enough to prevent this from happening. Each player moves fluidly, without the screen flashing or the dots jumping around. This demonstrates that handling two players, along with our threading overhead does not break the illusion of concurrency on the PIC32.

CONCLUSION

Our design met our expectations nicely. We were pleased with how smoothly the remote development process went. Overall, it had very little impact on our final result. One of the most worthwhile parts of this project was to implement the maze generation algorithm in Python first, and then port it over to C. This allowed us to verify the logic of the algorithm in an easily debuggable environment, which gave us confidence it would work correctly as we transitioned to the PIC32 as our target device.

In the future, we might be more aggressive in our attempts to optimize the number of nodes we are capable of displaying on the screen. Ideally, users would have the PIC32 TFT screen right in front of them, and would not have to view it via Zoom. In that case, it might be possible to increase the density of our Hard-level maze further, since the user would not be limited by the visibility of the TFT on Zoom. Also, we might have used just a few bits for each wall, so the size of a node struct would decrease, and the memory requirements for the maze would be largely reduced.

Our design did not have any safety considerations, considering it was playable via a remote desktop interface. No parts of this design can hurt anyone—except maybe the loser’s feelings.

Authors’ Note: As a part of this project, we credit Christian Hill for providing a Prim’s Algorithm implementation in Python [4], which we adapted slightly to fit our needs. We thank Sean Carroll for his creation of the PIC32 development board [1] which allowed us to interface with the TFT screen from the PIC32 while working remotely. Finally, we thank our instructors Hunter Adams and Bruce Land for successfully moving the course online, so that it could continue despite the ongoing pandemic.

REFERENCES:
[1] Carroll, Sean. “Cornell University ECE4760 Development Boards PIC32MX250F128B.” Cornell University ECE 4760 Designing with Microcontrollers, https://people.ece.cornell.edu/land/courses/ece4760/PIC32/target_board.html
[2] Dunkels, Adam. The Protothreads Library 1.4 Reference Manual, Swedish Institute of Computer Science, 2006.{Jeff: Might this link be more helpful than the reference to the Manual, alone? Other Cornell students routinely cite it for Protothreads. https://people.ece.cornell.edu/land/courses/ece4760/PIC32/index_Protothreads.html
[3] Microchip Technology. “32-bit Microcontrollers (up to 128 KB Flash and 32 KB SRAM) with Audio and Graphics Interfaces, USB, and Advanced Analog,” PIC32MX1XX/2XX datasheet, 2011-2012.  http://ww1.microchip.com/downloads/en/devicedoc/61168d.pdf
[4] Hill, Christian. “Making a Maze.” Learning Scientific Programming with Python, 13 Apr. 2017, https://scipython.com/blog/making-a-maze/

RESOURCES
Microchip Technology | www.microchip.com

Sean Carroll’s Big Board (SECABB)
Cornell University | https://people.ece.cornell.edu/land/courses/ece4760/PIC32/target_board.html

Remote Development Board
Hunter Adams, Cornell University
https://people.ece.cornell.edu/land/courses/ece4760/PIC32/index_remote.html

PUBLISHED IN CIRCUIT CELLAR MAGAZINE • FEBRUARY 2022 #379 – Get a PDF of the issue

Keep up-to-date with our FREE Weekly Newsletter!

Don't miss out on upcoming issues of Circuit Cellar.


Note: We’ve made the May 2020 issue of Circuit Cellar available as a free sample issue. In it, you’ll find a rich variety of the kinds of articles and information that exemplify a typical issue of the current magazine.

Would you like to write for Circuit Cellar? We are always accepting articles/posts from the technical community. Get in touch with us and let's discuss your ideas.

Sponsor this Article
+ posts

Kyle Infantino is an M.Eng. student at Cornell University majoring in Electrical and Computer Engineering. He is interested in the digital design process and will be working at Apple as a GPU Design Verification intern this summer. He can be reached at ki88@cornell.edu

Jack Brzozowski is an M.Eng. student at Cornell University majoring in Electrical and Computer Engineering. This summer, he will be working at AMD as a CPU Verification intern, and is interested in digital hardware design and working with MCUs. He can be reached at jtb237@cornell.edu

Dilan Lakhani is an M.Eng. student at Cornell University majoring in Electrical and Computer Engineering. This summer, he will be working at Apple as a GPU Low Power intern. He can be reached at djl357@cornell.edu

Supporting Companies

Upcoming Events


Copyright © KCK Media Corp.
All Rights Reserved

Copyright © 2022 KCK Media Corp.

Build a Maze Generator and Game

by Kyle Infantino, Jack Brzozowski and Dilan Lakhani time to read: 16 min