Final Deliverable Description

We have finally acomplished our project goals. The Improved Maze Runner works at a reasonable speed on several brands of computers at UC Berkeley. Aside from the texture mapped, six sided, connected polygon engine, we added a more pleasing background and interface. Vindalf the dungeon master represents the interactive help by giving you suggestions and making comments durring the game. He is not entirely comprehensive, yet fairly amusing and will not let a person using the demo leave without knowing the less obvious facts about our engine like clicking the right mouse button allows you to look up and down. The mouse cursor now changes to arrows in the view screen, so it is easier to tell what you will be doing when you click. In response to Prof. Forsyth's problem with his super fast computer, the speed of your character is now relative to how far your cursor is from center of the view screen. This way you can move as slowly or as fast as you want to. In addition to these interface features, animations were added to texture mapping, and the dungeon was expanded to show the advantages of using the Improved Maze Runner over the more restrictive engine shown in class. Various bugs that were found while testing and expanding the dungeon were also fixed.

---

• Division of Work - We are happy with how well the work was divided. Both of us did a comparible amount of work, and our engines melded nicely.
• Joshua Cantrell
• texture mapping structures and organization
• texture mapping algorithms
• polygon drawing algorithm
• X Windows interface using g++
• lighting algorithm
• texture animation
• drawing of the textures used
• designed a portion of the dungeon
• designed cursors for X Windows
• Shane Cantrell
• point, cube, face, and polygon data structures and organization
• sight clipping algorithms
• maze editing class
• movement algorithms, functions
• drawing of the background graphics, buttons, switches, and Vindalf as well as programming the interfaces for them
• bitmap class used for double-buffering, background animations, and retaining graphical information
• Windows 95 interface using Borland C++ Builder (as the compiler) and his Painter class to send the bitmaps to the window
• also designed a portion of the dungeon
• adapted Joshua's cursors to Windows and made them bigger :-)
• Final Statement of Goals - We accompished what we had expected and a little bit more...
• Accomplished
• Maze clipping algorithm
• Movement and collision detection
• Texture mapping the clipped polygons
• A dungeon to explore
• A mouse interface to interact with the program
• Simple lighting effects for the maze walls
• Maze editing class
• Exceeded
• Gravity which allows your character to fall
• Vindalf the helpful dungeon master who tries to be helpful
• Animated textures to liven up the maze
• Cross platform (can be compiled for SGIs, DECs, most HPs, Solaris, Linux, Windows 95, and Windows NT)
• Missed
• Nothing :-)

Previous to working on this project I had already been working on my own generalized line drawing algorithm. It shares qualities with other line drawing algorithms, but it was mostly influenced by whatever I have read about line drawing algorithms in books. The way I explain it is different than I've heard Bresenham's Line Algorithm explained, and I don't think the end result is as optimal, but it works and I used it in the development of my polygon drawing algorithm. For this project, I had one related page of information that was already in existance (a discussion of the line drawing algorithm) and I created two as a result of needing to create them (a discussion on texture mapping and a discussion on drawing polygons). To make my life easier, I chose to derive my own equations that texture map a polygon. I found by doing this that there is more than one way to arrive at an equation to texture map with (my end result looks different than other results I've seen). I also decided to modify the line drawing algorithm that I had already written before the start of the project to create my polygon drawing algorithm. Because I went into great detail on how I derived and came up with the results, I have separate WWW pages for each topic I have done (excluding those things I had no time to write so in depth about).

• Drawing Lines (previous to project)
• Texture Mapping (result of project)
• Drawing Polygons (result of project)

To make writing for Xlib easier, I made a C++ class about a year ago. I used this class in the project to help me avoid rewriting code that I already knew worked. As was necessary, I added to the class and moved functions from protected to public (mostly done to give me access to those functions necessary to make the graphics fast under X Windows). I even found some bugs that needed to be fixed and fixed them.

The basic engine is based on how we think the Descent engine made by Parallax did its texture mapping. We noticed that they used six sided figures that connected perfectly while using a free editor designed for the game called Devil. It was also obvious that the cubes were only aware of the ones connected to them because two passageways could cross without any problems. Some people refered to this as 4d since two objects could be within the same 3d space. For us it was an indication of how the programmers drew the maze by drawing recursivly forward instead of drawing each polygon individually. The Descent engine and Forsyth's maze runner lecture gave us the inspiration of how we could use the knowledge from CS184 to design a similar engine, even though our engine is slightly less flexible in comparison to the Descent engine.

Of course, inspiration is not a finished project. Before spring break, my brother and I argued over what to do for the project. At first, we thought it would be easier to make a maze runner based on Forsyth's only with variable heights for the ceilings and floors. This idea posed some annoying problems when dealing with ramped floors, though. After a few days of literally arguing about using this idea and attempting to make something similar to the Descent engine, I finally convinced Joshua that I knew how to implement the clipping for the Descent engine. Actually, I was thinking of using a method which could not possibly have worked, but it kept me happy until the week of contracts when we talked to Forsyth. After meeting with Forsyth, I realized how absolutely flawed my method was and told Joshua about my problem. Joshua then told me about his idea to clip the walls after projecting them onto the view plane. He also had a method for recursing through the cubes which required some very complex concave clipping, but I ignored this and used my previous idea for recursion using convex polygons to derive the basic algorithm we finally used.

