ZokumBSP

ZokumBSP is an advanced blockmap constructor, node builder and reject builder with an optional amount of geometry preprocessing. The code is based on ZenNode 1.2.1. It was created by Kim Roar Foldøy Hauge (Zokum).

The project started out as an experimental fork of ZenNode, attempting to produce smaller blockmaps in order to allow for bigger doom2.exe-compatible maps. The other primary aspect was to update the code to fix bugs and oversights, and make ZokumBSP more robust. Using 64-bit variables instead of 32-bit variables have made it possible for ZokumBSP to handle bigger maps than ZenNode. Various lint-tools like Valgrind have also been used to fix minor errors in the original code base.

The early version had the code updates focused on the blockmap generation code. Later versions also received bugfixes in the reject code and several novel algorithms added to the node builder allowing for the building of better nodes. The GitHub repository features experimental tweaks and improvements, but they may not always be stable and fast.

Roadmap

On the roadmap for future releases is further optimizations and convenience-additions. There are planned additions of features not seen in any other similar tools. The current multi-tree algorithm is in most use cases too slow for use, taking too long to compute a good BSP tree. Optimizing this to make it quicker is one of the main goals.

Blockmap features

Geometry simplification

This is a technique which can reduce the number of linedefs that has to be checked for collision detection. This in turn leads to a smaller blockmap, which allows for the construction of bigger maps. What it does is to look for two linedefs where one starts where the other ends, and they have the exact same orientation and share many of the same properties such as same number of sides etc. A new linedef is then added to the linedef list which spans these two linedefs. This new long linedef is the one that is checked against in the blockmap list. Each such simplification reduce the blockmap with 2 bytes. Additionally, this increases the chance that blocks will have the same list of linedefs, which allow for better conventional blockmap compression. This saves at least 4 bytes when it occurs. Since more than twoe linedefs can share properties, the added linedef used for collision detection can increase in length, substituting for several linedefs.

These new linedefs are marked as collision only, while the old ones are marked as rendering only for the generation of SEGS in the bsp step. Thus this step requires that the node builder understands what has been done during the blockmap creation.

This algorithm works flawlessly in the original Doom executables, but can lead to problems in ports. If the BSP tree is rebuilt, a port may try to render as if it had two linedefs on top of each other. Another problem is related to ports that use decals on walls. This code will usually derive the SEG to render the decal on from the linedef in the collision detection system. Since this one isn't linked to any rendered SEGS, no decals are displayed on these textures. It could be possible to deconstruct which linedefs are the corresponding ones and alter the blockmap in order to restore the decal functionality.

BSP tree features

Multi-tree algorithm

This is an algorithm where at each partition decision, multiple trees are built and compared. This is a much slower process than regular node building and it is not unusual for complex maps to take hours and days to build. The project website has a case study with typical build times for maps from The Ultimate Doom and Doom II.

The idea is that the algorithm that picks the best partition line may not be optimal, and in some cases the second choice would be better. During an early test of the concept a special version was built where the algorithm always picked the second best choice as the partition choice, unless there was only one choice. This led to most maps increasing slightly in size, some stayed the same, while others, such as map07 in Doom 2 was in fact smaller. Making a better picker algorithm could reduce the improvement this approach gives. This is however fairly hard and complex. What generally happens is that a choice may not appear to be the best partition line at that partition Further down the tree, the choices for partition lines are better.

The algorithm is not perfect and has bugs. It is currently too slow to be used for complex maps, which unfortunately is where it would be most beneficial.

The slow speed is due to the node builder algorithm not being designed with this in mind at all. It treats the node builder as a state machine and saves and restores the complete state at each decision to compare trees. It is the excessive memory copying that takes a long time since it would need to copy all the data structures no matter how small the compared sub trees are. If the second tree is equally good as the first tree, the second key is kept instead of copying over the original tree. A different design could lead to this approach being much faster. This algorithm uses a lot of memory, since the state of the node builder is kept at each partition until the best one is found and the less ideal tree is removed from memory.

