Jump to content
Search In
  • More options...
Find results that contain...
Find results in...
zokum

Widening the net when node building a map.

Recommended Posts

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.

Share this post


Link to post
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.

Share this post


Link to post
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.

Share this post


Link to post
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.

Share this post


Link to post

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.

Share this post


Link to post
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.

Share this post


Link to post

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.

Share this post


Link to post

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.

Share this post


Link to post

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.

Share this post


Link to post

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 🤔

Share this post


Link to post
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 :).

 

Share this post


Link to post
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.

Share this post


Link to post

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.

 

Share this post


Link to post

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.

Share this post


Link to post
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 by scifista42

Share this post


Link to post

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×