Introducing ZokumBSP

[zokum]

VGA: What problem? If you're talking about the 00-header, just about any map will be problematic if you rebuild the blockmap in the optimized fashion and use a buggy port.

[dew]

VGA said:

Does anyone have a sample wad where the problem is immediately obvious?

I provided an example here, you need to run the map along with any BtSX E1 version. The left side of the door right in front of your starting position is mangled.

Graf Zahl said:

Don't laugh, but I remember one person a few years back who stated that he was using 2.0.63a 'because it was the last good version of ZDoom' and he saw no point upgrading ever. As stupid as it may sound, these people do exist.

Well, sometimes everything needs to break apart around these people for them to wake up, heh.

[grommile]

Jon said:

In the age of Open Source I don't understand the desire to stick to supporting particular old *binary* versions of ports.

J. Random User doesn't want to build software from source code (because "I'm not a nerd") and doesn't want to upgrade software that they perceive to be working (because "an upgrade destroyed all my files once").

[Graf Zahl]

Jon said:

In the age of Open Source I don't understand the desire to stick to supporting particular old *binary* versions of ports. If enough Joe Bloggers preferred XYZDoom 2.0.whatever for some reason, they could keep that branch alive as source for as long as they wished, and fix blockmaps whilst they're at it.

I think you are expecting way too much of this type of user. Most people don't even know what a compiler is, let alone how to use it.

grommile said:

J. Random User doesn't want to build software from source code (because "I'm not a nerd") and doesn't want to upgrade software that they perceive to be working (because "an upgrade destroyed all my files once").

People stick to old stuff for all kinds of reasons. Just ask the random person here who still uses Windows XP as their primary operating system despite warnings all over the internet that it's obsolete, unmaintained and dangerous to do so. No, 'it still works fine'. Different product, same mentality.

dew said:

Well, sometimes everything needs to break apart around these people for them to wake up, heh.

Yeah, but when it does, who do they blame? Not their own laggardness but 'those evil people who dared to end support for the best version of xyz.'

[ZZYZX]

Why so much drama over the 00 header?
GZDoom is not vanilla-compatible already. It shouldn't be vanilla compatible. It's completely ok if it breaks with vanilla maps. And it ignores such blockmaps and as such doesn't break anyway.
Either way, I'm pretty sure there are other weird vanilla tricks that won't work on newer ports, and there's absolutely no point to blame the authors of these tricks or make 5 page drama about it.

u mad brah?

/me hides

[zokum]

I've just released 1.0.9-rc1:

ZokumBSP 1.0.9-rc1
- Added geometry simplification blockmap compression. Also speeds up the
DOOM engine due to less calculations runtime.
- Added more aggressive simplification of one sided walls in different
sectors, set with level g=2.
- Made 00 headers default due to bad optimizations in many ports.
- Added a method to add new linedefs.
- Added trimming of linedef list to reduce unneeded linedefs.
- Linedefs with tag 998 will not be added to BSP tree, ie not rendered.
- Renamed PREPROCESS TO GEOMETRY. Added statistics, progress and run time.

ZokumBSP 1.0.8-rc2
- Using 64bit uints in reject code to stop it crashing on large maps. This
fixed building a reject table on a 2k sector map. Bigger maps still crash
in a different location.

ZokumBSP 1.0.8-rc1
- Anotak found a nice optimization, moved checks out of a core loop. This
gives a 33% speedup.

I have also updated the blockmap theory page on the site with information about the new algorithm. Be wary that this is a 1-way-process, since it will change the geometry of the map. Undoing the process by hand is possible, but not recommended.

The new option is invoked by adding -bg=n, where n is 1 or 2. The default is n=0, which does not add linedefs to a map.

If anything is unclear or you have any otherquestions, feel free to ask.

Blockmap theory: http://doom2.net/zokum/zokumbsp/theory
Win32 binary: http://www.doom2.net/zokum/zokumbsp/releases/zokumbsp-1.0.9-rc1-win32-mingw.zip
Changelog: https://github.com/zokum-no/zokumbsp/blob/master/src/ZenNode/changelog.txt

