Boids, Predators, Joysticks, and Friends

Credit to Bramus for Smooth Scrolling Sticky Navigation

Introduction

 For our final project, we made a video game in which the player controls a predator and gains points by eating boids. The video game ended up having three different modes and could be played by either one or two players. We enjoyed taking the optimization lab of lab 2 and turning it into a playable game with a menu, scorekeeping, and sound effects while keeping boids in the picture.

Design

Completed System

Figure 1: The Completed System

Concept

 This project was largely an extension of lab 2. We took the boids algorithm that we had developed and optimized in lab 2 and encapsulated it inside of a game. The idea came from a statement one group member made when discussing how the predator for the 5000-level version of microcontrollers moves randomly. “What if we could control the predator!?” we thought. Then the juices got flowing and we made the idea into a reality.
 After working for over a month since the inception of the idea, we were able to create an entire gaming system. We combine different menus, instructions, modes, players, and sound effects with nostalgic joysticks and a button to bring the experience to life.

Hardware Description

Materials

A more detailed breakdown of the materials, their cost, and their vendors can be found in Appendix D.

  • Big Dev Board
  • TFT
  • PIC32
  • Jumper wires
  • Breadboard
  • Joysticks (x2)
  • 10 kΩ resistors (x8)
  • Button
  • Audio Socket
  • Lab speakers
  • DAC

Joysticks

 The Joystick was an integral part of the video game we created. It was one of two hardware components that was used as inputs to the game. The Joystick is an 8-way input device that allowed us to do a hardware read of the directional control that the players were moving in as they attempted to devour boids and escape the shark. The Joystick had a 5 pin interface-- one pin reserved for GND and four pins retained for the Cardinal directions. To integrate the Joystick with the PIC32 microcontroller a 10kΩ pull-up resistor was used to tie the four directional pins high to the MCUs 3V3 rail and the 5th pin was tied to the GND of the MCU. To detect which cardinal direction was pushed, one of the four directional pins would be tied to ground, essentially making the system active low. When they weren't pressed they would be tied back to 3V3 remaining idle high. See the below figure for an image of the joystick and reference the Gameplay interface section of the schematic capture in appendix C to see how the two joysticks were implemented in Hardware.

Joystick

Figure 2: Joystick

Select Button

 The second hardware component that was used for inputs was a button. Since our joysticks did not have a digital button integrated into its design we had to have a way to select choices within the game so we decided to implement a select button. To do this one terminal of the button was pulled up to 3V3 via a 10kΩ resistor while the other terminal was tied to GND from the PIC32. Our button functioned as an active high device and was idle low. The button was also debounced to account for false contacts that may have occurred during the oscillations of the internal spring inside the button. See the diagram below for the debouncing algorithm implemented via a finite state machine.

Debounce FSM

Figure 3: Debounce FSM

Audio Socket

 The audio socket was used to output audio signals from the DAC_A and DAC_B channels. Everytime a prey was eaten by a predator or the game ended, an “Oww!” or “Chomp!” sound (courtesy of Prof. Bruce Land) was outputted to the DAC_A and DAC_B channels and the audio socket enabled for the signals to be heard on the two lab speakers as it afforded a 3.5mm jack.The front pin on the audio socket was tied to ground and the two rear pins were individually connected to either DAC_A or DAC_B on the PIC32 Development board. Featured below is an image of the audio socket that was used in this project. Also reference the schematic in appendix C to view the connections from the DAC to the audio socket.

Audio Jack

Figure 4: The Audio Jack Socket

Completed Hardware Circuitry (Breadboard)

Breadboard

Figure 5: A Representation of the Breadboarded Hardware Connections

Software Description

 There was only one file that we created and worked on for this lab in C: bpjf.c. The project and clock settings in MPLab were left as default, and Bruce Land's libraries for controlling the TFT were used.
 We also created a python script to convert wav files (sound effects) into DAC outputs.
 There is a variable called game_state that reflects the current state of the player. MENU if the player is inside the menu choosing what to do next, PLAYING if the user is playing a game, GAMEOVER if the game has ended and the result is being displayed, and INSTRUCTIONS if the instructions are being displayed.

Menu

Menu

