Extended blockmap format?

After some fucking around with the code, I managed to get Mocha Doom to play the infamous Europe.wad, a notoriously limit-stretching map. The problem was to handle some outright mapping errors (double-sided sidedefs with no back side...ouch), aaaand to handle what appears to be a nonstandard (at least by vanilla criteria) blockmap.

First I tried to extend the limits of the data structures from shorts (signed) to chars (the closest equivalent to an unsigned short in Java), that did fix some thing but not everything. Then I went over the blockmap specs once again in the wiki, and discovered that offsets can't express absolute 16-bit word offsets beyond 128 KBytes anyway, so I wondered how the hell can a 16-bit number be used to point to blockmap chains beyond the 128 KB limit (Europe.wad's is 220 K or so) ...

I took a wild guess and reasoned that this was some hackishly extended blockmap format, and that offsets that were too small to be pointing beyond the blockmap offset zones, should instead be interpreted differently...so I added 64K to each offset which was clearly smaller than the first blockmap chain, and hey presto, it worked like a charm.

Still, that "extended format" has pretty flimsy limits itself and depends a lot on what exactly is stored, the blockchain/offset ratio etc.

Is this properly documented anywhere? Is it a well known blockmap format (boom extended?) or just an artifact of trying to build a way too large blockmap with inadequate tools? Should I switch to an auto-generated blockmap instead and do away with those crappy limits?

Maes said:

Is this properly documented anywhere? Is it a well known blockmap format (boom extended?) or just an artifact of trying to build a way too large blockmap with inadequate tools? Should I switch to an auto-generated blockmap instead and do away with those crappy limits?

I took a look through prboom-plus p_setup.c and it doesn't support anything like that. What it does is a bunch of sanity checks on the blockmap, and if any of those fail, it's rebuilt from scratch. I'm pretty sure that's been the standard since Boom.