[Coraline]

Zokum, can you enable private messaging? I want to get with you about replacing my Blockmap internal generator with Zokum and integrating it internally, but I will have port specific questions about it.

Interested in trying it out, but I would have to hack my blockmap generator first to accept empty blockmaps on a per-map basis :-)

[zokum]

If you want to contact me, holler on irc. You can find me in the usual channels on several of the major networks. The source is on github if you need it. Updated it with the new 1.0.9 stuff.

Took me a while to remove all the bugs and kinks in the new algorithm since i had to extend the functionality of the original ZenNode wad handling code.

[Jon]

Graf Zahl said:

I think you are expecting way too much of this type of user. Most people don't even know what a compiler is, let alone how to use it.

Sure, I realise that, and the options I see are

• user uses more than one port to play doom stuff
  
• user sticks to old binary of a particular port only, and accept they won't be able to necessarily use newer things that come along (and even if its targetting vanilla, these tricks are new)
  
• user sticks to old source branch for whatever reason, and the strength of their conviction that this particular version of the port is the One True Version and so they learn about source stuff and backport things like this if they care enough
  
• source port authors are forced to forgo things which might upset special snowflake users
  

In case it's not obvious, the first option seems to be more than reasonable, and the last one completely unreasonable. The ones in the middle are options open to them.

[Graf Zahl]

Regardless of all that, compiling from source may be prevalent on Linux, it is anything but on other platforms. Binaries is what users expect and what they will get.

[grommile]

Jon said:

In case it's not obvious, the first option seems to be more than reasonable, and the last one completely unreasonable. The ones in the middle are options open to them.

It seems to me that the engine source port authors are in the clear. They can do whatever they want in newer versions of their ports.

It's the wad authors using specialist optimization tools that try to coax every last possible scrap of headroom out of the hard limits of the v1.9 executable who will get the negative reviews and angry e-mails from the users who are sticking to a particular Doom binary that plays basically every wad they've ever seen a reason to care about so why should they upgrade it just because some random on the internet wants to define "vanilla" as "works on DOOM2.EXE v1.9" rather than "works everywhere".

[Linguica]

I thought I would add a little more context re: elastic collisions since it's especially relevant to a blockmap compression tool.

You may or may not have seen my "Doom Movement Bible" thread where I tried going through the movement / clipping code and documenting all the strange effects. The last one is especially relevant since it has to do with colliding on lines that are in your same blockmap block, even if you should not be touching them.

In short, when the player is moving at a speed of less than 16 units per tic and sliding along a wall / solid thing, the Doom engine checks for collision against lines by using a faulty algorithm. Rather than checking the player's intended movement line segment to see if it intersects with a linedef's line segment, it checks if the player collides against that linedef as if it were extended out to an infinite line.

Usually this effect is blunted by the fact that the engine is only checking within the immediate blockmap, so only lines within the blockmap have the chance to spuriously block movement. If you start compressing the blockmap by having multiple block pointers point to the same super-block, then all the extra linedefs not normally within the block will also have the chance to impede the player's movement if they happen to be pointing in the right direction.

[Graf Zahl]

It seems I never read the specs here carefully enough. If it really merges blockmap blocks to include lines outside the actual block, it can indeed cause problems with almost all ports.

Since this is a relatively little known bug in the original code it's doubtful that it got fixed in many engines. I did fix it for ZDoom, of course, when it came up but I remember the discussion from last year with nobody really knowing that the issue existed to begin with.

[zokum]

In general, the original wads and pretty much every pwad out there already has line 0 in every blockmap. This is a line that is outside the block in most cases. This is rarely an issue, but it does matter for demo compatibility, due to the issue Linguica mentioned, and possibly others.

ZokumBSP doesn't do any merging of blocks unless instructed to do so via command line switches. The only merger type supported in the current version is when a list is a sub list of another.

I'll show with an example of what this entails:
List A has linedefs 1,2,3,4,5 in it.
List B has linedefs 2,3,4 in it.

Then it can "merge" these by letting any references to list B instead point to list A, since it already covers all of the lines.