Program invocation

As of version 1.0.10-rc1 the program supports the following parameters:

Usage: zokumbsp {-options} filename[.wad] [level{+level}] {-o|x output[.wad]}

 -x+ turn on option   -x- turn off option  * = default

Switches to change level geometry and optimize geometry.

  -g      Geometry pass, 1 suboption.

    s=    Simplify collision geometry.
*     0   No simplification.
      1   Only if same sector.
      2   Also 1-sided lines in different sectors.

Switches to control BLOCKMAP strucure in a map.

* -b      Rebuild BLOCKMAP, 8 suboptions.
    b     Build big 32bit BLOCKMAP, N/A.
*   c     Compress BLOCKMAP.
    h     Output BLOCKMAP data as HTML.
    i     Id-compatible BLOCKMAP. Sets 'o=1n=2g=0' and 's-r-'.

    o=    Offset configuration.
      0   ZenNode 0,0 offset BLOCKMAP.
      1   DooMBSP / BSP 8,8 offset BLOCKMAP.
*     2   Best of 36 offset combinations.
      3   Heuristic method to reduce from 65536 offsets.
      4   Best of all 65536 offset combinations.
      x,y Specify specific offsets.

*   r     Remove non-collidable lines from BLOCKMAP.

    s     Subset compress BLOCKMAP.

    z=    Zero header configuration.
      0   No zero header.
*     1   Conventional zero header.
      2   Zero footer.

Switches to control BSP tree and related structures in a map.

* -n      Rebuild NODES.

    b     Remove backside seg on on some linedefs.
*   c     Calculate BAM from SEGs instead of lineDefs.
    i     Ignore non-visible lineDefs.
    q     Don't display progress bar.
    u     Ensure all sub-sectors contain only 1 sector.
    1     Alias for a=s.
    2     Alias for a=d.
    3     Alias for a=f.

    a=    Partition Selection Algorithm.
      s   Minimize splits.
*     d   Minimize BSP depth.
      f   Minimize time.
      a   Adaptive tree.
      m   Multi-tree. (Slow)

    m=    Metric, what kind of node tree do you favor.
*     b   Favor 2 splits = 1 subsector.
      s   Favor fewer SEG splits.
      u   Favor fewer subsectors.

    p=    Favor certain node selection picks for depth algorithm.
      z   No favoring, use old algorithm for a balanced tree.
      s   Favor nodes that do not split segs.
      u   Favor nodes that do not create subsectors.
*     b   Favor both of the above equally.
      m   Try all of the above.

    t=    Tuning factor, varies from algorithm to algorithm.
      100 Default for adaptive tree.
    w=    Number of sub trees to generate in multi-tree mode.
*     2   Default width and also minimum.

Switches to control REJECT resouce in a map.

* -r      Rebuild REJECT resource.

    z     Insert empty REJECT resource.
    f     Rebuild even if REJECT effects are detected.
*   g     Use graphs to reduce LOS calculations.
    m{b}  Process RMB option file (.rej).

Switches to control other options.

  -c      Enable 16 color output.
  -cc     Enable 24bit color output.
  -t      Don't write output file (test mode).

  -s=     Which output stats to show.
     m    Show a total for all computed levels.

 level - ExMy for DOOM/Heretic or MAPxx for DOOM II/HEXEN.

Example: zokumbsp -b- -r- -sm -na=a file.wad map01+map03
This rebuild nodes only, adaptive tree, give a total summary.
It reads from file.wad, but only builds map01 and map03.

For a complete explanation of all the parameters, read the project documentation found on the GitHub repository and website.

Case Studies

On the web page for ZokumBSP, one can find a few case studies showing what different parameters and options can do for well-known maps and how this affects the size of the blockmap.

External links

• Official website (archived 🏛)
• GitHub repository