Wolfenstein Take-Off #6,837Mike Mills 6.837 Final Project Writeup 12/5/99 AbstractA method for two-dimensional ray casting with arbitrary angle walls is presented. The system wasimplemented for DOS 3.0 in order to compare to a popular game of the same nature called Wolfenstein. The basic method is discussed first, followed by a description of the implementation process. Wallintersections are calculated by first pre-computing a grid data structure containing lists of the linesegments that pass through each square. Cramer’s Rule and a simple loop are used to calculate theclosest intersection. Textures are also applied to the walls and optimizations made in an effort toachieve between 15 and 20 fps on the test platform, a high-end 486. 1 IntroductionWolfenstein 3D (c) was a popular first person "shoot ’em up" in the early nineties and late eighties. Atthe time it provided a clever alternative to the traditional polygon-based flight simulators that peopleassociated with "3D games," and judging by the trend of clones that followed it, looked to be the waveof the future. After all, ray-tracing, in all of its elegance, is a very attractive idea; all Wolfenstein didwas take that idea from three dimensions to two. A fully functional ray tracer casts a ray (or multiple rays) through each pixel in the viewport out into thevirtual world. When the ray returns, it contains information about how to shade or color that particularpixel of the viewport. The advantage of this approach is the ability to view the scene from any angleand observe a nearly exact picture. The quality of a ray traced image does not come without its costs,though--ray tracing is extremely CPU intensive and therefore usually too slow to run in real time oncurrent desktop machines. However, the ray tracing algorithm does not have to be so general simply tocreate a video game. For instance, Wolfenstein places numerous restrictions on the world in order tocreate a ray casting algorithm that can be run in real time without much computing power (the game wasdesigned to run on 386 and 486 IBM compatibles in the early 1990s): The camera is always located at the position z = 0 The camera angle has no z component (cannot look up or down) All objects in the world are perfect cubes of the same size All objects are located in discrete positions, far enough apart so that they never overlap All objects are located at z=0 as well This essentially reduces fully functional, three-dimensional ray tracing to two-dimensional ray casting. The difference between casting and tracing is very subtle here: Ray casting only involves using rays tofind the location of objects, whereas ray tracing is a recursive process that regenerates rays at eachobject collision until a light source is found. More simply put, ray casting tells us what object is visibleat a certain pixel on the screen, but ray tracing tells us both what object is visible and how to shade thepixel. A simpler statement of the above restrictions might be that the world is composed of square blocksarranged in a grid on the XY-plane (Figure 1). The observer walks around this plane, always lookingstraight ahead. Since we are now only dealing with a two dimensional space, we can send out one rayfor each vertical sliver on the screen instead of for each pixel. Depending on the size of the display, thisalone speeds up the process by a factor of a hundred or even a thousand (A viewport of size 320 by 200pixels would normally require 64000 rays to be cast, but if we only have to cast one ray for each verticalsliver we reduce that number to 320 rays--a two hundred fold improvement!). In addition, calculation ofintersections in two-dimensional space is much simpler than in three dimensional space, and therestriction of objects to squares in a grid makes it almost trivial. Furthermore, since there are only so many directions that a ray can be cast in the XY-plane (some smallmultiple of 360), we can now precompute lookup tables for virtually every necessary calculation as well. Thus the algorithm becomes very simple: 1.Send out a ray for each vertical sliver and calculate its first intersection with a wall and how faraway that wall is. 2.Take a vertical of the texture for that wall, scale it vertically based on its distance, and paste it to thescreen Of course, our goal here isn’t simply to recreate Wolfenstein, it is to improve upon it. The problem withthis algorithm is that all walls have to be at 90 degree angles, in cube shapes. Unfortunately, this doesn’tmake for a very exciting video game. Instead, we would like to envision an engine that could handlewalls at any angle. This leads to a much more capable engine that can recreate winding halls and cavesand allow a (somewhat) more realistic representation of the real world. Now, despite whatever the trend seemed to be in 1992, experience has shown that first person 3Dengines have moved decidedly away from the ray casting methods used in Wolfenstein. Ironically,they’ve gone back to using polygons. Perhaps this is because polygons are easy to implement inhardware (i.e. in the grain of the ever more powerful graphics cards), but it still begs the question ofwhether or not it is the right direction. If Wolfenstein can be generalized to arbitrary angle wallswithout hurting the performance very much, perhaps there’s hope for real time ray casting. In thisproject, I hope to show that the "big step" of moving from cubes to arbitrary angled walls is not that bigof a step at all, and that perhaps more attention should be paid to this seemingly "antiquated" method.Throughout the implementation of this project, I’ve come to form opinions on both sides of this issue,which will be discussed in more depth in the Conclusion. 2 Design GoalsThis section is copied directly from the project proposal. We will analyze later how successful we werein meeting these goals. This project aims mainly to create an engine that will run in real time, but also to create a very generalshell that can be easily expanded. At this point, I plan to provide hooks for: Running the engine under any screen resolution or palette Running the engine on any platform Any input module Sprite overlay before double-buffer updates (Hopefully) A standard graphics file format for wall textures and sprites The primary design goal is, of course, to make the engine run in real time. Wolfenstein 3D was writtenfor high-end 386’s and low-end 486’s.
View Full Document
Unlocking...