Sushilicious You Got a New High Score Select This Button to Play Again
For our ECE 4760 terminal projection, nosotros created a maze game playable on a PIC32 series microcontroller via a Python interface on a PC. This game is consummate with iii dissimilar difficulty levels as well every bit a ii player manner which allows you lot to race to the end against an opponent. We also include a time trial manner which allows users to continue track of highscores in the course of how quickly they can consummate a maze at a given difficulty. The Python plan includes a GUI which enables the user to change game modes, view highscores, and generate new mazes from a PC.
To play our game, the user opens the Python plan which launches a GUI to control the game. From the GUI, a player can select their desired difficulty equally either easy, medium, or difficult. They can choose to play in unmarried or two thespian style, and can toggle time trial style on or off. Once they have selected a game mode they are satisfied with, clicking the "New Game" button will generate a maze on the PIC32's TFT display. When the maze is generated, there is a blood-red square in the top left of the screen with a circle inside of it; this is where the user begins the maze, and the circle is the user's player. A light-green square in the bottom correct corner is the target exit point of the maze. Getting to this square is how the user completes the maze and wins the game! In order to movement their icon, player 1 uses the WASD keys to motility upwards, left, down, and right respectively. In 2 actor mode, the second player can apply the arrow keys to move their icon.
Figure 1. The Python GUI used to modify the game mode.
The dissimilar varieties of gameplay allows for people to enjoy the maze game in unlike ways. For example, ane could relax in costless play mode, not worried about time trials or chirapsia another player, and just make their fashion through the mazes at their own pace of enjoyment. More competitive spirited players tin choose to race the clock or each other to effort to crush highscores and establish a legacy as the fastest maze solver in the history of ECE 4760.
Effigy 2. The TFT brandish with an "Easy" maze displayed.
The generation of mazes of varying difficulty was created through the employ of Prim's Algorithm. To create a maze, the algorithm can be run on a grid of nodes, where each node represents a portion of the maze. The algorithm starts on a given node, which tin exist selected manually or randomly from the nodes in the graph. In this implementation, the starting node is selected randomly. The next step is to add together nodes that border the starting node to the frontier set. When a node is added to the frontier set, a backpointer is saved pointing to the maze node it borders. For example, when the starting node adds its bordering nodes to the frontier set, the backpointer for each of these nodes is the starting node. To grow the maze, a new node is randomly selected from the frontier fix. The wall between the selected node and its backpointer node is knocked down, adding the selected node to the maze. Once the selected node is added to the maze, the bordering nodes are checked to run into if they are eligible to be added to the frontier set. A node is eligible to exist added if it both has all of its walls, pregnant it is not already part of the maze, and is not already in the frontier set. This prevents loops from being created in the maze. The process of selecting nodes from the frontier gear up, knocking down a wall to add together information technology to the maze, and adding its eligible bordering nodes to the frontier set is repeated until the frontier set is empty. The frontier set will only be empty once every node has been added to the maze, meaning the user is able to access every office of the maze. At this point, the maze generation is consummate and an capricious exit can be added to the maze. In this implementation, the bottom right corner of the maze was selected as the get out. The generated maze is displayed by the Moving picture on a connected TFT display.
This game contains support for multiple different modes including single player, two player, and time trial, likewise as piece of cake, medium, and hard difficulties. To interact with the game, the user tin can make selections on a Python interface displayed on the computer. The user also uses this interface along with the arrow/WASD keys to move the actor icon. The calculator and so sends this data to the Moving picture over a series connection.
Effigy 3. The winning screen of a Player 1 victory in Time Trial mode.
Effigy 4. Layout of the Sean Carroll Big Board.
This project was created using a PIC32MX256F128B microcontroller and a serial interface to a PC. This was done using Sean Carroll's Big Lath (SECABB), a former Cornell ECE who designed the board for this grade. This lab too utilizes some key hardware from the remote development board developed by 5. Hunter Adams for this course. This board enables us to reset the PIC32 remotely from the Python interface, using the reset hardware shown in the effigy below:
Figure 5. Layout of the Remote Learning Board.
Nosotros use the TFT display as well as timer2 in this project. The TFT display is the screen where the game displayed, and so this is core to the functionality of our game. We include the tft_master.h and tft_gfx.h header files to configure and update the TFT in accordance with the intended beliefs of our game. In primary, nosotros ready the TFT by calling tft_init_hw() and tft_begin(), and nosotros prepare rotation to 1. This rotation makes information technology such that the origin is in the top left of the screen, the 10-axis grows to the right, and the y-axis grows down.
Timer2 was utilized to implement the fourth dimension trial functionality of our lawmaking. In master, we configure this timer to interrupt every 10ms, and nosotros likewise reconfigure it to do the aforementioned in our New Game thread, as long as time trial way is enabled. This allows u.s.a. to increment a counter every hundredth of a second, which allows the states to go on rail of how long the user/users take to complete the maze. We close this timer in our endgame thread, which captures the time it takes to complete the maze authentic to ane-hundredth of a second. Nosotros prepare the timer up with a prescaler of 16, and a timer_match value of 25,000. This results in an interrupt every 400,000 cycles. Since the principal clock is 40MHz, 400,000 cycles corresponds to the 10ms period we sought.
It is also worth noting that the protothreads library utilizes timer1 behind the scenes, and therefore as a consequence of our use of the protothreads library, we use timer1 in this project. 1 interesting protothread telephone call that we brand in our code is a call to PT_GET_TIME() at the beginning of a new game. This call allows u.s. to somewhat randomly cull a random seed to generate mazes from. Since this call is triggered by user input, we tin can look the random seed generation to be adequately random, such that unlike mazes should generate each time a user tries to play.
The software for this project includes generating and displaying a maze, as well as handling users moving through the maze and different play modes. The procedure of generating a maze begins with cartoon a grid to the TFT. The size of this filigree is adamant by the selected difficulty of the maze. The piece of cake difficulty corresponds to a maze 12 nodes long and 9 nodes high, while medium is 16x12 and difficult is 24x18. These dimensions were called to friction match the TFT display height to width ratio such that the square nodes would fill the screen. The left and right x and height and bottom y coordinates of the TFT screen edges were hardcoded to be 320x240 (the dimensions of the TFT), but could be changed to adapt a unlike sized screen. The horizontal length xlen in pixels of each node is then calculated by subtracting the 10 coordinate of the right side of the screen by the x coordinate of the left side of the screen, and then dividing past the horizontal number of nodes of the grid. This is so repeated using the y coordinates to calculate the vertical length ylen of the node. Since the grid dimensions match the pinnacle to width ratio of the TFT, the nodes are all squares. Nonetheless, the grid ratio could be changed and still produce a correct maze with rectangular nodes.
Once these values are calculated, the TFT display is cleared by coloring the entire screen black. The grid is and then displayed on the TFT past drawing a vertical white line every xlen pixels and a horizontal white line every ylen pixels. To create the entrance and exit, the left side of the top left grid cell and the right side of the bottom right grid cell are colored black. To make these cells more obvious, the starting cell in the pinnacle left is colored red and the leave prison cell on the bottom correct is colored greenish. Since xlen and ylen are calculated using integer partitioning, their values are rounded down to the next integer. When cartoon the grid, this could result in the grid non filling the whole screen. To account for this possibility, black rectangles are drawn from the end of the fatigued filigree to the end of the TFT screen in both the horizontal and vertical directions.
Later on the grid is fatigued on the TFT, the maze is generated and drawn on the TFT by removing filigree lines. Before the maze is generated, the node modules are instantiated and placed in a second 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 is limited past the memory of the PIC as well as what is visible on the TFT, the maximum number of back up nodes is equal to that used in the hard difficulty, which consists of 432 total nodes. The nodes are bundled into a 24x18 2D array such that nodes can be indexed by their position in the grid. Each node object contains an int8_t value for its ten and y coordinates, as well equally 4 values to stand for if the node has its northward, s, due east, and west walls. It also contains 2 values for the x and y coordinates of its backpointer node and 1 to stand for if it was in the frontier ready 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 findValidNeighbors helper role is and then called to notice which adjoining nodes are eligible to be added to the frontier set. The findValidNeighbors function takes in the current node equally an argument and adds eligible bordering nodes to a neighbors array where each index represents the eligible node in a designated direction. For instance, index 0 of the array is the node direct above the current node. To determine if a bordering node is eligible, the node is first checked to see if all of its wall attributes are 1, meaning the node nevertheless has all of its walls. The borderland attribute of the node is too checked to ensure the node is not already in the frontier fix. If the node has all of its walls and is not in the frontier set, it is added to the neighbors array at the appropriate index. The backpointer values of the node are set to point to the current node and the frontier attribute is set to 1. For example, if the node to the right of the current node is valid, the x backpointer of the right node volition be set to -one and the y backpointer will be set to 0, meaning that the 10 coordinate of the point that added this point to the borderland set is one less than the 10 coordinate of this point. If a neighboring node is found to not be eligible, that index of the neighbors array is set to NULL. If the current point lies on the edge of the grid, the index corresponding to the direction beyond the grid is too ready to Zippo.
Once the role returns, the valid nodes in the neighbors array are added to the frontier set. A node is so randomly selected from the borderland array and is added to the maze by knocking down the wall between the selected node and the node that added it to the frontier. The helper role knockDownWall takes ii nodes as an argument. One node is the selected node, and the other node is the one that added it to the frontier set, indexed from the nodes array using the backpointer coordinates of the selected node. The function compares the coordinates of the two nodes to determine which wall to knock down. For case, if the selected node is to the right of its backpointer node, the attribute representing the west wall of the selected node is set to 0 and the e wall of the backpointer node is fix to 0. The 10 and y coordinates of the node closest to the origin are so multiplied by xlen and ylen to calculate on which pixels of the TFT the wall is drawn. The wall is so "erased" from the TFT by coloring a black line over the wall segment.
Once the maze has been generated and displayed, the protothreads library is used to control the game. The protothread_serial parses serial data sent from Python, and uses it to gear up the proper flag then that the handler thread for that particular outcome will exist scheduled. If a push effect occurs, the new_button flag is raised, if the user sends a cord, the new_string flag is raised, etc. 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 last version of our code.
Figure six. The TFT display with a "Difficult" maze displayed.
Protothread_serial is an important link to the python/user input side of this project. This thread allows united states of america to encode various messages from Python to key events as part of the maze game. For instance, we apply this thread to bespeak the NewGame thread, the keypush thread, and the aforementioned python_string thread. The NewGame thread is signaled past protothread_serial whenever the New Game button is pressed down on the python interface. The keypush thread is signaled every time the user presses or unpresses one of the eight keys associated with moving role player 1 or 2. Information technology then checks if the key was pressed or released and to which user the fundamental belonged. If a fundamental was pressed, the move variable of the appropriate user is set to the direction of movement, otherwise the user does non movement.
The NewGame thread is called at the first of every new game initiated by the user. Earlier pressing the new game button, the user would have configured their preferred game difficulty and mode, and this thread simply captures that information and uses information technology to generate a maze. For example, if the user selected easy mode, protothread_newgame sets the dimensions of the maze to be 12x9 by setting dimensionx to 12 and dimensiony to 9. Information technology and then sets xlen and ylen to be the appropriate length and width of a grid cell. At this point, the game is initialized by calling drawGrid(), srand(PT_GET_TIME()), which creates a random seed, generateMaze(), and drawPlayer(). If time trial is enabled, nosotros outset timer2. At this bespeak, the game is ready to begin!
Protothread_player drives player icon motion during the game. The keypush thread is responsible for setting the user direction, which is used in this thread to update the user position. This thread yields for 10msec between iterations to ensure that user icons practice not motion too quickly. If two player style is not enabled, the 2nd user icon is non drawn or updated. This thread is also used to determine a winner/signal the endgame thread past checking if either player's icon has entered the winning filigree square. Importantly, this thread is responsible for ensuring that user icons stay on the midline between grid walls, and it does then via the canMove function. Based on the existing walls of a particular grid jail cell, we can determine the locations which are legal to motion to. As shown in the effigy below, the cerise lines shows where a role player is allowed to move. If the player is not centered left and correct on a cell, just would like to move down, nosotros snap them to the heart of the cell they are at if information technology is legal to move down, so move them down. This ensures a player ever stays along the red line without having to exist perfectly centered when changing directions.
Figure 7. Visualization of the canMove function.
Protothread_endgame is signalled by the game_overFlag whenever a histrion enters the ending node. The game_overFlag is first cleared, then Timer2 is disabled. If the winner has not however been displayed, the phrase "Player X Wins!" is written to the TFT, where X is either 1 or 2 depending on which actor finished the maze beginning. If time trial mode is enabled, the bulletin 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 consummate the maze. The time and maze difficulty are as well 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 fourth dimension, the received fourth dimension is set as the new high score and displayed on the GUI. To store the fastest times more permanently, the fastest fourth dimension for each difficulty is written to a maze_highscores.txt file. This file is written to and read from by the Python program, and the data is stored until it is overwritten or the file is deleted.
In order to complete the project, we added functionality incrementally and tested each characteristic extensively earlier moving on to the next one. We began our projection by generating a maze using Prim's algorithm. The first iteration of our maze was built using Python; this allowed the states to lawmaking and debug using high-level functions and let us abstract away memory management that we would somewhen take to do on the microcontroller. We then printed out an ASCII representation of our maze in gild to verify that the maze had a beginning, an end, and a path connecting them together. We as well used this representation to make sure that our maze contained no loops.
Effigy eight. String representation of a generated maze used for debugging.
Once we were able to verify that our high-level algorithm was correct, we ported our lawmaking over to C. Unlike Python, C does not comprise uncomplicated array-manipulating functions like len() and suspend(). Thus, nosotros had to expand on many of the abstruse Python functions to create the same functionality in C. 1 example of this was checking the length of the borderland array when deciding whether the maze generation was complete. In Python, we could only employ the len() function on the borderland node listing. When writing the code in C, we create an assortment with length equal to the number of total nodes in the maze. This is overkill, as there will never be a situation where the frontier array needs to hold every node in the maze. However, we did non want to get a segmentation fault in a corner example if the array overflowed. In order to cheque how long the frontier array was, we created start and end variables that tracked the alphabetize of the first and last nodes in the frontier set. We then calculated the deviation between those two variables to become the length of the borderland assortment. Testing our C maze generation code was a niggling tricky, as we had not written any lawmaking to display the maze on the TFT. Thus, nosotros used the same ASCII representation as before and printed the output to the Python GUI. With this method, nosotros tested the maze generation lawmaking in isolation to verify its correctness.
The next feature that we added was drawing the maze on the TFT brandish. We began past testing the Like shooting fish in a barrel difficulty, which generates a simple maze that is easy to debug. Initially we ran into a trouble where if the node sizes did not divide evenly into the TFT screen's dimensions, the nodes got cutting off. We amended this issue by filling in the actress infinite on the TFT with blackness and modifying the dimensions that the maze generating function used to calculate node sizes. Effectively, this caused all the nodes to fit inside the given premises and cleaned up the display. Once the easy maze worked, we easily extended the generate maze function to handle a medium and hard-sized maze.
In our game, we also wanted the user to exist able to start a new game when they completed a map. We tested this out by finishing the initial maze then generating a new maze. At first this caused the PIC to reset, and so we idea we were using too much memory on the PIC. Nevertheless, after examining our code nosotros found that we did not re-initialize our start and end variables, causing an assortment out-of-bounds error. After fixing this mistake, we were able to generate new mazes whenever the histrion desired.
An important feature of our game is the ability to move the actor 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. Commencement, we tested that the Python to Picture series communication worked correctly past press the key presses to PuTTY. We then drew a big white blob on the center of our maze and attempted to go far move with central presses. Once nosotros 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 movement over and through walls. We could see this when testing, as the player would overwrite and delete portions of walls when information technology passed over them. We remedied this issue by moving the player to the eye of a node whenever key presses were detected. This forces the player to movement within the lines, and makes it easier for the user to command the player through the maze.
When nosotros tried to go the player to move at a set frame rate to make the motion appear smoothen and to control the speed at which the player moved, the player thread got called once so was never scheduled again. This caused the histrion to not respond to key presses, stalling the player in its initial location. We realized that we had not enabled system-broad interrupts, significant that PT_YIELD_TIME_msec() could non interrupt and schedule itself again after a certain number of milliseconds had passed. One time we enabled interrupts, we were able to utilize an update frame charge per unit of 100fps that gave us a manageable player speed.
Afterward getting the basic functionality of the game working, we decided to add a multiplayer mode that allowed two players to race each other to the terminate. One problem nosotros had when testing this occurred when thespian ii crossed over player 1 and player 1 did not movement. This would cause player 1 to disappear. We realized that nosotros had optimized our code so that the player is not redrawn unless it was moved; however, with two players this would cause 1 player to delete some other until the other player moved once more. We fixed this bug by redrawing each player every time the player thread runs, the tradeoff existence that the thread volition take longer to execute.
Finally, we added a time trial mode that lets users track their highscores on different maze difficulties. Nosotros decided to display the highscores on the Python GUI, then we had to communicate the completion fourth dimension serially to the lab PC. We tested that the data transferred from the PIC was formatted correctly, and then parsed and displayed it on the GUI. We got the window to update by attaching a key to the text element, then calling the update method on that key.
Our final design features a maze game with singleplayer or multiplayer way, three difficulties, and a toggleable time trial mode Additionally, information technology has a high score tracker for fastest maze completion fourth dimension at each difficulty when time trial mode is enabled. Below are videos of gameplay that highlight dissimilar features of our game:
Figure 9. Playthrough of an "Easy", "Medium", and "Difficult" maze in Single Actor mode.
The first video highlights single player gameplay with time trial mode disabled. Initially, the role player attempts to solve an Like shooting fish in a barrel maze, navigating with the WASD keys. We see that the actor cannot move closer than half of a node width to a wall. We also see that the player cursor volition slightly snap back to the middle of a node if the player tries to motility towards an open up section but is not exactly in the eye of the node. This is necessary to keep the histrion inside the tracks of the maze and to foreclose the player from crossing walls. In one case the actor reaches the green box at the finish of the maze, we run into the game-winning message displayed across the screen. Fifty-fifty though the game has ended, the thespian tin all the same movement around on the screen. Nosotros decided to include this characteristic, every bit it is fun to travel downwardly other paths on the maze after you finished merely to see where they cease up. After we complete the easy maze, nosotros then gear up the difficulty level to Medium and click New Game, which redraws the maze. Now, the player finds their manner through the more hard maze. Once the light-green foursquare is reached, the same win message is displayed on the TFT. Finally, we set up the maze to Hard mode and trounce it to meet the win screen one time again.
Figure 10. Playthrough of a "Medium" maze in Two Histrion fashion.
The 2nd video has two-player mode enabled, and nosotros tin can come across two dots representing the players on the TFT. The first histrion is still controlled with WASD, while the second player uses the arrow keys to navigate the maze. Both players tin can cantankerous over each other without deleting the other cursor, meaning our blitheness is robust. Each role player can likewise move independently and fluidly, without the screen flashing or the dots jumping around. This proves that handling two players along with our threading overhead does not suspension the illusion of concurrency on the PIC. Each histrion races to the finish, and we meet that once one player wins, the winning screen congratulates that player. Like in single player mode, both players tin still motion around, erasing parts of the winning bulletin and exploring other maze paths. Even if the player who lost finishes the maze, the winning screen however specifies the original winner. Thus, we will non have a situation where the real winner is dethroned past a poser.
Figure 11. Playthrough of a "Medium" maze in 2 Player mode with Time Trial mode enabled.
The last video enables time trial mode, which opens a timer when the New Game button is pressed. That timer runs until the commencement player reaches the end of the maze, then displays the completion time alongside the winning screen. In the Python GUI we encounter that the high score for the medium maze is updated to the histrion's completion fourth dimension. Now, we play a new medium maze and have a player beat the old high score. The Python GUI updates to brandish the new high score, and the players can continue trying to lower their completion time on each difficulty!
To animate the thespian, we utilise the protothreads_player thread. This thread yields for 10 ms at a fourth dimension, so we end up with a framerate of 100 fps. This speed was chosen considering it moves the actor at an adequate speed across the screen. Every bit a result, it is as well not very jumpy, and results in a rather polish playing experience for the player.
When we first began cartoon mazes on the TFT, nosotros were unsure as to whether the limitation on the largest viable maze size would be the user visibility of the screen through remote desktop, or the memory of the Moving picture microcontroller. Nosotros drew grids of diverse sizes on the screen, with the individual grid squares getting progressively smaller until we adamant we would non be able to play the game easily, or until the PIC reset from inundation retention. When allocating a 36x27 maze, the Motion picture reset, so this was the breaking point for how big a maze could possibly be on the PIC. As a result, we chose the maximum size maze for the hard difficulty to be 24x18.
Our design met our expectations nicely. Every feature that we planned to implement worked as we intended, and our development process was pretty efficient. One of the well-nigh worthwhile things nosotros did as function of this project was to implement the maze generation algorithm in Python kickoff, and then port it over to C afterwards. This allowed us to verify the logic of the algorithm in a language similar Python that is hands manipulated, which gave us confidence it would work correctly every bit we transitioned to the PIC32 as our target device.
Next time, nosotros might be more aggressive in our attempts to optimize the number of nodes we are capable of displaying on the screen. In an ideal world, the user would have the PIC32 TFT screen correct in front of them, and would not have to view it through a zoom screen. In that case, information technology may have fabricated more sense to push button the size of our hard level maze even further, every bit the user would exist able to more hands see the maze. Nosotros could have made each node as small as possible using just a single bit for each wall, Northward Southward, E and W instead of using shorts. In doing this, the size of a node struct would decrease significantly and the space in retentivity it takes to shop a maze would be largely reduced.
In that location are no patent opportunities as part of this project, nor did nosotros have to sign an NDA. Our pattern did not have any safety considerations, considering it was playable via a remote desktop interface. There are no parts of this design that can hurt anyone (wait mayhap the loser's feelings).
Every bit a role of this projection, we would like to credit Christian Hill for providing a Prim's Algorithm implementation in Python which we adapted slightly to fit our needs. Yous tin find Christian's code at the link in Appendix F.
According to the IEEE lawmaking of ethics, it is essential to maintain and improve our technical competence and to undertake tasks for others only if qualified by grooming or feel. As part of this project, we all gained valuable experience working with microcontrollers, and improved our technical abilities. We tried to avert harassment/bullying behavior by allowing users to choose non-competitive modes of gameplay, so users don't need to experience obligated to 'win' or beat an opponent. We wanted to avoid a situation where our game allowed someone to feel as though they were lesser than someone else, it'south just supposed to exist fun!
ABOUT US
Meet the team:
Jack Brzozowski
Jack is a junior ECE at Cornell University. His areas of involvement include microcontroller programming and development, and digital ASIC design. He will be pursuing a Primary's of Applied science degree in Electrical and Computer Engineering later on graduating in the Fall of 2021. In his costless time, Jack enjoys playing disc golf and guitar hero with his friends.
Dilan Lakhani
Dilan is a senior ECE major at Cornell University. His areas of interest include ASIC verification and embedded systems programming. He will be pursuing a Master's of Technology caste in Electrical and Reckoner Engineering subsequently graduating in the Spring of 2022. In his costless time, Dilan likes to play the drums and hang out outdoors.
Kyle Infantino
Kyle is a junior majoring in ECE with a minor in Figurer Science at Cornell University. His interests include embedded systems likewise as figurer architecture and ASIC design. He plans on graduating in Spring 2022 and continuing with a Primary'southward of Engineering in ECE. Kyle enjoys running in his gratis fourth dimension.
Source: https://people.ece.cornell.edu/land/courses/ece4760/FinalProjects/s2021/ki88_djl357_jtb237/ki88_djl357_jtb237/
0 Response to "Sushilicious You Got a New High Score Select This Button to Play Again"
Postar um comentário