To determine the cat’s motion, we brainstormed many algorithms. One ambitious option was movement based on a trained neural network. A neural net is a representation of neurons in a brain. Each synapse fires if the input is large enough (determined by a sigmoid function). Inputs to the neural net would be the position and velocity of the mouse and outputs would be the change in direction of the cat. In order to train the neural net, each move would be given a fitness score based on how much closer the move has brought the cat to its goal. The weights on the input of the neural net would be readjusted based on this fitness score. Neural nets normally perform very well on FPGAs because both are very parallel processes. However, the complexity of implementing the basic game play and a simple algorithm precluded us from writing a neural net. Additionally, a fitness function and the training of the neural net would be very difficult.
We were able to implement a simpler algorithm. This algorithm would take the positions of both the cat and the mouse and determine what direction the cat has to move to reach the mouse’s current position. It then subtracts the desired position from the current and feeds that into the change of position for the next move. We divide the space around the cat into eight segments, however, these 45 degree segments are not evenly distributed because the FPGA cannot easily perform complicated math functions like sine. One can imagine how this algorithm may be improved. One way is to factor in the current direction the mouse is heading so that the cat can anticipate the motion of the mouse. Also, at times when the cat or mouse is on the border of two directions, the cat oscillates between the two very quickly and wastes time that could be used pursuing the mouse. We could program in hysteresis to fix this. All in all, though, the cat’s algorithm performs relatively well in capturing the mouse.