zokum Posted October 21, 2017 (edited) TLDR: A new way to build doom maps, spend more time, and you might just get a better built map. Spend a lot of time on your final build for release for a better result with fewer bugs and higher frame rate. Possibly less VPO and HOM as well. I have been working on a new and novel approach for node building in ZokumBSP. Node builders generally pick one dividing line and use that one to split the play area in roughly two equal parts. Each line picked after that splits the remaining are on each side of the parent line into two more areas. Picking the best splitting line is very important and is something a node builder needs a good algorithm to do well. Initially I wanted to check how good the algorithm was and added a small hack to pick the second best line at every decision. As expected this was produced overall not as well built trees, but not in all cases. For Doom 2 map07, the tree was noticably better. Obviously one or more of the top picks was not the best one with the default algorithm. So after a lot of testing and tweaking I finally figured out a decent approach to checking more than one line. I basically treat the node builder as a state machine and makde backups of all the important data, build a left and a right sub tree, then restore the state, pick a different line and build two more trees. This approach makes the node building time sky rocket. The approach I got is far from ideal and there's a lot of room for speed optimizatiosn, and there might be subtle bugs in the code. Only time and testing will tell. I had already tweaked the old Zennode algorithm to produce better results. Here are my results of how it fares when node building all of doom2.wad: MAP01 Old New %Change %Limit Time Elapsed Segs: 601 => 593 98.67% 1.81% * Subsecs: 194 => 182 93.81% 0.56% 0.017 secs MAP02 Old New %Change %Limit Time Elapsed Segs: 797 => 772 96.86% 2.36% * Subsecs: 224 => 208 92.86% 0.63% 0.015 secs MAP03 Old New %Change %Limit Time Elapsed Segs: 980 => 962 98.16% 2.94% * Subsecs: 301 => 280 93.02% 0.85% 0.023 secs MAP04 Old New %Change %Limit Time Elapsed Segs: 812 => 806 99.26% 2.46% * Subsecs: 249 => 226 90.76% 0.69% 0.018 secs MAP05 Old New %Change %Limit Time Elapsed Segs: 1391 => 1368 98.35% 4.17% * Subsecs: 409 => 387 94.62% 1.18% 0.041 secs MAP06 Old New %Change %Limit Time Elapsed Segs: 1551 => 1530 98.65% 4.67% * Subsecs: 484 => 462 95.45% 1.41% 0.052 secs MAP07 Old New %Change %Limit Time Elapsed Segs: 325 => 317 97.54% 0.97% * Subsecs: 97 => 97 100.00% 0.30% 0.004 secs MAP08 Old New %Change %Limit Time Elapsed Segs: 919 => 915 99.56% 2.79% * Subsecs: 276 => 264 95.65% 0.81% 0.026 secs MAP09 Old New %Change %Limit Time Elapsed Segs: 992 => 965 97.28% 2.94% * Subsecs: 325 => 312 96.00% 0.95% 0.034 secs MAP10 Old New %Change %Limit Time Elapsed Segs: 1417 => 1397 98.59% 4.26% * Subsecs: 455 => 417 91.65% 1.27% 0.062 secs MAP11 Old New %Change %Limit Time Elapsed Segs: 1309 => 1276 97.48% 3.89% * Subsecs: 430 => 403 93.72% 1.23% 0.040 secs MAP12 Old New %Change %Limit Time Elapsed Segs: 1277 => 1225 95.93% 3.74% * Subsecs: 423 => 377 89.13% 1.15% 0.035 secs MAP13 Old New %Change %Limit Time Elapsed Segs: 1837 => 1784 97.11% 5.44% * Subsecs: 557 => 511 91.74% 1.56% 0.067 secs MAP14 Old New %Change %Limit Time Elapsed Segs: 2815 => 2752 97.76% 8.40% * Subsecs: 851 => 768 90.25% 2.34% 0.146 secs MAP15 Old New %Change %Limit Time Elapsed Segs: 2647 => 2578 97.39% 7.87% * Subsecs: 875 => 814 93.03% 2.48% 0.148 secs MAP16 Old New %Change %Limit Time Elapsed Segs: 1230 => 1185 96.34% 3.62% * Subsecs: 421 => 382 90.74% 1.17% 0.044 secs MAP17 Old New %Change %Limit Time Elapsed Segs: 1980 => 1962 99.09% 5.99% * Subsecs: 615 => 581 94.47% 1.77% 0.091 secs MAP18 Old New %Change %Limit Time Elapsed Segs: 1132 => 1113 98.32% 3.40% * Subsecs: 416 => 395 94.95% 1.21% 0.042 secs MAP19 Old New %Change %Limit Time Elapsed Segs: 2117 => 2039 96.32% 6.22% * Subsecs: 721 => 667 92.51% 2.04% 0.110 secs MAP20 Old New %Change %Limit Time Elapsed Segs: 1678 => 1614 96.19% 4.93% * Subsecs: 577 => 540 93.59% 1.65% 0.077 secs MAP21 Old New %Change %Limit Time Elapsed Segs: 640 => 626 97.81% 1.91% * Subsecs: 229 => 225 98.25% 0.69% 0.014 secs MAP22 Old New %Change %Limit Time Elapsed Segs: 995 => 993 99.80% 3.03% * Subsecs: 316 => 303 95.89% 0.92% 0.023 secs MAP23 Old New %Change %Limit Time Elapsed Segs: 586 => 579 98.81% 1.77% * Subsecs: 197 => 187 94.92% 0.57% 0.014 secs MAP24 Old New %Change %Limit Time Elapsed Segs: 1954 => 1925 98.52% 5.87% * Subsecs: 697 => 665 95.41% 2.03% 0.109 secs MAP25 Old New %Change %Limit Time Elapsed Segs: 1164 => 1159 99.57% 3.54% * Subsecs: 407 => 389 95.58% 1.19% 0.038 secs MAP26 Old New %Change %Limit Time Elapsed Segs: 1305 => 1288 98.70% 3.93% * Subsecs: 453 => 428 94.48% 1.31% 0.057 secs MAP27 Old New %Change %Limit Time Elapsed Segs: 1522 => 1503 98.75% 4.59% * Subsecs: 484 => 458 94.63% 1.40% 0.050 secs MAP28 Old New %Change %Limit Time Elapsed Segs: 1181 => 1155 97.80% 3.52% * Subsecs: 456 => 443 97.15% 1.35% 0.072 secs MAP29 Old New %Change %Limit Time Elapsed Segs: 1911 => 1862 97.44% 5.68% * Subsecs: 751 => 704 93.74% 2.15% 0.139 secs MAP30 Old New %Change %Limit Time Elapsed Segs: 137 => 137 100.00% 0.42% * Subsecs: 43 => 38 88.37% 0.12% 0.001 secs MAP31 Old New %Change %Limit Time Elapsed Segs: 814 => 805 98.89% 2.46% * Subsecs: 229 => 221 96.51% 0.67% 0.016 secs MAP32 Old New %Change %Limit Time Elapsed Segs: 308 => 305 99.03% 0.93% * Subsecs: 91 => 87 95.60% 0.27% 0.003 secs As you can see, it will generally improve on the size and complexity of every single tree in the game. So with that in mind, I will now show the results of a few more builds. This time I specified to use a width of 2. In order to speed things up, I made it not try wider trees when the depth is above 10. As the algorithm improves, this is something I cand and will tweak. MAP01 Old New %Change %Limit Time Elapsed Segs: 593 => 593 100.00% 1.81% * Subsecs: 182 => 182 100.00% 0.56% 6.051 secs MAP07 Old New %Change %Limit Time Elapsed Segs: 317 => 316 99.68% 0.96% * Subsecs: 97 => 96 98.97% 0.29% 0.592 secs MAP15 Old New %Change %Limit Time Elapsed Segs: 2578 => 2562 99.38% 7.82% * Subsecs: 814 => 798 98.03% 2.44% 66.626 secs Ok, let's try it with width = 3 then, and try to improve on the existing width = 2. Can we do any better? MAP01 Old New %Change %Limit Time Elapsed Segs: 593 => 592 99.83% 1.81% * Subsecs: 182 => 173 95.05% 0.53% 258.747 secs MAP07 Old New %Change %Limit Time Elapsed Segs: 316 => 311 98.42% 0.95% * Subsecs: 96 => 92 95.83% 0.28% 32.398 secs MAP15 Old New %Change %Limit Time Elapsed Segs: 2562 => 2558 99.84% 7.81% * Subsecs: 798 => 766 95.99% 2.34% 3584.205 secs Ok, it seems we are definitively seing that there's more to get, but the total build time was reported as: 3 Levels processed in 64 minutes 35.350 seconds - 3 Levels needed updating. I think a slightly different approach and less stringent cutoff could yield similar data in a more reasonable amount of time. My hunch is that the big decisions early on matter more than the later splits. So with that I tried the following approach: width is X - nodedepth / 3. So if we set it to 4, it would do 4 different split lines until the depth was 3, where it would start doing 3 until the depth was 6 etc. I tried it with 3, very fast but results are not nearly as good: MAP01 Old New %Change %Limit Time Elapsed Segs: 592 => 593 100.17% 1.81% * Subsecs: 173 => 182 105.20% 0.56% 0.693 secs MAP07 Old New %Change %Limit Time Elapsed Segs: 311 => 317 101.93% 0.97% * Subsecs: 92 => 96 104.35% 0.29% 0.136 secs MAP15 Old New %Change %Limit Time Elapsed Segs: 2558 => 2571 100.51% 7.85% * Subsecs: 766 => 807 105.35% 2.46% 6.696 secs Let's try it with 4, see how much better it performs than 3. MAP01 Old New %Change %Limit Time Elapsed Segs: 593 => 592 99.83% 1.81% * Subsecs: 182 => 178 97.80% 0.54% 26.099 secs MAP07 Old New %Change %Limit Time Elapsed Segs: 317 => 315 99.37% 0.96% * Subsecs: 96 => 93 96.88% 0.28% 3.670 secs MAP15 Old New %Change %Limit Time Elapsed Segs: 2571 => 2561 99.61% 7.82% * Subsecs: 807 => 789 97.77% 2.41% 260.086 secs Total build time is a much more reasonable 4 minutes 49.855 seconds. We're not doing as well as the previous approach width = 3, but we're at a fraction of the time spent, 4 minutes instead of 64. Map01 has the same amount of segs, but 5 more sub sectors. Map15 has 3 more segs and 23 more sub sectors. We could be doing this all night, and I have been at this for well, weeks now. There's a lot of interesting things to learn here. Chief among them is to try to make a better heuristic so that the first pick is the best pick, but also to try to optimize the overall approach since there's plenty of room for making maps that are more complex, bigger and has more details visible. Maps with fewer sub sectors could in many cases need fewer vis planes to render. Maps with fewer segs would lead to less HOM in complex scenes. Code has been added to tweak the metric as to what is a better tree. -nm=u for setting fewer sub sectors as the metric and -nm=s for setting fewer segs as the metric. Use what you need to get YOUR map under the limit. If you're interested in beta releases, contact me on irc or build from GitHub sources. None of this is available in the stable releases. Edited October 21, 2017 by zokum : Mostly spelling. 15 Share this post Link to post
Niya Posted October 22, 2017 (edited) I thought node building was one of the few things that was mastered early on. I'm curious as what benefit can be derived from developing it further at this late stage in Doom's life. Not doubting you made some kind of improvement but as far as I know, node building was fast enough and good enough already 99% of the time. Are there still bugs in major node builders today ? Just curious. I've been away for 11 years. 3 Share this post Link to post
Linguica Posted October 22, 2017 1 hour ago, Niya said: I thought node building was one of the few things that was mastered early on. Node building was never really "mastered," just sort of made "good enough." Remember that even a simplistic node builder could take many seconds or even minutes to run back in the mid 90s and there was no obvious benefit to experimenting with this sort of brute-force approach to optimization. There are other potential improvements that could be made - in the back of my mind I still think it would be possible to create a node builder that didn't split any segs at all. It would result in a much larger BSP tree, but at this point in Doom's life, the seg limit is more of an annoyance than engine speed or download size, so it could be an actually useful thing to do. 6 Share this post Link to post
Niya Posted October 22, 2017 47 minutes ago, Linguica said: Node building was never really "mastered," just sort of made "good enough." Remember that even a simplistic node builder could take many seconds or even minutes to run back in the mid 90s and there was no obvious benefit to experimenting with this sort of brute-force approach to optimization. There are other potential improvements that could be made - in the back of my mind I still think it would be possible to create a node builder that didn't split any segs at all. It would result in a much larger BSP tree, but at this point in Doom's life, the seg limit is more of an annoyance than engine speed or download size, so it could be an actually useful thing to do. Ah, I see. I would have thought all this would have been completely figured out by now. 2 Share this post Link to post
scifista42 Posted October 22, 2017 53 minutes ago, Linguica said: in the back of my mind I still think it would be possible to create a node builder that didn't split any segs at all. Good to know I'm not alone. 55 minutes ago, Linguica said: It would result in a much larger BSP tree, I wouldn't say "much" if optimal choices of splits and the size-saving ideas described in later posts of previous threads about the concept were used. The trick is in using normal overhead-free binary splits wherever possible, and that the size of the overhead for each non-binary split won't be quadratically proportional to the total number of nodes in the split's subtrees, but only quadratically proportional to the number of immediate children nodes of the split, which will be mostly just 3, rarely 4, even more rarely 5 and so on, so actually, the total size of the overhead will be minimal. 2 Share this post Link to post
zokum Posted October 23, 2017 To be honest, a bigger tree might not be that much worse if you have to render fewer segs, store fewer segs, vertices etc. A split free algorithm could start by dividing sectors into convex subsectors with a near optimal layout, there are algorithms for that, and then construct the tree based on that, insead of segs. 0 Share this post Link to post
scifista42 Posted October 24, 2017 8 hours ago, zokum said: A split free algorithm could start by dividing sectors into convex subsectors with a near optimal layout, there are algorithms for that, and then construct the tree based on that, insead of segs. This bottom-up approach would tend to result in trees with the number of (overhead) nodes quadratically or even exponentially proportional to the number of (actual) subsectors. The top-down approach I've been proposing wouldn't have this problem. 0 Share this post Link to post
zokum Posted October 24, 2017 Scifista42: I still want to do it from top to bottom, but I'd want the end result to be a very good set of sub sectors. Having no splits is all nice and dandy, but fewer subsectors could mean less vis planes. And too many vis planes is a much more serious problem than too many split segs unless one is aiming for a 32kib seg map. 0 Share this post Link to post
scifista42 Posted October 24, 2017 I guess there is a sort of three-way tradeoff: Subsectors vs. splits vs. overhead nodes for split-free trees. If your goal is to minimize visplanes, alright, it makes sense to focus on subsectors first. My goal is to eliminate imprecisions in positions of vertexes generated by the node builder, in order to avoid slime trails and other glitches, and also to minimize drawsegs. Therefore, I focus on splits first, and since achieving zero splits might result in intractably large amounts of overhead nodes, I focus on overhead nodes second. 0 Share this post Link to post
zokum Posted October 29, 2017 Well, if you start with a good set of convex sub sectors, you will end up with the smallest possible amount of splits, possibly none. You could then apply your idea on top of that and end up with the sub sectors created early on. 0 Share this post Link to post
Linguica Posted October 29, 2017 Free idea: a node builder that attempts to make all node splits either vertical or horizontal so the Doom code can always use its shortcut code for those instances 🤔 3 Share this post Link to post
zokum Posted October 29, 2017 2 minutes ago, Linguica said: Free idea: a node builder that attempts to make all node splits either vertical or horizontal so the Doom code can always use its shortcut code for those instances 🤔 Yeah, I thought about that as well, at least for the initial splits until you're left with just a few lines. ZokumBSP has code to favour non-diagonal lines over diagonal lines. If all else is equal, it will go for the vertical or horisontal lines :). 0 Share this post Link to post
Linguica Posted October 30, 2017 2 hours ago, zokum said: Yeah, I thought about that as well, at least for the initial splits until you're left with just a few lines. ZokumBSP has code to favour non-diagonal lines over diagonal lines. If all else is equal, it will go for the vertical or horisontal lines :). I wonder if for a big map, an axis aligned favoring BSP tree versus a purposely non axis aligned BSP tree would actually make a difference. 0 Share this post Link to post
zokum Posted October 30, 2017 I've been looking into different metrics, and I found that going for a secondary characteristic sometimes hurt the primary characteristic. I had initially set it up so that if the metric was subsectors, it would take a line with fewer splits if it existed as long as the amount of subsectors was the same. That turned out to end up with more subsectors in the end due to favoring unbalanced trees. I have considered researching into the root node split (and maybe 1-2 levels more) to favour a good balance over pretty much anything else for a big map in order to greatly reduce the amount of bad divisions in later data. There are cases where a split line might actually be quite unbalanced, but be alongside a line that splits the map neatly into two parts without adding anything in the way of segs or subsectors. So in those cases, cutting off a "perfect" part of the map might look really unbalanced, but would make the remaining areas simpler, thus simplifying the original split. A map like map32 has some of those charateristics. Splitting the map into two alongside the door near the start should not lead to any more sub sectors or segs as far as I can tell, but would be a very badly balanced tree. A perfect uneven split, a split that reduces complexity without adding any complexity in the form of new ssectors or segs. With a vertex pair algorithm, I think a lot of map designs might have many of these. The map01 example i posted a while ago is a good example, and they most likely exist on many other maps, or at least occur often in sub trees. 0 Share this post Link to post
zokum Posted October 30, 2017 Reminds me, when it comes to vertex pair algorithms, it could be between any two vertices in the map. A nice good-enough optimization would be to only check between those in the same sectors as it is highly unlikely that vertices far away from eachother would make for better split lines without passing through vertices in the same sector anyway. It's on my list of things to research into, but I wanted to get my wider search working first, and there are still some bugs that need fixing, but I got a bit of progress tonight. 0 Share this post Link to post
scifista42 Posted October 30, 2017 (edited) 11 hours ago, zokum said: Well, if you start with a good set of convex sub sectors, you will end up with the smallest possible amount of splits, possibly none. You could then apply your idea on top of that and end up with the sub sectors created early on. The problem is, even though my idea can be applied onto arbitrary sets of subsectors, the number of non-binary-split-overhead nodes will tend to grow extremely intractably high unless the set of subsectors was specifically selected to make this number low, which would typically be a (very) different set of subsectors from the one that minimizes the total number of subsectors. In other words, the two goals are competing and generally incompatible for combining them in a single optimal solution. Edited October 30, 2017 by scifista42 0 Share this post Link to post