Stupid BSP Tricks

[esselfortium]

Szymanski said:

Yeah the reason I haven't used them is mainly because they chew through sectors.
A quake style sliding door will always have to move backwards with each step which can look odd. Wolfenstein style secrets aren't too bad.

When I've done sliding doors with lowering sectors, I've found that you can avoid having a thickness difference between each 'layer' of door by using near-90-degree diagonal lines for the front and back of the door, just one unit off of what you'd expect it to be. That way you can keep them all the same thickness without lines overlapping.

(I may have explained this poorly.)

[scifista42]

Did you mean something like this?

[printz]

esselfortium said:

I hope your assumption is correct, because a userfriendly tool for LoD-ing complex faraway structures could be revolutionary. Not only for ducking the vanilla limits, but possibly even more usefully for optimizing performance on complicated limit-removing maps!

Why, does Doom really need dynamic control of detail? I found it to be pretty fast for any arbitrarily complex scenery.

[Csonicgo]

printz said:

Why, does Doom really need dynamic control of detail? I found it to be pretty fast for any arbitrarily complex scenery.

for a limit-removing port, sure. in vanilla, you get HOM and crashes.

[esselfortium]

scifista42 said:

Did you mean something like this?

http://i.imgur.com/3oPEtkg.png

Exactly like that, just pulled in only 1 mapunit instead of several.

[Jon]

Linguica said:

*collapses, dies*

http://www.doomworld.com/linguica/hax/portal5.gif

http://www.doomworld.com/linguica/hax/portal5.wad

Chocolate Doom only (or presumably a port that has changed the seg-fixing code?)

Give crispy doom a spin. It is fixed there too, and the port has a few nice features.

[Superluigieth1]

Tutorial for a 'lingortal'?

[andrewj]

Superluigieth1 said:

Tutorial for a 'lingortal'?

A linguortorial ?

Wait until there is tool support, I suggest.

[Gez]

Figure it out by yourself, and you can then call yourself a cunning linguortalist.

[hfc2x]

kb1 said:

I smell a megawad...

I'm waiting for the official announcement.

[iori]

Gez said:

Figure it out by yourself, and you can then call yourself a cunning linguortalist.

Yes... a cunnilinguortalist.

[scifista42]

kb1 said:

I smell a megawad...

And it would be called "Power of the Hex (-editing)".

[RestlessRodent]

C ReMooD 1.0a (and by extension Doom Legacy 1.42):

portal2.wad:


portal3.wad:


portal5.wad also works as intended.

Doom Legacy was pretty much DOSDoom but with Boom features added in after the fact. This means any renderer fixes that were brought in were cherry picked.

When I get to the renderer in Java ReMooD, it will just be a port of the existing one.

fraggle said:

... domains ...

On another note, if these tricks mess with the NODES and SEGS lumps, then they will freak out all of the bot code for Doom I have ever written (since they use said lumps to generated navigation data). I would highly suggest that your node builder has a way to mark NODES and SEGS which are in the normal play domain (where you would normally walk) so any bot codes which use the node data do not get completely confused by them. This data could be added into another lump for example called NODESDOM which would be a hint that said elements of the NODES/SEGS are to not be considered as part of the navigable level.

EDIT: To not double post.

Is the trick that is done with the bridge in MAP31(?) of AV.WAD (the green color zone) a trick such as this?

[Csonicgo]

GhostlyDeath said:

Is the trick that is done with the bridge in MAP31(?) of AV.WAD (the green color zone) a trick such as this?

I think that one is just a variant of the mordeth bridge, though I can't be too sure.

[Untamed64]

Can we have these maps all in the one wad? or is that not possible

[RestlessRodent]

Untamed64 said:

Can we have these maps all in the one wad? or is that not possible

Depends, these WADs do not have associated TXTs with them so by default they go to the default copyright. Assuming USA, it would default to All Rights Reserved, which means anyone who downloaded the WAD and possesses it has violated copyright law and is capable of being sued for copyright violation.

Other than the legal barrier, it is possible to place all of these WADs into a single WAD using differing map slots.

EDIT: These are hosted on DoomWorld, so he knows who you are by your IP address in the server logs!

[RestlessRodent]

And as a big screw you to Linguica's copyright, I have packaged these together.

http://remood.org/downloads/linguortals.zip

If the URL 404s then just wait 10 minutes and try again, since a refresh is required to actually make new files visible.

[jazzmaster9]

This portal trick is very impressive.

Seeing vanilla mappers finding new tricks to play with gives me more of a reason to think DooM and vanilla mapping will last.

Its like the 90s again when they discovered self referencing sector tricks.

[Jon]

jazzmaster9 said:

Its like the 90s again when they discovered self referencing sector tricks.

Dude that was the 80s.

[Jaxxoon R]

Yeahsuresure

As we all know, all those anniversary pages were in fact 10 years behind to cover up the fact that Doom was built for alien technology and was stolen by time-travelling skater dudes in the 80s that then discovered all the mapping tricks and posted them online after the original planned release of thee game to cover up the fact that they stole it in the first place.

[riki2321]

This is awesome! Keep the good work up!

[Linguica]

Stupid BSP Trick 4: Free Speedups, Inquire Within

It's been a while, but I'm back with a brand new invention.

