zokum Posted July 31, 2017 I'm working on tweaking the node builder code in ZokumBSP to produce better trees for large maps. A lot of this is specific to ZokumBSP 1.0.10 which is not out yet, and some of the code isn't even on GitHub yet, but some is. As some of you know, vanilla maps have something called segs. That is shorthand for linedef segments. A linedef has at least one seg, two segs if it's two-sided. Additional segs are added if a linedef is split as part of the node building. A good rule of thumb is to assume you'll have about twice as many segs as you have linedefs. My go-to map for testing is as always av.wad map20. That map has 14839 linedefs and 27997 segs if built with -na=d, a ratio of about 1.886 segs per linedef. The released map is built with the seg split partition algorithm, which aims to pick partition at the line with the least amount of splits. In general however, the second algorithm, the divide evenly one tends to produce fewer splits. This is a bit counter-intuitive. The reason this most like happens for is that the fewer-splits algorithm will often pick lines that down the road lead to more splits. It's basically painting itself into a corner, all the time. The balanced-tree approach will overall lead to less split segs and thus fewer segs. The way ZenNode's seg partition algorithm works is that it's an inter-changable method. It's possible to swap algorithm while building nodes. I figured I could use an approach similar to the one quick sort uses. Use the good even dividing partitioner on the top level and go with the split reducer when there are very few segs left. I tried a fairly arbitrary value of 30, and tested this on every map in av.wad. This produced some maps with more segs, some with less, but not much. We're talking about less than half a percent in most cases. Still, some gain over no gain is always beneficial. We are after all talking about a lower amount than any of the ones found in ZokumBSP. So i tried a few different thresholds, and results varied in all directions. What was good for one map was bad for another, and vice verca with another value. Time to use brute force! I then made a nice little hack where it would try values starting with 0 and going up to 50 and remember the best tree, the one with the lowest seg count. This worked better, several maps now saw improvements. The values for some of the thresholds were pretty high, so i figured i'd try all the values from 50 to 100. Turns out some of them also got reductions with those numbers as well, and in one case, even better reduction. Judging by this I figured I'd try all the way from 0 to 250 on the smaller maps. That gave me a map with a rather high best threshold, 237. So I caved in and tried building all the maps with values from 0 to 500 as threshold, and here is the output. It contains a small printf-debug showing the best threshold with some "-" around it. It takes a while to compute these, so here are the first 19 maps. It's still working on map20 and it will for another hour or so... As for the output, the important columns are column 2,3,4 with 4 showing overall how much of an improvement it is. The %Limit column shows how near one is the maximum size in vanilla Doom. ZokumBSP Version: 1.0.10-beta1 (c) 2016-2017 Kim Roar Foldøy Hauge Based on: ZenNode Version 1.2.1 (c) 1994-2004 Marc Rousseau Working on: av.wad MAP01 Old New %Change %Limit Time Elapsed Linedefs: 1359 => 1359 100.00% 4.15% 0.000 secs - 141 - Nodes: 723 => 724 100.14% 2.20% 42.774 secs * Segs: 2310 => 2303 99.70% 7.03% MAP02 Old New %Change %Limit Time Elapsed Linedefs: 1203 => 1203 100.00% 3.67% 0.000 secs - 70 - Nodes: 608 => 611 100.49% 1.86% 36.795 secs * Segs: 1946 => 1939 99.64% 5.92% MAP03 Old New %Change %Limit Time Elapsed Linedefs: 2549 => 2549 100.00% 7.78% 0.000 secs - 30 - Nodes: 1545 => 1551 100.39% 4.72% 135.034 secs * Segs: 4880 => 4873 99.86% 14.87% MAP04 Old New %Change %Limit Time Elapsed Linedefs: 2418 => 2418 100.00% 7.38% 0.001 secs - 237 - Nodes: 1255 => 1277 101.75% 3.88% 101.390 secs * Segs: 4160 => 4152 99.81% 12.67% MAP05 Old New %Change %Limit Time Elapsed Linedefs: 2328 => 2328 100.00% 7.10% 0.000 secs - 26 - Nodes: 967 => 972 100.52% 2.96% 74.430 secs * Segs: 3718 => 3715 99.92% 11.34% MAP06 Old New %Change %Limit Time Elapsed Linedefs: 2192 => 2192 100.00% 6.69% 0.000 secs - 13 - Nodes: 1315 => 1316 100.08% 4.00% 104.263 secs * Segs: 3857 => 3855 99.95% 11.76% MAP07 Old New %Change %Limit Time Elapsed Linedefs: 1355 => 1355 100.00% 4.14% 0.000 secs - 23 - Nodes: 767 => 771 100.52% 2.35% 51.561 secs * Segs: 2222 => 2219 99.86% 6.77% MAP08 Old New %Change %Limit Time Elapsed Linedefs: 2602 => 2602 100.00% 7.94% 0.000 secs - 0 - Nodes: 1633 => 1633 100.00% 4.97% 194.176 secs Segs: 4653 => 4653 100.00% 14.20% MAP09 Old New %Change %Limit Time Elapsed Linedefs: 3729 => 3729 100.00% 11.38% 0.000 secs - 11 - Nodes: 2187 => 2188 100.05% 6.65% 361.752 secs * Segs: 6433 => 6429 99.94% 19.62% MAP10 Old New %Change %Limit Time Elapsed Linedefs: 7555 => 7555 100.00% 23.06% 0.000 secs - 0 - Nodes: 4163 => 4163 100.00% 12.66% 1120.114 secs Segs: 12660 => 12660 100.00% 38.64% MAP11 Old New %Change %Limit Time Elapsed Linedefs: 8299 => 8299 100.00% 25.33% 0.001 secs - 437 - Nodes: 5140 => 5226 101.67% 15.90% 1868.975 secs * Segs: 14707 => 14687 99.86% 44.82% MAP12 Old New %Change %Limit Time Elapsed Linedefs: 3193 => 3193 100.00% 9.74% 0.001 secs - 67 - Nodes: 1489 => 1504 101.01% 4.57% 148.859 secs * Segs: 5071 => 5060 99.78% 15.44% MAP13 Old New %Change %Limit Time Elapsed Linedefs: 3005 => 3005 100.00% 9.17% 0.001 secs - 0 - Nodes: 1748 => 1748 100.00% 5.32% 167.719 secs Segs: 5380 => 5380 100.00% 16.42% MAP14 Old New %Change %Limit Time Elapsed Linedefs: 3991 => 3991 100.00% 12.18% 0.001 secs - 0 - Nodes: 1959 => 1959 100.00% 5.96% 299.936 secs Segs: 6390 => 6390 100.00% 19.50% MAP15 Old New %Change %Limit Time Elapsed Linedefs: 3435 => 3435 100.00% 10.48% 0.000 secs - 13 - Nodes: 1754 => 1756 100.11% 5.34% 194.456 secs * Segs: 5571 => 5570 99.98% 17.00% MAP16 Old New %Change %Limit Time Elapsed Linedefs: 3110 => 3110 100.00% 9.49% 0.001 secs - 72 - Nodes: 1746 => 1755 100.52% 5.34% 178.603 secs * Segs: 5299 => 5289 99.81% 16.14% MAP17 Old New %Change %Limit Time Elapsed Linedefs: 2099 => 2099 100.00% 6.41% 0.000 secs - 0 - Nodes: 1004 => 1004 100.00% 3.05% 77.442 secs Segs: 3283 => 3283 100.00% 10.02% MAP18 Old New %Change %Limit Time Elapsed Linedefs: 4817 => 4817 100.00% 14.70% 0.000 secs - 0 - Nodes: 2812 => 2812 100.00% 8.55% 462.239 secs Segs: 8440 => 8440 100.00% 25.76% MAP19 Old New %Change %Limit Time Elapsed Linedefs: 5353 => 5353 100.00% 16.34% 0.001 secs - 11 - Nodes: 2736 => 2743 100.26% 8.34% 511.833 secs * Segs: 8722 => 8719 99.97% 26.61% I know how to write a better split reduction algorithm, it's fairly easy to do in pseudo code. Getting it into code is a whole different project, but I might do just that, seing how this simplistic approach did do better, albeit not much. As for now, it should be possible to reduce the seg count by a little for most maps in the next release. When I get more numbers, I can post them in this thread if it is of interest to people. I think map20 will be the most interesting one of the bunch. 4 Share this post Link to post
Linguica Posted July 31, 2017 35 minutes ago, zokum said: A linedef has at least one seg, two segs if it's two-sided. *pushes up glasses* actually, a 0 sided linedef is perfectly valid in vanilla Doom. 1 Share this post Link to post
zokum Posted July 31, 2017 1 minute ago, Linguica said: *pushes up glasses* actually, a 0 sided linedef is perfectly valid in vanilla Doom. You are correct, but they're not all that useful nor important when trying to limit segs, since 0-sided ones do not generate segs. I should have said "most linedefs". 0 Share this post Link to post
zokum Posted July 31, 2017 Here comes the final batch of numbers. The threshold for map20 really surprised me, being 231. That was until I saw map25 with 498, map28 with 493 and map29 with 360. Finding a "best" threshold or a reasonable range isn't very easy. Map20 sees a reduction of 30 segs, not that much, but every bit does help. Map28 got a reasonable 25 segs reduced, and is a noticably smaller map. All in all I would categorize this kind of optimization as a very minor and time consuming optimization. I wouldn't go for this unless one really wanted to cram the last few segs out of a vanilla format map. It should be noted that the various cutoffs might change the way a map is split drastically, so if you got a map where an area is plagued with HOM due to the 256 limit, some of the BSP trees might be a better build. I think you'd be much better off just marking off lines as do-not-split though to help on such cases. All in all, it's a tool that is soon out there, people can play around with it and for those wanting the "perfect" final build of a map, this might be the setting of choice. I plan on adding a paramter -t for thoroughness allowing you to test different ranges. Most likely ranges along the lines of 3-10, 3-25, 3-75, 3-150, 3-300, 3-500, 3-750, 3-2000, 3-4000, 3-8000, 3-16000 and 3-32678. I think a better split reduction algorithm would make all of this moot, but here is the data of what can be done today, and code people can play with. I just committed code for checking from 3 to 500, just use -na=a to select the adaptive algorithm. https://github.com/zokum-no/zokumbsp MAP20 Old New %Change %Limit Time Elapsed Linedefs: 14839 => 14839 100.00% 45.29% 0.001 secs - 231 - Nodes: 9943 => 10021 100.78% 30.48% 6113.413 secs * Segs: 27997 => 27967 99.89% 85.35% MAP21 Old New %Change %Limit Time Elapsed Linedefs: 4366 => 4366 100.00% 13.32% 0.001 secs - 42 - Nodes: 2649 => 2657 100.30% 8.08% 378.928 secs * Segs: 7228 => 7216 99.83% 22.02% MAP22 Old New %Change %Limit Time Elapsed Linedefs: 2223 => 2223 100.00% 6.78% 0.000 secs - 0 - Nodes: 1176 => 1176 100.00% 3.58% 101.642 secs Segs: 3710 => 3710 100.00% 11.32% MAP23 Old New %Change %Limit Time Elapsed Linedefs: 5295 => 5295 100.00% 16.16% 0.000 secs - 16 - Nodes: 3479 => 3484 100.14% 10.60% 764.453 secs * Segs: 9701 => 9687 99.86% 29.56% MAP24 Old New %Change %Limit Time Elapsed Linedefs: 3982 => 3982 100.00% 12.15% 0.000 secs - 15 - Nodes: 2697 => 2701 100.15% 8.22% 424.636 secs * Segs: 7418 => 7414 99.95% 22.63% MAP25 Old New %Change %Limit Time Elapsed Linedefs: 7095 => 7095 100.00% 21.65% 0.001 secs - 498 - Nodes: 3919 => 4000 102.07% 12.17% 875.905 secs * Segs: 12205 => 12190 99.88% 37.20% MAP26 Old New %Change %Limit Time Elapsed Linedefs: 4710 => 4710 100.00% 14.37% 0.000 secs - 6 - Nodes: 2386 => 2386 100.00% 7.26% 373.239 secs * Segs: 7807 => 7806 99.99% 23.82% MAP27 Old New %Change %Limit Time Elapsed Linedefs: 7328 => 7328 100.00% 22.36% 0.001 secs - 30 - Nodes: 4023 => 4033 100.25% 12.27% 1172.359 secs * Segs: 12181 => 12180 99.99% 37.17% MAP28 Old New %Change %Limit Time Elapsed Linedefs: 6700 => 6700 100.00% 20.45% 0.001 secs - 493 - Nodes: 3651 => 3730 102.16% 11.34% 834.532 secs * Segs: 11612 => 11608 99.97% 35.42% MAP29 Old New %Change %Limit Time Elapsed Linedefs: 4111 => 4111 100.00% 12.55% 0.001 secs - 360 - Nodes: 2605 => 2626 100.81% 7.99% 545.751 secs * Segs: 7407 => 7382 99.66% 22.53% MAP30 Old New %Change %Limit Time Elapsed Linedefs: 1952 => 1952 100.00% 5.96% 0.001 secs - 101 - Nodes: 1123 => 1123 100.00% 3.42% 120.131 secs * Segs: 3415 => 3411 99.88% 10.41% MAP31 Old New %Change %Limit Time Elapsed Linedefs: 4816 => 4816 100.00% 14.70% 0.000 secs - 5 - Nodes: 2477 => 2477 100.00% 7.53% 327.312 secs * Segs: 8053 => 8052 99.99% 24.57% MAP32 Old New %Change %Limit Time Elapsed Linedefs: 914 => 914 100.00% 2.79% 0.000 secs - 5 - Nodes: 530 => 530 100.00% 1.61% 16.702 secs * Segs: 1658 => 1657 99.94% 5.06% 0 Share this post Link to post
zokum Posted August 8, 2017 (edited) This might not be quite the correct thread, but I didn't want to start up another thread. I did some research just to see what _could_ be done manually to improve a map, so that I knew what the code i wrote should aim for. The idea was to manually add a linedef on a map that would make it easier for the node builder to partition the map into two parts. Basically, I added a new linedef on map01, it went from the corner of the lift near the plasma on multiplayer to the corner of the hallway leading to the large plasma room. Here are my results: ./zokumbsp -b- -r- -sm -na=dt=xq doom2.wad map01 MAP01 Old New %Change %Limit Time Elapsed Nodes: 185 => 185 100.00% 0.56% 0.010 secs Segs: 611 => 611 100.00% 1.86% And now with my new "hint" line: ./zokumbsp -b- -r- -sm -na=dt=xq map01hnt.wad map01 MAP01 Old New %Change %Limit Time Elapsed Nodes: 184 => 184 100.00% 0.56% 0.010 secs Segs: 598 => 598 100.00% 1.82% That is a reduction of 13 SEGs by _adding_ a two-sided linedef. I've added a screenshot of me doodling a bit, the line in question is the red one. Ignore the other ones. Edited August 8, 2017 by zokum 0 Share this post Link to post
zokum Posted August 8, 2017 It should be noted that this technique might help in other node builders as well. Feel free to experiment. 0 Share this post Link to post
