Stupid BSP Tricks

[Linguica]

So I was thinking about the NODES structure of levels ( http://doomwiki.org/wiki/Node ) and how part of the structure is defining the bounding box surrounding each of the child nodes.

This bounding box is used for a quick-n-dirty visibility calculation for the back side of a partition line. The engine takes the two appropriate corners of the bounding box and calculates if any part of that bounding box is even in the player's field of view; if not, it skips descending that part of the BSP tree at all, because why bother.

It made me wonder what would happen if you manually edited the bounding box for a node.

So I made a simple WAD:



Then hex edited the NODES structure to make one of the bounding boxes not match its actual location.



As you can see, the left child of this node is now a tiny little box off outside the map, not actually covering the center sector like it ought to.



Anyways, here's the result:



In the GIF I am turning back and forth so the tiny far-off bounding box enters and leaves the edge of my vision. I'm honestly surprised it worked in ZDoom because I thought ZDoom rebuilt nodes or otherwise did some futzing with them. Anyways, so yeah, it lets you hide something in plain sight, because the engine can't "see" the bounding box around it so it doesn't bother trying to draw anything there. I guess this applies to walls, floors, and things all.

Dunno if there's any useful purpose to this, I just thought it was neat.

[Gez]

Linguica said:

I'm honestly surprised it worked in ZDoom because I thought ZDoom rebuilt nodes or otherwise did some futzing with them.

ZDoom will rebuild nodes if:
- You're using the textured automap and GL nodes aren't available
- You've told it to always rebuild nodes
- The nodes are missing or invalid

[Obsidian]

Linguica said:

Dunno if there's any useful purpose to this, I just thought it was neat.

Ohh, I'm sure we can think of something. It'd certainly be useful for any sort of horror-themed maps.

[Edward850]

As a note of clarification:

Gez said:

- You're using the textured automap and GL nodes aren't available

GLNodes only rebuild the segs, so in some cases constructs like that will remain intact.

Gez said:

- You've told it to always rebuild nodes

This has no storable option for, deliberately so because it can actually break the rendering on some maps, such as Super Sonic Doom (the trees have a habit of rendering out of order if you rebuild the nodes).

In fact, Super Sonic Doom is also an example of GLNodes as well, as the trees remain intact despite the rebuilt segs.

[3_nights]

That's a really neat trick. I can see this being used ad nauseum in some tacky gimmick wad.

[Gentlepoke]

3_nights said:

That's a really neat trick. I can see this being used ad nauseum in some tacky gimmick wad.

The sort which uses Linguica's face?

[Maes]

Well, as you verified yourself, the expected result would be that it'd mess with the rendering. Perhaps you can even force the rendering of objects that are supposed not to be visible from your current position, in the same way you forced the non-rendering of that pillar.

[3_nights]

Valid question: Does this exploit affect sector lighting? As in, if the child sector has a different light level than the parent, and it's not drawn according to the bsp tree, will the lighting "flicker" the same way?

[Linguica]

Stupid BSP Trick 2: Who Needs Occlusion?

OK, for this one you need to think about what the Doom BSP tree REALLY does.

When you break it down, all the NODES structure does is present a bunch of lines. The engine starts at the "root" and asks: am I currently on the right side or left side of this line? Then it jumps to whereever the structure tells it to jump, takes a new line, and asks if it's on the right or left side again, until finally the structure says, "OK, now you can be sure you're within one specific subsector." Then it starts drawing from that subsector, and works its way back up the way it came, dropping down the other branches along the way and drawing whatever it comes across.

Part of what this means is that the normally-bulletproof occlusion culling, or whatever you want to call it, of the Doom engine is purely an artifact of a well-ordered BSP tree, and not something "enforced" in any way.

So let's exploit this:



Here's an incredibly simple level. 3 sectors, with 2 connected, and a third disconnected. This is a view of the root node, splitting the level along a line with the southern 2 sectors in one node and the northern sector in the other. Because the player is south of this line, the engine delves further down the BSP tree.



Here's the next split: either the player is in the northern sector or the southern sector (duh, right?). At this point, the NODES structure would then tell the engine, "OK, you're in subsector 1 / 2, draw that and start working your way back up."

However, nothing in the engine ENFORCES that. So what if we were to add another, entirely fake, level to the node structure?



With this setup, if the player is in the southernmost sector, the engine will now look at another line (which happens to be the exact same one as before). Except now, the right side (i.e., back side) of the node line points to the hidden northernmost sector, which has no place being listed here.

So now when the player is in the southernmost sector, the algorithm goes:

* Check root node, player is on right side, delve to child node
* * Check node, player is on left side, delve to child node
* * * Check (fake) node, player is on left side, delve to child node
* * * * Child node is southernmost subsector, draw this subsector and start going back up
* * * Check back (right) side of (fake) node, delve to child
* * * * Child node is northernmost subsector, draw this subsector and go back up
* * * Checked both sides of this node, go back up
* * Check back (right) side of this node, delve to child node
* * * Child node is middle subsector, draw this subsector and go back up
* * Checked both sides of this node, go back up
* Check back (left) side of root node, delve to child node
* * We're back at the northernmost subsector, but it's not drawn at this point for Reasons
* Checked both sides of root node, we're done!



Anyways, so yeah, I hex edit the NODES structure to add the fake node, and then run it.



It works! I did something that 3D engine programmers take pains to have NOT happen, hooray!

I know this is not very impressive looking, but whatever.

[Linguica]

Stupid BSP Trick 2.5: Fuck It Let's Mess With Segs Too

To make it slightly more impressive, I changed the WAD slightly. Then I edited the SEGS lump to make the segs for the northernmost sector stretch all the way down to the southernmost sector.



This breaks the effect in ZDoom, obviously, since ZDoom regenerates segs. But in PrBoom-plus it now looks like this:

[kb1]

Ok, I know there's something really fucking cool that this will allow. And, the cyberdemon thing is actually really fucking cool. But, what else? Could you fake some > 2.5d architexture? Or maybe use a scrolling Boom floor, and suck the player into a weird warping thing, like the blood swirl teleport deal in Doom3?

[Quasar]

Can we be sure to state up front that use of these kinds of hacks will not be supported in advanced source ports? :) Ports like EE have to depend on there being a valid BSP in order for things like dynasegs to work properly.

