VigilantBSP (v0.72 UPDATE) - a multi-threaded nodebuilder

Ayyy congrats on the release!

Ooo! I'm gonna have to make some maps and take this for a spin.

Congratulations Vigilante! I'm no mapmaker, but I know that it must have taken a lot of time and effort, as well as talent, to produce something like this. Thank you for sharing it with the community.

I honestly don't know what a nodebuilder is, but judging by the the amount of words and wathever mathematic language you've used.. i guess that it might be something very important.

I won't congratulate you on the release as i'm saving that to pinpoint-ely annoy someone in the future - as i find that particular sentence far more insulting than anything (not a particular jab at anyone, that's just my schizoid perception).

So for now have my sincere thanks (in advance, so when my future self properly understands the significance of this contribution; you'll already have this small token of appreciation) and let me blow you a kiss dressed in FIREBLU2 lipstick directed at your heart, my dear. ^{Catch it while is fresh}

Here you go. 


doomwiki.org/wiki/Node_builder

Great job, and very interesting - I map exclusively for vanilla (doom2.exe) and only recently started using ZokumBSP because I have a few maps that I just couldn't seem to get under the seg & visplane limits. Switching to ZokumBSP did help a lot, but if it turns out you have developed a tool that will allow me to cram even more pointless detail and smoothed corners into my vanilla maps, I will be very happy

edit: Tried it with the "target vanilla" parameters on a troublesome map, but the number of visplanes in high-stress areas of said map didn't differ from the same level built with ZokumBSP as far as I could tell after a quick dual stress-test.

I have a question regarding segs though; the documentation states that you can set the same tag as ZokumBSP on linedefs (998) to have them not rendered. However, when I built the map mentioned above (using "target vanilla" parameters from the command line) I got a drastic increase in rendered segs on the map (about 20+ more than with ZokumBSP) leading me to beleive that the 998 tagged lines were not rendered invisible after all (it's a section of a map with a lot of different sky heights). Do I have to set another parameter switch to achieve this in addition to the ones specified in "target vanilla"?

That's sad. But of course, the algorithms in ZokumBSP and VigilantBSP are really different, so one or the other could win on some maps. One thing that ZokumBSP clearly wins over mine is producing less deep BSP trees. In fact, I have a map where choosing visplane reductions over default in VigilantBSP produces deeper BSP tree, but ZokumBSP, on the other hand, produces less deep tree than with plain seg reduction.

A lot of hard work that went into ZokumBSP is hard to replicate: I have trouble reading its code, there are huge swaths of commented code, unclear names or logic, etc. Even Zennode's was already hard to understand, but it seems to have gotten even more cryptic in ZokumBSP. A shame, cause I would really like to understand its depth reduction and multi-tree algorithms.

I tried to alter my "advanced visplane reduction" to produce less depth, segs etc. but generally make equally good picks as in balancing sectors. However, while this was possible to achieve, it sometimes made some hard-hit areas have worse visplane counts, so I discarded such experiments as of yet. They might work as a basis of some partial "multi-tree" fuckery later (I would try to make search space much smaller though, so it would be practical to use on real maps), but that kind of algo will take quite some time to implement.

No, the parameter should have been respected. You can try passing "-v" parameter and redirect console output to file and verify that it contains output: Linedef <number> will not be rendered because it was either tagged so (tag 998) or assigned an action with numeric code 1086.
What really happened, is that algorithm in VigilantBSP produced more seg splits. Significant in this case... Try to use "-ni=2" then, although similar effect can be tried in ZokumBSP with "-ni", and he will probably get better results there too. However, the effect this has on visplane count is not predictable, sometimes culled segs may have been better partition picks or something (I have yet to understand how, but this was observed on a map I'm testing it most of the time).

Basically, nodebuilders initially map all 1-sided lines to 1 seg, all 2-sided lines to 2 segs, but then they get split when necessary in process to produce the final BSP tree. That is, of course, when tags or heuristic to skip seg creation are not used.That functionality originated from ZokumBSP as well. It has an effect on making only 1 seg be produced from 2-sided line initially. It still can be split further in process. The effect will probably differ from complete omission in that one side will get rendered when it is supposed to be visible (depending on angle of the viewer). Another side-effect is that since a seg will exist, the line will be considered a partition candidate, which means nodes will be built differently from the case of not rendering it all, and more similar to the case when the line didn't get any special treatment at all, but you'll get fewer segs overall and fewer drawsegs when looking from particular angle than with that latter case.

I'm considering to maybe create some experimental releases targeted towards particular use-cases and user requests (i.e. until the modifications can be confirmed to be definite, and not circumstantial improvement), but that of course would require some sort of cooperation, like me getting maps via pm or something. Meanwhile, you can try to use a different factor (-nf=<number> parameter) to see if result gets better at values lesser or greater than default value of nf=17.

Yeah, self-referencing sectors in ZokumBSP is a head-scratcher. My "workaround" is that I rarely use them, and if I have monsters in them I make sure those monsters are alerted to the player via sound/dummy secors off-map so they at least move out of said sectors and then attack. Not an optimal solution, though.

And it's good to hear you're also interested in squeezing more mileage out of vanilla! Keep up the good work

nnn✓ork Is this a map o_O?! At first I thought it was just a cheerful drawing, a bit disturbing with mousenises going through a cheek and an eye.

Looks like a source of potential trouble for nodebuilder indeed.

Anyway, writing text takes a lot of time (even more would be need to make it readable). Plus I've not rebuilt ZokumBSP with the latest changes to be 100% sure the development version is affected, but if it is, an issue on github is probably worth opening there.

Damn github also sucks with it sending an e-mail with verification code on every login attempt. Can't just type username/password to go onto website. Good thing pushing changes from local repo onto github doesn't require it, as I do it from command line using a generated access token.

I still have not written some things about VigilantBSP I have wanted to write, specifically about adjustments that distinguish "advanced visplane reduction" from "Lee Killough's algorithm for BSP nodebuilder". The former is built on the latter using Lee Killough's unimplemented ideas once again, and they have yet bugs that affect accuracy (could use some help over there), but fuck I hate writing text.

Excerpt from changelog about v0.67a -> v0.69a :


Breakdown:
1. Use secondary score for partition selection.

Zennode/ZokumBSP family of nodebuilders - unlike BSP nodebuilder - use a more fine-grained partition scoring when evaluating a partition candidate (usually, a seg) for algorithms other than fast/seg split minimization. You can instruct VigilantBSP to do the same, currently only in advanced visplane reduction mode. Although Killough's visplane reduction could be augmented to use it as well, I consider Killough's algo as a backup when you want visplane reduction but want a faster performing (even if inaccurate) algorithm.

Since having multiple scores produces some ambiguity on what could be picked, you can prioritize minimizing seg splits (for lower seg count) or subsectors (for depth reduction), or both equally (now default, for both lower seg count and lower depth than without using secondary score), while the results about visplane counts should be roughly the same.

Also, the option that should be producing the best results is already enabled by default. You can choose to disable it entirely (and get the same results as VigilantBSP v0.67a would give you, in case a regression happened), or experiment by trying other values.

2. Fixed bug: dummy linedefs created by nodebuilder to implement fast/remote scrolling shall not be added to blockmap and bsp tree

Support for fast/remote scrolling via the same mechanism as ZokumBSP 1.0.11 (and some earlier versions) was added to VigilantBSP in the initial release already, but I forgot to take the same precautions as found in ZokumBSP to make all the dummy linedefs needed to implement effect to be omitted from blockmap and bsp tree (nodes). They're really not needed there for effect to work, and best removed to keep blockmap and bsp tree minimal for the same results.

3. Debug parameters: --cpuprofile <file>, --memprofile <file>

They are only documented in accompanying text file, but do not show when you launch VigilantBSP from command line with no parameters. What they do, is write additional files that show which function calls within program code take what time or how much memory is allocated by them. This data can be analyzed by a person with programming skills, and is more informative when a map is also provided. Using this data, a programmer can identify what makes the nodebuilder slow or how to lower its memory consumption.

4. Fixed bug: panic in blockmap builder due to linedef with max index was missing from bounds computation

A stupid bug was fixed. When deciding what blockmap covers entire map sans non-collideable linedefs, linedefs with maximum index was not included in the computation. This could cause nodebuilder to crash if it was then to be added to blockmap as it would be outside "blockmap boundaries".

5. Fixed bug: panic in reject builder due to out-of-bounds access to array of solid (1-sided) lines in certain circumstances

This bug was inherited from Zennode family of nodebuilders and causes crashes (or in case Zennode/ZokumBSP working from map editor, a map editor freeze) when those nodebuilders - or previous version of VigilantBSP - build reject under certain circumstances. Workaround for nodebuilders (versions) that have not (yet) fixed this bug is to build zero reject.

6. A good thing not mentioned in changelog: before those bugs were fixed, when VigilantBSP crashed but was called from GzDoomBuilder, the latter managed to pass the error message printed by VigilantBSP along and display it to the user, so user could see that: 1) nodebuilder failed 2) capture screenshot to file a bug report containing meaningful (to programmer) information about error, including its exact location . Whereas Zennode and ZokumBSP just cause editor to freeze on crash.

That behavior on crash is not my cunning, though, just VigilantBSP was written in Go whereas Zennode and ZokumBSP in C++. Both are compiled languages, but the former is a bit easier to program in (though similar algorithm could work faster in C++), whereas the latter allows better performance in theory ("close to metal") but more bugs can creep up, and more ceremony about memory management needed during the "implementing new features" phase (which can be distracting), hence my choice.