Figure 6: Menu

 Upon reset, the player uses player one's joystick to select between TIMED, RACE, and SHARK modes, or to view the INSTRUCTIONS. As can be seen above, there are 50 boids in the background of the menu that flock and fly around to give the game a dynamic feel. A blue triangular cursor moves up and down to display which option is being selected. A variable keeps track of which is currently selected, so when the PIC reads an input corresponding to a joystick moving up or down, it will erase and redraw the cursor accordingly. It will then update the variable to the new position. We do not allow for wraparound, so if you try to go down from INSTRUCTIONS, nothing will happen. If INSTRUCTIONS is highlighted and the pushbutton is pressed - signifying a selection - then the game state switches to INSTRUCTIONS.
 INSTRUCTIONS simply displays the instructions. Nothing is redrawn or animated when in this game state. It took some time to get everything to look right given we could only draw to the TFT using x and y coordinates, but the end result looks rather professional.

Instructions

Figure 7: Instructions

 If one of the game modes is instead selected, then the mode variable is set to whatever mode was selected and we transition to displaying a player selection. Shark mode only allows for single player mode and race mode is only multiplayer by nature, but if timed mode is chosen the user must select whether they want to play in one- or two-player mode. There is also an option to go back to the main menu. Selecting the number of players does two things: it switches the game_state to PLAYING and it also sets the number_of_predators so the appropriate number of predators are drawn in gameplay.

Menu FSM

Figure 8: Menu FSM

Sound Effects

 We have two sound effects “ow” and “chomp” that we play at different times during the game, by sending the encoded samples to the DAC at the correct audio sample rate. Programming an interrupt handler, however, would require sacrificing additional CPU cycles to copy DAC data that could be used for animation.
 To generate the sound effects without expending additional CPU cycles, we set up a DMA channel to the DAC. On startup in the main method, we set up the SPI channel in framed mode to the DAC. We open a DMA channel in default mode, and set the transfer event to be on a timer interrupt with the same frequency as the audio sample rate. We also store the sound data beforehand in flash memory in an array of shorts. This setup allows us to initiate a DMA transfer from an array in flash memory to the SPI channel to the DAC at the frequency of the timer interrupt.
 In the animation thread, when it is detected that a boid has been eaten or the player lost, we set a DMA transfer from the desired encoded sound array to the SPI channel linked to the DAC. Then we force the transfer and enable the channel to initiate the DMA transfer.

Gameplay

 Most of the gameplay loop stayed consistent regardless of the mode we were in. At the beginning of a game, 200 boids are initialized. Also, one or two predators are initialized inside a predators list - depending on the number of players. The game runs at 30 fps.
 Each frame, the 200 boids are erased and looped through to update their positions and their velocities. We employ a minimum and maximum velocity, a turn factor, a visual range, and a predator avoid factor. We do not have boids center or avoid because the boids still appear to flock since they automatically avoid the predators.
 After the boids' positions and velocities have been updated, we next loop through the predators. The predators only have positions since their x and y velocities are constants. We erase the predators and update the position of the predator based on the position of the joystick. Each of the 8 directions (4 directions per joystick x 2) are mapped to a digital input to the PIC. If a pin goes low then the joystick has been moved there. Therefore, for example, if RB9 goes low and that is attached to player one's right, then we add predator_velocity to predator_list[0].xpos. If we are in single-player mode and player two's joystick gets moved, nothing happens.
 Next, we check to see if the predators have “eaten” any boids. If a predator's x and y position are less than predator_size away from a boid, then the two will be overlapping and the boid should be eaten. The boid will be set to dead, it will be moved to 0,0 with a speed of 0, and, most importantly, the player's score will be updated. Also, if a boid was eaten, we DMA to where the DAC values of our “ow” sound is stored and we play a half-second clip of Dr. Bruce Land saying “ow.” Thank you Bruce. Since we loop through each predator, we will be able to tell if player one or player two should get the points based on if it's our first or second time through the loop.
 The last thing we do is redraw. All of these steps happen in just 1/30th of a second.

Boids Avoiding Predators

Figure 9: Minnows Avoiding Two Predators During Gameplay

Timed Mode

 The basis for the game is the same no matter the mode. What's different mode-to-mode is the game over condition. In timed mode, we switch from PLAYING to GAMEOVER when time_remaining = 0. The timer starts at 60 and is decreased every second. The time_remaining is also printed in the upper left corner of the TFT.

Race Mode

 The premise for race mode is similar to timed, but instead of playing for a finite time, we play to a finite score. Race mode is multiplayer only because the player who eats 25 boids first is deemed the winner. A condition checks to see if either player's score is >= 25.

