Blockmap optimizations

[zokum-no]

The blockmaps in all of id's maps aren't compressed. Rebuilding them to be compressed could make the game more cache friendly. You could also rebuild them to perhaps be without the 0000 header in each block and have that checked by the algorithm as part of the code rather than having to traverse the blockmap for this entry every time.

The 0000 checks are mostly not needed if I'm not mistaken, but at slow player speed does affect gameplay due to bad collission code. Maybe you could enable the 0000 check only when the player/projectile/monster is moving slowly?

[viti95]

I've checked that compressing the IWADs with Zennode or ZokumBSP makes them faster. As you said, having smaller lumps makes them more cache friendly, as the cache in 386/486 systems is very limited. Maybe having also smaller number of nodes, segments, etc reduces the number of iterations the game engine has to do. I'm still learning how the blockmap thing works, what do those 0000 headers exactly?

[zokum-no]

DoomBSP (id's tool) inserts a 0000 header for each blockmap list as well as the end of list FFFF marker. The engine however doesn't need/understand these 0000 headers and interpret them as line 0. So for every collission detection check in the game, linedef 0 is checked.

For performance it is adviced to keep linedef 0 short, on the outskirt of the play area and non-diagonal etc.

Due to errors in the collission detection code, demo compability relies on these line 0 checks to get playback correct on many demos.

However, if your code just checked this 0 anyway without needing the lookup, you could remove those 0000 entries from the blockmap data in memory and still obtain 100% demo compatibility. Removing the 0000 headers usually shrinks a blockmap by 5-15%. For the uncompressed id blockmaps, the saved amount should be much higher.

Edit_ Changed end marker from 0000 to FFFF. Took a showerearleir today and realized my error. Been bugging me for a while :D

[zokum-no]

And please don't implement the boom port fix. They simply ignored the first linedef, the 0000 header. Forcing all maps to include the 0000 header for compatibility. Since almost all ports are derived from Boom some still have the bug, some have backported in a a reversion of this hack. This "fix" also broke demo compatibility. The correct fix would be to fix the tools, not implement a port hack.