Here's what I have planned to do in a future version:

If a list is a sub list, reorder the list and have it offset so that the second list only points to the correct data.

IE

List A: 1,2,3,4,5
List B: 2,3,4

List A is changed to: 1,5,2,3,4
List B is accessed by pointing to the address of list A + 2 as the offset.

So in essence A is 1,5,2,3,4 and B is 2,3,4. There is nothing in the blockmap code that forbids the offsets to point to the middle of a list.

This should be a fairly safe and decent optimization level. If need be, one could even tack on the 00 "headers" by having them twice in a list. You would still save more space and hopefully have no problems with badly optimized ports. The cost would be a few unnecessary 00 line lookups happening twice instead of once, or once instead of never if the port has the header-skip-problem.

Modified list, where B is inside A.
List A: 0,1,5,0,2,3,4
List B: 0,2,3,4.

The total space of two seperate lists with header and end marker would be: 14+10 = 24 bytes.

The total space of a combined list would be: 16 bytes.

Using the second method would disallow merges in the style of:

A = 1 2 3
B = 1 2
C = 2 3

That style is currently allowed when using the -bc switch.

[kb1]

I just wanted to say that this tool incorporates some brilliant ideas! You've studied the blockmap extensively, and you use that knowledge to squeeze the absolute most out of it. Very awesome work - I'm intrigued!

[fabian]

Hi there,

first of all, thank you for working on such an obscure project like an optimizing BLOCKMAP builder, this is realy cool!

In this context, I have just finished porting DoomBSP's BLOCKMAP builder to C for it to become Crispy Doom's internal BLOCKMAP builder. Admittedly, it is about 250 x slower than the previous implementation that I have taken from MBF, but it builds BLOCKMAPS in exactly the same way as they are in id's IWADs, so full 30 maps demos run without desyncing even when the '-blockmap' parameter is given on the command line. To me, this is really worth it. ;)

While at it, I also implemented some naive compression by detecting empty blocks (i.e. blocks which do not contain any line) and have all their offsets point to the same block in the blocklist. This saves between 50% and 10% of memory depending on the map, which is quite nice given that it reduces the BLOCKMAP size for a behemoth like e.g. planisf2.wad from around 1,4MB down to 800kB. (For the interested, the code is all here: https://github.com/fabiangreffrath/crispy-doom/commit/0d6c6b480d0f59de0d69c7e9f04a00f3bed9a481 )

What I don't get, though, is the benefit of even further compression. I mean, is memory really this sparse these days that it makes sense to further squeeze some more bytes out of a BLOCKMAP or is this more like an academic challenge for you? Also, I don't think that rendering will be any faster depending on the BLOCKMAP size, or am I wrong here?

[Graf Zahl]

fabian said:

What I don't get, though, is the benefit of even further compression. I mean, is memory really this sparse these days that it makes sense to further squeeze some more bytes out of a BLOCKMAP or is this more like an academic challenge for you? Also, I don't think that rendering will be any faster depending on the BLOCKMAP size, or am I wrong here?

It's more that the maximum size of a blockmap is limited by the possible index values that fit into a signed short. With more compression you can make larger maps that still play on Doom2.exe.

[Gez]

fabian said:

In this context, I have just finished porting DoomBSP's BLOCKMAP builder to C for it to become Crispy Doom's internal BLOCKMAP builder. Admittedly, it is about 250 x slower than the previous implementation that I have taken from MBF, but it builds BLOCKMAPS in exactly the same way as they are in id's IWADs, so full 30 maps demos run without desyncing even when the '-blockmap' parameter is given on the command line. To me, this is really worth it. ;)

What exactly is the use-case here? Rebuilding the blockmap to play demo of maps that don't need their blockmap rebuilt?

[fabian]

Graf Zahl said:

It's more that the maximum size of a blockmap is limited by the possible index values that fit into a signed short. With more compression you can make larger maps that still play on Doom2.exe.

I see, that's reasonable!

Gez said:

What exactly is the use-case here? Rebuilding the blockmap to play demo of maps that don't need their blockmap rebuilt?

Kind of, yes. ;)