That would be a pretty crappy extended format anyway, and it would still be limited to no more than 128K of blocklists (the offset table just wouldn't count against it). I'm betting it's just the faulty result of a tool.

Got DoomLegacy to play Europe.wad last year.
The Europe.wad blockmap overruns its index numbers 3 times, so your solution is going to fail. That was the first thing I tried too, and it looked good for a while.

The DoomLegacy source has the notes but from what I remember, the Europe.wad blockmap index runs upto 0x00035000 or so, with only the lower 16 bits written.
Apparently the editor that wrote the wad never checked if the blockmap index was too large for the wad field.

The index written to the wad file is just the lower 16 bits.
I found that the blockmap index numbers appear in sequence, so I made
code to restore the missing high bits.
Made the reading index var 16 bit unsigned, and saved it to a 32 bit blockmap index.
Kept var of the missing high bits and last index, detected when the index rolled over to a low number so I could increment high bits with 0x10000.
I still have the patch files used to commit to DoomLegacy.

That was not the only problem, it also overruns the automap, which must be made to handle a larger map. Also will need to change the view reference point from being the corner of the display, to be the center of the display, otherwise the viewpoint wanders.

Even after all this, there is a problem at corner of the level by the dam with the boat. Jump into the chasm to get to the boat, then exit by the door near the dam. You are off the blockmap, so wall collision, shooting, etc. do not work.

natt said:

I'm pretty sure that's been the standard since Boom.

MBF, actually, although BOOM 2.02 may have also added its own independent blockmap extension code (I'm just not familiar enough with 2.02, I think I remember seeing something about it in there).

MBF would rebuild the blockmap however only if it was out-of-whack in terms of size - in particular, if it was 0 bytes or if it was larger than 64 KB. Wads like this one are exactly why Lee coded it that way - blockmaps larger than 64K will have wrapping indices.

Anyway, the extended verification code which is in prboom-plus actually comes from Eternity, and is code that I wrote. I verify the full offset table and walk all the blocklists for invalid linedef #'s or unterminated lists.

This extended verification became necessary after it was found that there are a rash of wad files uploaded to /idgames which have mysteriously corrupt blockmaps, containing a few 0xFE's where they ought to have 0xFF for block terminators. This will cause any port still using only MBF-style blockmap extension to try to access the lines[] array at index 65534, leading to an access violation.

Vanilla DOOM would have accessed lines[] at a very negative offset instead, and never seems to suffer any negative consequences from the access - even when the index is outrageous.

natt said:

What it does is a bunch of sanity checks on the blockmap, and if any of those fail, it's rebuilt from scratch.

Does it break demo compatibility? If so, how should I record demos for such "broken" maps?

Yes, it would break demo compatibility. If you want to record demos for such a map you will need a source port that fixes these issues both for recording and playback.

wesleyjohnson said:

Got DoomLegacy to play Europe.wad last year.
The Europe.wad blockmap overruns its index numbers 3 times, so your solution is going to fail. That was the first thing I tried too, and it looked good for a while.

Hmm. I did walk through the map a bit (mostly start area, big open area, tube station, and final city) and had no problems with collision detection (although there were some pickup problems in the big open area).

Don't forget that since I'm running in a managed environment, if a rogue/clipped blockmap offset takes me anywhere else than a valid blockchain, it crashes very soon with an overflow, so that hack worked fine at least for those areas. That's both Mochadoom's blessing and curse. But the map is pretty big, and I didn't really try it block-by-block, so it might very well break in some other area. What surprised me was that vanilla-format savegames still worked with that map (although they grew nearly 850KB in size).

From what everybody says however, it seems the sanest thing to do is rebuild the blockmap myself. Well, gonna borrow some Boom code for that, and internally I was already using a wider pointer table for blockmap links anyway (ints) ;-)

It's surprising that map even worked....and even more surprising that it's still classed as a doom2 (non-limit removing) map: first of all it won't play in vanilla due to an unknown object (Thing id 32000, 3D mode start point), and then come all the broken blockmap problems. That should be Boom-only.

Quasar said:

MBF would rebuild the blockmap however only if it was out-of-whack in terms of size - in particular, if it was 0 bytes or if it was larger than 64 KB. Wads like this one are exactly why Lee coded it that way - blockmaps larger than 64K will have wrapping indices.

Just a bit anal about semantics here -you mean "64K shorts" right? Or 128 good old KBytes. What wesleyjohnson said -assuming that indices that wrap around, perhaps multiple times, are always sequential is also too strong of an assumption to make, especially if the blockmap has been generated with compression on or manually tweaked.

Maes said:

Just a bit anal about semantics here -you mean "64K shorts" right? Or 128 good old KBytes. What wesleyjohnson said -assuming that indices that wrap around, perhaps multiple times, are always sequential is also too strong of an assumption to make, especially if the blockmap has been generated with compression on or manually tweaked.

Yes, correct. I should have stated it differently :P The byte count is /2 before comparison with 0x10000 in order to account for the fact the offsets are in short ints rather than bytes.

Maes said:

From what everybody says however, it seems the sanest thing to do is rebuild the blockmap myself.

What about special effects where the level designer intentionally removes a line from the BLOCKMAP?

Actually this is not as important as I thought, as I discovered when I tried to create a level as an example. I thought that this would be necessary to create an animated wall that the player can walk through, but clearing the "2-sided" flag is sufficient (you would still need to remove it from the BLOCKMAP to allow gunfire to pass through, however.)

finnw said:

What about special effects where the level designer intentionally removes a line from the BLOCKMAP?

There is absolutely nothing where this would do anything good. It'd create a glitch which would be perceived as a bug. AFAIK there has never been any type of blockmap editor and there probably never will due to lack of usefulness.

finnw said:

What about special effects where the level designer intentionally removes a line from the BLOCKMAP?

Those would pose no problems, actually. But trying to reference an -inexistent- sidedef of a two-sided linedef is quite a problem. In C/C++ ports (the majority), that's no problem: you'll simply read/write to random garbage, as ever, and if you get any ill effects at all they will be pretty delayed or asymptomatic, and unlikely to be easily traceable to the cause. I'm not sure how Delphi Doom would cope with a similar situation at runtime (but compile-time checks would be just almost as strict as in Java).

As I said, Mochadoom has both the curse and the blessing of having an almost zero tolerance for corrupt Doom data structures. On the one hand, this allows discovering bugs that would otherwise be near impossible to discover with a "conventional" source port unless you were painstakingly debugging opcode by opcode, on the other hand it forces me to introduce stricter sanity checks (e.g. I have to watch out for unused sectors, negative indices into sectors, inexistent sidedefs, negative thing ids, incomplete lumps etc. )

Maes said:

Those would pose no problems, actually. But trying to reference an -inexistent- sidedef of a two-sided linedef is quite a problem. In C/C++ ports (the majority), that's no problem: you'll simply read/write to random garbage, as ever, and if you get any ill effects at all they will be pretty delayed or asymptomatic, and unlikely to be easily traceable to the cause. I'm not sure how Delphi Doom would cope with a similar situation at runtime (but compile-time checks would be just almost as strict as in Java).

I can only speak for Eternity as compiled under Visual C++ 2008, but it always crashes immediately with an illegal access exception if it ever tries to access any invalid linedef or sidedef pointers or indices.

Part of the reason? Eternity uses the C/C++ heap wrapped weakly by the Zone-Native subsystem, which provides DSALs and additional error checking. This means that there are gaps in the heap and that the system is capable of detecting overflows and illegal accesses to areas that are not in blocks mapped to the process or as being writable memory.

This alone has improved the ability to find such problems ten-fold over using the old one-solid-block-of-RAM-do-whatever-you-wish-to-it zone heap.

Hey, that's pretty neat. So it's not just Mocha Doom's "curse" after all!

Actually....it shouldn't be a curse at all, because malformed/corrupt levels shouldn't exist. But since they do, all ports should be ready to handle the occasional mapping fuckup, corrupt blockmap, missing reject map etc.

So far, the weirdest hack I had to put together was load-time tolerance for malformed patch columns (!), encountered in a sky replacement I had made yeeeears ago with a primitive lump/graphics editing tool. I detect the broken columns at load-time, and replace them with a special "error column" :-p

Maes said:

Hey, that's pretty neat. So it's not just Mocha Doom's "curse" after all!

Actually....it shouldn't be a curse at all, because malformed/corrupt levels shouldn't exist. But since they do, all ports should be ready to handle the occasional mapping fuckup, corrupt blockmap, missing reject map etc.

So far, the weirdest hack I had to put together was load-time tolerance for malformed patch columns (!), encountered in a sky replacement I had made yeeeears ago with a primitive lump/graphics editing tool. I detect the broken columns at load-time, and replace them with a special "error column" :-p

Modern compilers are quite capable of producing C++ programs that are significantly hardened compared to the good ol' do-whatever output of the yesteryear compilers such as Borland, Watcom, and earlier Visual C++'s.

This is particularly true in debug mode. When compiled in debug mode, Eternity has stack checking, heap checking, and even some limited forms of array bounds checking enabled which can detect and report instantly on pretty much any type of funny business except just-plain-wrong pointer math.

This makes C++ development ALMOST as smooth a prospect as development in some of the managed languages, and has really narrowed the gap IMHO when it comes to these languages being able to claim they are much more secure.

The remainder comes down to discipline and skill on the part of the programmer and determination to create the most defined-behaving program possible.

Graf Zahl said:

There is absolutely nothing where this would do anything good. It'd create a glitch which would be perceived as a bug. AFAIK there has never been any type of blockmap editor and there probably never will due to lack of usefulness.

Here is an example of something you can do by removing a line from the BLOCKMAP that you cannot do just by editing line flags & sidedefs.

If you set the "2-sided" flag, the waterfall will not animate.

If you add linedef #36 to the BLOCKMAP, you will no longer be able to shoot through it.

I remember a tool floating around back in the late 90s that would do this, but I can no longer find it.

You could also do something surreal like e.g. allowing the player to get out of the map without noclip and wander into the void, perhaps making him seek some special hidden bonus :-p

Of course, such tricks will be destroyed by any sane blockmap-rebuilding tool.

However it seems strange that waterfalls would not animate if two-sided... I'm pretty sure I've seen two-sided, shoot-through and crossable animated textures before :-S

Maes said:

However it seems strange that waterfalls would not animate if two-sided... I'm pretty sure I've seen two-sided, shoot-through and crossable animated textures before :-S

It's a quirk of the rendering algorithm in Vanilla DOOM. There's no technical reason why it cannot animate (and I would not be surprised if most modern ports did animate it.)

It's also mentioned in the UDS (section [4-4]):

Also note that animated wall textures (see [8-4-1]) do NOT animate
if they are the "middle" texture on a 2-sided line. So much for the
lava waterfall with the hidden room at its base...hmm, maybe not...

Pretty sure BOOM removed that limitation.

I noticed that only some areas were failing when blockmap checking.
Go to the room with the imps behind bars, at opposite end of corridor from yellow keyed bars, near secret stairs up to closed cell. If stand outside and look at angle, can see clear through to cliff face.
Another place is at the far end of the long wide corridor, looking in the courtyard with the revenants on the parapet.

There is probably some level than can trick the sequential assumption code. To minimize that, it must be a transition from the one of the largest indexes to the smallest, to invoke the index increment by 0x10000. It would have to be a very large level itself.

wesleyjohnson said:

I noticed that only some areas were failing when blockmap checking.
Go to the room with the imps behind bars, at opposite end of corridor from yellow keyed bars, near secret stairs up to closed cell. If stand outside and look at angle, can see clear through to cliff face.
Another place is at the far end of the long wide corridor, looking in the courtyard with the revenants on the parapet.

There is probably some level than can trick the sequential assumption code. To minimize that, it must be a transition from the one of the largest indexes to the smallest, to invoke the index increment by 0x10000. It would have to be a very large level itself.

My question for you is, what does the blockmap have to do with rendering glitches?

If you are having rendering glitches, surely those are due to the BSP tree.

wesleyjohnson said:

There is probably some level than can trick the sequential assumption code.

Europe.wad one definitively can do it. The majority of blockchain references are to infamous block "65304" or somesuch, which is essentially the very first, empty blockchain after the offsets table. Due to blockmap compression, many blocks reference that one in an unpredictable fashion e.g. a "hole" in the blockmap buried between an ocean of non-empty blocks, so any sequentiality assumption algorithm would have to contain extra checks and "smarts" to detect a compressed blockmap and exclude references from sequentiality.

Maes said:

Europe.wad one definitively can do it. The majority of blockchain references are to infamous block "65304" or somesuch, which is essentially the very first, empty blockchain after the offsets table. Due to blockmap compression, many blocks reference that one in an unpredictable fashion e.g. a "hole" in the blockmap buried between an ocean of non-empty blocks, so any sequentiality assumption algorithm would have to contain extra checks and "smarts" to detect a compressed blockmap and exclude references from sequentiality.

I don't think that's possible, because if you see an offset of 65304 you do not know whether it refers to the original or to a later blockchain whose offset has been truncated (e.g. 130840.)

I'm curious about ZDoom now. I've had a quick look at its P_setup.cpp and I don't see how it could be parsing the BLOCKMAP from europe.wad. But if it does not parse it and builds its own instead, why does it suffer from the collision detection problems at the north end of the map?

finnw said:

I don't think that's possible, because if you see an offset of 65304 you do not know whether it refers to the original or to a later blockchain whose offset has been truncated (e.g. 130840.)

Exactly. Your scanning algorithm would have to be super-intelligent and perform some statistical analysis on the blockmap and cross-check with the actual lines. E.g. a simple stat analysis reveals that this particular blockchain is referenced A LOT, and an actual check would reveal that there are indeed no lines wherever this block applies. Then again, if you are to implement such heuristics (which again, won't be 100% fool-proof), you're better off going the extra mile and rebuilding the blockmap, rather than trying to "decompress" it.

Edit: then again, the threshold of what is "super intelligent" seems to be guestimated quite erroneously sometimes. E.g. I recall some oldschool emulator discussion boards in 1996 discussing about how a direct decompiling-recompiling emulator would have to be "super intelligent" in order to recognize loops etc., just a few years before Java brought JIT to the masses (and there were already emulator cores with dynamic recompilation for projects like RAINE). Similarly, reconstructing infighting from stock, old vanilla savegames proved to be a no-brainer... but yeah, in the case of the blockmap, the "no brainer" is to simply rebuild it while having the good sense of NOT using a broken, limited 16-bit format for offsets :-p

During the debugging on Europe.wad, I had put in printf statements to make sure of my assumptions. I only got the three prints when it wrapped back to a low blockmap id number, so Europe.wad must be totally sequential in its blockmap id numbers.

Most maps are not large enough to invoke this code, as it requires a large blockmap id that would have already caused the previous code to fail. This is an incremental improvement on the previous failing code.

I have not yet encountered a map that causes this to fail, but as I stated, there probably will be some overly large map that confuses the code because of the sequential assumption. It cannot be Europe.wad because I checked that it was sequential, but from your discussions about compressed block maps, I suppose a really large level with a compressed block map could fail (but please notice it would have already failed with the original blockmap reading code).

A simple test would be to verify that the only negative blockmap id transitions are the ones where the block map wraps (from largest to lowest blockmap id). If not true (not sequential), and blockmap overrun detected (by seeing largest blockmap ids), then declare an Error (or invoke a blockmap rebuild).

Making a blockmap is something that I have preferred to leave to zennode, which does it well. Either I create a second-rate version, or copy their work, neither which appeal to me.

The rendering problems disappeared when the blockmap reading was fixed from what I remember. I am going from memory from a year ago. But what I suggest is that you could test your simple fix by looking at those locations for the visible flaws, to see if you get them too.
I assume that the bsp traversal uses the blockmap somewhere.

wesleyjohnson said:

During the debugging on Europe.wad, I had put in printf statements to make sure of my assumptions. I only got the three prints when it wrapped back to a low blockmap id number, so Europe.wad must be totally sequential in its blockmap id numbers.

I briefly looked at it in a hex editor and came to the same conclusion (there are monotonically increasing offsets mostly incrementing by 2, implying that there are many empty non-shared blockchains.)

Most maps are not large enough to invoke this code, as it requires a large blockmap id that would have already caused the previous code to fail. This is an incremental improvement on the previous failing code.

I suggest you try it on some smaller maps, with the same test enabled unconditionally. ZDBSP definitely shares blockchains between blocks with identical sets of lines. I haven't looked at its code but I once implemented my own BLOCKMAP generator that worked this way, and found that its output matched that of ZDBSP, byte-for-byte. The map loaded fine in ZDoom (of course) and Chocolate Doom. I did not try any other ports though.

A simple test would be to verify that the only negative blockmap id transitions are the ones where the block map wraps (from largest to lowest blockmap id). If not true (not sequential), and blockmap overrun detected (by seeing largest blockmap ids), then declare an Error (or invoke a blockmap rebuild).

As I said I suspect this will fail for a lot of recent maps (whose BLOCKMAP is likely to have been built with ZDBSP.)

A more reliable (i.e. ZDBSP-compatible) test might be whether the block offset is no lower than 32767 words below the highest offset seen previously (regardless of the overall size.) If any block fails this test then it is almost certainly due to wrapping.

Of course the test would also fail if ZDBSP-style blockchain sharing was used and the BLOCKMAP was still large enough for offsets to wrap around, but such a BLOCKMAP would not be salvageable anyway. I don't think you would need a special check for this combination though - just apply the normal sanity checks after compensating for wrapping.

I loaded europe into prboom-plus and gzdoom, and in both cases I observed what appeared to be massive blockmap glitching in the area around (3000, 15000). (North end, big pit with the boat in it, try taking the stairs back up). Either there's some shared engine bug (possible, but not terribly likely; the two ports are much different codebases), or there's something wrong with the map even after you correctify it.

That test sounds exactly like mine, just different words.
It is an incremental fix just for one busted wad (the wad does violate the blockmap format descriptions), the next wad that overruns the blockmap may force another solution.

Something that can pick the correct (or most likely) blockmap index from several candidates comes to mind. It cannot be an index that does not exist, nor larger than the number of blockmap indexes seen.
There may be some locality that can be used, like a test for the closest neighbor. It would be interesting to know just how far away (by some test) another index could be in a compressed blockmap. Is all compression the reuse of local similar blockmap entries.

That area with the boat, the stairs back up are still off the blockmap, even after fixing the id wrap. From what I remember, the (x,y) is simply too large to be on the blockmap, there was no fix possible (short of doubling some field sizes).

wesleyjohnson said:

That test sounds exactly like mine, just different words.
It is an incremental fix just for one busted wad (the wad does violate the blockmap format descriptions), the next wad that overruns the blockmap may force another solution.

Something that can pick the correct (or most likely) blockmap index from several candidates comes to mind. It cannot be an index that does not exist, nor larger than the number of blockmap indexes seen.
There may be some locality that can be used, like a test for the closest neighbor. It would be interesting to know just how far away (by some test) another index could be in a compressed blockmap. Is all compression the reuse of local similar blockmap entries.

That area with the boat, the stairs back up are still off the blockmap, even after fixing the id wrap. From what I remember, the (x,y) is simply too large to be on the blockmap, there was no fix possible (short of doubling some field sizes).

The extents of the map are as follows:

X: -11200..15968 (27168)
Y: -18592..19168 (37760)

The broken area of the map exactly corresponds with limiting the blockmap to 32768 units in the Y direction, but keeping the same origin. ie, Y: -18592..14176 is ok; Y: 14176..19168 is broken. But where does such a limit come from?

Prboom-plus does not use the internal blockmap in this case; it builds its own. All of the indices in that internal blockmap are 32 bit.

Also, the generated blockmap appears to be correct: Spot check:

by = 260, bx = 109, list:

0
9932
9929
9927
9926
9923
-1

Note that this block is in the "broken" area. So I'm pretty sure the calculation failure is somewhere else, and the blockmap is in fact fine (when generated on the fly by prboom).

Now I feel like an idiot. I can't help but thinking I'm the only one who didn't know about this limit because it's so obvious once you see it... but I don't think I've ever seen it mentioned before?

The code to convert x, y to blockmap index looks something like this and is repeated many times:

fixed_t x; // coordinates you want blockmap index for
fixed_t y;

fixed_t bmaporgx; // (fixed point) blockmap origin, initiated at level load time
fixed_t bmaporgy;

#define MAPBLOCKSHIFT (FRACBITS+7) // p_maputl.h

int bx; // blockmap indices you're going to make, hopefully between 0 and bmapwidth/bmapheight
int by;

bx = (x - bmaporgx) >> MAPBLOCKSHIFT;
by = (y - bmaporgy) >> MAPBLOCKSHIFT;

The problem is, (x - bmaporgx) is a fixed point, so its limited to -32768..32767, so you can't go more than that far from the blockmap origin without causing problems.

When you fix it like this:

bx = (unsigned) (x - bmaporgx) >> MAPBLOCKSHIFT;
by = (unsigned) (y - bmaporgy) >> MAPBLOCKSHIFT;

You break checking on the "wrong side" of the blockmap origin, which fails anyway (if bx < 0 or by < 0, you abort because there's no blocklist there), and you fix checking on the "right side" of the blockmap origin up to 65535 units away in either direction. Tested in prboom-plus, fixes all problems at the north end of europe.wad.

God knows what compatibility problems it causes...

patch against prboom-plus svn 4004
http://pastebin.com/TWPHChUv

edit: btw, this patch causes some other problems, but that's not really an issue, because I just made it to demonstrate the limit; I don't think it's worthwhile trying to fix this.

natt said:

edit: btw, this patch causes some other problems, but that's not really an issue, because I just made it to demonstrate the limit; I don't think it's worthwhile trying to fix this.

Not when just building a correct unlimited map from scratch at runtime is both less error prone and also has the same amount of "compatibility".