Super Noah's Ark 3d (Source Code)

Overview

After reading the excellent game engine black book DOOM V1.1 by Fabien Sanglards and trying to understand the source code to ID tool doombsp. I still dont really understand how BSP trees work I mean I understand the basic idea. However every time I look at the code in doombsp or chapter 60 of Michael Abrash's graphics programming black book, I get lost in the coding complexity and get disheartened and lose interest.

Fast forward three years and I noticed that Matthew Callis had found the source code to super Noah's Ark 3d and uploaded it to github. You are probably wondering what Super Noah's Ark got to do with BSP trees well theres a quote in game engine black book wolfenstein 3D V1.0 by Fabien Sanglards page 265.

"When I ported Wolf to the SNES, the ray casting performance cost was too much, so I had to make a new wall span renderer. Learning about BSP trees allowed me to much more accurately resolve the culling challenges, and it worked out ok, leading the way to the Doom renderer" -- John Carmack

If you have not guessed already super Noah's Ark 3d is based of the SNES version of wolfenstein 3D. I started thinking I wonder if I can actually understand the BSP tree used with super Noah's Ark 3d (and Wolf on the SNES). I wondered if the source code actually had the BSP tools in it and if it was readable / usable so I started digging around in the super Noah's Ark source code.

Source code first contact

Its interesting to note that all the source code to the game seems to be present under the SOURCE directory. However the most interesting thing to me in my quest to understand BSP trees is that under the UTILS directory all the source code to compile the tools used to make super Noah's Ark is present. Also all the compiled map information from TED (ID map editor) is also present under the MAPS directory.

Under the UTILS folder there is a subfolder called MAPTRACE this folder contains all the source code and the built exe to a tool called MAPTRACE. MAPTRACE takes a given range of map numbers at start up via the command line and converts these to BSP trees.

Unfortunately the prebuilt maptrace.exe in the maptrace folder does not run in a windows 64 bit enviroment. However the tool is only made using three 'C' file

maptrace.c /* contains the core BSP routines and main entry point into the program */

tedmaps.c /* contains routines to read compiled map files produced by TED */

cmdlib.c /* utility functions to open / close files malloc memory etc etc */

So I decided to import the code into visual studios 2019 and try to regenerate the maptrace tool functions within a 64 bit enviroment and also try and work out how the BSP is created.

MAPTRACE architecture