One thing that made me so insistant on making an engine that uses six sided maze segments is that each segment can be treated in exactly the same way. This meant that only one case had to be considered and debugged instead of several, and at the same time the engine would be capable of representing mazes more complex than a simple grid. The first step involves rotating and translating all of the points into camera space for the current cube. For each of the cube's faces (except for the one you entered through), the lines are clipped against a given z value to get rid of the distortions that happen near and below a z of zero. Once clipped in 3d, the points are converted into 2d, and clipped using the Sutherland-Hodgeman method against the entering face (the face which the recursion entered through). Both the new face and any polygons formed by the face intersecting the view plane are returned. The new face is either drawn if given a texture or continues drawing the cubes beyond. Whenever the view plane is intersected, the side outside of the current cube is drawn. These are the basic steps to the clipping engine though actually implementing these steps requires a bit more thought.

The movement engine represents the player as a sphere levitating above the floor. It uses a sphere so the player will be able to turn without getting stuck. The levitation is accomplished by shooting a vector through the floor and finding the distance to the intersection. If the intersection is less than the player's height, the player moves up, and if the intersection is more than the player's height, the player moves down. It also traces the path of a vector to determine the destination cube of the view plane when turning or moving which is important in making sure the engine begins drawing from the correct cube after the move.

---

A Final Set of Screen Shots - For the poor souls who can't run one of our executables. :-(

You look back at the enterance to the dungeon.

---

Things have changed slightly since your last visit. Now the chasm is filled with water.

---

You wonder what BIG surprise awaits around this bend. :-P

---

What is this? A mine shaft in the dungeon?

---

Executables! - Since we have an executable for so many types of computers, there is almost no reason why you can't try the program out for yourself. Each executible comes with a README file.

• Windows 95 / NT
• To run the executable, first unzip it using pkunzip 2.50 (or any other unzipping utilities that expand *.zip files). Finally, run the game by clicking on "ingarth.exe".
• Because I ran out of room on my school's account, I was forced to remove the UNIX executables. Most UNIX users should still be able to compile the program using the source code which is available at the bottom of this page.
• Linux (for the Intel PC)
• To run the executable, you must first ungzip the file with the command "gunzip ingarth.linux.tar.gz". Then you must untar the resultant file with the command "tar -xvf ingarth.linux.tar". Finally you can run the executible by the commands "cd ingarth" followed by "ingarth".
• SGI
• To run the executable, you must first ungzip the file with the command "gunzip ingarth.sgi.tar.gz". Then you must untar the resultant file with the command "tar -xvf ingarth.sgi.tar". Finally you can run the executible by the commands "cd ingarth" followed by "ingarth".
• HP (except the ones in the graphics labs)
• To run the executible, you must first ungzip the file with the command "gunzip ingarth.hpux.tar.gz". Then you must untar the resultant file with the command "tar -xvf ingarth.hpux.tar". Finally you can run the executible by the commands "cd ingarth" followed by "ingarth".
• Solaris on the Pentium Pros
• To run the executable, you must first ungzip the file with the command "gunzip ingarth.solaris.tar.gz". Then you must untar the resultant file with the command "tar -xvf ingarth.solaris.tar". Finally you can run the executible by the commands "cd ingarth" followed by "ingarth".
• DEC (running Ultrix)
• To run the executable, you must first ungzip the file with the command "gunzip ingarth.ultrix.tar.gz". Then you must untar the resultant file with the command "tar -xvf ingarth.ultrix.tar". Finally you can run the executible by the commands "cd ingarth" followed by "ingarth".

---

Source Code! - Wow! An actual 3d engine that works and isn't being kept top secret! Actually, the code and graphics are still protected by Copyright Law, so don't copy them and give yourself the credit. If you have any questions, just mail the person who worked on that part of the code. :-)

• UNIX Source
• To access the source, you must first ungzip the file with the command "gunzip ingarth.unix.src.tar.gz". Then you must untar the resultant file with the command "tar -xvf ingarth.unix.src.tar". Finally you can learn more about the source code and how to compile and run the program by the commands "cd ingarth" followed by "more README". The code can generate slightly different code than the machine specific binaries because of machine specific default parameters used when compiling the code for a particular machine (more is discussed in the README).
• Windows 95/NT Source (This code only works with Borland C++ Builder. Of course, the organization of Borland C++ Builder is very obvious, so it should be fairly easy to understand what is going on.)
• To access the source, unzip it using pkunzip 2.50 (or any other unzipping utilities that expand *.zip files).