--start--

This archive contains the source code for a sample system to render
3-D scenes from 2-D BSP trees, as discussed in my "Ramblings in
Realtime" column in the May/June, July/August, and November/December
1995 issues of _Dr. Dobb's Sourcebook_.  The archive contains the
source code for BSPMAKER, a C++ program to generate 2D BSP trees from
input line segment lists, and MAZE, a C program to allow first-person
3-D viewing of those trees in realtime.  Both programs are Win32
programs, tested with VC++ 2.0 running on Windows NT 3.5.

To make the VC++ projects for these two programs, just unzip this
archive into a directory using the -d option to pkunzip.  This will
create two subdirectories, BSPMAKER and MAZE.  Have VC++ build two
projects, one from the files in each directory.  Besides the source
code, there is a sample BSP tree to view, several sample input line
segment files, and the Win32 executables, bspmaker.exe and maze.exe,
in the respective WinDebug subdirectories.

To run the BSP compiler, make BSPMAKER the current directory and type

windebug\bspmaker

Then load one of the .lin files, and compile and save as desired.

To run the BSP-based animation, make MAZE the current directory and
type

windebug\maze

The BSP tree in bsptree.txt will be displayed.

BSPMAKER
========
The UI is simple and self-explanatory; you can load a line file, and
can compile either either one split at a time with visual feedback as
to where the splitting is happening, at a paced speed with visual
feedback, or as quickly as possible with no feedback.

You can save the compiled BSP tree to any file, but in order to view
it with the MAZE program, you must save it to the file bsptree.txt in
the directory that is current when MAZE is run.

MAZE ==== MAZE automatically displays the BSP tree stored in the file
bsptree.txt in the directory that is current when MAZE is run.  The
arrow keys move the viewpoint forward, backward, and turn right or
left; the minus key moves the viewpoint up and the plus key moves the
viewpoint down. There is no way to tilt the viewing angle up or down.

SAMPLE FILES
============
The MAZE directory contains the sample BSP file bsptree.txt, which is
compiled from the line file test.lin in the BSPMAKER directory.  This
BSP tree is displayed automatically when you run MAZE.
Sample line files in the BSPMAKER directory are:

test2.lin: a very simple four-line case
test.lin: a fairly simple case designed to look a bit like a real
          level
mike.lin: a fairly complex case with the level spelling out "Hi Mike"
hand.lin: a complex case with the level in the shape of a hand

One important thing to keep in mind is that walls face in a
direction, and are only visible from one side.  This means that if
you walk around to the other side of a visible wall, it will vanish. 
This is the way real game levels work, where walls have volume, and
you only see the outside of the polygons bounding the volume. 
Test.lin looks more realistic than the other levels because I've
inserted pairs of collinear polygons for the walls, one facing in
each direction, so the wall are visible from both sides.  In a real
game, the walls would be separated by some distance, and there would
be top and bottom surfaces to make the walls volumes rather than
flat, 2-D planes.  Note that the collinear walls can be confusing
when you do a visual compile of test.lin, because it appears that the
same wall is compiled multiple times.  It's not the same wall,
though, it's another wall that's collinear with the first wall that
was compiled.  In a production BSP compiler, collinear walls would
share a single BSP node, for compactness and efficiency, and to avoid
problems that can arise from collinear BSP splits.

NOTES
=====
Please note that these programs are provided totally "as-is."  I am
well aware that the UI is crude and probably has some bugs, that the
visualization could stand some improvement as well, that there
certainly should be a built-in line-segment editor, and that the
animation could be much faster, especially if it used DirectDraw, but
that's not really what this archive is about.  The object of this
particular archive is primarily to provide working 2D BSP code for
people to learn from, and to provide visual feedback to make it
easier to understand how BSPs work, and secondarily to provide a
skeleton upon which a full-featured BSP compiler and BSP-based
rendering system could be built. Please feel free to improve upon
this program in any way you wish, and to use this code for any
purpose, although acknowledgement is always appreciated. Please DON'T
send me mail or disks or email telling me about your improvements; I
just don't have time to read them; instead, post your comments and
code on the net, for example in rec.games.programmer.

Thanks to Chris Hecker and John Carmack for their help.

Enjoy!

Michael Abrash
mikeab@idsoftware.com
11/4/95

--end--