Author ====== (c) 2016-2023 Kim Roar Foldøy Hauge (c) 1995-2004 Marc Rousseau (ZenNode base) Description =========== ZokumBSP is an advanced node/blockmap/reject builder created for Id Tech 1 games, including Doom, Doom 2, Final Doom, Heretic, Hexen, Strife, and Hacx. This powerful tool, based on ZenNode 1.2.0, is available for download from GitHub and in binary release form for select operating systems. While ZokumBSP offers many advantages over other similar tools, it may occasionally have bugs when using new features, as it is an experimental Doom tool. With ZokumBSP, constructing larger and more intricate maps is possible. Although ZokumBSP has port-specific handling, it is primarily developed for vanilla 1.9 executables and Chocolate Doom. Maps created with the tool's advanced options may not function properly in some ports, so it's important to keep this in mind when using it. Index ===== 01. Project goals 02. Basic usage 03. Doom V1.9 limits / algorithms 04. Special effects 05. Linedef specials 06. Geometry pass 07. Blockmap builder 08. Nodes builder 09. Reject builder 10. Other options 11. Compatibility 12. Usage in projects. 13. Usage together with other tools 14. Other resources 15. Changelog 16. Acknowledgements 17. Other relevant tools Section 01: Project goals ========================= The primary objective of ZokumBSP is to offer a node builder that's fully compatible with ZenNode and the classic version 1.9 Doom 2 executable. In this document, we refer to this version as "classic Doom" or simply "Doom." While we strive to support other source ports in terms of features and limits, it's crucial that they do not interfere with our support for classic Doom. Ultimately, our main focus is on empowering creators, and we aim to achieve this by providing a robust and reliable node builder that meets the needs of Doom enthusiasts. 01:01 Non-Doom games -------------------- While the primary focus of the project is on supporting Doom, we also aim to include support for Hexen, Heretic, and Strife as nice-to-have features. The existing features of these executables will be preserved, but not tested when new code is added due to the added complexity it would cause. As of 2023, there has been minimal interest in these executables. However, if there is a genuine need for support or bug fixes, we will consider addressing them. However, we do not plan to add specific features that are only usable in these games, as this is outside the current scope of the project. It's worth noting that Hexen wads have been successfully produced and tested using a recent version of the tool. We will continue to monitor interest in these games and adjust our plans accordingly. 01:02 Slot in for ZenNode ------------------------- One of the essential goals of ZokumBSP is to function as a seamless replacement for ZenNode. Users should be able to run it with the same parameters as ZenNode and obtain a similar result, with the added benefit of improved runtime performance and better-built structures. ZenNode has several bugs and default settings that are problematic. To address these issues, we've made changes and improvements to the tool. As a result, maps built with ZokumBSP may not be identical to those built with ZenNode, but they should be of comparable quality or better. We are committed to providing a reliable and efficient node builder that meets the needs of Doom enthusiasts. As such, we will continue to refine and improve ZokumBSP, taking into account user feedback and the evolving needs of the community. 01:03 Bigger and more complex maps in classic Doom -------------------------------------------------- A central objective of the ZokumBSP project is to empower mappers to create larger and more complex maps than what's possible with other similar tools while still ensuring that they remain playable in classic Doom. One of the key challenges in building larger and more complex maps is maintaining a playable frame rate. ZokumBSP tackles this problem by optimizing the map's node structure, making it more efficient and enabling it to render more quickly. This approach makes it possible to create sprawling, intricate maps that push the limits of the classic Doom engine without sacrificing playability. In addition to performance optimization, ZokumBSP also provides a range of advanced features that make it easier for mappers to create complex maps. These features include improved sector merging, custom node splitting, and better handling of slopes and stairs. With these tools, mappers can create maps that are not only larger and more complex but also more visually appealing and immersive. Ultimately, the goal of ZokumBSP is to offer a powerful and flexible node builder that empowers mappers to unleash their creativity and push the boundaries of classic Doom mapping. By providing a tool that can handle larger and more complex maps without sacrificing performance, we hope to inspire a new generation of mappers to explore the possibilities of this timeless game. 01:04 Advanced and novel special effects ---------------------------------------- ZokumBSP is a highly versatile node/blockmap/reject builder that offers mappers a range of powerful switches, options, and tweaks. By leveraging these features, mappers can create complex and detailed maps with unique gameplay mechanics and visual effects. One of the key strengths of ZokumBSP is its ability to generate highly optimized data structures that allow for more efficient rendering and better performance. By adding new switches, options, and tweaks, ZokumBSP can enable mappers to create unique special effects that rely on the final data structure output from the tool. This can include custom architecture, detailed lighting setups, and intricate level designs. While ZokumBSP does not provide built-in support for advanced features such as dynamic lighting or 3D floors, mappers can still use the tool to create highly detailed and engaging maps that take advantage of the features offered by their chosen source port. 01:05 Documentation guidelines ------------------------------ The documentation is formatted to fit within an 80 character wide terminal and expects the reader to have a decent understanding of Doom terminology and concepts, or at the very least, the patience to search for terms on the doomwiki.org The doomwiki.org is the only wiki the author updates, so you're adviced to go there and disregard other sources as they may be outdated or incorrect. Some of the documentation has been rewritten and formatted by Chat GPT in order to make it easier to read. 01:06 The name of the tool -------------------------- The official name is ZokumBSP, but it can be referred to as Zokumbsp or zokumbsp. Those are acceptable variations. 01:07 Why the name ZokumBSP? ---------------------------- My handle is 'Zokum' so it made sense to use this in conjunction with the acronym BSP in order to quickly convey what the tool does and who makes it in case someone has bug reports. Section 02: Basic usage ======================= 02:01 Basic syntax ------------------ To build a map for use in Doom, simply use the command "zokumbsp mapfile.wad", where "mapfile.wad" is the name of your map. However, please note that a bug in the tool could potentially corrupt your original file. Therefore, it is strongly recommended to use the "-o output.wad" option to specify a different name for the output file and avoid overwriting your original file. 02:02 Help screen ----------------- To quickly get an overview of ZokumBSP's commands, you can simply run the tool without any arguments to see the help screen. Keep in mind that the help screen contains more lines than a standard 25 line terminal, so it is recommended to use a higher-resolution terminal or a scrollback buffer to ensure all the available information can be seen. 02:03 Supported arguments / switches ------------------------------------ Most supported parameters are explained in sections 5 to 10. 02:04 Color output ------------------ -c Colored output, 16 colors. With the switch "-c" the output will be color coded and map headers get a different background. This makes it easier to see if any entries are near or over the limit. The colors currently use standard vt220 ansi escape sequences and might not be available on all consoles. Older windows terminals tend to lack the support. -cc Colored output, 24bit colors. This mode uses special terminal sequences to output 24 bit colors. This applies to the map header, which is now in Romero Blue and the progress bar which is rendered with shades from purple to red to orange. Support for this is known to work on Linux with a modern terminal. Section 03: Doom v1.9 limits / algorithms ========================================= There are several size limitations for a Doom map, but this document will only focus on those relevant to ZokumBSP's node, blockmap, and reject building capabilities. In version 1.0.10, a new text output format was introduced. This format generally appears in the following manner: MAP07 * Entry Old New %Change %Limit Time Elapsed Blockmap 1862 => 1862 100.00% 2.84% 16ms Segs 311 => 311 100.00% 0.95% Splits 28 => 28 100.00% - Subsecs 92 => 92 100.00% 0.28% 16s 806ms Reject 14.03% => 14.03% 100.00% - 3ms The %Limit column will give a percentage of how close to the Doom2.exe limits the lump is. Splits are a sub type of segs, so the limit would be the same. The reject lump does not have a known limit, and is therefor not computed. 03:01 Sidedefs -------------- A map can't contain more than 32768 sidedefs. A tool called dshrink can reduce the amount of sidedefs by combining identical side defs. For very big maps, the usage of this tool in addition to ZokumBSP could make maps not normally playable in Doom playable. Some ports have changed the sidedef limit to 65536. 03:02 Linedefs -------------- The limit of linedefs is the same as sidedefs. It is possible to have more linedefs than sidedefs if dshrink is used to compress the map. There isn't much that can be done about this static limit. It should be noted that turning on geometric simplification compression can increase the number of linedefs, possibly leading to a map that will crash Doom. TODO: Fix max-linedefs limit crash bug! 03:03 Segs ---------- Segs are linedef segments and are used by the rendering part of the engine. The limit is a 32768 segs. Susually, at least one seg is created for every linedef, two for a two-sided linedef etc. Additional segs are also created as part of the node building process, this happens when the node builder splits a sector into smaller subsectors, creating a new seg where a seg is split. Different partitioning algorithms can change the amount of segs in a map. For more information about segs-count manipulation, see the special effects chapter of the manual. 03:04 Vertices -------------- The limit for vertices is the same as many other structures, 32768. It should be noted that a node builder will add vertices to a map when it splits a seg into several segs as part of the node building process. All node builders do this. It is theoretically possible to create a map with more vertices than segs or linedefs, but in practice this is very rare. This is most easily done by adding a lot of two-sided lines in the middle of a sector where both sides belong to the same sector. These lines can then be used for trigger lines, but will not generate segs, and with 2 vertices per line, it can theoretically go over the limit. Section 04: Special effects =========================== One of he goals that were added later in the development was the addition of new and interesting special effects. 04:01 Invisible floors / deep water ----------------------------------- By adding a sector inside another with sector references on both sidedefs of all involved linedefs in the new sector, it is possible to create a height-changing effect compared to the rendered floor. This technique can be used to create a deep water-style effect by placing an invisible sector with a lower floor level. However, it should be noted that objects such as trees, monsters, and players are drawn completely, which can ruin the effect. It is recommended to use this sparingly in areas where other players or monsters can be seen. Invisible floors do not have any clipping problems, but it should be kept in mind that stairs can be difficult for monsters to ascend and descend if the height difference is too great. 04:02 Do not add to blockmap - 'tag 999' ---------------------------------------- Linedefs tagged with the tag 999 will not be added to the blockmap, this can allow you to add architecture that will not incrase the blockmap. If used correctly, this can lower the size of the blockmap. In Doom a lot of the architecture is mainly for decoration, often only in the ceiling. Since one cannot look up or down, it is in most cases impossible or very hard to hit these lines. Adding such lines will allow for nice architecture without making the blockmap bigger, making it possible to put more architecture into a map than what would normally be possible. This will also speed up collision detection and in some ports the line of sight calculations. This is due to the reduced amount of linedef the engine has to check in an area. 04:03 No render tag for linedef - 'tag 998' ------------------------------------------- By setting the tag to 998 on a linedef, this line will not be rendered by the Doom engine. More specifically, this will not create a seg out of that linedef. This can be used to add impassible lines and manually simplified geometry. See the next section for more information. 04:04 Manually simplified geometry ---------------------------------- By using a combination of blockmap only lines and rendering only geometry the size of the blockmap can be reduced. If one has a rounded corner that consists of 16 linedefs, one could surround that corner, possibly reuse vertices to only 4 collissionable linedefs. Another good example would be simplifying geometry one is never near into simpler shapes, and flag the more complicated geoemtry just behind as non-collidable. This will ensure that stray projctiles and shots are still colliding, but not at the exact location of the rendered geometry. Section 05: Linedef specials ============================ ZokumBSP has additional linedef specials that change how the map is rendered and plays. This is a quick list of all the specials and their numeric value. The sections further down will describe them in more detail. Numeric Effect 48 Exactly like regular doom, except tag decides scroll speed. 998 Do not render this linedef. 999 Do not add this linedef to the blockmap. 1048 Remote scroll nearest wall with same tag. 1078 Change start vertex of all with same tag to be same as this line. Make line non-render. Also copies sidedefs. 1079 Change end vertex of all with same tag to be the same as this line. Make line non-render. Also copies sidedefs. 1080 Rotate the rendered wall N degrees, where degrees is taken from tag. 1081 Set the wall rotation to a hardcoded degree, degree taken from tag. 1082 Rotate the rendered wall N BAMs, BAMs taken from tag. 1083 Set the wall rotation to a hardoced BAM, taken from tag. 1084 Do not render seg on the second side of a linedef. 1085 Do not render seg on the front side of a lindedef. 1086 Do not render segs on any side of a linedef. 05:01 Seg manipulation specials ------------------------------- This feature is available in version 1.0.10+ The following four additional linedef specials allow you to change the angle of the rendered wall. This can be useful for special effects like subtly changed secret doors. BAM (Binary Angle Measurement) is the internal degree system used in the Doom engine games. They use 16 bits to differentiate up to 65536 different angles. There is support for both BAMs and the more familiar 360 degree system. The tag tells the node builder how many degrees clockwise the wall should be rotated. Numeric Effect 1080 Rotate the rendered wall N degrees, where degrees is taken from tag. 1081 Set the wall rotation to a hardcoded degree, degree taken from tag. 1082 Rotate the rendered wall N BAMs, BAMs taken from tag. 1083 Set the wall rotation to a hardoced BAM, taken from tag. 1084 Do not render seg on the second side of a linedef. 1085 Do not render seg on the front side of a lindedef. 1086 Do not render segs on any side of a linedef. 05:02 Scrolling wall specials / changes --------------------------------------- This feature is available in version 1.0.10+ It should be noted that there is a maximum limit of 64 scrolling walls in a map. Speeding it up to 3x uses three times as many of the 64 maximum entries. '48' Scrolling wall, in addition tag sets speed. In addition to the normal behaviour of a scrolling wall, one can now adjust the scrool speed by setting the tag of the wall. Setting it to two will make it scroll twice as fast as a normal scroller, 3x 3 times as fast etc. '1048' Remote scroll nearest wall with same tag. This one works similar to the regular scroller, 48, except it allows for that wall to have an special. One can make scrolling doors, switches etc. The chosen lindef is the one that is nearest the linedef with the 1048 type. The distance is the absolute distance from the starting vertex. 05:03 Floor specials speed differences -------------------------------------- The normal speed is the speed most floors move up or down at, however, some types move faster or slower than this speed. The donut is the only floor type that can move lower slower than the regular speed. These are the ones in Doom 2 that do not move at the regular speed. Heretic, Hexen and Strife etc. have slightly different lists. Numeric Type Speed Units per tic Effect 7 S1 Very slow 2 Raising stairs, 8 height 9 S1 Slow 4 Donut (up+down) 20 S1 Slow 4 Raise floor next higher floor, texture 22 W1 Slow 4 Raise floor next higher floor, texture 68 SR Slow 4 Raise floor next higher, texture 36 W1 Very fast 32 Lower floor 8 above highest 70 SR Very fast 32 Lower floor 8 above highest 71 S1 Very fast 32 Lower floor 8 above highest n. floor 98 WR Very fast 32 Lower floor 8 above highest n. floor 100 W1 Very fast 32 Raising stairs, 16 height 127 S1 Very fast 32 Raising stairs, 16 height 129 WR Very fast 32 Raise floor to next higher floor 130 W1 Very fast 32 Raise floor to next higher floor 131 S1 Very fast 32 Raise floor to next higher floor 132 SR Very fast 32 Raise floor to next higher floor Types 132+70 can be used to create lift-like constructions that use a switch. Types 129+98 can be used to walk-over lift. Add a regular lift to generate the expected sound. Section 06: Geometry pass ========================= The geometry pass is a pass one the level done before the blockmap, nodes and reject maps are done. It will find the basic dimensions of the map and will also apply some geometry changes used by later steps like the blockmap, nodes and reject steps to produce a smaller blockmap and better node tree etc. 06:01 Geometry pass command line options ---------------------------------------- Currently the only geometry change possible is the collission geometry step, which is outlined in the blockmap builder chapter. 06:02 What does the geometry pass do? ------------------------------------- Many of the extended linedef specials that affects segs and scrolling walls are handled at this step. This pass handles effects and transformations that can have an impact on several of the other passes. Section 07: Blockmap builder ============================ The blockmap is a data structure that is part of the map format. It is a lookup table where the engine can quickly see which lines are in a given area when performaing collission detection. The blockmap builder has gone through a very substantial update of the old ZenNode base. There are a lot of new options available. All blockmap parameters must follow after the main -b parameter. Typically something like -bo=1s=0g=2. The blockmap is rebuilt by default, to turn this off, invoke ZokumBSP with the paramter "-b-". The blockmap consists of a small header that gives the dimensionns and coordinate system of the map, a set of 2-byte values that represent a grid of 128 by 128 game units with the values being addresses of a list of linedefs that exist in that specific block. It is possible to exceed the maximum size of a classic Doom blockmap purely by having a too large grid. The exact size of the blockmap is undefined, due to the addresses of the start of the list can only be within 65536 bytes. A list can be of variable length, with the list entries extending beyond 65536 bytes. 07:01 'c' - Compress BLOCKMAP ----------------------------- This turns on basic compression of the blockmap. This makes identical lists only appear once in the blockmap. The code in ZokumBSP performs a better search than ZenNode, and will yield a better result in many cases due to checking more eligible lists. ZenNode would mostly find identical lists from the same row, but not same column or diagonally. 07:02 'h' - Output BLOCKMAP data as HTML. ----------------------------------------- This will oputput a simple html output to the standard output. On a unix-like operation system, this output can be piped into a file, and with some minor edits of the file, produce a color coded visualization of the offset addresses in the grid part of the blockmap. 07:03 'i' - Id compatible BLOCKMAP. Sets 'o=1n=2' and 'c-s-r-' ------------------------------------------------------------- This switch will turn on and off several other switches and options for the blockmap in order to attempt to produce blockmaps that are demo compatible with the ones produced by Id's DoomBSP tool. Although they are compressed unlike Id's many off the advanced techniques are disabled and the grid offset is always set to 8,8 compare to the bottom most and left most vertex. It should be noted that not all IWAD maps have been built with DoomBSP, and using it on these maps could break demo compability. This most likely applies to: Ultimate Doom: e4m7 was not built with DoomBSP. Doom 2: All maps were built with DoomBSP Final Doom TNT.wad: None were built with DoomBSP Final Doom Plutonia.wad: None were built with DoomBSP. The Master Levels are most likely not built with DoomBSP. The following pwad is probably built with DoomBSP: id Map01 idmap01.wad: map01 07:04 'o' -Offset configuration. -------------------------------- The 128x128 grid offset can start at any arbitrary location, but due to the size, anything more than 127 game units more than the leftmost or bottom most vertice, will lead to the same grid as a different offset, but with more grid data. The smallest possible offset, 0,0 is what ZenNode has at its basic offset. DoomBSP from Id is set to 8,8. This minor safety margin is not needed. It should be noted that due to bugs in the collission detection algorithms in Doom, collissions are aparently slightly different when a line is exactly on the edge of a grid. This is seen in the near-exit jump on Doom 2 map14 which is a jump that is longer than expected. Different offsets can line up the data in blockmap grids in different ways, allowing for smaller or bigger total size. You can specify how many or which offsets to use. o=0 - ZenNode 0,0 offset BLOCKMAP. This is the same offset configuration that ZenNode and probably many other node builders use. Use this if you want a quickly built blockmap. o=1 - DooMBSP / BSP 8,8 offset BLOCKMAP. An offset of 8,8 is used by DoomBSP. This has a slightly higher chance than 0,0 to build bigger blockmaps due to an increased risk of a bigger grid. o=2 - Best of 36 offset combinations. This is the default configuration for ZokumBSP. 36 offsets will be tested, from 0 to 40 along both axises,in increments of 8. It will test (0,0), (0,8), (0,16) ... (0,40), (8,0), (8,8), (8,16) ... (40,40) This is a reasonable compromise between speed and thoroughness of offset variations that will yield a smaller total result for most maps than a single offset. o=3 - Heuristic method to reduce from 65536 offsets. In this confiuration, a lot more offsets will be tested, all the way from 0 to 127 for both X and Y. The Heuristic to decrease the time spent is to avoid computing blockmaps if a combination of X and Y yields both an extra row of grid and an extra column. Testing on av.wad and doom2.wad showed that this yielded the same results as the complete range, at reduced run time. There were plenty of examples of blockmaps with an added column or row still producing the best result. o=4 - Best of all 65536 offset combinations. This is the same algorithm as approach as o=3, except without the heuristic. It is possible, but highly unlikely, that this can give a better result than the approach using the heuristic. o=x,y - Specify specific offsets. This setting allows you to select a custom set of offsets. This can be useful if you are creating a map where a specific jump or some other blockmap related artifact requires a specific setting. Aparently the collission detection algorithm performs differently when lindefs are on the exact edge of a grid in the blockmap. This can also be used as a form of special effect or to improve the collission detection in central areas in a deathmatch map etc. 07:05 'r' - Remove non-collidable lines from BLOCKMAP. ------------------------------------------------------ This option will try to remove some lines from the blockmap that one cannot interact with. These are typically the outer edge of zero-height sectors which are often used on the edges to create the illusion of a sky horizon. This option can reduce the amount of lines and the size of the grid due to the removal of the outermost lines in sky-sectors. Other lines that will be dropped are two-sided lines where both sides of the line belong to the same sector and the line is not a special line. Unlike the similar algorithm found in the nodes code that removes segs, textures do not matter. TODO: Fix bug with self-reerncing sectors. 07:06 's' - Subset compress BLOCKMAP. ------------------------------------- This option will reuse a list in the blockmap if the list is a sub set of another bigger list. This can save a nice amount of space in the list defintions of the blockmap. The downside is that there is a risk of errors in the collission detection when the player moves slowly. This is due to the engine using a fautly algorithm when the player moves slowly. This is a fairly rare occurance, and rarely noticable during normal play. The original engine and IWAD data already has a faulty line 0 in all the lists, and this is not considered a big problem in normal gaemplay. 07:07 'z' - Zero header configuration. -------------------------------------- Id's DoomBSP would originally added a small 00 header in each list. This is a bug. The engine does not parse this correctly, and sees it as a reference to linedef 0. This increases the size of the blockmap and slows down the run time speed. Additional linedefs not present in the block can in some rare cases lead to faulty collission detection. This option controls whether blockmap lists should have this header in some ports which will skip the first entry in a blockmap list regardless of it being a 0-header or not. The approach taken in MBF, to skip this redundant header, was a bad fix. The fix should instead have been done in the node builders. Due to the fact that skipping this header is needed for demo compatibility, many ports have this as a togglable option in the code anyway. Hopefully, ports will include a fix for this bug, but due to demo compatibility, older versions will have to emulate this behaviour to properly play back demos recorded with this bad optimization in place. z=0 - No zero header. This option produces a smaller blockmap. This works flawlessly, in fact better, when maps are played in the original engine and Chocolate Doom. There is however a known bug in some ports, like MBF, and those based on this port where a poor optimization will skip this header without actually checking that it is a zero-header. Such ports will have very faulty collission detection in every area in the map. If one is aiming for newer ports where this has been fixed, classic Doom or Chocolate Doom, this option is generally safe. There is a fix for this header in newer versions of the Eternity Engine. GZdoom generally ignores the blockmap, and should work fine with or without this option. z=1 - Conventional zero header. This is the current default option due to the many ports with a faulty header optimization. This adds about 2 bytes of overhead per list in the blockmap. It is also needed for demo compatibility if one is using this to compress blockmaps to make a map take up less space and use marginally less memory at runtime. z=2 - Zero footer. This is an experimental feature used in testing. It will add the 00 as the last entry in the linedef list. Doing this causes demos to desync. This is proof that not only the entries, but also the order is important. This parameter serves no other use. 07:08 'g' - Geometry simplification ----------------------------------- This is an umbrella term for several optimizations that will alter the level geometry by adding linedefs that only sohw up in collision detection and flagging linedefs as rendering only, no collision detection. Combining and changing the linedefs in a map in such a manner can result in a blockmap that is smaller and possibly more efficient when playing the game, due to fewer line collission detections required. These change will alter the level, and are not reversible with ZokumBSP. Manually fixing these changes in an editor is possible, but may take some time. When using this option at anything but level 0, turned off, it is recommended that one specifies a seperate output file or has a backup of the original map if further editing is planned. This option can add linedefs to a map, increasing the size of this data structure, with the goal of lowering the size of the usually more size constrained blockmap. Although possible, it is highly unlikely that this will add too many linedefs to a map. There is currently no check for this limit in the code as of version 1.0.9. g=0 - No simplification. This is the default setting. This will not change the level geometry at all. g=1 - Only if same sector. This is a basic level of optimization. This will try to combine linedefs that have the same sidedef sector data into longer linedefs that span the length of two or more linedefs. This not only leads to smaller blockmaps, there are also fewer lines that need to be checked during game play, resulting in a marginally higher frame rate. g=2 - Also 1-sided lines in different sectors. This will add another level of optimization. I tries to find one-side walls in a similar fashion even if they belong to different sectors. Geometrically a one-sided wall can be seen as inifinitely tall, and which sector it belongs to has no importance for the purpose of collission detection. This has not been extensively tested, but should be a fairly safe optimization. 07:09 'a' - Build big 32bit BLOCKMAP ------------------------------------ This is experimental code, and is not fully functional. The plan is to make this entry have a different name than the current name, BLOCKMAP in order to allow for bigger blockmaps that will support bigger maps. Using this will override the check for a too big blockmap, allowing for a big blockmap to be constructed. This option will only produce playable maps in ports where the blockmap is ignored. Sine the specifications are not final, nor the output correct, one cannot at this time expect any port to support this option. Section 08: Nodes builder ========================= There has been significant changes, tweaks and improvements in version 1.0.10 of ZokumBSP and upwards. There's support for different ways to manipulate SEGs directly, like the angle. 08:01 'a' - Partition selection algorithm ----------------------------------------- ZokumBSP offers the same 3 algoritms as ZenNode does. a=s - Minimize splits This is the simplest and most basic algorithm. Although it is stated to attempt to minimize splits, it may produce more segs than the other algorithms. a=d - Minimize BSP depth This is the most complex of the two main algorithms, and will attempt to produce a BSP tree that is not as deep as the ones made with the first algorithm. Anecdotal evidence suggest that this algorithm can in fact produce fewer splits for bigger maps. Try both if a reduced seg count is required. a=q - Minimize time This lagorithm uses the same approach as algorithm 2, except it doesn't check for as many combinations as a=2. It will pick the best out of 30. This makes the nodes build much faster. The downside is that the better splits may not be found every time, leading to a worse performing tree. a=a - Adaptive algorithm This one uses the depth minimization algorithm first, to make good choice for an effective tree, then changes to the split minimzation algorithm when tackling a certain amount of SEGs or fewer. In addition it will try different thresholds and final output will be the one that produced the fewest amount of segs. How man ythresholds to test can be adjusted by the thoroughness switch. The threshold will never be higher than the amount of SEGs the map initiially had. There is also a tuning factor to allow you to tweak at how many segs the algorithm changes to low-split. a=m - Multi-tree algorithm. This algorithm will build multiple trees for every partition and compare them and pick the best tree. Other than that, it works like the depth algorithm. The different metrics operate with a score, and it will pick the tree with the lowest score. The balanced algorithm exists to avoid picking trees that have a significantly higher amount of splits, with little reduction in the amount of subSectors. This is the default model. m=b - segSplits + (subSectors * 2). // Balanced m=s - segSplits // Reduce segs m=u - subSectors // Reduce subsectors. a=v Vertex algorithm This is a completely new way of picking partition lines. The current version in version 1.1 is set up to try to minimize splits. If it is possible to build a map without any split segs, this algorithm will find this build. On some maps this new approach might make produce more splits than the old one. This will hopefully improve as more research is done. This approach to finding the best partition line is a bit more complex and time consuming, so a lot of old assumptions and ideas are no longer applicable. Here is a list of maps that can be built without ANY splits: doom.wad: e2m8, e3m1, e4m2, e4m4. doom2.wad: map30, map31 Quite a lot of maps can be built with a low split count. Some enhancements are possible to lower this count, but most likely not to eliminate them. 1-2 splits: doom.wad: e1m9, e3m5, e3m8, e3m9, e4m8. doom2.wad: map04, map07, map22, map25, map28, map32 This approach is well suited for smaller maps. The current approach is not too good at picking a good line when a split is the only option. This does lead to more splits as the map is built further. More research will have to be done in this field. There are bound to be improvements to be found. The values and algorithms chosen give good overall numbers for doom.wad and doom2.wad. Slightly different tunings have been shown to improve on some maps, but give overall worse results when all the 68 maps are built. Finding and identifying why this happens will be an important research topic. 08:02 'q' - Don't display progress bar (Disabled in version 1.0.10+) -------------------------------------- This hides all the updates indicating the progress and depth of the BSP tree. If one does not pay attention to the tool output, use this option to speed up the node building process slightly. 08:03 'u' - Ensure all sub-sectors contain only 1 sector -------------------------------------------------------- This will try to make sure that sub sectors only contain one sector. This is important to have turned on when designing areas with invisible floors and other similar effects. A subsector is a convex area that are used to construct a convex area out of concave sub sectors. This property is important when designing a 3d engine since it allows for much faster rendering if all of the areas are convex. 08:04 'i' - Ignore non-visible lineDefs --------------------------------------- When enabled, this will remove two sided linedefs that have the same sector on both sides from the rendering / sub sector generation. Even with this on, it will however add sub sectors and segs if one of the following conditions are met: * The line has a tag other than 0 * There is a normal texture (render bars and fences). * There is a lower texture that will never be displayed anyway. The last one is there to make it easier to design maps with invisible floors / deep water / self referencing sectors. If this option is turned off, it will generate more segs than strictly necessary in some cases. With this on you can avoid dummy tags or a dummy lower texture. Turned off, it should build maps much more like most other node builders do, like BSP. Note: This document was updated in 2023 to clarify how the tool is intended to work, if it doesn't work like this, it is most likely a bug in the implementation. 08:05 't' - Thoroughness ------------------------ This option allows you to select how many different thresholds to try out in order to try to minimize SEG splits. Higher numbers performs more checks and take longer to compute. Setting it to 'x' will attempt to try all possible combinations. Section 09: Reject builder ========================== Only one thing has been changed from the reject builder code found in ZenNode. A overflow was fixed by using a bigger integer type of variable, allowing reject maps to be built for very big levels. It has been tested for reject maps with over ten thousand sectors. When building reject maps this big, one might have to use big blockmap support in order to compute the reject table. 09:01 'z' - Insert empty REJECT resource ---------------------------------------- This will insert a REJECT table where all the lookup values are zero. This means the engine has to do all the checks during regular gameplay. This is a very fast way to build a compliant reject lump for a map, but the performance will be low if there are monsters or other things that perform line of sight calculations. This is mostly used for testing a map in the game without having to wait for a long time due to building a reject table. 09:02 'f' - Rebuild even if REJECT effects are detected ------------------------------------------------------- This forces ZokumBSP to build a reject table even if the old one seems to contain special effects. Reject special effects usually involve setting certain entries to 1 instead of 0 to make monsters appear blind or fail to attack from certain areas when the player is in a certain area. 09:03 'g' - Use graphs to reduce LOS calculations ------------------------------------------------- Use this for a quicker built reject table. The idea is that if a sector A cannot see into sector B at all, then any sector where the line of sight has to go through sector B will also not see into sector A. 09:04 'm{b}' - Process RMB option file (.rej) --------------------------------------------- This allows ZokumBSP to use the same kind of .rej files that RMB supports in order to have similar special effects applied. Section 10: Other options ========================= 10:01 't' - Test mode, do not write data to disk ------------------------------------------------ Section 11: Compatibility ========================= The goal is to have a nodebuilder that is highly compatible with all the classic Doom engine based games and vanilla compatible source ports. 11:01 Heretic ------------- Geometry simplification may not work correctly with Heretic due to different linedef types than Doom. 11:02 Hexen ----------- Geometry simplification may not work correctly with Hexen due to different linedef types than Doom. 11:03 BOOM compatibility ------------------------ Generic raising stairs and similar specials will be autodetected, disabling the removal of some seemingly unneeded collision lines in the blockmap. 11:04 32 and 64 bit ------------------- ZokumBSP was developed on a 64bit system, and has not been tested on 32bit systems. Hopefully this will be tested in the future to ensure a wide range of systems can run this tool. The reject pass of the tool utilizes a 64bit integer in a non-time-sensitive part of the code to avoid an overflow found in ZenNode. 11:05 Operating systems supported --------------------------------- * Linux * ZokumBSP was primarily developed on Linux, using gcc, and should hopefully work well on most distributions. ZokumBSP was developed on a x86 64bit system, and has not yet been tested on a 32 bit system. It may need a newer compiler than ZenNode needed. Later versions were develped in a Virtualbox VM in order to utilize a better workstation and easy testing with windows-specific tools. * Windows * The Windows versions are usually mingw static compiles built on a Windows machine from the same source tree as the Linux version. It's usually compiled with -O2 and no special architecture specific switches, but will most likely require a semi modern win32 platform. Only Windows 7 has been tested extensively. So far no one has reported problems with incompatibilities, so it's likely one can assume it works well on other versions of this operating system. * BSD * No BSD builds have been tested. With the rise of VM technology, it is within the project scope to check release builds on BSD variants. * DOS * No DOS ports have been tested. ZenNode supported DOS builds, and there hasn't been any major changes to the code base that would make this an impossible feat compiler-wise. The tool will use a lot of memory in some situations, so it may not be possible to run every option on DOS-era appropriate hardware. * OSX * I currently don't have any hardware to test this on. Section 12: Usage in projects ============================= This is a short and incomplete list of projects / wads that used this tool in some capacity. * Doom / Doom 2 projects * This also includes some that requite Boom or limit removing support etc. 1000 Lines 2 - Community Project 1.0 Akeldama Arrival Bond of hatred BRutal EXtinction International Tournament BTSX Episode 2 Bury My Heart Knee Deep BuzzSaw: City Under Siege CABIN: An Apocalyptic Nightmare Clock Out Delta Touch - 4PDA Dire Strait Entropy Gore IMAJANA Jamal Jones Knee-Deep in KDiZD Lithubristics Under Sanguine Twilight Ozonia Suburbs (ChatGPT Edition) Technobabel * Hexen projects * It is nice to see that the untested Hexen functionality seems to work fine. Lost Luxury Section 13: Usage together with other tools =========================================== 13:01 GZ Doom Builder --------------------- ZokumBSP is a drop in replacement for ZenNode, so simply copying your current settings for ZenNode should suffice. 13:02 Other node builders or tools ---------------------------------- Each step can be disabled by adding a hyphen after the switch. -b- will disable the blockmap generation. -n- will disable the node building. -r- will disable the reject builder step. Section 14: Other resources =========================== If you are interested in more information about ZokumBSP and the Doom specs, try the following resources: Project web site: http://doom2.net/zokum/zokumbsp Github: https://github.com/zokum-no/zokumbsp Wiki: https://doomwiki.org IRC: #nightmare Section 15: Changelog ===================== The changelog is kept in a seperate file, 'changelog.txt'. This document is slightly more programmer-centric than this document. Section 16: Acknowledgements ============================ This is in no particular order. Similar entries got grouped together. Please do tell me if you don't want to be on this list for some reason, or want a change of name etc. Marc Roussaeu - ZenNode. 'Anotak' - Bug fixes and improvments. Brad Spencer - Web site layout and feedback. Helene - Being awesome 'Dew' - Feedback and bug testing. Anders Johnsen - Feedback and suggestions. Martin Aalen Hunsager - Feedback and testing. Andrew 'Linguica' Stine - Feedback and information. 'x38_ViTa_38' - Spell checking. 'Xaser' - Tool output suggestions, bug reports. Eternity Engine - Adding compatibility fixes and testing. #nightmare - Feedback and support. #d**** - Feedback and information. #noteternityenginere... - Feedback and information. Cacowards 2022 - The project won an award! Section 17: Other relevant tools =============================== ZokumBSP wouln't existed without ZenNode. Other node builders have also been used as references for algorithms. These tools could have goals and features that cover areas that ZokumBSP does not. Most notable is support for limit-less or gl nodes. You can freely combine these tools with one or more passes from ZokumBSP. 17:01 Regular node builders --------------------------- * AJBSP * https://gitlab.com/andwj/ajbsp * BSP * http://games.moria.org.uk/doom/bsp/ * DoomBSP / IdBSP * https://www.doomworld.com/idgames/utils/level_edit/node_builders/ibsp102d * Vigilant BSP * https://github.com/vigilantdoomer/vigilantbsp * ZDBSP * https://zdoom.org/wiki/ZDBSP * ZenNode * http://www.mrousseau.org/programs/ZenNode/ 17:02 GL Node builders ---------------------- * glBSP * http://glbsp.sourceforge.net/ * ZDBSP * https://zdoom.org/wiki/ZDBSP 17:03 Reject map builders ------------------------- * RMB * Rmb is an older tool that builds very good reject maps and only reject maps. It has support for special effects and some of those options also work in ZokumBSP. It should be noted that the RMB support in ZenNode is partially broken.