New Super BSP building algorithm! No seg splits, works for any map, vanilla comp.!

[scifista42]

Graf Zahl said:

But seriously, why should anyone bother about those special cases? They cannot really occur in actual maps so optimizing for them seems rather pointless.

They do - for example the exit pyramid in Doom2 MAP25, and I'm fairly sure that similar nested-sector structures exist in all IWADs and most PWADs.

Graf Zahl said:

I'm not really so sure about the nested setup. I am fairly convinced that it'll fail at least in R_PointInSubsector.

I have to admit, all of my BSP-related "inventions" in this thread were based on an assumption that the BSP tree will only be used for rendering. I haven't really considered game logic using the BSP tree. I think it can be salvagable anyway, though.

Yes, R_PointInSubsector will fail to find the correct subsector and followingly its sector. I looked into vanilla's code, and it looks like R_PointInSubsector is used only in functions that spawn mobjs. So theoretically, the node builder would check the map's THINGS lump, check if given sectors contain any things, and if not, use this trick to minimize count of subsectors and avoid seg splits. I'm not 100% certain it would be perfectly error-proof, though, specially in source ports which may use R_PointInSubsector for other purposes. So, after all, it might not be a good idea to do, indeed.

Anyway, this little trick was just a side note. I will better get back to trying to "proof" the main algorithm proposed in this thread, probably by partitioning the "double-U" map, which should be more "testable" than the "single-U" one.

[scifista42]

Here is the new diagram. 6 subsectors, 18 nodes, 3 subworlds (A1=orange, A2=greenblue, A3=yellow), no seg splits, and it should always sort subsectors alright during rendering. If you find the diagram confusing or don't understand how it works, see my previous one, which is analogous, but more simple and explained.



