6. Target Generator

Pseudo Random Number Generators

This module randomly generates the position of the next target that the player must get the snake to eat. This is done using two pseudo random number generators. If you remember, these were mentioned right at the beginning of the laboratory, along with shift registers. This is because that is pretty much all they are.

Pseudo random number generators (PRNGs) come in a variaty of forms. This particular style of generator is called a Linear Feedback shift Register (LFSR). It is a synchronous device which shifts all of its bits each clock cycle, but instead of taking its input from an external source, it creates the new value from a series of "Taps" (connections to various bits along the length of the shift register), which are combined with XOR gates. For more information regarding LFSRs look at the corresponding wikipedia article. You might recall from last year's Digital Circuits course that this is a Class 2 type of state machines. Look at your notes from last year.

Reduced Resolution

The VGA interface supports a resolution of 640 by 480, but this is far too detailed for our game. Because of this, when the Snake Control module determines the colour of a pixel based upon its address, the first two bits of each address bus are ignored, thereby reducing the resolution by a factor of four in each direction.

We therefore require two LFSRs, one 8-bits long, the other 7-bits, to be able to randomly generate numbers between 0 and 160 (horizontal axis), and 0 to 120 (vertical axis).

The Tap values required for 7 and 8 bit LFSRs are detailed in a Xilinx article named xapp052.pdf, which is freely available:
http://www.xilinx.com/support/documentation/application_notes/xapp052.pdf.
Note that the values from these taps are not XORed together, instead you must use XNORs instead.

Fetching a New Random Number

Once constructed, these LFSRs will constantly shift, producing a new random number every clock cycle. This is not what is required here, as we wish to hold a pixel address until the player successfully steers the Snake to target. Therefore, a second process is required that records and holds the current value of the LFSR whenever the reached target signal is asserted, thereby allowing the LFSRs to constantly shift in the background. Because each player will take a different amount of time to get to each target, the selection of the new target is a random number too.

One last aspect of the recording mechanism, is that it must make sure that the random number that is presented to the Snake Control module lies within the pixel range (i.e. within the 160 by 120 range). Therefore control logic should be in place to test to see if this is so, and if not, change the horizontal or vertical values, or both, to a pre-determined value (80 for horizontal, 60 for vertical, are both good as it places the target in the middle of the display).