🚀 go-pugleaf

In article <1992Aug11.022821.1737@drycas.club.cc.cmu.edu> greenie@drycas.club.cc.cmu.edu writes:
>Hi -
>
>I know this was discussed before, but I was wondering if someone out there
>could explain how the graphics were done in Apogee's WOLF3d?
                                             ^^^^^^ APOGEE DID NOT MAKE WOLF3D!
                                           (Sorry--this is a pet peeve of mine)

I don't know that this was discussed before, because it's been a long time
since I've read this group.  But I think that this is of general interest:

I have right now some working C code that does 3D graphics that are quite
similar to Wolf3d's walls (not the objects).  Compiled with DJGPP it's very
fast--I don't remember the exact number of frames per second but it's a lot
more than are needed.  I suspect that Id used used the same algorithm that
I'm using, but I'm not sure since I haven't looked at their code.

This algorithm is surprisingly simple and completely does away with the
need for hidden plane elimination, clipping to screen borders, texture-
mapping of a square bitmap to an irregular quadrilateral, etc..  My
love affair with Wolf3d ended at about the same time that I discovered
this algorithm.  After all, graphics were about the only thing the game
had going for it, and I'd just discovered that they were faked (in the
sense that they weren't nearly as sophisticated as they looked).  I
think that this has enormous potential if it's used as the basis for a
better game, though.

Other people have probably invented this algorithm independently.  If
you're one of them, please read my description of it and send me
suggestions.  Thanks.

Jay Wilbur of Id Software is on the internet; his address is
jwilbur@holonet.net.  In case you're wondering, no, I haven't said
anything about this to him.  Who knows, though--he may read this message.

I'll probably release my code once it's in any condition fit for release,
which it isn't right now.  I'd like to ask that other people not use the
following description to write code and then release it before I do; that
would be a little unfair to me.  (If you already knew about the algorithm,
then obviously you can do whatever you want.)

Here's my description of the algorithm.  It doesn't use any complicated
math, but it's pretty long and it might be a bit difficult to wade through.

The first thing you should notice is that there is never more than one
wall visible in any screen column.  The reason for this is that you can't
see behind the first wall that's visible in that direction.  (If there
were windows in the walls of if you could see over them, you might
be able to see other walls behind them, but there aren't.)  This means that
every column of the screen is made of a vertical section of wall with
the ceiling color above it and the floor color below it.  Furthermore,
the wall is always centered in the column.  (Run Wolf3d and see for
yourself.)

To determine what should be in a column, we "shoot a ray" in the direction
which that column represents, find the first wall it intersects with,
determine the height of the wall by its distance from the viewer, and
scale the appropriate column of the appropriate image to the correct
height.  I'll explain that in more detail...

I keep a vector called "ahead" which points in the direction the player
is facing.  (I'll use "C" rather than algebraic notation when talking
about vectors.)  From this you can get a vector pointing right by
right.i = ahead.j; right.j = -ahead.i; .  Now the idea of 3D projection
is to plot a point on the screen that is in the same direction from the
viewer's eye as the equivalent point on the object being projected would
be.  That way, the object looks the same as if it were really there (as
long as you look at it with only one eye, and that eye is in the place
used in the computer's calculations).  So, assuming that the viewer's
eye is on the line perpendicular to the plane of the screen and going
through its center (in other words, the screen is facing the viewer
(which it probably is)), the middle column of the screen will correspond
to "directly ahead" (i.e. the "ahead" vector), and columns to the right
and left of the middle correspond to the "ahead" vector plus or minus
some fraction of the "right" vector.  Let's write that as a formula.
Assuming 320 columns (which Wolf3d doesn't use, but my code does):

ray = ahead + ((column - 160) * right / 200);

(This can be done much more efficiently of course, but I'm trying to
keep things simple.)

I call the vector "ray" because it points in the direction of the
ray which we're about to shoot.  The "200" is connected with how far
the viewer is from the screen.  It can be adjusted; lower values give
a wider viewing angle (just like getting closer to a window lets you
see more through it).

Now we "shoot a ray" from the position of the user in the direction
pointed by the "ray" vector, and find the closest wall that intersects
the ray.  This is a bit difficult; you can't just step along the ray
by a constant length, because you might miss cases like this:
                     ______ 
                    |      |     /
                    |      |   /
                    |______|_/____
   (Sorry; I'm no          /      |
    ASCII artist.)       / |      |
                       /   |______|

I solved the problem by stepping along the ray twice, once with the
i coefficient normalized to 1 and then the same with the j coefficient.
This always works, except when the ray passes through the exact
intersection of the blocks in the case illustrated above.  (Does anybody
know a better way?)

Once we've found the intersection, we take the fractional part of the
appropriate coordinate (the length of the side of a block being one),
multiply it by 64, and use that column from the in-memory image of
the wall (which is 64x64).  Some high-school geometry, or just
knowledge of the rules of perspective, will tell you that the height
of the wall should be inversely proportional to the distance between
the wall and the viewer's eye.  Actually, I make it inversely
proportional to the distance from the wall to the plane through the
viewer's eye and parallel to the screen, for two reasons: first, the
math is easier (hence faster), and second, it actually looks better
in most cases.  If you do the math, you'll find that most of the
final formula is not dependent on the column you're working on, and
so needs to be calculated only once per frame.

All that remains to be done is the actual drawing.  This is easy
(and it's left as an exercise for the reader).

I want comments from anybody who persevered long enough to read this
sentence!

--
Ben Rudiak-Gould
benrg@ocf.berkeley.edu   <--- NOTICE NEW ADDRESS 
"It's easier to ask for forgiveness than it is to ask for permission."
	-- Admiral Grace Hopper