to the project page...
The Improved Maze Runner's 2nd Deliverable Page
By Shane Cantrell (cs184-dd)
and Joshua Cantrell (cs184-de)
2nd Deliverable Description
2nd Deliverable Notes
So far in this project we have been progressing mostly as planned. Our
3d engine now has texturmapping, lighting, movement, gravity, and the ability
to look up and down. We are having difficulties transfering graphics to
an X Window quickly, so the X Windows version is slower than the Windows
95/NT version which seems to run reasonably well on a Pentium 100 MHz.
Getting this far with the Improved Maze Runner was not easy. Despite the
simple looking product, clipping, movement, texture-mapping, and drawing
polygons gave us considerable problems. We lost large amounts of sleep
during the past two weeks trying to invent practical solutions to the many
problems we had encountered.
Joshua was satisfied with his 1st deliverable's polygon drawer until we
used it to texture map the maze. Then we noticed missing walls, holes,
cracks, and other displeasing effects caused by floating point imperfections
(and a few bugs in the polygon algorithm).
Both clipping and movement were also haunted by floating point errors --
especially numbers very close to zero, but not zero.
Conceptually clipping seemed easy from within a cube, but when starting
the project we forgot to think about moving in between the cubes. One oddity
Shane immediately noticed was when your view-plane is intersected by a
face in the middle of a passage way, your algorithm must know to draw the
adjacent cube. View-plane intersections can be observed in "line mode"
by aligning yourself slightly with a face and looking along that face.
A line (which does not represent an edge) will be drawn where the engine
is forced to recursivly clip down the two adjacent cubes instead of just
the one you are in. (Actually, Shane overlooked this at first because he
forgot that every face would not be a wall... *grin*)
Movement and collision are just as important as clipping with this engine
since everything is contained within a cube. If your view-plane is allowed
to intersect a wall, then the clipping alorithm will draw nothing on the
other side causing strange effects. The movement engine also has to keep
track of which cube your view-plane is in or the clipping engine will get
confused and may think there is nothing to see. An example of this was
shown with an earlier movement engine where the view-plane would get lost
when you aligned yourself perfectly with a cube's edge (from the center
of the cube), and you walked through it. It was possible to see the cube
you left from within the void (and all the cubes beyond it) if you turned
around, but everything in front of you was clipped. We joked that the character
was entering another dimension (definitely another memory location).
Texture-mapping is one of the most crucial aspects of a maze runner. We
discovered this when Joshua ran it from Linux at home and found that his
texture-mapping algorithm was eating up far more time than even the clipper.
He promptly made some optimizations, but it still ran sluggish on his 486
66 MHz. :( One technique Joshua uses to optimize his code is to use binary
shift operators to avoid using multiplication and division unnecessarily.
Another technique he uses is linear interpolation to predict which texture
points to use for a selected number of points instead of calculating the
transformations for each individually.
Another problem we faced with getting the maze runner to work was the actual
making of a maze. Our scheme is too flexible to use a simple grid like
the Java maze runner. Forsyth suggested making an editor with fixed block
units, but after thinking it over, we decided that an editor would have
been a project in itself. (Actually, it may have been possible with one
more group member.) Instead, Shane made a slightly intuitive class to help
him make the maze we took the screen shots from. The current maze consists
of 20 cubes.
We are especially proud of this engine because we did not have to use Open
GL, and we have been able to port it to HPs, SGIs, and Intel machines (running
either Linux or Windows 95). (One of our personal goals was to make the
We are also proud of the great wall textures Joshua was able to make using
Deluxe Paint II enhanced, and how well Shane's palette scheme worked for
Some Super, Sensational Screen Shots!
The player looking down into a shallow chasm from a bridge.
The player glances across a dome-like room. The enterance (and
the bridge) are now in a darkened passage, and another passage leads down
into the chasm.
The player begins descending down the ramp.
The player looks up at the bridge from within the chasm.
Executables! - After seeing the screen shots maybe you would
like to look around yourself. :-)
(These links have been disabled because the Final Deliverable
page has the final version of the assignment.)
SGI (Slower, older version from 5-2-97. One reason for its slow
speed is the fact that we forgot to use -O3 (the optimizer) when compiling.)
To run the executible, you must first ungzip the file with the command
"gunzip csgame.sgi.tar.gz". Then you must untar the resultant file with
the command "tar -xvf csgame.sgi.tar". Finally you can run the executible
by the commands "cd csgame" followed by "csgame".
Windows 95 / NT (Faster than the SGI version... at least on a
Pentium 100MHz or faster. It also has real-time falling and a smoother
mouse interface.) To run the executible, you must first make a new folder,
put the file in the folder, and type "pkunzip cetest.zip" using pkunzip.
Run the game by clicking on "cetest.exe".
Linux for Intel PCs (Bearable on a i486 dx2 66MHz. Requires X
Windows in 8bit linear mode. It also has real-time falling and a smoother
mouse interface.) To run the executible, you must first ungzip the file
with the command "gunzip csgame.linux.tar.gz". Then you must untar the
resultant file with the command "tar -xvf csgame.linux.tar". Finally you
can run the executible by the commands "cd csgame" followed by "csgame".
Note: Line mode draws lines to show the borders of all the polygons