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

jerko, Yes that would be possible, although not quick to hack up but worth to consider.

Note that ZokumBSP multi-tree works differently from what you suggested - it tries up to tree width (specified by user) amount of best linedefs per each node, not just root one, but that means running time scales exponentially rather than linearly compared to approach you suggest.

Then there is always a problem of determining which is actually the better tree visplane-wise. Now this would be a definite HARD part as I have not yet investigated how a Visplane Explorer, for example, computes visplanes, while having a "heat" map for each tree would probably be desirable for the sake of eliminating VPOs specifically and not just balancing sectors/reducing sector splits and hoping that results in VPO-free map. Cause the balance may get better, but what do we care about some VPO-free area getting less visplanes while VPO-heavy area gets more? I'm afraid this might happen as all known heuristic in nodebuilders operates on subsectors and sometimes also segs, but those don't map to visplanes 1:1. Of course they never cared to build it otherwise as computing visplanes can only happen when entire BSP tree is constructed.

I am also currently taking a break from work on nodebuilder but once I return to it I'll try to implement your suggestion. Of note, advanced visplane reduction mode does have bugs in its algorithm to identify void space, which algorithm's accuracy is necessary to, in turn, improve the accuracy of Lee Killough's heuristic for rejecting partition line candidates that cut across whole rooms without much incidence with segs. That's really hair-pulling task to fix those bugs, as inaccuracy of machine computations (resulting in the same actual point getting different coords) and cases of crossing multiple linedefs at once at one point are really confusing.

I remember I wanted to do a write-up for how I decided to determine void space so someone can help but I never did that either, constantly feeling fatigue for various reasons.

P.S. I have decided to withdraw from doomer boards otherwise and logged in just to reply to you. You can find me on the forum I have in my signature ( thegreatresist.freeforums.net ).