Shark Mode

 Shark mode was definitely the hardest to implement but is also the most fun. In this single-player mode, you control your predator (red dot) to eat the boids, but there is also a Shark (larger, cyan dot) that tries to eat you. The shark's name is Bruce, named after the shark in *Finding Nemo*. The shark automatically follows the player at `shark_speed` using some math. By calculating the dx and dy between the shark and the player, we can normalize the speed to not exceed shark_speed the same way we did in lab 2. By using alpha max beta min, we can approximate the speed of the shark without having to take the square root of a sum of squares, which would take hundreds of precious clock cycles. However, since there is only one predator, we are able to normalize the speed using a division instead of a bit shift. We found that the bit shift approximation, `dx -= dx >> 2`, was not sufficient here because for a couple frames the shark still moves faster than the maximum which made the game too difficult. Using a divide was okay since it is only done once for dx and once for dx per frame, not 200 times if it were being executed on each boid.
 Similar to when a predator eats a boid, if the shark overlaps with the player then the shark is said to have eaten the player. In this case, the game is over and we transition to the GAMEOVER state.
 To add even more complexity to shark mode, the playable border decreases by 2 pixels per second. Similar to fortnite where to increase the difficulty and concentrate the players as time goes on, the decrease in border size means that the shark will always be right on your tail, but also it means that the boids will be concentrated in the center as well. So, the longer you survive the shark the harder it gets, but you are guaranteed to rack up more points. In order to implement this border, every half of a second a black rectangle is drawn circumscribed inside the previous rectangle. Every second, the margin is decreased by 1 pixel. The predator is unable to move outside the margin, and the boids will turn based on their turn_factor when it hits the margin, which is growing ever closer to the center. The black rectangles being drawn over the blue ocean give the appearance that the ocean and thus the TFT is physically shrinking.
 When the shark finally gets you, we DMA to an array of DAC values of another recording of Dr. Bruce Land, this time saying “chomp.” The voltage output to DAC A goes to the speaker and sound can be heard.

Shrinking Borders

Figure 10: Shrinking Borders in Shark Mode

Game Over

 There are two Game Over screens, which depend on the number of players. In single player mode, we care about how many boids were eaten so the game over screen will display the exact number of boids the player had eaten in the allotted time or before the shark ate them. However, in multiplayer mode it is all about who wins. If the number of players is two, then GAME OVER will compare the scores of the two players and display the winner. In the event of a tie, it will display as such.

Gameover Singleplayer

Figure 11: Game Over Showing Points in Singleplayer Mode

Gameover Multiplayer

Figure 12: Game Over Showing Points in Multiplayer Mode

WAV to DAC

 To convert our audio recordings to the encoding used by the DAC, we wrote a Python script to automate the process. External to the script, we first converted our recordings to the WAV file format using online tools. The DAC is 12-bits, and requires a 4-bit header for each 16-bit frame. Using the wave package, we read each wave file in 2-byte segments, scale the data down by a factor of 0.75 to convert from 16 bits to 12 bits, and prepend bits 0011 for the header. We also added functionality to trim and compress the audio clip. By using lambda expression and higher-order-functions, we were able to quickly specify the length of the resulting sound file in terms of the length of the audio sample. Our script offered compression in the form of averaging two data packets to reduce the number of samples after trimming by a factor of two. These features were crucial to fitting the data into the limited flash memory available. For convenience, we also construct the header file and put the DAC data for each sound effect into an array. That way, we were able to make quick adjustments to the audio data and copy-and-paste the new header file into our project, since we could only test the DAC encoded data on the PIC32 itself.

Testing

Joysticks

 There was no datasheet or schematic for the joysticks, so we had to test them to figure out how they worked. There were five pins to figure out what was what. Using a multimeter, we tested to see which pins were shorted together when a given direction was actuated. Then, we could deduce which was the common pin we would use as ground. The other four pins were the directions, so we pulled them up to 3V3 with a 10 kOhm resistor to ensure they are never floating.

Sound Effects

 The sound effect testing was done by ear. We had two constraints: the program data and perceived audio quality. We decreased the audio data size by trimming then compression until both samples could fit within the program data. We compressed the samples as a last resort, but we could not fit both samples within the program data without some compression. We tested the samples on PIC out of necessity since we needed to test the DAC output which required audio data to be encoded according to the DAC. We continually made adjustments to maximize the audio quality within the program data constraint. We had some issues early on setting up DAC. We successfully merged in sample code from Adams' example DAC program, but in switching from auto to default mode we mistakenly unlinked the event transfer from the timer. After setting up the DAC correctly however, we were able to test through playing the game that the sound effects were played at the correct time and sounded somewhat distinguishable relative to the audio effect we were trying to achieve.

