Labyrinth Get in the Maze Laplie Anderson and Mihalis Papalampros 6.111 – Introductory Digital Systems Lab December 13, 2006Abstract Labyrinth is a 3D maze game. The goal of the game is to reach the center of the map without getting lost. To complicate things, players start the game in a random location on a randomly generated map. The player aided by only what they see in front of them, and a minimap that shows their general location on the map. Labyrinth was programmed using Verilog and the Xilinx tool-chain. Labyrinth runs on the 6.111 Labkit displaying the game at 1024x768 resolution.Table of Contents Abstract List of Figures List of Tables 1 Overview 1.1 Initialization 1.2 User Interface 1.3 Winning 2. Module Description and Implementation 2.1.1 Map Generator 2.1.2 Linear Shift Register 2.13 Game Logic 2.2 Video System 2.2.1 MiniMap 2.2.2 SceneRenderer 2.2.3 Trigonometric Lookup Table 2.2.4 DistanceToHorizontalWall/DistanceToVerticalWall 2.2.5 DividerWrapper 2.2.6 ColumnRenderer 2.2.7 DoubleBuffer 2.2.8 BufferSelect 3 Testing 3.3 MiniMap/Background 3.4 DividerWrapper 3.5 DistanceToHorizontalWall/DistanceToVerticalWall 3.6 DoubleBuffer 3.7 ColumnRenderer 3.8 SceneRenderer 5 ConclusionsList of Figures Figure 1. Block Diagram of Entire System Figure 2. Map Generation Technique Figure 3 Ray Tracing Algorithm Figure 4 Field of view of the player Figure 5 State transition diagram for SceneRenderer Figure 6 Common Debugging Screen Figure 7 Internal Representation of Map1. Overview Labyrinth is a 3D maze game designed in Verilog. Players are presented with a 3D view of their location in the maze and must use this information along with a sparse minimap to navigate. The goal of the game is to reach the center of the map. There is at least one path to the center and the player must find that path. To complicate things, the starting location of the player and the map are both randomly generated at the start of each game. As a result, the replayability of the game is increased dramatically. 1.1 Initialization When the game begins, it is in its initialization state. In this state, the game is randomly generating maps and then checking to see if the generated map is a valid map. When a valid map is found, the game begins. You can generate a new random map by pressing the start button at any time. 1.2 User Interface The game is controlled using the buttons and switches on the Labkit. Using the forward and back buttons, the player steps forward or steps backward in the general direction that they are looking. Using the left and right buttons, the player turns left or turns right. Due to time constraints, the player does not move in the exact direction that they are looking. The current implementation only distinguishes between eight distinct directions of movement though the player is able to see a full 360 degrees. In addition, there is a start and a reset button. The reset button puts the game into the initialization state and tells all modules to stop what they are doing. The start button is very similar to the reset button in that the game begins again. The difference is that the start button only generates a new map without initiating a global reset. The player location changes to a start position, and the map changes, but other modules are not told to reinitialize. There is not a noticeable difference to the player between start and reset, but there is a difference for diagnostic purposes. The minimap is controlled by two switches. Switch0 toggles whether or not the minimap is displayed on the screen. Switch1 toggles ‘cheat mode.’ In cheat mode, the location of the walls is displayed on the minimap. With this extra information, the game in instantly winnable. Therefore, in an actual game, the use of ‘cheat mode’ is strongly discouraged. 1.3 WinningThe game is over when the player reaches the center of the map. The player is free to continue exploring the map or pressing ‘start’ to restart the game. 2. Module Description and Implementation Labyrinth is divided into two major parts: the map generation and game logic, and the graphics display system. Each part has various modules responsible for a specific tasks described later in this document. The interconnections between the modules are shown in Figure 1. Figure 1: Block diagram showing the connections and interfaces to the major modules of Labyrinth. The modules with the dotted outline are modules either provided by the 6.111 staff or generated modules from IPCore. Each directed arrow is an information flow from one major module to another. The labels for the arrows are the Verilog names for the given wires. 2.1.1 Map GeneratorThe Map Generator creates a random 21x21 map for the labyrinth each time start is pressed. It has as inputs the clock, the start signal, and reset. The outputs are the map, which consists of 441 bits, and the done signal. Due to the fact that we cannot have two dimensional arrays in Verilog, the representation of the labyrinth map must be done through a one dimensional array of binary digits, with one corresponding to a wall and zero to empty space. That means that the first twenty one digits correspond to the first row, the next twenty one bits to the second and so on. In the very beginning, namely right after the compilation of the whole project, reset should be pressed in order to have the appropriate initializations of the registers. Then each time start is pressed setup goes high and done is set to low. With that condition, that is with setup being high and done being low, the main core of the code inside the always statement starts. We first set the reset signals of the lfsrs to be low again since the reset is done once for every lfsr. That happens because an lfsr should be reset once in order to produce its pseudorandom sequence of numbers. Figure 2. Map Generation technique. The goal is to go from the initialization picture on the left to the maze on the right. The first step of the always block is the initialization. The initialization is actually creating concentric squares of empty spaces and walls, that is all zeros or ones, alternately. We could do that with three nested loops, one for k, the number of the square, one for j, the number of the row we are working on, and one for i, the number of the column. The best way to do that is through a finite state machine with four
View Full Document
Unlocking...