Filled with the code of Doom
Yeah, this is strictly a "can it be done in Vanilla" thing. If source ports have to rebuild, they can rebuild.
I'm pretty sure this isn't a problem. Remember that the blockmap is only a very coarse list of "lines you should check" when checking for collisions and interactions, not a list of "lines that were crossed". The engine already does the line checks itself: the blockmap is just there to make the process more efficient.
This one is actually brilliant, but there's no easy way of telling if it will be side-effect free (e.g. tracers will cross more lines than usual, thus inflating the lists of crossed linedefs) and maybe triggering unwanted effects (if there are no further checks of whether a line really belongs in that block).
It completely depends on the structure of the level, but quite a lot of levels are built around regular layouts, even if they aren't entirely grid-based. If you limit yourself to 16-pixel offsets from the normal (0,0)-aligned grid, that's 64 different offsets. It's probably not too CPU-intensive to check each of them and find out how many block boundary crossings there are in each case. No matter the level, some must be "better" choices than others.
Minimizing block extension/grid dimensions through origin centering should be something that every decent blockmap tool should be able to do.
But in general the problem with maps that exhaust their blockmap space is that they are too "densely" built, almost every used block has several lines crossing it, and simple tricks like saving a block here and there usually are not enough.
I'm not entirely convinced it's workable either. Moving floors/ceilings are the big problem here. With sufficiently clever logic it might be able to work out which lines are safe, but it depends if it's worth it. I'd need to figure out some statistics about the number of candidates in typical levels to find out.
Maybe, but again, it would be too complex to write an algorithm able to make this (and other) call(s) correctly all of the time. Maybe a visual editor and hand-optimization by an expert...
I really want to avoid any kind of manual interaction if at all possible, because I'm sure mappers probably don't want to know about this stuff at all if they can avoid it.
That would work, by forcing the engine to check every line. If implemented, such an "universal collision block" or UCB should be used sparingly, if at all. It could be used e.g. for blocks at the outer limits of the map, decorative features etc. where a player or monster is unlikely to enter or shoot. But again, that's a judgment call that's better done by an expert mapper, rather than an algorithm, and once again, a visual editor that lets a mapper directly edit the blockmap or at least leave "hints" for the blockmap builder would be required (e.g. "This is an outer wall far from the playing area only designed to look pretty, thus don't waste a good block for it, and map it to the UCB instead"). An extreme version of that, would be for the blockmap NOT to include some parts of the map, provided this does not create other problems like no-clipping in areas where players may wander.
I think the "huge trailing blocklist" idea ought to be a final, last resort if every other technique fails. Probably the best thing to do in that situation is to restructure the level or give up on Vanilla compatibility entirely (and the theoretical blockmap builder I haven't written yet ought to say as much). But in terms of generating a valid blockmap, I would think that the best course of action would be to combine all the largest blocklists - they're already going to be slow anyway.
I checked the source, and it looks like you are correct.
As for Zennode, I'm certain it does at least simple 100% identical blocks compression.
Maybe this is a laughably naive question to be asking, but 256x256 blocks is a 32768x32768 sized map. Do any such maps even exist?
the one singlest inefficiency of the blockmap is this: no matter how carefully you craft the blockchains themselves (which can be "sparse", in a sense), the POINTERS to them are always a dense structure. For a 256x256 blockmap, they alone would use up ALL of the available 128 KB space, leaving NONE for the blockchains themselves (!). No way to "skip" some either: it's always a dense grid of pointers.
It's an amusing idea, and theoretically you might be able to do this (put everything in a single block list that overlaps with the blockchain) but I think at this point we've crossed into the realm of complete insanity :)
A REALLY extreme solution would be to stuff some blockchains INSIDE the space reserved for blockchain pointers. The reasoning is this: in large maps, the blockchain pointer array itself will be large, but most pointers will be wasted for blocks that are IN THE VOID. Unless a player idclips, he will never visit those regions of the map...so, why not place actual blockchain data in them? After all, pointers are defined from the beginning of the blockchain lump (which is another big weakness of the format...) ;-)
Of course, for this to work, you need a blockmap which leaves enough contiguous blockmap cells free (each cell gives you two bytes...so for e.g. a 32x32 or 4x256 region in the void you would get 2 KB), and a builder which is super-smart when building it, keeping track of void blocks and using "pointer space" whenever possible.
Edit: saw the "64 KB" update now. That just makes finding a solution even more pressing....so what do you think about pointer-space reuse?