My rationale is that if I really have to build a blockmap, it should be done in a way that is as Vanilla as possible. I know that it doesn't make immediate sense, but I like the feeling of it. :D

[Graf Zahl]

Hm, so the stock maps will survive a blockmap rebuild now, but what about all those maps using other node builders? They will suffer as much as before. And isn't that algorithm known to have some bugs?

Ultimately for a tool like a blockmap builder, for me speed is the most important factor, so this wouldn't be an option for me.

[BigDickBzzrak]

fabian said:

it is about 250 x slower than the previous implementation that I have taken from MBF

And how much is that exactly? 250x sounds bad.

BTW, could someone explain to me what do these 998/999 tags do?
I don't really understand. :/

[grommile]

bzzrak said:

And how much is that exactly? 250x sounds bad.

BTW, could someone explain to me what do these 998/999 tags do?
I don't really understand. :/

The blockmap is used to test for collisions between things and linedefs.

If a linedef has no trigger action and the sectors on both sides of it are guaranteed to have the same floor and ceiling height as each other at all times, then there is (or at least should be) no need to test for collisions with that linedef.

Any linedef that doesn't need to be collision-tested can (in principle) be left out of the blockmap.

The proposal for reserving a tag number for marking such linedefs is a way to allow the human who creates the level to apply their knowledge of the level to say "this linedef should never be collidable-with, so it doesn't need to be collision-tested".

[zokum]

ZokumBSP can rebuild blockmaps to be, as far as I know, compatible with DoomBSP's. This is invoked by using the -bi paramter, short for Id-compatible. This refers to the id tools, not the iwads.

I tested this with playing back 30famax2.lmp, a very long demo spanning map 1 to 30 of DOOM 2, it's a max kill with -fast.

It should be noted that e4m7 in udoom and all the Final Doom maps in both episodes were most likely built with other tools than Id's DoomBSP, and aren't compatible with the -bi switch. You could rebuild the blockmaps of those most likely with a different set of switches, -bo=0r- should probably do the trick. I haven't looked at the blockmap of the maps.

e4m7 has according to the doom wiki a 'perfect' reject table when compare to the output of RMB, most likely due to John Anderson using RMB himself and most likely a different node builder and other entries were probably not rebuilt by the Id people.

As always I would turn off reject and node building when rebuilding iwads with the intention of staying demo compatible. Use -r- -n- switches to do that.

When it comes to bugs in the blockmap algorithm, I don't think DoomBSP has any apart from the now infamous 00-header-problem, which from the engine point of view is a bug.

ZokumBSP has a fair amount of speed optimizations when it comes to the compression, it tries to narrow down the possible lists of candidates when trying to find identical lists. Due to fixing some algorithm oversights in ZenNode, it performs better, and in most cases also faster.

Speed wise here are some numbers from rebuilding the original 32 maps in doom 2, with -bi on a 3.2GHz Opteron:

32 Levels processed in 0.543 seconds - 32 Levels need updating.
58.931860 levels/sec

Since the project is GPL, you can freely rip out the pieces you need and use them in another GPL project.

Tag 999 and 998 and possibly future others are extensions that is supported by ZokumBSP to enable certain special effects and optimizations.

Tag 999 marks a linedef as never-collidable. This means that it will never stop you from entering a sector, can't have a special-type assigned to it like a D1 door, switch, teleporter. Scrolling walls should work. They are rendered just fine, but they do not show up in the blockmap. One 1-sided walls they will act as if you had the idclip cheat activated. On two sided walls you will be able to go from one sector to another without down-wards height checks in place. This can lead to a player or monster stepping down from ledges higher than 24 pixels instantly. Feel free to use this for vertical teleporter style movement, monster traps, etc.

EDIT: Clarified the ledge check is only skipped when heading to a lower level.

Tag 998 marks a linedef as never-render. This means it will not show up on the screen inside the game, it will however be collidable on the blockmap. The main use for this is to simplify the geometry and allow for very esoteric special effects like weird transparent floors.

