This case study was done using ZokumBSP 1.0.5-rc1. Newer versions may change the data produced.
One of the goals of ZokumBSP was to reduce the blockmap so that one could make even bigger maps. One of the datasets used heavily in the testing looked at was Alien Vendetta. This 32 map set for Doom 2 is well known in the community for being a high quality map set, utilizing many complex special effects, advanced level geometry and most importantly for for the goals of ZokumBSP, several very large maps, made by different people and with different tool chains.
This test is performed without updating the reject tables and node tree, and without writing the results back to av.wad. This is done to minimize the impact of other parts of the tool chain and disk io.
$ ./ZenNode -n- -r- -t -b av.wad ZokumBSP Version: 1.0.5-rc1 (c) 2016 Kim Roar Foldøy Hauge Based on: ZenNode Version 1.2.1 (c) 1994-2004 Marc Rousseau Working on: av.wad *MAP01 : BLOCKMAP - 4216/5386 (78.28%) Compressed: 94.95% 0.014 secs *MAP02 : BLOCKMAP - 4446/5228 (85.04%) Compressed: 93.44% 0.014 secs *MAP03 : BLOCKMAP - 14502/16900 (85.81%) Compressed: 72.28% 0.348 secs *MAP04 : BLOCKMAP - 13690/16192 (84.55%) Compressed: 75.34% 0.403 secs *MAP05 : BLOCKMAP - 8392/9630 (87.14%) Compressed: 85.67% 0.039 secs *MAP06 : BLOCKMAP - 16092/31992 (50.30%) Compressed: 71.69% 0.604 secs *MAP07 : BLOCKMAP - 7682/9072 (84.68%) Compressed: 81.95% 0.154 secs *MAP08 : BLOCKMAP - 22256/25490 (87.31%) Compressed: 63.65% 0.755 secs *MAP09 : BLOCKMAP - 14626/18276 (80.03%) Compressed: 83.70% 0.188 secs *MAP10 : BLOCKMAP - 25130/29086 (86.40%) Compressed: 94.99% 0.280 secs *MAP11 : BLOCKMAP - 37010/41868 (88.40%) Compressed: 76.96% 1.633 secs *MAP12 : BLOCKMAP - 13958/16592 (84.12%) Compressed: 85.30% 0.246 secs *MAP13 : BLOCKMAP - 18972/22036 (86.10%) Compressed: 72.70% 0.415 secs *MAP14 : BLOCKMAP - 18954/22924 (82.68%) Compressed: 82.60% 0.568 secs *MAP15 : BLOCKMAP - 19240/22978 (83.73%) Compressed: 75.53% 0.868 secs *MAP16 : BLOCKMAP - 13326/15816 (84.26%) Compressed: 87.12% 0.198 secs *MAP17 : BLOCKMAP - 8772/10524 (83.35%) Compressed: 81.65% 0.047 secs *MAP18 : BLOCKMAP - 26702/31080 (85.91%) Compressed: 76.95% 1.419 secs *MAP19 : BLOCKMAP - 26102/29028 (89.92%) Compressed: 78.32% 0.551 secs *MAP20 : BLOCKMAP - 53148/65114 (81.62%) Compressed: 87.59% 2.450 secs *MAP21 : BLOCKMAP - 11988/13188 (90.90%) Compressed: 95.49% 0.013 secs *MAP22 : BLOCKMAP - 9598/11164 (85.97%) Compressed: 86.10% 0.080 secs *MAP23 : BLOCKMAP - 22360/28308 (78.99%) Compressed: 86.86% 0.768 secs *MAP24 : BLOCKMAP - 27420/50166 (54.66%) Compressed: 73.32% 0.984 secs *MAP25 : BLOCKMAP - 38680/64088 (60.35%) Compressed: 79.07% 2.464 secs *MAP26 : BLOCKMAP - 21258/25578 (83.11%) Compressed: 84.18% 0.854 secs *MAP27 : BLOCKMAP - 39830/47002 (84.74%) Compressed: 78.86% 2.112 secs *MAP28 : BLOCKMAP - 27074/30490 (88.80%) Compressed: 87.77% 0.447 secs *MAP29 : BLOCKMAP - 20610/24334 (84.70%) Compressed: 82.24% 0.528 secs *MAP30 : BLOCKMAP - 14846/16968 (87.49%) Compressed: 66.28% 0.343 secs *MAP31 : BLOCKMAP - 20066/24852 (80.74%) Compressed: 82.32% 0.455 secs *MAP32 : BLOCKMAP - 5972/6910 (86.43%) Compressed: 78.50% 0.117 secs Changes would have been written to av.wad ( 23,657,409 bytes ) 32 Levels processed in 20.359 seconds - 32 Levels need updating. 0.636219 secs/levelProcessing 32 maps took a bit over 20 seconds on a 3.2GHz multicore Opteron. ZokumBSP is singlethreaded and is generally cpu bound. The default settings for optimizations are used, that means dropping the 0000 header in lists, trying different offsets and removing some linedefs from inclusion in the blockmap and block grid size calculations.
The output in column 3 and 4 are the most important ones. They give the raw data and the ratio. Smaller percentage numbers are better, that means the new blockmap is so and so many percent of the original size.
There are a few outliers in the data here, and there are some likely reasons to this. The levels map06, map24 and map25 all have significantly better results than the other, which tend to be from 80% to 90%. This is most likely due to these maps being build with a node builder that didn't 'compress' the blockmap in any significant way. This is the default mode of BSP. Some of the other map authors used various versions of ZenNode, and early in the development of ZokumBSP the blockmaps were identical so this seems to be correct. Accorind to the Alien Vendetta project lead (Anders Johnsen), Kim Malde, and probably many of the others from the core team used ZenNode (most likely various versions). The version this fork is based on is several years newer than Alien Vendetta. Versions of ZenNode were released during the production of Alien Vendetta.
The case study will focus on three maps in this 32 map set:
Map01: An iconic and well known small map, and is easy to use as a testing ground.
Map03: The first relatively big map in the set.
Map20: Misri Halek, the biggest and most complex map in the set.
*MAP01 : BLOCKMAP - 4216/5386 (78.28%) Compressed: 94.95% 0.014 secs *MAP03 : BLOCKMAP - 14502/16900 (85.81%) Compressed: 72.28% 0.348 secs *MAP20 : BLOCKMAP - 53148/65114 (81.62%) Compressed: 87.59% 2.450 secs
Map01 receives a fairly good reduction, this is mostly due to ZokumBSP being better at finding identical block lists and dropping the 0000 header in each block.
Map03 isn't quite as well improved as map01, but it's still a decent improvement.
Map20 is the most interesting one, very close to the limit af about 65535 bytes. Project sources indicates that the map was changed to stay under that limit. With this tool, a significant amount of level geometry could have been added without reaching the limit, about 12k. It's possible that adding more geometry to this map could make it overstep the limit on 'segs', which is also 65536. A seg is a linedef segment, and a map has at least one linedef segment per line. The segs size of map20 is 336036 bytes, with 28003 entries. Given the size, this seems unlikely.
One of the reasons map20 has a big blockmap is that it has a large blockmap grid. The grid is a square area that encompasses all the geometry on the map. Map20 has a lot of empty space in two major areas, upper left and lower right. Placing additional geometry there would have meant more lists, but the same size block grid. The most optimal geometry has the map designed in such a way that it fits within a rectangle.
With the current size in mind, we could try some of the more advanced switches to see how they affect the size of the map. Let's start with map01. Changing the offsets is a safe optimization, that has some effects on gameplay due to the way the Doom engine works. Maps are usually not designed with this in mind, so in general a change here doesn't matter. Using ZenNode offets yields:
>./ZenNode -n- -r- -t -bo=0 av.wad map01 *MAP01 : BLOCKMAP - 4216/5386 (78.28%) Compressed: 94.95% 0.000 secsThis for this map, the ZenNode default of 0,0 offset margins happens to give the same result as testing 36 different offsets. This also dramatically reduces the runtime, due to making 36 times fewer blockmaps.
Using the heuristic brute force and the true brute force we should hopefully be able to find a better offset.
./ZenNode -n- -r- -t -bo=3 av.wad map01 *MAP01 : BLOCKMAP - 4206/5386 (78.09%) Compressed: 94.86% 3.034 secs ./ZenNode -n- -r- -t -bo=4 av.wad map01 *MAP01 : BLOCKMAP - 4206/5386 (78.09%) Compressed: 94.86% 3.282 secs
The result was a reduction of a mere 10 bytes, with the heuristic algorithm being slightly faster, about 10% faster. This is mostly due to the map not having that much geometry and not much to optimize. Even though the size reduction was "only" 10 bytes, that was 10 bytes from the list, and a significant part of the total blockmap size for a map like this, is in the grid. The ideal offsets for this map was X=0 and Y=20. This usually means that the edges line up so that some blocks get a lot of geometry and others not so much, without having too man slightly different lists with a lot of elements.
If one perform the same test on map03, we get the following results:
(ZenNode offsets) ./ZenNode -n- -r- -t -bo=0 av.wad map03 *MAP03 : BLOCKMAP - 14540/16900 (86.04%) Compressed: 72.46% 0.009 secs (Testing 36 combiantions) ./ZenNode -n- -r- -t -bo=2 av.wad map03 (ZokumBSP testing 36 combiantions) *MAP03 : BLOCKMAP - 14502/16900 (85.81%) Compressed: 72.28% 0.348 secs (Heuristic near brute force of 65k variations) ./ZenNode -n- -r- -t -bo=3 av.wad map03 *MAP03 : BLOCKMAP - 14490/16900 (85.74%) Compressed: 72.23% 89.772 secs (Brute force) ./ZenNode -n- -r- -t -bo=4 av.wad map03 *MAP03 : BLOCKMAP - 14490/16900 (85.74%) Compressed: 72.23% 89.687 secs
Here we see a modest gain of about 12 bytes trying 36 combinations, and another 12 bytes gained when using heuristic near brute force. The time spent computing the blockmap is 0.348 seconds in the default mode and about 90 seconds for the heuristic approad. This is about 300 times longer for 12 bytes. Not an optimization level suited for anything but a final release. The optimal offsets were X=45 and Y=17. Using the true brute force took about 90 seconds as well. Most like the tiny amount of more time spent on the heuristic meant it couldn't find many blockmap offsets that are unlikely to yield smaller blockmaps. The extra processing time is the time spent computing that heuristic minus the time saved.
Map20 is a very large map, and it takes a long time to process when using more thorough searches.(ZenNode offsets) ./ZenNode -n- -r- -t -bo=0 av.wad map20 *MAP20 : BLOCKMAP - 53310/65114 (81.87%) Compressed: 87.61% 0.056 secs (Testing 36 combiantions) ./ZenNode -n- -r- -t -bo=2 av.wad map20 *MAP20 : BLOCKMAP - 53148/65114 (81.62%) Compressed: 87.59% 2.419 secs (Heuristic near brute force of 65k variations) ./ZenNode -n- -r- -t -bo=3 av.wad map20 *MAP20 : BLOCKMAP - 53070/65114 (81.50%) Compressed: 87.59%514.854 secs (Brute force) ./ZenNode -n- -r- -t -bo=4 av.wad map04 *MAP20 : BLOCKMAP - 53070/65114 (81.50%) Compressed: 87.59%645.577 secs
With a complex map we're starting to see bigger gains when testing more offsets. Spending about 2.5 seconds instead of 0.05 on the blockmap yielded a reduction of 138 bytes. With the heuristic approach the processing time is a LOT longer. Optimal offsets of x=55, y=43 yielded a reduction of a further 78 bytes for a total of 216 bytes reduced. The true brute force yielded the same result. The ru time is starting to get excessive with the heuristic approach spending a bit over 8 and half minutes and the true brute force spent 10 minutes and 45 seconds. Here we see the heuristic cutting reducing the processing time by 2 minutes and 15 seconds and yielding the same results.
Without going into too many details, subset compression is the concept of making a smaller list point to a bigger list if all the elements from the smaller set are also in the bigger set. A list of linedefs 1, 2, 3, 4 is then a valid substiture for compression if a list of 1,2 or 1, 2, 4 etc is needed. This can reduce the size at the expense of more computations needed during gameplay. Checking linedefs outside the block is not a big problem in Doom. All the stock blockmaps contain a 0000 header that makes it look at the first linedef to check for collisions in every single block. Due to bugs in the engine, this optimization can under very rare circumstances lead to minute changes in gameplay. The errors are consistent though, so demo playback is not affected if this optimization is turned on.
Using this optimization can change interactions with the offset optimizations, and the two can be combined for even greater optimizations than any of them alone.
(Subset and 36 offsets) ./ZenNode -n- -r- -t -bso=2 av.wad map01 *MAP01 : BLOCKMAP - 4074/5386 (75.64%) Compressed: 91.76% 0.011 secs (None-subset and 36 offsets) ./ZenNode -n- -r- -t -bo=2 av.wad map01 *MAP01 : BLOCKMAP - 4216/5386 (78.28%) Compressed: 94.95% 0.014 secs (Subset and brute force) ./ZenNode -n- -r- -t -bso=4 av.wad map01 *MAP01 : BLOCKMAP - 4074/5386 (75.64%) Compressed: 91.76% 2.617 secs
As we can clearly see, this optimization yields a decent optimization. Reducing the size by 142 bytes on map01. One can also combine this with a full brute force search. This takes about 2.6 seconds compared to 0.01 seconds, but yields no better results.
If we try this optimization on a bigger map, like map03 we get the following results.
(Testing 36 combinations) ./ZenNode -n- -r- -t -bo=2 av.wad map03 (ZokumBSP testing 36 combiantions) *MAP03 : BLOCKMAP - 14502/16900 (85.81%) Compressed: 72.28% 0.348 secs (Subset and 36 offsets) ./ZenNode -n- -r- -t -bso=2 av.wad map03 *MAP03 : BLOCKMAP - 13828/16900 (81.82%) Compressed: 68.97% 0.120 secs (Subset and heuristics) ./ZenNode -n- -r- -t -bso=3 av.wad map03 *MAP03 : BLOCKMAP - 13810/16900 (81.72%) Compressed: 68.89% 31.651 secs (Subset and brute force) ./ZenNode -n- -r- -t -bso=4 av.wad map03 *MAP03 : BLOCKMAP - 13810/16900 (81.72%) Compressed: 68.89% 31.719 secs
Here we see much the same as we did without subset compression. The heuristic is on par with brute force, and very minor gains at greatly increased processing time.
For map20 the brute force was skipped as it takes a very long time and the previous results are a good indication as to what the result would be.
(Testing 36 combinations, no subset) ./ZenNode -n- -r- -t -bo=2 av.wad map20 *MAP20 : BLOCKMAP - 53148/65114 (81.62%) Compressed: 87.59% 2.419 secs (36 combinations, subset compression) ./ZenNode -n- -r- -t -bso=2 av.wad map20 *MAP20 : BLOCKMAP - 51470/65114 (79.05%) Compressed: 84.82% 1.453 secs (Heuristic offset compression and subset compression) ./ZenNode -n- -r- -t -bso=3 av.wad map20 *MAP20 : BLOCKMAP - 51408/65114 (78.95%) Compressed: 84.85%288.083 secs
One can clearly see that as a whole, subset compression is much more efficient than offset testing, and is even more efficient when combined. The run time of near brute force and subset compression is also lower than without subset compression. This means that for quick and dirty test builds, using sub set could yield a faster process. 36 offsets took only 1.453 seconds to compute, without subset, this took 2.419 seconds.