From DoomWiki.org

Revision as of 02:35, 18 October 2022 by Xymph (talk | contribs) (External links: archive link)

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.


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.


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.

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