A mapper that is near the limit of the vanilla blockmap size could create an outside area with a complicated architecture with loads of lines. All of those lines could be then tagged with 998, and a 999 tagged line could be placed in front of this to make sure that bullets collide, rockets stop, monsters don't travel outside of the map.

The geometry simplification switch turns on a very conservative variation of this where it overlays lines that are extensions of eachother with a longer linedef spanning the length of the two lines.

A mapper can also flag geometry that will never realistically be collided with with tag 999. Doom maps tend to have a lot of decorations on the ceiling, since they do not interfere with gameplay. Removing these lines from the blockmap can significantly lower the size of the blockmap.

I am working on writing a decent manual for ZokumBSP where all of this is explained, with examples of how to use it with GZDoomBuilder. This will include a much more thorough explanation of all the switches and options than the oneliners in the current help screen.

[Ribbiks]

zokum said:

Tag 999 marks a linedef as never-collidable. This means that it will never stop you from entering a sector, can't have a special-type assigned to it like a D1 door, switch, teleporter. Scrolling walls should work. They are rendered just fine, but they do not show up in the blockmap. One 1-sided walls they will act as if you had the idclip cheat activated. On two sided walls you will be able to go from one sector to another without the height checks in place. This can lead to a player or monster stepping up and down from ledges higher than 24 pixels instantly. Feel free to use this for vertical teleporter style movement, monster traps, etc.

oh dang, this sounds cool. Do you have any demo maps that demonstrate this? does it break horribly in non-vanilla ports?

[Graf Zahl]

It should be noted, though, that this may not work in all ports. With its special approach to generalization and eschewing the native data format it wouldn't surprise me if Doomsday choked on it.

The more 'traditional' ones, including ZDoom, which still use the blockmap as it was intended to, should be ok with it, but in general I'd be very careful with maps that abuse the special properties of machine-generated lumps like this, they can have side-effects that may be undesired.

One situation where it may produce inconsistent behavior is sight checks with the old 1.2 blockmap algorithm.

[printz]

Graf Zahl said:

One situation where it may produce inconsistent behavior is sight checks with the old 1.2 blockmap algorithm.

Damn, and Quasar modified Eternity to also use that algorithm (with code taken from ZDoom too). I wonder why shouldn't I just revert it to the Doom 1.9 algorithm (only for maps without linked portals).

[esselfortium]

printz said:

Damn, and Quasar modified Eternity to also use that algorithm (with code taken from ZDoom too). I wonder why shouldn't I just revert it to the Doom 1.9 algorithm (only for maps without linked portals).

From what I understand, the 1.2 algorithm is used because it's faster. It was taken out of later vanilla versions because of a bug that at the time couldn't be figured out, but that's since been fixed, so it's ultimately a better solution for performance.

[Graf Zahl]

The 1.2 algorithm is a lot faster, especially on larger maps because it works far more locally, the 1.9 BSP algorithm needs to walk the entire BSP and the larger that gets the slower it will be. On larger maps it can be a 5-6x speed difference (no kidding!)

For demo playback the 1.9 algorithm is needed anyway, so that part shouldn't be a major issue.

What can happen with bogus blockmaps is that monsters can see through them with the blockmap sight check but not with the BSP sight check.

[Linguica]

zokum said:

On two sided walls you will be able to go from one sector to another without the height checks in place. This can lead to a player or monster stepping up and down from ledges higher than 24 pixels instantly. Feel free to use this for vertical teleporter style movement, monster traps, etc.

Uh, have you actually done this? Because the code should explicitly disallow this:

if (!(thing->flags & MF_NOCLIP)) {
  if (!(thing->flags & MF_TELEPORT) && tmfloorz - thing->z > 24 * FRACUNIT)
    return false;  // too big a step up
  if (!(thing->flags & (MF_DROPOFF | MF_FLOAT)) &&
      tmfloorz - tmdropoffz > 24 * FRACUNIT)
    return false;  // don't stand over a dropoff
}

[zokum]

Linguica: I haven't tested much, but it seems to work on step-down, look at the youtube-video posted earlier, check out the revenant.