ZokumBSP

From DoomWiki.org

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 bug fixes 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[edit]

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.

Preprocess features[edit]

Certain features affect several of the other algorithms and have been put into this pass. There are plans for more features related to compression and special effects, but currently only the geometry simplification is in the code base. It was moved out of the blockmap pass since it also affects the nodes pass. The way switches are handled in ZokumBSP also makes it beneficial to move things into a new pass.

Geometry simplification[edit]

This is a technique which can reduce the number of linedefs that have 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 two 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 and blockmap code understands what has been done during the pre-processing.

This algorithm works flawlessly in the original Doom executables, but can lead to problems in source 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.

Blockmap features[edit]

Id compatibility[edit]

There's a switch (-bi) to make it build blockmaps with the same offsets as in the original games and no compression. These should be completely demo compatible, but use less memory and disk space. This switch is shorthand for the following options: '-bo=1n=2g=0s-r-'.

Variable offset[edit]

Most blockmap tools will use a specific offset to generate the blockmap data structure. By trying many different offsets the data structure can take less space due to beneficial alignments that can occur. The default is to check a 36 different offset variations, but one can optionally check up to 127x127 different offsets or just one. The heuristic algorithm will start at 0 and go up to 127 along each axis unless this means adding both a new row and column in the blockmap. This adds so much more data that it is unlikely that an offset would be found that would reduce the overall size, but it cannot be guaranteed to produce the best possible result. The heuristic will usually produce the same result as the complete check, but will do it faster in most cases.

No zero header[edit]

DoomBSP produced blockmap lists starting with a 00 00 entry and ending with an FF FF entry. The Doom engine however interpret the 00 00 as a reference to linedef 0. This leads to unnecessary checks and buggier behavior. This also adds 2 bytes of size to every list entry. Turning off these faulty headers reduces the blockmap size quite substantially in most cases. The downside is that Boom introduced a questionable optimization in which the code would always ignore the first linedef in the linedef list. Many ports inherited this behavior. Some of the ports have however made the check more intelligent or have it as a compatibility setting to make them compatible with maps made with this option on. Ignoring the first linedef breaks demo compatibility with demos recorded without this code change.

BSP tree features[edit]

Multi-tree algorithm[edit]

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 II 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.

Vertex-pair algorithm[edit]

This algorithm uses pairs of vertices as the source for possible partition lines instead of segs as their source. Basing it off of segs is also what other node builders usually do. In a vertex pair algorithm, every possible sensible partition line is tested. Any lines beyond these will give the same balance as one already tested, but lead to more seg splits.

In a conventional algorithm any partition line that sorts data on both sides of the partition line is a valid partition line that will eventually lead to convex subsectors when done recursively. This is not the case when using vertex pairs and care has been taken to not divide the sectors into unnecessary subsectors. This makes it harder to compute good partition lines. The current algorithm in ZokumBSP is not very good.

This algorithm will often find partition lines that cause fewer split segs compared to the others. Split diagonal segs are the cause of slime trails. Fewer splits should lead to faster rendering and a smaller data structure to keep in memory as well as allow for the construction of larger maps. A splitless map does not have slime trails.

Due to a higher chance of the partition lines being diagonal, boundary box exclusion may be less efficient.

A better approach for ranking partition lines that produces a more balanced tree is possible. Use the conventional algorithm to generate a worst case, and then search for all vertex pairs that are better in some aspect than this one or use the one from the conventional approach. This should lead to no worse performance than the current algorithm(s) and a possible improvement in most maps. This approach has been tentatively named 'guided approach' and is on the list of planned features.

Reject algorithm[edit]

The building of the REJECT tree has some limited support of features copied from RMB. This is not well tested and was commented out in the ZenNode base. The reject pass is the one with the least amount of changes and optimizations. The original code base had an integer overflow that could affect large maps that has been fixed.

Graphs[edit]

Using graphs will speed up the algorithm, but it may fail to generate the expected result when using self-referencing sectors. This happens due to these sectors often not sharing linedefs with other sectors, which leads the algorithm to assume it is an isolated sector. An isolated sector with no neighbors is assumed to not be able to see into any other sectors. Since this is the default setting, it can lead to unexpected results. It will most likely no longer be the default option in newer versions.

Known bugs and incompatibilities[edit]

There are a few known bugs and some known incompatibilities in the current version.

Reject build fails on oversized maps[edit]

When building the REJECT entry the algorithm uses a generated blockmap internally. This leads to problems if the blockmap is too large. Some compression options cannot be used when building this WAD entry, leading to an excessive blockmap size and crashes.

Self-referencing sector tagging needed[edit]

A slightly faulty optimization will fail to generate self-referencing sectors properly unless the linedefs have a tag or type associated with them.

Multi-tree breaks on certain maps[edit]

The multi-tree node builder algorithm never finishes building DOOM E2M4 and most likely many other maps. It seems to get stuck in a never-ending loop, but the exact details are not known.

Program invocation[edit]

As of version 1.1.1-alpha1 the program supports the following parameters:

ZokumBSP Version: 1.1.1-alpha1 (c) 2016-2023 Kim Roar Foldøy Hauge
Based on: ZenNode Version 1.2.1 (c) 1994-2004 Marc Rousseau

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)
      v   Vertex-tree (N/A)

    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 resource 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.
    e     Sector count.
    l     Linedef count.
    p     Seg split count.
    n     Nodes count.
    s     Subsector count.
    t     Thing count.
    v     Vertices count.
    a     Show all of the above.
    m     Show a total for all computed levels.
    x     Count percentage by 65535 limit of source ports.

 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[edit]

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[edit]