This time I'll explain how to speed up a Doom level by up to 15% or more without changing a single thing about the engine or the level^*.

^{* Under very specific hardware configurations and circumstances}

Confused? Read on...

So as you may or may not know, the NODES data structure is just a series of 28-byte data structures with a particular format:



When a node builder is building nodes for a map, it basically does the following:

1. Calculate the root node that covers the whole level, and the first partition line to split it in two
   
2. Store this root node as node #0
   
3. Descend to the left half of the map and do the same thing, calculating the node for this level, and another partition line
   
4. Store this node as node #1
   
5. Keep descending to the left, and then going back up and to the right side as needed, until the whole level is done
   
6. Reverse the entire list so that the root node is last, the last node is first, etc
   

When this is done and written out, that means you end up with a NODES structure that has an awful lot of stuff like this:



Where descending a node leads you to the node right above it, and then to the one above that, etc etc.

The issue - and here is where I go off the edge of the map of my knowledge on the subject into educated guessing - is that this is pretty much literally the worst possible way to order your data when you are passing it to certain kinds of CPUs. Pretty much all modern processors have multiple levels of CPU caches, which work by sending a chunk of data to a special spot where the CPU can access it extremely quickly. The idea is that if this little chunk of data you've loaded happens to contain the next relevant bit that the program needs, the CPU can get to work right away instead of having to wait a few extra nanoseconds to ask a lower cache level, or god forbid the RAM, for it.

So if a CPU asks for a given node in the node structure, and the processor is designed to take the requested data plus the next several kilobytes' worth and stick it into the cache, what happens here? It processes the root node #6653, then asks for 6652 - MISS! OK, then it loads #6652 plus some following data into cache, and now it wants #6651 - MISS! And so on.

So in that case, what would happen if you were to, say, flip the data around?



Now lots of nodes are followed by the one immediately next in the structure, so they're more likely to be in the cache, right? Well, let's find out by running a demo on a random level with a fairly beefy node structure, Sunlust Map19:



HAHA NO. Modern PCs don't give a shit. Nowadays we have gobs of cache and lots of research has gone into this sort of thing, so there is effectively zero benefit to be gained here.

But what if we try it on an older PC, like a circa-2004 Pentium-M laptop??



OK, now we have something going. This is a fairly minor speed bump, but it's still a 3.4% increase for free.

What if we take it to further extremes? The lion's share of the time in the Doom engine is spent rendering stuff. What if we use the special -fastdemo command to tell the engine to just blast through the demo as fast as possible and not even bother about rendering each frame?



Aha, now we're seeing some serious improvement. In this case we have a 16.8% increase in frame rate (well, tic rate, really) by doing absolutely nothing other than rejiggering the NODES structure.

And here's one more thing that I can't even begin to explain. What if instead of just reversing the NODES structure, we reshuffle it, so they're all in a random order? Presumably that will give a baseline for the worst-case performance, right?


^{(this should read "-fastdemo" obviously)}

Weirdly enough, no. The randomly shuffled BSP tree is basically indistinguishable from the reversed one, and - get this - still significantly faster than the default one. So whatever is going on with the default NODES structure, it is not just laid out in a not-great manner for old CPUs, but in an actively terrible one.

Also I should note that this seems to make a difference for levels with a *LOT* of nodes, and more specifically, a lot of visual complexity. When I tried timedemos on Alien Vendetta Map20, which is about as big and complex as a vanilla map can get, there was basically zero difference between the forward and reversed nodes.

Anyways, here's the omgifol script I used, along with the edited omgifol library to add a Node object in the first place: http://pastie.org/10568794

[andrewj]

Quite interesting that the effect can be so large on old CPUs.

I presume the resolution was 320x200, and higher resolutions give a much lower result (in percentage terms, the overall time saving is likely the same).

P.S. the BSP tree is used for monster sight checks, so it would be interesting to try Nuts.wad and see how much the reversed nodes improves performance.

[RestlessRodent]

Linguica said:

But what if we try it on an older PC, like a circa-2004 Pentium-M laptop??

I could try it on a Pentium 3.

[Linguica]

I've been working on a ~~~linguortal generator~~~~ and I have the basics working!!

4, 4 linguortals in 1 map! Amazing!! http://www.doomworld.com/linguica/hax/gen01.wad

Here's the godawful script which uses the same edited omgifol library as before: http://pastie.org/10577062

[jmickle66666666]

holy crap

[Graf Zahl]

What engines is this supposed to work with?

I tried two different ZDooms, one recent and a rather old one, and one Eternity install I had ready at hand and all showed crippling glitches with this map.

[scifista42]

Have you forgotten?

(vanilla/Choco only)

[jmickle66666666]

https://www.dropbox.com/s/duoxex2r36xha3e/Screenshot%202015-11-24%2015.59.45.png?dl=0

not working as intended, lol


edit: https://github.com/jmickle66666666/linguortal-gen

chucked it up on github, made some changes so it works with the latest omgifol (which has node support already). Also created an EXE build in there so people without python can try it out.

[Graf Zahl]

scifista42 said:

Have you forgotten?

(vanilla/Choco only)

I wasn't sure if it really requires the original unaltered renderer or just a software renderer. And the new search function here pretty much sucks.