return to my programming demos page.
BSP (Binary Space Partition)
Compiler and Viewer

BSP Compiler (C++, MFC)

BSP Compiler

OpenGL Map Viewer

Map Viewer

Download here


Place the MapEditor.exe, Maze.exe executables and the texture file brick.ppm in the same directory.

Note that you will need the GLUT (OpenGL Utility Toolkit) to run or compile the Maze program.  You can obtain GLUT here:

How to Use

Run MapEditor.exe to create a map.  Click and drag the mouse within the window to draw the walls of the map.

NOTE:  When you view the map using the Maze program, you will always start in the upper left hand corner, facing the lower right.  So you probably want to draw walls in the upper left hand corner of the window.  See the screen shot at the top of the page.

Now you are ready to create a BSP file which can be viewed with the maze program.  Click on the BSP menu and select the Compile Map option.  Your map will be saved in BSP format in the file "maze.bsp".

Now you can run the Maze program.  This program will automatically load the "maze.bsp" file and the brick texture (from the "brick.ppm" file).  You can now move around the maze you have just created.  Use the up and down arrow keys to move forwards and backwards, and the left and right arrow keys to turn.

Press Q to quit the Maze program.

Other stuff

You can use Clear All under the Edit menu to clear the map.

Using the File->Save option will save the map as a binary MAP file.  This format is *not* readable by the Maze program.  You must compile the maze using the BSP->Compile Map menu option.

The maze.bsp is a text file.  Here's the file format:

File Format

Vertices in x, y, z format.
Name of texture files.  Currently only one texture is supported.
Line segments (nodes) are stored as a series of 16 numbers:

  • First number: Index of Texture to use (currently always 0)
  • Next 8 numbers: Texture coordinates
  • 10th number: Number of vertices in the polygon (currently always 4)
  • Next 4 numbers: Indices of the vertices to use (so "0, 1, 2, 3" means use the first 4 vertices listed in the file)
  • Next 2 numbers: Indicates if this node has left or right subtrees.  These indicators are always 0 or 1.


NOTE:  You will need GLUT to compile and run the Maze Viewer.  You can download
it from:

Both projects were compiled with Microsoft Visual C++ 5.0

Map Editor Source
BSPNode.cpp  A BSP tree stores the lines when the map is compiled
ChildFrm.cpp Generated by MFC
CLine.cpp Every line segment on the map is a CLine
MainFrm.cpp Generated by MFC
MapEditor.cpp Generated by MFC
MapEditor.rc Listing of all Windows resources
MapEditorDoc.cpp The heart of the program.  Stores the CLines and compiles & writes the BSP file.
MapEditorView.cpp Handles mouse moves and drawing of line segments
StdAfx.cpp Generated by MFC
BspNode.h BSP Node header
ChildFrm.h Generated by MFC
CLine.h CLine header
general.h General utility functions
MainFrm.h Generated by MFC
MapEditor.h Generated by MFC
MapEditorDoc.h Header for Document class
MapEditorView.h Header for View class
Resource.h Generated by MFC
StdAfx.h Generated by MFC
res\MapEditor.ico Application's icon
res\MapEditor.rc2 More resources
res\MapEditorDoc.ico  Icon for child windows
res\Toolbar.bmp Used to create toolbar
MapEditor.clw Used by Class Wizard

Maze Viewer Source
main.cpp Main display loop
maze.h Header file for maze
maze.cpp Stores pointers to the polygons, vertices and textures
polygon2.h Stores each rectangle to be displayed by the Maze object
texture.h Header file for Texture object
Texture.cpp Attributes of a texture file -- filtering options, etc.
texturefile.h Header file for TextureFile object
TextureFile.cpp  A TextureFile stores the binary texture data
vertex.h Vertex header file
vertex.cpp A vertex is a point and a normal
vec3.h Vector header file
vec3.cpp A Vector is stored as x,y,z coordinates
general.h General utility functions
glut.h GLUT library header file
brick.ppm You will need the brick.ppm texture to run the Maze program.

For More Information

Chapters 59, 60 and 62 of Michael Abrash's Graphics Programming Black Book Special Edition provide an excellent introduction to BSP trees.  Abrash is a noted optimization guru who was also a programmer on Quake.  The book is out of print, but fortunately the author has allowed web sites to download PDF scans of the text.

The BSP Trees FAQ can be found here.

Dan Royer, co-author of Advanced Game Programming in DirectX 7.0, has a BSP tutorial at his site.

Charles Bloom, a lead programmer at Oddworld Inhabitants, has a BSP Tips page.

return to my programming demos page.

You are visitor number