M A Z E A S I M P L E G P U WIT H EMBE DDE D V I D E O GAME Designed by: Joseph Liang [email protected] Joe Zhang [email protected] Wei-Chung Hsu [email protected] David Lau [email protected] of Contents 1. Introduction 2. Design 2.1 Hardware Components and Connections 2.2 Maze Generation 2.3 Bersenham’s Line Drawing Function 3. Implementation 3.1 Maze Generation and User Input (UART) 3.2 Hardware Implementation 3.3 Optimizations 4. Advice For Future Students 5. Responsibilities 6. Source Code 7. References1. INTRODUCTION We implemented a random maze generator. The program generates a random 10x10 maze. The way this was done is to start with all blocks in the 10x10 matrix in separate disjoint sets, then, randomly remove walls until all the blocks are in the same joint set. Each maze will have only one path from the starting block to the ending block. The user starts at the starting point, and then he can use the arrows to control the direction in which he moves. A square represents the user. When the square reaches a pre-defined block, the program will detect a successful path out of the maze and it terminates. We designed a simple GPU processor that contains a line drawing. The user would be able to control a graphical object to traverse through a generated maze using the keyboard. There are 3 parts to our project, (1) hardware functions, (2) firmware/driver/API functions, and (3) software game logic. For our hardware, we utilized UAT to establish a connection between the keyboard and the FPGA. Within the FPGA we implemented the Bernsenham’s line drawing algorithm in VHDL, which was translated to an API function and called by our software. We then coded game engine with, which produced signals to communicate with the external Toshiba 512KB SRAM and the Texas Instrument Video D/A converter to display graphics.2. DESIGN 2.1 Hardware components and Connections We implemented our video memory into Toshiba 512KB SRAM. For each color frame with 640x480 resolutions, it took 300KB, and this would limit us to implement a double buffer swapping function. The data buffer has both a read and a write feature. Therefore, it could load the game graphics data in the game loading time. We directly imported a lot of the Lab 5 source code in Spring 2004 [1] as it was similar in structure. We need two cycles delay between PAD I/O and VGA, because the VGA comes two cycles later. The following is a diagram of our data flow:The FSM in the above diagram is an implementation of bersenham's algorithm. Basically, bersenham's algorithm takes two points , (x0, y0) and (x1, y1) and plots pixels between these points to approximate a line drawn between these two points. Our FSM is an implementation of Bersenham's algorithm, which takes 4 integers from the OPB_bus which represent x0, y0, x1 and y1. In each clock cycle, it produces a new Xout and Yout, which represent the pixel that needs to be drawn in this clock cycle. When it finishes the line, it waits for the next set of points from the OPB bus. We also implemented a VGA block which interfaces between the monitor and the rest of the blocks. We programmed our FSM to have priority over the VGA block, so we have the stall signal connected to the VGA block. When the stall signal is on, it indicates that the FSM is writing to the SRAM, so the VGA should not be reading from the SRAM at this time! If ths stall signal is not on, then the VGA sends a read request to the PAD I/O block with the address of the data it wishes to access. The PAD I/O block takes the data from this address in the SRAM, and sends it to the VGA. The VGA then writes this data to the screen. The PAD I/O block services read/writes to the SRAM via the VGA and FSM blocks. The FSM writes data to the SRAM whereas the VGA reads from the SRAM; thus the data line from the PAD I/O block to the SRAM must be a tri-state buffer. The pad I/O has as its inputs an address line and a read/write signal to let it know whether it is writing to the SRAM or reading from it,.2.2 Maze Generation Generating a random maze involves manipulating disjoint sets. Disjoint sets, in computer science, are collections of objects that have no common members. They can be represented any basic data structure. The basic idea of random maze generation is to start with as many disjoint sets as there are blocks in the maze, then randomly remove a boundary between two sets and combine the neighboring contents into one set. This process stops until all blocks are determined to be in the same set. Here is the pseudo code for the maze generation algorithm: While (not all blocks are in the same set) { Wall = randomly chosen boundary between two sets If (the neighboring elements are not in the same set) Remove wall Change their set numbers to the same number } We used a matrix to represent the maze. Each element of the matrix represents a block in the matrix, and it’s a struct that has three members: set number, right wall, bottom wall. The set number denotes the set that the current block is in. The right and left walls denote the boundaries with its right and bottom neighbors. This is an efficient way of representing the information about the maze because it facilitates the process of analyzing and printing the maze on screen.2.3 Bernsenham Line Drawing Function We needed to print the maze using hardware. The maze consisted of only straight lines, and therefore we decided to implement a famous hardware line-drawing function called the “Bersenham Line Algorithm”. The algorithm takes the coordinates of two pixels on screen, and would draw a straight line connecting the two pixels. The following is the pseudo code of Bersenham’s Line Algorithm, taken from wikipedia [2] (http://en.wikipedia.org/wiki/Bresenham's_line_algorithm). function line(x0, x1, y0, y1) boolean steep := abs(y1 - y0) – abs(x1 – x0) if steep then swap(x0, y0) swap(x1, y1) if x0 > x1 then swap(x0, x1) swap(y0, y1) int deltax := x1 - x0 int deltay := abs(y1 - y0) int error := 0 int y := y0 if y0 < y1 then ystep := 1 else ystep := -1 for x from x0 to x1 if steep then plot(y,x) else plot(x,y) error := error + deltay if 2xerror ≥ deltax y := y + ystep error := error - deltaxThe line is drawn between two points (x0, y0) and (x1, y1). It starts from (x0,y0) and starts to go in the down and right directions. It
View Full Document
Unlocking...