About

The game involves a cat which is programmed to be an "AI" with the ability to move autonomously and automatically to chase the mouse (controlled by the user through push buttons). The Cat & Mouse game was prototyped on a breadboard and finalized on a hand-held PCB assembly. Background music was played through an audio jack and the display screen was designed to be a selective menu with touch screen.

An STM32F091RCT6 ARM microcontroller with 256 KB Flash memory and 32KB SRAM was used to program the game. SPI (Serial Peripheral Interface) was used to send data between the microcontroller and LCD display. The type of touch screen used was a 3.2" ILI9341 TFT LCD with breakout board from Adafruit, which had a display of 320*240 resolution. It had a four-wire resistive touchscreen and we wrote a simple driver for it to detect single touch locations. DAC (Digital to Analog converter) was used to convert and generate music. ADC (Analog to Digital converter) was used to communicate the touch screen data. Timers and interrupts were used to listen and respond to any instructions depending on what the user was doing (e.g. pressing a button in the menu). GPIO was used to receive input from push buttons.

Click here to view the source code. Most of the algorithm can be found in ece362_finalproj/src/support.c.


Cat's Algorithm
The cat was programmed to seek the shortest path towards the mouse with the idea inspired by dijkstra's algorithm. A continuous loop is run which implements the necessary functions to keep the game going such as checking which of the mouse's directional buttons are pressed. For every certain number of iterations in the loop, the cat will check and update its path towards the mouse. As the game keeps going and the user increases levels, the frequency at which the cat updates the shortest path will increase to give the player the feeling that the cat is getting smarter. The cat was programmed to only exist within the 14 by 10 tile maze and as you may notice it never walks past the outer green perimeter. In order to prevent the cat from walking through walls, the length of path coded into the black wall tiles was 140 while the white path tiles had a length of 1. Therefore, when dijkstra's algorithm is used to evaluate the shortest path between the cat and mouse, there will never be a path determined that will lead the cat to go through a wall. Another problem we had to solve was working with tile vs pixel values. As you may notice, the cat and mouse are not hopping from one tile to another and they may appear to be in between two tiles at times. We therefore had to convert back and forth between their specific pixel location and the closest tile such that the shortest path could be evaluated successfully.

Dijkstra's Algorithm in action
An example maze figure is shown where the cat is on the top left: coordinates (row 0, column 0). And the mouse is on the bottom right: coordinates (row 7, column 6). Each number on the 8 by 8 matrix represents the shortest distance from the mouse to that coordinate. A value of 8 x 8 = 64 is encoded into the path length of each wall tile. The wall tile coordinates highlighted in red show the higher values which ensure the cat will not attempt to walk through a wall. The shortest optimal path found from the mouse to the cat is highlighted in yellow. By backtracking through this path, the cat would be able to reach the mouse quickly.

The path found through the algorithm for the cat to take is as follows with the first index of each tuple representing rows and the second columns:

(1, 0) -> (2, 0) -> (2, 1) -> (2, 2) -> (3, 2) -> (4, 2) -> (5, 2) -> (5, 3) -> (6, 3) -> (7, 3) -> (7, 4) -> (7, 5) -> (7, 6)

Mouse Mechanics
The input push button values are read in from the GPIO port input data register and the mouse will then move towards the corresponding direction. Unlike the cat, the mouse's method of wall detection involved a more brute force approach. The challenge in this part was to ensure that not even a portion of the mouse would be able to overlap with a wall. Since both the mouse's and wall's location were only located at a single pixel coordinate, we could not just check if the two points were the same to detect wall collision obviously due to the fact that both the wall and mouse were larger than one pixel in size. Therefore each black wall tile had a "radius" of no entry to account for both the size of the wall and mouse.

Map and Wall Generation
Apart from implementing the shortest path algorithm, one of the biggest problems faced was including several maps in the game. Towards the end, we were able to include 30+ hard coded maps. Because there was not enough flash memory to store 30 individual wallpaper backgrounds, we had to condense the information into a matrix data structure. The inner maze consisted of 14 by 10 tiles. However, we were able to further condense each map matrix into a 12 by 8 given that we will never place a wall directly next to the outer green blocks. With this done, we simply filled in each matrix coordinate with the appropriate binary value (eg. 0 for a path 1 for a wall) which was the minimum amount of information we needed in order to generate the maze. For each map chosen during gameplay, the selected matrix will be passed to a variety of functions in order to inform them of where a wall or path is. Using this method, the functions were able to determine where to place black/white block tiles, where to assign a length of 1 or 140 for the cat's algorithm and where to allow the mouse to go.

SPI (Serial Peripheral Interface)
SPI was used to communicate between the microcontroller and the LCD display. In SPI communication, the two devices communicating are typically named Master and Slave. Master refers to the device which configures the clock speed, data format and other parameters for communication. The Slave refers to the other device which is able to receive information from the Master but (in some cases) also send back information to the Master. In this case, the microcontroller serves as Master and the LCD display serves as the slave. The SPI configuration usually consists of a 4 wire interface.


On the example, we could see what it looks like to transfer 15 bits of information from the Master to the Slave. Communication only begins when the NSS is low and one bit is sent for every clock pulse.

Because the LCD display does not send back information to the microcontroller, we only use 3 of the 4 wires: MOSI, SCK and NSS. The Baud rate (or the frequency at which the bits are transferred) is controlled by the serial clock. In the STM32 microcontroller, we can configure the Baud rate in first SPI control register. The first SPI control register consists of 16 bits each with their own function.


PCB design and soldering
On the hardware side, we drew the schematic and completed the layout using Altium from the ground up, referencing the Kicad design. We were able to utilize the huge online component library to quickly place component footprints and buy them online at the same time. The final PCB soldering process had some obstacles including being unable to reset the microcontroller. However, after some debugging, it turned out the issue was that we forgot to connect VCCA to 3V. After flywiring it to the 3V rail, the PCB worked as expected.