Menu

 Testing the menu involved a lot of trial and error to get graphics and text in the right location. We drew out how we wanted the menu to look, but translating that into TFT helper functions took quite a few flashes and edits. We had to get the text size correct, the spacing correct, and the cursor had to line up perfectly with the words. We also had to manually center the options. Since INSTRUCTIONS is a much different length than RACE, centering those required different x-values to set the cursor before printing. After getting the general idea down, we made aesthetic adjustments to give it the final professional feel we have now. Then, the menu could be methodologically depth-first-search tested by selecting every option and player count, then clicking back until the main menu was reached, to ensure the menu was working 100%.

Gameplay

 Our final project, by nature, is meant to be playtested. Truly, we aimed to make a fun, playable, bugfree videogame. Therefore, in Hunter's famous words, “if it looks right, it is right.” Tyler took the game home during Thanksgiving break where his 10-year-old cousin played the game many times because he was having so much fun that he found a bug. When playing shark mode twice consecutively without reset, the TFT did not get wiped to blue at the start of the game which led to the actual boundary mismatching with what is displayed on the screen.

Results

Qualitative Analysis

Gameplay

 The game ended up being pretty fun. Whether you are playing against a friend or battling against a shark, the game induces competition and gets adrenaline pumping. The instruction screen was the perfect balance of simplicity and explanation to understand the premise of the game. A player who had never seen the game was able to get the fact that sharks should be avoided and boids should be eaten to gain points. The nuances of race mode and timed mode are not essential to the gameplay and can be discovered by the players after a few minutes.
 The game ran smoothly and was not laggy. Even towards the end of shark mode when the screen becomes super small and you are overloading the joystick with tons of inputs, the predator still remains responsive. The joysticks themselves added an element of nostalgia to the system. They are very tactile and fun to actuate, keeping the player more involved than if, let's say, a keyboard was used instead.
 The boids on the menu flock and look beautiful in the background while the game starts up and the player makes their selections. Even though the boids in the actual game are not *truly* following a full boids algorithm, the number of boids combined with their avoidance of the predators gives the appearance of such.

Sound Effects

 In order to output recordings to the DAC and fit them in memory on the PIC, they had to be compressed and resampled. The trimming and resampling process did not affect the audio quality too much, and the result yielded decent quality and similarity to the original. The compression by averaging, however, caused the most damage to the sound quality. This process distorted Land's words to the point where it was not possible to tell who the voice actor was. However, the words can be discerned and the distortion to the sound effects seems to fit well with the retro feel of our game. The grainy audio quality, tactile joysticks, and standard definition TFT all come together to drive nostalgia into the player.

Quantitative Analysis

Gameplay

 When we first started making the game we settled on 200 boids during gameplay and stuck with that throughout the entire process. We throttled our game at 30 fps and we never dipped below that threshold. On the menu, there are 50 boids also moving at 30 fps.
 In lab 2, in order to run at 30 fps, every boid must be erased, new positions and velocities calculated, and redrawn within 33 milliseconds. In our game, with the addition of reading joystick input, erasing and redrawing predators, incrementing scores, and checking to see if the game is over added an estimated 500 cycles per player per frame. Most of these cycles come from the multiplying and dividing the fixed point data type `_Accum`. However, even in 2-player mode, the addition of 1000 clock cycles per frame, performance is not affected at all. At the default clock speed of 40 MHz at 30fps, we have 1,333,333 clock cycles for each frame. The additional 1000 clock cycles is insignificant as it only uses up 0.07% of our allotted clock cycles per frame.

Sound Effects

 The original audio samples for the sound effects after a rough trim and conversion to wav format were 108 KB and 96 KB. Each was about 1 second in duration and were converted from audio recordings from an iPhone at 44 kHz sample rate. When sending these files from one of a phone to a laptop (through Telegram), we noticed that the audio recordings were on the order of 10 times smaller, speaking to the level of compression that can be achieved by modern communication systems and perhaps an area of future improvement for our project. Our final sample data was 29 KB and 25 KB, enough to fit in the program data in flash memory, a little over 130 KB. At first, we just trimmed the samples further, but we could only fit one audio sample at a time in the program data. To store both sound effects, we compressed the samples by averaging to reduce the audio data by a factor of 2, and correspondingly doubled the frequency of our timer for the DMA transfer. At the end, our total flash memory usage was 83% and just under 110 KB.

