Search In
• More options...
Find results that contain...
Find results in...

# Reducing SEGs on a map with ZokumBSP, prelimenary numbers

## Recommended Posts

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

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.

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

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%```

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 by zokum

It should be noted that this technique might help in other node builders as well. Feel free to experiment.