The maptrace program starts at line 1174 in maptrace.c in function main() it takes three arguments start map number, end map number and an optional draw argument. Maptrace first loads the map files (MAPHEAD.N3D and MAPTEMP.N3D) found in directory NOAH3D\MAPS (which was produced using ID's TED tool) using function LoadTedHeader().

It then sits in a loop from start map number to end map number unpacking each map using SetupMap() converting it into a BSP tree using function BSPMap() and finally saving the converted map using SaveMap().

LoadTedHeader()

This function first loads the map index data from MAPHEAD.N3D into a structure called tinf it then opens file MAPTEMP.N3D which contains all the compressed (run length encoded) maps for the game.

SetupMap()

This function is a bit more complicated it first loads the map number passed to it, into the mapplanes array via a function call to LoadMap(). mapplanes[0] contains the maps background using unmasked tiles (levels walls) and mapplanes[1] contains the maps foreground and uses masked tiles (game objects). SetupMap copies mapplanes[0] into array back and then copies mapplanes[1] into array front. At this point the mapplanes are not used anymore and all processing is done using the back and front arrays.

SetupMap then calls function DrawMap() which draws the unmodifed background tiles now held in the back array. As the orginal maptrace program will not run in a 64bit enviroment and most of the drawing routines are designed for a NeXTSTEP enviroment. The maptrace program was ported to visual studios 2019 and SDL2 was used for graphics. Below is the output of DrawMap() when called with back array filled with map zero of super Noah's Ark.

Next SetupMap calls function RemovePWalls which moves the push wall back two tiles to its open position. Map zero of super Noah's Ark contains two push walls circled in yellow below as you can see they have been moved two spaces by RemovePWalls().

RemovePWalls() also creates two line segments where the orignal push wall was placed. RemovePWalls() and later CreateSegments() create all the required line segments from the passed tile map to create a new line segment based BSP tree.

Line segment direction

Line segments have a direction and this is used to work out if the line is facing the player or not. Its used for displaying culling when the bsp is rendered. The coordinate system used is as follows

Theres a comment in the code that says "the direction is from point 1 (view left) to point 2 (view right)". Taking the coordinate system shown above and the comment from the code lets say the player is facing the push wall in the top right of the map. In this case the surface of the push wall viewed from the player is traveling left to right ie its direction of travel is easterly. RemovePWalls() creates two easterly line segments where the original push wall was placed.

Because the created lines have a easterly direction they can only be seen if the player is facing north, if the player is in the secret area and is facing south towards the easterly running walls they will no longer be shown. Next SetupMap calls function FindDoors() this searches the back array and places the location and number of the door found in doornum array, it also marks the location of a found door on the front array.

SetupMap then calls function CreateSegments() this basically turns all the wall tiles in the back array into line segments. As super Noah's Ark and wolfenstein 3D are both based on a 64 x 64 square grid and no walls run diagonally CreateSegments() splits the task of creating line segments into two parts. First it creates line segments for all the horizontal tile walls then it creates line segments for all the vertical tile walls.

Lets follow the code through on the first horizontal line segment created, CreateSegments() search each row looking for a change in tile type.

As can be seen from the image above the first four rows are background tiles (dark green) so no line segment is required. On row five we have are first row of horizontal wall tiles (light green) however there are no area tiles (purple) so again no line segment is required. On row six we do have a change in tile type from a background tile (dark green) to a wall tile (light green) then to a area tile (purple) as highlighted by the blue horizontal markings. This tile change pattern is recognised by the code in CreateSegments() to be a start of line segment. Similarly with a change in tile type from a area tile (purple) to a wall tile (light green) then back to a background tile (dark green), again highlighted by the blue horizontal markings. This tile change pattern is recognised by the code in CreateSegments() to be a end of line segment. As noted all line segments need a direction if the row above the current line segment is a wall tile (highlighted by the red marker) the line is going easterly. However if row below the current line segment is a wall tile the line is go westerly.

With the start / end / direction of the line segment worked out CreateSegments() calls AddSeg() to create a horizontal line segment as drawn above in black. This process is then repeated for all the horizontal and vertical wall tiles producing an array of line segments covering the whole map as drawn below (line segments in black).

Finally SetupMap() calls FloodMap() I dont fully understand the point of this step however it appears to fill all the "open areas" that the player can walk in with a known value as shown below.

BSPMap()

Now that SetupMap() has produced an array of line segments covering all walls in the map we can produce a line segment based BSP tree from this array. For me this is where having only horizontal and vertical lines in the line segment array really help with understanding how a BSP is created. First BSPMap() creates a linked list of line segments from the line segment array created by SetupMap(), because link lists can be split up easily into smaller lists. Then BSPMap() calls BSPList() which builds the BSP tree from the linked list of line segments.

BSPList()

BSPList must find the best line segment within the passed link list to split the list in half. The choosen split line should ideally split the list into two halfs each half having equal number of line segments, the split line should ideally not create any new line segements. BSPList() calls CountSegSplits() which evaluates each line within the passed link list as a split line. It counts the number of lines in front of potential split line and the number of lines behind the potential split line, it also notes how many new line segments will be created by the potential split line. After iterating over the passed link list it chooses the best split line based on the lowest number of new line segments created and how equal the front and back line segment count is.

Front and Back

CountSegSplits() when evaluating a potential split line it considers a line segment to be in "front" of the potential split line if the line segment is towards more positive coordinate then the potential split line.

For a potential split line shown above in black CountSegSplits() would consider the line segment in red to be in front because its has a more positive x coordinate. It would also consider the line segment in blue to be behind the potential split line.

First Split line

After SplitSegs() is called BSPList() decided which line segment list (front or back) to work on next based on the orientation of the split line (horizontal or vertical). It then calls itself recursively splitting line segment lists. Only stoping when the line segment list passed to it is convex and no more splitting is required. Below Highlighted in white is all the split line recursively worked out from CountSegSplits() for Map zero of super Noah's Ark.

BSP Nodes

SaveMap()

Resources

MAPTRACE (visual studios 2019 version using SDL)