You can also notice that this tree can be further optimized. For example, if you are standing anywhere in subworld A1, you are guaranteed that subsector S3 should be rendered before S4, so that the "V10->V5" check (the first one on the bottom-most line of the diagram) is redundant and can be replaced by "V1->V1" (but then S3 should be this node's right child and S4 its left child).

[Graf Zahl]

Well, actually this was pretty pointless, as basically it's precisely the same as the 3-subsector version from last page, which each of the original subsectors being split once more. It doesn't offer any new insights in how the proposed algorithm works in general - it just adds a tiny bit of complexity to what was there already.

I really don't doubt that you'll manage to create somewhat reasonable trees on maps that are this contained and this simple - that part's actually easy if you just invest sufficient time.

You really have to do this with a somewhat more unorganized map layout with more sectors and, most importantly, more interconnectedness.

Just put a pillar in here and try to split that up - you will see that complexity will quickly go out of the window. The number of separate areas you need to create will rise so fast that you'll inevitably get problems managing the data.

Just going back to the original proposal, let me point to the (IMO) major fallacy in there - the latest diagram just reinforced my opinion about this:

Your entire idea REQUIRES for each subworld to have a subtree of its complement world (yes, that's really all the rest of the map, provided you didn't do a REAL BSP division further above the tree, then it'd just be the remaining parts of the map on the same side of the last true BSP split) I already told you I'd expect quadratic growth of the number of nodes - I just made one little mistake in my estimate, something which this map clearly hints at - it does not depend on subsectors, but subworlds! (Assuming that the subworld can be split traditionally.) But from here there's no going back - this very property is an inherent part of your entire approach and unavoidable. So the ultimate question will be: What's the growth ratio between number of subsectors and number of subworlds - the main limiting factor here is clearly the overarching rule that no splits may be made.

And since your entire approach seems to work from the bottom-up (i.e. it starts by creating convex subsectors, not by having subsectors be the results of the divisions up the tree) there's very little safeguards to keep this number down. Since your goal is to avoid splits at all costs, it effectively prevents you from any optimization.

But wait, there's more...

Actually, I think the biggest issue here will not be to prove that the approach is sound, but to actually IMPLEMENT it in the first place. It looks to me like a problem that's far more suited to how the human brain works than a computer algorithm. And for that you haven't even started to provide the basics.

[scifista42]

Graf Zahl said:

Well, actually this was pretty pointless, [...] It doesn't offer any new insights in how the proposed algorithm works in general

By this diagram, I tried to address your complaint that the previous diagram was "untestable because the origin subsector itself would take care of all clipping with its single-sided lines". Your newest complaint is valid, but you didn't say anything in regards to the old one which I believe I corrected now. Such a communication makes it harder for me to continue making progress with proving the theory. Please, don't try to destroy it by such non-constructive means.

Graf Zahl said:

Actually, I think the biggest issue here will not be to prove that the approach is sound, but to actually IMPLEMENT it in the first place.

Sounds good, as it means another bit of progress. First you were claiming that my theory is total nonsense and could never work. Then when I showed you a plausible diagram, you implied that you agree that the principle works, but you questioned its testability and memory efficiency. When I showed you that those are much less bad than you were afraid of, you are merely questioning implementation in a computer program. Don't worry, that will come - perhaps not soon, though. My tools and skill are limited.

Graf Zahl said:

And for that you haven't even started to provide the basics.

You're right, I haven't. It's been too short time since I came up with the concept, and the concept itself may not be finalized in its best optimized form. Also, it's going to be very complicated, obviously, and as I said, my tools and skill are limited. I see no reason why it should be impossible, though.

Graf Zahl said:

So the ultimate question will be: What's the growth ratio between number of subsectors and number of subworlds - the main limiting factor here is clearly the overarching rule that no splits may be made.

And since your entire approach seems to work from the bottom-up (i.e. it starts by creating convex subsectors, not by having subsectors be the results of the divisions up the tree) there's very little safeguards to keep this number down. Since your goal is to avoid splits at all costs, it effectively prevents you from any optimization.

Why do you assume / how can you know that? As you said yourself, there are not even basics laid down. Optimization is possible almost everywhere, specially where no previous optimization has been done yet.

Graf Zahl said:

You really have to do this with a somewhat more unorganized map layout with more sectors and, most importantly, more interconnectedness.

Right, but once again, my tools and skill are limited. It WILL require a lot of time and/or help from somebody before the important steps towards practical implementations can be made. In the meantime and as a start, I'm trying to convince people like you that the method can work in principle and can have its benefits to be attempted to be implemented.

[Graf Zahl]

Let me first address the issue of "untestability". Effectively you haven't done anything to improve your situation here. It's the same basic shape, it's the same basic node tree, you just replaced the former subsectors with another node leading to two subsectors each. And since that added stuff is just a plain regular BSP with no tricks involved it doesn't change anything about this not being a robust test case.

So far all you have shown that you CAN create a seemingly valid node tree for semi-trivial maps where potential interference with your not-quite-BSP splits and geometry in the background is completely removed by having one-sided walls everywhere which block all potential view into problem spots and are 100% guaranteed to be processed first.

But let's not get there. While I do not believe that you can prove universal functionality, I think doing so is a waste of time. You first need to prove that the data structure actually fits into a Doom node tree. If that won't work the rest is pointless - and the proof/disproof for the size problem is a lot easier to do.

How about a different approach that doesn't require you to manually create a node tree to a complete map?
Would you consider dividing E1M1 into convex subworlds? Just a colored map what you would consider a good processing of that map?

Just for the record: That map has 88 sectors and the original nodes contain 239 subsectors. I already pointed out that with quadratic growth and each subworld being one subsector you'd at most have about 180 subworlds to use, of course with subworlds consisting of more than one subsector that number will shrink rapidly.

[scifista42]

Graf Zahl said:

Would you consider dividing E1M1 into convex subworlds? Just a colored map what you would consider a good processing of that map?

Before I would do that, I would split E1M1 via traditional BSP several times, like in the picture below, to have smaller worlds to begin with. This is just a start that I quickly whipped up, I may continue with subworlds of each part later. (BSP hint: first split off the yellow area, then the green one, then the blue one)

[Graf Zahl]

I'd surely start like this, too. It's still going to be very complex.

Oh, one more thing: I still believe that you are ultimately defeating yourself with a totally strict 'no splits whatsoever' rule.

You should let splits of orthogonal walls at full integer coordinates pass, they cause no problems at all, with that you can easily divide the red part into two again.

[scifista42]

If it's true that seg splits of orthogonal walls at full integer coordinates cause no problems at all, it will definitely come in handy to the (still hypothetical) new "perfect" nodebuilder. However, this nodebuilder must be able to cope with any map. If you imagine an alternative E1M1 with all orthogonal lines shifted by a single pixel into becoming non-orthogonal, it won't be possible to reliably split in traditional way. Since I want to really explore my theory at this point, I consider all segs non-splittable.

---

Here is a continuation to my research of ideal BSP structure for E1M1. Based on the picture in my post above:

-The Purple, Cyan, (Blue) and Yellow worlds can be fully partitioned without splitting any segs using traditional BSP only! The resulting trees may not always be balanced, and there would be many subsectors consisting of only 1 seg, but it's possible! (EDIT: Sorry, I made a mistake, Blue one cannot)

-The Blue world can be almost fully partitioned without splitting segs using traditional BSP, but the 2 sectors forming the outdoor area entrance will remain unsplittable, I think. I will look into their partitioning with my algorithm.

-The Red and Green worlds (probably) not, and I still have to think out their partition with my algorithm.

[Graf Zahl]

scifista42 said:

-The Purple, Cyan, (Blue) and Yellow worlds can be fully partitioned without splitting any segs using traditional BSP only! The resulting trees may not always be balanced, and there would be many subsectors consisting of only 1 seg, but it's possible! (EDIT: Sorry, I made a mistake, Blue one cannot)

Yes, that's quite obvious.

I wonder how a map like E3M2 will fare. There's basically no chance to get the size down without doing any splits. That looks to me like it's close to the worst case scenario you can get for a map this size.

[scifista42]

^ Right, E3M2 is damn good at being hard to partition. On the other hand, its structure nicely hints how a subworld partitioning via my algorithm can be made. As a first step, I have split it into 11 convex subworlds, as below:



EDIT: Picture updated, fixing a little mistake.

[kb1]

Linguica said:

It might render right, but what about monster logic? Wouldn't a monster on the other side of the pillar try and shoot you anyway, because it was in the same subsector and assumed it had a clear LOS? (I don't actually know the answer to this.)

edit: it actually looks as if P_CheckSight() and its associated functions don't just assume there is a clear line of sight if two things are in the same subsector, which kind of surprises me, actually.

Actually, I think I remember MBF adding this optimization, then having to make it a compatibility toggle cause it failed on the "blind sergeant" bug!

@scifista42: You know, the goal is not to "convince Graf", or others that it will work. The goal is to mock it up and prove it! Is the problem that you're not a programmer? From your attention to detail, you could be.

If you can program, go ahead a write a small program that generates your tree, and use it to generate a WAD with some maps that use your algorithm.

If you are not a programmer, I am sure a programmer here will help you. I'll help you. But, not until you write a pseudo-algorithm.
What is a pseudo-algorithm? It's a step-by-step process, that you can give to someone who knows nothing about Doom, or sectors, or geometry, etc. That someone can take your pseudo-algorithm and convert it into a program.

Actually, you can assume that this programmer can load a WAD file, load a map, and have access to all the map's lines, sectors, etc.

A pseudo-algorithm looks like this:

1. For each sector S of Sector[]:
2.   For each line L of S.Lines[]:
3.     Vertex1X = L.Vextex1.X
       Vertex1Y = L.Vextex1.Y
       Vertex2X = L.Vextex2.X
       Vertex2Y = L.Vextex2.Y
4.     If Vertex1X = Vertex2X Go to Step 10 // Line is vertical
5.     If Vertex1Y = Vertex2Y Go to Step 15 // Line is horizontal
6.     ...                                  // Line is diagonal
...
       Make a node ...

Something like that. A set of instructions, with all of the math required to determine which nodes to make, and how to make them. All of the steps to determine convex/concave, which lines to use for splitting planes, etc. A old programming saying: "If you can't make it work on paper, you can't code it."

If you have a solid idea, you should be able to provide steps in the above fashion. Those steps should include required looping (If Count > 0 Go back to Step 8) when a step is to be done more than once.

And, even if you don't know ALL of the math involved, if you can describe exactly the result you're looking for, in simplistic terms, the programmer can probably fill in the rest. For example, you might not know how to calculate the angle/slope of a line, but if you write "Step 12: A = Angle(Line[x])", the programmer can figure out the functions needed.

But, this is your idea, so you have to provide the steps. This tool is too complicated to be general about it. Sure, I can say "I want a node builder that never splits lines", but, unless I can describe the exact process, I might as well say:

1. Steal underpants.
2. ???
3. Profit!!!

In all fairness, you have provided some good detail, and diagrams. But, I need a step-by-step guide to understand it. With exact yes/no conditional step taking, and exact formulas. And, that's exactly what a computer needs as well. If you can write this pseudo-code well enough, it is trivial to write the program to execute it.

[Quasar]

kb1 said:

Actually, I think I remember MBF adding this optimization, then having to make it a compatibility toggle cause it failed on the "blind sergeant" bug!

Correction: Lee never realized it was a compatibility issue. This was realized a couple years later by cph during PrBoom development. Eternity, PrBoom+, and other such ports have compat options to control it.

[Graf Zahl]

kb1 said:

In all fairness, you have provided some good detail, and diagrams. But, I need a step-by-step guide to understand it. With exact yes/no conditional step taking, and exact formulas. And, that's exactly what a computer needs as well. If you can write this pseudo-code well enough, it is trivial to write the program to execute it.

Correct, that's what we'd need. But I think that's one of the issues that cannot really be resolved.

Let me just summarize the issues I see here (in order in which they will occur when implementing this):

1. "Split the map into convex subworlds" is a process the human brain can easily perform because it actually perceives the shape of the map and its parts. But a computer algorithm does not! That's not saying that writing such algorithms is impossible, but it's a major undertaking and requires quite advanced skills.

2. The original concept has already shown that for every convex subworld there needs to be an entire tree for the complement part of the level. The inevitable outcome here is that the size of the generated tree will grow quadratically with the amount of subworlds.

3. This part I'm not sure about yet, but it's the most critical issue here. IMO is the thing that needs to be addressed next: If a subworld needs to split up into smaller convex subworlds without using actual BSP techniques - can the complement parts be restricted to the current subworld or do they need to contain the entire level? If they only need to contain the current subworld this still stands a chance, if not there is no chance you can put the required data into a Doom format BSP because you'll quickly exceed the data size limit of 32767 available nodes.

4. Only after it has been proven that the above issues won't blow up the BSP to unmanageable proportions it makes sense to think about the general viability of the algorithm. Even if it may actually be possible to solve the problem by just throwing an endless amount of data at it, that 'solution' is evidently not viable and therefore insufficient evidence that the approach is sound.

[scifista42]

I am a programmer (with little practical experience, but I believe I know more than well how to approach algorithmization), and the reason why I haven't created any code or pseudocode yet is exactly what Graf Zahl claimed to be the #1 issue in the post above. It would be so complicated that I can't imagine the subworld-splitting algorithm yet. I'm sure it should be possible, though.

Graf Zahl said:

3. This part I'm not sure about yet, but it's the most critical issue here. IMO is the thing that needs to be addressed next: If a subworld needs to split up into smaller convex subworlds without using actual BSP techniques - can the complement parts be restricted to the current subworld or do they need to contain the entire level? If they only need to contain the current subworld this still stands a chance, if not there is no chance you can put the required data into a Doom format BSP because you'll quickly exceed the data size limit of 32767 available nodes.

I never planned that each subworld's complement would be a unique new tree for the entire rest of the map - only the rest of given parent world, of course. I merely planned that each complement tree would "redirect" to its parent world's complement tree, in the way I describe in the OP with "X1/PX" nodes. I believed this would save traversal time. However, after what Linguica told me about BSP traversal (that the engine doesn't abort it when the screen is full), I came to a conclusion that this will save no time, and therefore it's redundant for the "X" nodes to exist at all. At least the node count can be saved thanks to knowing this. Also, I have recently looked into the definition of R_CheckBox (function that checks if given partition line's back side is potentially visible at all, and aborts traversal of the back tree if so), and there is a chance that this function will abort some of the redundant traversal anyway (thanks to the solidseg handling code, which might find out that the given part of the screen is already filled), so that not all efficiency is lost.

[Reisal]

How would this work on an extreme example, say Sunder MAP10? (The Hags Finger)

[Linguica]

Glaice said:

How would this work on an extreme example, say Sunder MAP10? (The Hags Finger)

Very poorly and pointlessly.

[Jaxxoon R]

So how is this any different really from that "ZDoomBot 5.2" thing from not too long ago?

[printz]

Graf Zahl said:

Correct, that's what we'd need. But I think that's one of the issues that cannot really be resolved.

Let me just summarize the issues I see here (in order in which they will occur when implementing this):

1. "Split the map into convex subworlds" is a process the human brain can easily perform because it actually perceives the shape of the map and its parts. But a computer algorithm does not! That's not saying that writing such algorithms is impossible, but it's a major undertaking and requires quite advanced skills

Isn't choosing the partition line (in regular nodebuilders) for optimal tree balance also a complex task?

What would be optimal here? Minimum number of subworlds? Similarly sized subworlds? Or something else?

[RestlessRodent]

Jaxxoon R said:

So how is this any different really from that "ZDoomBot 5.2" thing from not too long ago?

Different.

After putting down Scifista's claims, he remained ambitious to a much more complicated and memory inefficient (and thus computationally inefficient) way to split the nodes of a Doom level.

After putting down Gustavo's claims, he changed his viewpoint into just flat out acceptance after being told why his way would end up wasting him more time and create issues down the line.

Commonly though and by their own admission, they lack the programming skill required to effectively accomplish their feats. Their oppositions do have the required programming skill required to accomplish their feats. Programmers rely on fact and truth, same as those who work with math. Decomposition of this algorithm how it may be is essentially a heuristic which deems it worthy or unworthy if it should be continued. There is a difference between math/logical guess based results and personal opinions.

However, sometimes plunders can lead to better things. Scifista would most likely fail miserably working on this algorithm to have it efficient and fast, but would gain knowledge as he must force himself to learn (more) about BSPs, O^n, and P = NP. This learned knowledge could then lead to something better than what the current node builders offer. You learn by your successes, but you learn even more by your failures (assuming you actually learn from them and your failure does not result in long duration incapacitation).

[Graf Zahl]

Finding a partition line is a simple mathematical problem. What you want is a balance of two factors: the least number of splits and the best balance between both sides. All you really need is weigh between both factors to get an optimal result - and if you don't it isn't really that bad either - the tree may become unbalanced but it'd still work. Ultimately this boils down to something like

for(line in lines)
{
    calculate_cost();
}
pick_line_with_lowest_cost();

But this one here is not easily described in mathematical terms. The concept of "convex subworld" is something that's relatively easy to comprehend for a human brain, but describing this in terms that can be calculated algorithmically is anything but.

But wait: You want more - namely to split up the entire map so that it's not just enough to find a convex subworld - they also need to be laid out so that further processing does not explode the data set you create. Again, the human brain sees the shape of the map and can make decisions based on that - an algorithm capable of the same thing is a very, very complex thing, and still might not be able to do it right because an algorithm only can see as far as its developer did when creating it.

Glaice said:

How would this work on an extreme example, say Sunder MAP10? (The Hags Finger)

You'd most likely end up with a node tree that's larger than your computer's memory.
And you'd probably end up with a calculation time of several years... :D (that's assuming you could even save it somehow...)

Read some of my previous posts. Aside from general feasibility due to calculation complexity my main issue here is that the size of such a degenerate node tree will grow so fast that it'll quickly exceed the size of what the format can handle, even for small maps.

But since the entire point here is vanilla compatibility, this will be the hard limit of what can be done - all source ports that are somewhat relevant can handle extended nodes with full vertex precision which almost completely eliminate the problem this is supposed to solve WITHOUT having to resort to a different approach for creating nodes.

(And besides, it still needs to be proven that for subworlds within subworlds it's not necessary to create a node tree for the entire complement instead of just the complement of the parent subworld. Hell, it still needs to be proven that this can handle anything more complex than a simple, mostly orthogonal and closed-off shape.)

[RestlessRodent]

Graf Zahl said:

You'd most likely end up with a node tree that's larger than your computer's memory.
And you'd probably end up with a calculation time of several years... :D (that's assuming you could even save it somehow...)

Perhaps one can team up with Microsoft and/or Google and have a node builder as a service. However, if you write a OpenCL/Vulkan program you may be able to speed up node building by having your GPU do it. So this would add questions in this forums "Is a Radeon 6900 good enough to build the nodes of my map?".

[Linguica]

This is sort of an aside, but I think the "node builders should strive to build balanced nodes" received wisdom is basically just superstition. Balanced nodes would make a difference if you were doing something like a raytracer where you are walking near to far once for every single pixel in the image until you hit a polygon (not even counting bounces and so forth), but in Doom, you're walking the entire tree near to far exactly once to draw the entire screen. I bet that if you purposely built the most lopsided Doom map BSP tree that you could, it would make zero noticeable difference in the game's speed.

[Quasar]

Linguica said:

This is sort of an aside, but I think the "node builders should strive to build balanced nodes" received wisdom is basically just superstition. Balanced nodes would make a difference if you were doing something like a raytracer where you are walking near to far once for every single pixel in the image until you hit a polygon (not even counting bounces and so forth), but in Doom, you're walking the entire tree near to far exactly once to draw the entire screen. I bet that if you purposely built the most lopsided Doom map BSP tree that you could, it would make zero noticeable difference in the game's speed.

Balance is good when the tree is being searched. This is the case during R_PointInSubsector. A significantly unbalanced tree means that some searches for a leaf node will be much longer than others. Balance is irrelevant (theoretically at least) when visiting every node, as you state is the case for rendering.

Because DOOM does some of both, it's probably best to have a relatively balanced tree but with more emphasis placed on split avoidance. The two are usually a tradeoff; it's exceptionally difficult to build a "perfect" tree that has both optimal balance and minimal splits. But minimal splits will offer the most gain usually, maybe outside of pathological cases like Sunder MAP11 anyway, where the 5000 monsters are taking more processing time than drawing the also very complex scene.

[scifista42]

I made a new observation which I think is worth mentioning. Inspired by Linguica's Stupid BSP Tricks.

The "little BSP tree", used to find the correct subworld within a given world, is only supposed to do just that, but not traverse the other subworlds once it finds the nearest one to the camera (the complement world's tree will do it instead). If the tree was traversed into the side branches, the entire map would be attempted to be redrawn multiple times! How to reliably prevent it?

I have noticed that the BSP traversal function calls R_CheckBox, to check the world's potential visibility according to its bounding box + abort traversal if the check returns false, only when traversing the "back" tree, aka the tree "further from the camera", on the opposite side of the partition line.

void R_RenderBSPNode (int bspnum)
{
    node_t*	bsp;
    int		side;

    // Found a subsector?
    if (bspnum & NF_SUBSECTOR)
    {
	if (bspnum == -1)			
	    R_Subsector (0);
	else
	    R_Subsector (bspnum&(~NF_SUBSECTOR));
	return;
    }
		
    bsp = &nodes[bspnum];
    
    // Decide which side the view point is on.
    side = R_PointOnSide (viewx, viewy, bsp);

    // Recursively divide front space.
    R_RenderBSPNode (bsp->children[side]); 

    // Possibly divide back space.
    if (R_CheckBBox (bsp->bbox[side^1]))	
	R_RenderBSPNode (bsp->children[side^1]);
}

Now the tricky part:

What would happen if each node in the "little BSP tree" had a bounding box with zero area? (making R_CheckBox always return false)

The tree would be traversed towards the camera, and find the correct nearest subworld as intended, because bounding boxes are not even checked at this point. According to my algorithm, the tree will be traversed deeper, the respective subworld will be rendered, and then its complement world will be rendered too. Then the tree will start climbing up the "little BSP tree" back towards root. Normally, it would have a tendency to traverse each of its side branches, rendering each subworld and its complement worlds, which are guaranteed to overlap the already drawn area (and therefore undesired). But thanks to the zeroed bounding boxes, the "little BSP tree" will never enter any of those side branches, and never reach any "sibling" subworlds to the already drawn one. The "little BSP tree" will simply quickly climb up to its "little root", where it can continue normal BSP traversal to other parts of the map.

This is a lot better than I thought. All the potential overdraw, respectively unnecessary traversal, which I was afraid of, can be prevented! It surely makes the algorithm one step more viable for practical usage.

[wallabra]

I have measured your brain's power to 3 terabytes per second, compared to my 2.4 terabytes which isn't enough to make BSP calculations. Unfortunately for at least 95% certainty it will work is needed 3.4 terabytes per second but I calculated the BSP's effectiveness to be at 87% which is still good compared to some ideas I found that were immediately proven impossible.

[Graf Zahl]

scifista42 said:

This is a lot better than I thought. All the potential overdraw, respectively unnecessary traversal, which I was afraid of, can be prevented! It surely makes the algorithm one step more viable for practical usage.

No, it isn't!
You really should try to get a deeper understanding how this all works.

And you still solely think about step D while not addressing A, B and C first (A being some thought about how to implement this, B to ensure that it doesn't actually blow up the nodes beyond the limit and C to actually verify that subworlds within subworlds do not need a full separate complement tree!) - not to mention that this is even viable for maps that go beyond trivially primitive.

Your entire idea is worthless, even when it's theoretically sound, if it cannot be implemented, be that for not being able to create a working algorithm or because it exceeds the data format's limits.

[Linguica]

scifista42 said:

Now the tricky part:

What would happen if each node in the "little BSP tree" had a bounding box with zero area? (making R_CheckBox always return false)

Dude, I literally made this exact observation back on the first page of this very thread.

Linguica said:

(This works because you can set the back side of a BSP node to always be skipped over, simply by setting its bounding box to be 0x0. Therefore you can use a BSP node to do an if-else by having the bounding boxes on each side be 0x0; it will go down one side or the other, and when it eventually comes back up to the same node, it won't go down the other side at all.)

[scifista42]

I know you did, and gave you credit at the top of my post. The idea I'm presenting as "new" is the usage of the trick in "little BSP tree" for directed traversal into a subworld and out of it without entering other subworlds.

[wallabra]

Jaxxoon R said:

So how is this any different really from that "ZDoomBot 5.2" thing from not too long ago?

I can write ZDoomBot 5.2! And no one can whine in my project! I grab ZDoomBot source code, I put new functions, I make shit, I make a new ZDoomBot! What the fuck else do you want?!
This project is different, because mine isn't a THEORY, is a PROPOSAL, and proposals are DONE!

[scifista42]

Graf Zahl said:

And you still solely think about step D while not addressing A, B and C first (A being some thought about how to implement this,

I have began planning out the algorithm actually.

I came to a conclusion that splitting the whole map into subsectors prematurely would make things harder to implement and possibly prevent finding the very ideal solution, so I'm getting rid of it. The structure/composition of subsectors should be defined recursively.

The first step now is to create an algorithm to find the best partition line which doesn't split any seg at all, and detect if no such line exists.

The algorithm would go like this: For every possible pair of vertices in the world, define a line which crosses them both. Then for every linedef in the world, check if it intersects said line. If it does, abort testing the rest of linedefs and check next pair of vertices. If it doesn't, check how close the line is to the world's center, or how comparatively big are the 2 halves of the world split by this line, or what's the ratio of vertices/lines/sectors on each side of the line. Convert this number into "effectivity value". Always remember the line with the best effectivity value. So, if the new line's effectivity value is better than the best currently known one, forget that one and remember the new one. When all possible pairs of vertices are processed, partition the world by the best line. If no such line exists, try to split the world into 3 subworlds instead (algorithm todo).

You may see that this algorithm without optimization would have complexity at least O(v*v*l), where "v" is total number of vertices and "l" total number of lines, which might be over the top for large maps. Thankfully, I have come up with some optimizations, and although I'm still unsure about their implementation, the principles should work.

For example, there is no need to actually check every pair of vertices, but only pairs of those vertices which both touch the same sector - because if the goal is to not intersect any linedef, a partition line going through a given sector must undoubtly cross 2 different vertices both on the boundary of this sector. A continuous field of void should be treated as a sector too, in this case. This should reduce the total number of checks, but requires some pre-computing to determine which pairs of vertices lie on the boundary of the same sector. This can be determined only once, at the beginning of the node builder's run, and reuse the information while continually cutting down the number of pairs to check as the world/subworld sizes decrease.

Also, if 2 vertices lie on a part of the same sector, and there is a linedef in the middle between them, "blocking" the way, this pair of vertices can be omited from being checked for the entire rest of the node builder's run for all worlds. Again, this would require some pre-computing, but it might be worth it in the end.

Still planning it out.