If you make a map like this, don't expect it to work anywhere but on the original engine and one or two ports (Choco and PrBoom-Plus software renderer, maybe).

[Linguica]

Actually that one works in EE: http://www.doomworld.com/linguica/hax/show.wad

[Arctangent]

I think it also goes without saying to not expect stuff like this to stay working on an advanced port. This kind of thing is the first thing to go if it gets in the way of further updates.

[Linguica]

http://www.doomworld.com/linguica/hax/change.wad there's another one to try in non-ZDoom ports. This one is just messing with segs though.

[Jon]

+1 would read again

keep it up!

[Quasar]

Right I just mean if you tried to do things like this *in concert* with advanced features... it might not end well :P

[Blzut3]

Linguica said:

This breaks the effect in ZDoom, obviously, since ZDoom regenerates segs.

am_textured 0

Still has trouble drawing the fake segs, although I'm not entirely sure why off hand. It does show what you were trying to accomplish though.

Quasar said:

Right I just mean if you tried to do things like this *in concert* with advanced features... it might not end well :P

I'm now curious what exactly would happen if a poly object was thrown into one of these. Both EE and ZDoom.

[printz]

Arctangent said:

I think it also goes without saying to not expect stuff like this to stay working on an advanced port. This kind of thing is the first thing to go if it gets in the way of further updates.