Conclusion

 Looking back on our project proposal, we have met our original expectations. The basis of our idea was to create a multiplayer boids and predators game, which we have definitely achieved. Our game has a complicated menu with multiple layers of options. The game also has both single and multiplayer options. Shark mode exceeded our expectations. A predator chasing a predator chasing boids with shrinking borders was definitely not part of our project proposal and ended up being the most fun of the three modes.
 If we were to continue this project, we might add an option for the user to choose how long the timer runs for in timed mode. Further, we could introduce a more intense flocking algorithm to single player timed mode. This may make the game even more fun and introduce new strategies to maybe wait until the boids flock together before going after them.
 Another customizability option would be to have different levels, something we discussed in our proposal but instead implemented different modes. Easy mode would have a fast-moving predator and slow boids with a small visual range. Hard mode would have boids that moved more responsively and a larger visual range to “see” the predator coming from further away.
 If we had a larger budget, we would have used a larger TFT. The larger TFT means we could see everything larger and then maybe even upgrade to four joysticks. Using four joysticks would mean we would need either to use 4-to-1 multiplexers so we do not use four inputs for each joystick, or otherwise use the port expander. The larger TFT would take longer to erase and draw on because there are more pixels, which is something we would need to be wary of.
 The file that we wrote is completely original. However, it does call on helper functions for TFT and protothreads that were written by Syed Tahmid Mahbub and Bruce Land respectively. Both libraries come with .c and .h files and have copyright and author information at the top so it is completely clear where the code came from. We believe that this falls under fair use because the code was written for students in ECE 4760 to use for educational purposes. We do not plan to sell our game, and Land's code is available on his website for anyone on the internet to view. There are no real patent opportunities for our project, but it is very possible to be published in a minor periodical or on an instagram account. We did not do any academic research, so publication as a research paper seems unlikely.
 After referring to the IEEE Code of Ethics, our design decisions and actions are consistent with their guidelines. When working as a group, we treated each other and other groups with respect. We acted with integrity by making sure no code was plagiarized and communicating effectively with each other along the way. When something was not working, we did not criticize or point fingers, but instead tested our code, did research, and proactively solved problems. The final product does nothing to intentionally offend or harm any individual or entity. Our project does not involve any parts of the design or materials that could be dangerous to those who do not know how to use them or anything that is controlled or limited under the law.

A Special Thank You

A special thank you to Hunter and the ECE 4760 course staff for an awesome semester!

And thank you to Microchip for tweeting about us!

Appendix A

The group approves this report for inclusion on the course website.
The group approves the video for inclusion on the course YouTube channel.

Appendix B

Gist Link if Gist is not embedded above.

Appendix C

Schematic

Appendix D

Description Part Number Vendor Unit Price ($) Quantity
Red 5-Pin Arcade Joystick B01N2G0H1T Amazon 11.00 2
Big Board ECE 4760 10.00 1
PIC 32 PIC32MX250F128B Microchip Technology 10.00 1
TFT LCD ILI9340C Adafruit 10.00 1
Lab Speakers ECE 4760 2.00 1
Audio Socket SJ1-3525N CUI Devices 0.70 1
Breadboard 239 Adafruit 5.95 1
Jumper Cables 266 Adafruit 0.05 23
10 kOhm Axial Resistor MFR-25FRF52-10K Yageo 0.01 8
Push Button B06XT3FLVM Amazon 0.61 1
2.1mm power jack ECE 4760 5.00 1
MCP4822 DAC MCP4822-E/P-ND Microchip Technology 3.92 1

Total Price: $72.13

Appendix E

Quin

  • Debouncing button
  • Menu FSM and logic
  • Menu cursor and selection
  • Menu boids in background, flocking
  • Wave to DAC conversion and script
  • DMA

Tyler

  • Instruction screen
  • Multiple predator compatibility
  • Predator avoidance algorithm
  • Eating boids, keeping score, and determining a winner
  • Game Over screen
  • Timed Mode
  • Shark Mode, including movement of shark and shrinking borders

Chidera

  • Part ordering
  • Testing the Joysticks
  • Breadboarding and mapping the Joysticks to the PIC
  • Movement of the predators
  • Multiple predators
  • Predator avoidance algorithm
  • Schematics
  • Race Mode
  • Wave to DAC conversion

References