BLOCKMAP builders

[smite-meister]

This is a somewhat technical subject, so bear with me.
As you may know, the BLOCKMAP data structure which Doom engine uses for collision detection is often the first limiting factor you hit when making a really large map. The data structure has design limitations which make it impossible to create a valid BLOCKMAP for a sufficiently large map.

The usual way around this is to include a modified blockmap builder to the level loading code in a source port. If the BLOCKMAP lump is missing or corrupted, the builder kicks in and saves the day.

So far Legacy has been without one, but I'm about to add one now. Since there is no reason to re-invent the wheel, I'd like to know if there are good existing GPL builder codes we could use. From the ZDoom source I gather that the builder Lee Killough wrote for MBF does not always produce a correct result, so I guess that one is out. What about others, such as the one from ZenNode?

[DaniJ]

You could have a look at the one used in the 1.9.x series of Doomsday which is based on the method used in PrBoom by Lee K.

I've actually started rewriting the algorithm using vector math but haven't gotten around to finishing it yet. After that I'll be considering whether to increase the precision as it will be fairly trivial.

Another place you could look is the Risen3D source which looks like it was based on the PrBoom method but it has been enhanced for greater precision.

[Exl]

I'd suggest a test of blockmap builder's accuracy. Put Zennode, BSP, Warm and whatnot up for comparison.

[Ajapted]

EDGE has blockmap generator code. It is not optimised like the PrBoom code is, hence it is easier to understand and therefore easier integrate with your code. It is GPL, and uses floating point.

[smite-meister]

Well, now Legacy 2 has a BLOCKMAP builder. *bday*
I decided to write my own, using the same algorithm as the one in P_PathTraverse. No packing yet, but it's pretty compact and uses floating-point arithmetic.
Tested it on Deus Vult map05, seems to work.
Thanks for the advice, looking at other people's solutions certainly helped.

[Ajapted]

Congrats.

No packing yet
Why bother packing? The reasons node builders pack the blockmap (1. save disk space, 2. help prevent BLOCKMAP overflow) do not apply for an in-game blockmap.

[xbolt]

Another programming hurdle behind us. We're getting there. ;)

[smite-meister]

Why bother packing? The reasons node builders pack the blockmap (1. save disk space, 2. help prevent BLOCKMAP overflow) do not apply for an in-game blockmap.
3. Limit runtime memory usage, which only really applies to mobile devices nowadays. Since I don't think anybody is about to port Legacy to one anytime soon, you're absolutely correct. :)

Exl's idea of comparing generated blockmaps could be interesting. Technically they should be identical, assuming that the origin is set at the lower left corner of the map root bounding box...

[Ajapted]

Exl's idea of comparing generated blockmaps could be interesting. Technically they should be identical, assuming that the origin is set at the lower left corner of the map root bounding box...
It never hurts to have a linedef in a box that doesn't actually touch it (apart from performance, of course). Hence on border-line cases, like a linedef going straight through a corner or sitting directly along the edge of a block, there may be some differences.

[Pate]

What about tossing blockmap altogether and using BSP for collision detection? Doesn't ZDoom do that already?

BTW where in Tasmania are you ajapted? I'm in Melbourne for a few months still...

[Ajapted]

What about tossing blockmap altogether and using BSP for collision detection? Doesn't ZDoom do that already?
If it ain't broke ;)

The blockmap is quite an elegant method for object-object collision detection, it can be done with BSP of course but it's a large chunk of new code to write and debug...

BTW where in Tasmania are you ajapted? I'm in Melbourne for a few months still...
Just over the Bass Strait in Launceston.

[Graf_Zahl]

What about tossing blockmap altogether and using BSP for collision detection? Doesn't ZDoom do that already?


No, it doesn't. ZDoom, like most other ports uses the blockmap for this.


If it ain't broke ;)


Precisely! Sadly enough Doom's collision detection is as broken as it gets and could desperately need a complete rewrite...


The blockmap is quite an elegant method for object-object collision detection, it can be done with BSP of course but it's a large chunk of new code to write and debug...


I wouldn't do it as the blockmap is significantly more efficient. ZDoom uses Hexen's sight checking code which also uses the blockmap and tests have shown that this code is considerably faster than Doom's BSP based algorithm.