I hate how such innovative discoveries are stumped by source ports. Were this popularized before source ports, they would have become standard, and ports would have been required to support them. Now we have to restrict gameplay against any of these ports, somehow.

[andrewj]

printz said:

I hate how such innovative discoveries are stumped by source ports.

Really disagree, while tricks like these a kinda neat, they have little real utility in maps, and I know from experience that supporting them in a source port or a node-building tool can be a major pain in the neck.

[Gez]

printz said:

I hate how such innovative discoveries are stumped by source ports.

Funny, many port developers on the other hand hate how innovative new features in source ports are stumped by having to preserve obscure hacks like this.

Ultimately I'd rather use an engine that has proper support for polyobjects and instant sector property changes, giving clean ways to recreate the same setup, than an engine where using "advanced features" requires hex editing the node structure.

[printz]

Yeah, you say that because you work on those ports or otherwise support them closely, but that's irrelevant; if wads in the wild have to support tricks and you want your port to replace Doom.exe, you have no choice but to implement and/or keep the hacks in the logic.

[Gez]

Yeah, yeah, whatever, I'm pretty sure there are thousands of wads made for ZDoom using ZDoom features for every wad made for vanilla using obscure hacks that required the author to hex edit the node structure.

[Arctangent]

printz said:

I hate how such innovative discoveries are stumped by source ports. Were this popularized before source ports, they would have become standard, and ports would have been required to support them. Now we have to restrict gameplay against any of these ports, somehow.

Based on what I know of Graf, this is entirely false and he would've just said "fuck it" if this sort of thing got in the way of what he wanted to do with the engine.

[Linguica]

Gez said:

for every wad made for vanilla using obscure hacks that required the author to hex edit the node structure.

This is an irrelevant argument. The very first Doom PWAD started out with *quickly searches* Jeff Bird having to hex edit one together. That didn't mean making a PWAD was an obscure pointless hack, just that nobody had written any tools yet to replace such low-level work.

Which is not to say anyone will ever make any tools for directly messing with the NODES / SEGS structures (I kinda doubt it). But if someone had made tools to do it in 1995, today we'd all just say, "right, SEGS editing, that's normal."

[Gez]

It's quite disingenuous to compare making a level before tools were publicly available with deliberately messing with level data to obtain an odd behavior the engine was never meant to have.

For example, Doom was shipped with playable levels (nine of them in the original shareware episode) even before Jeff Bird invented origwad.

[Linguica]

Gez said:

deliberately messing with level data to obtain an odd behavior the engine was never meant to have.

You mean like every Doom "special effect" ever invented? DoomEd didn't have any way to make self-referencing sectors, for instance, but that didn't stop people from inventing WAD editors that *did* have the ability to make them, and then exploiting the result.

[FireFish]

I can not call this "stupid".
Its a neat trick which provids extra information and examples about making fun litle vanilla engine based mods.

edit ;
it kind of resembles an effect i was trying to make... to then crash zdoom... without using a hex editor.

[Tormentor667]

Imagine diecovering this in the 90s

[Linguica]

Stupid BSP Trick 3: Oh Hey A Portal Sorta

Building on the last thing, let's try and wrangle this occlusion trick into something more impressive.



This level is a small little area where the player is trapped, and then a giant hellish area up outside the map that can't be accessed.



Here's a closeup of the main area.

Now what we need to do is mess with the NODES structure involving this subsector right here:



The left side of this BSP dividing line points to subsector 17. When the engine gets this far down in the tree, it will draw subsector 17 and continue. But what if instead of the NODES structure jumping to subsector 17 at this point, it jumped to BSP node #20, which just happened to be the node that contains all of the hell stuff up north of the map? Wouldn't the engine just shrug and draw all that stuff instead?

(Also I edit the division line here so that it's outside the main area of the map for other reasons, but that's secondary.)



Oh hey it works! A "portal" in vanilla Doom!

http://www.doomworld.com/linguica/hax/portal2.wad (not in ZDoom)