Introducing ZokumBSP

[Graf Zahl]

Step down is different because that's being tested as dropoff which requires a line. Stepping up does an absolute test of z before and z after which will trigger even with a bogus blockmap.

[Danfun64]

fabian said:

I have just finished porting DoomBSP's BLOCKMAP builder to C for it to become Crispy Doom's internal BLOCKMAP builder.

Umm..... I'm not sure the release of DoomBSP's source is GPL (compatible)...is it?

[zokum]

Ah ok, that explains the odd behaviour. OH well sorry aobut that, will edit my previous posts then.

[printz]

Graf Zahl said:

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.

Guess I'll tell people to use -vanilla then, if they play maps relying on that blockmap trick to work correctly.

[Danfun64]

The problem with -vanilla is that it (apparently?) only works when you're demo recording...unlike how prboom-plus allows you to set complevels without recording demos.

[Edward850]

Danfun64 said:

The problem with -vanilla is that it (apparently?) only works when you're demo recording.

Nonsense.

[dew]

Danfun64 said:

The problem with -vanilla is that it (apparently?) only works when you're demo recording...unlike how prboom-plus allows you to set complevels without recording demos.

My video on page 1 quite clearly proves this is not true.

[printz]

I think the problem with -vanilla is that it doesn't persist if you start a new game or cheat to another level.

[Danfun64]

Yeah, that's the issue.

[fabian]

Graf Zahl said:

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?

Yes, this is true. And, no, it is not the blockmap builder that is know to have some bugs, but the node builder. And the bug in question is that it produces slimetrails.

bzzrak said:

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

Indeed, it is. Please note that this is probably the most naive blockmap algorithm imaginable. It iterates through all blocks and for each block it iterates through all lines, so its runtime scales with (number of blocks) x (number of lines). The code from BMF, on the other hand, iterates through all lines only once and adds each line to the two blocks that its start and end vertex lie in as well as all the other blocks in between.

I have done some tests with planisf2.wad, which is one of the most extreme map that I know of, and the results differ from "under 1 second" for the MBF code to "several seconds" for the DoomBSP one. On the system that I am currently working on the factor between the startup times was between 40 and 70, which results in 30-40 seconds for the DoomBSP blockmap builder. Yes, that's a shame, but it is only once at map start-up.

zokum said:

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.

I have done my tests using 30uvmax4.lmp, which should be about the same but without -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.

The same applies to e.g. plutonia.wad, which features different blockmaps than the ones DoomBSP produced. Not to talk about the DOOM 3 BFG Edition IWADs maps 02, 31 and 32 (although doom2.wad map02 keeps in sync with demos recorded with the original doom2.wad if rebuilt with the DoomBSP code).

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.

Yep, the bug that's referred to in the README has been identified as the phenomenon that we call slimetrails nowadays.

Danfun64 said:

Umm..... I'm not sure the release of DoomBSP's source is GPL (compatible)...is it?

Oops, good question. I am not really sure either, because there is no proper license applied to it. I somehow took it as granted, as it is released source code and the rest of the source code released by id has been licensed under the GPL. I am afreiad I will have to contact some id people to get clarification...

[Graf Zahl]

fabian said:

Indeed, it is. Please note that this is probably the most naive blockmap algorithm imaginable. It iterates through all blocks and for each block it iterates through all lines, so its runtime scales with (number of blocks) x (number of lines). The code from BMF, on the other hand, iterates through all lines only once and adds each line to the two blocks that its start and end vertex lie in as well as all the other blocks in between.

Now that finally explains why they considered it necessary to pregenerate the blockmap instead of always doing it at run time. It always seemed like such a total waste of valuable disk space to me.

[Linguica]

fabian said:

Yep, the bug that's referred to in the README has been identified as the phenomenon that we call slimetrails nowadays.

Not quite, remember? https://www.doomworld.com/vb/source-ports/71272-what-bug-is-carmack-describing-here/

[zokum]

Pregenerating the blockmap may be fairly low-cost with today's cpus. On the target audience of 386 and 486, it might have been a fair bit slower. For the original Doom maps, I doubt that this map entry wasted much disk space compared to the decreased loading times. A 100 sector reject map should lead to about 1.25kb of data + some header overhead. A very small price to pay for decreased load times and reduced executable size and complexity.

[Graf Zahl]

zokum said:

Pregenerating the blockmap may be fairly low-cost with today's cpus. On the target audience of 386 and 486, it might have been a fair bit slower. For the original Doom maps, I doubt that this map entry wasted much disk space compared to the decreased loading times. A 100 sector reject map should lead to about 1.25kb of data + some header overhead. A very small price to pay for decreased load times and reduced executable size and complexity.

The blockmap for E1M1 is 7 kb and the one for E2M7 is 10kb. So with 27 maps it's probably around 250kb. And computers back then weren't THAT slow. HD's were, though.
Recreating a blockmap for those maps today takes a few milliseconds, even if you multply that with 100 it was still mostly irrelevant (provided you used an efficient algorithm, which id did not.)

They could have saved more time by using hashing for searching the WAD directory. THAT really cost time.

[zokum]

For 1.0.10 I have planned finishing the first version of the manual, a minor bug fix, some new features and some quality of life improvements.

The manual has currently the following sections planned, and is at about 10.5k of data in 99.9% ascii so far. The only non-ascii character is probably the ø in my name.

1. Project goals - First draft done.
2. Basic usage - First draft done.
3. Doom V1.9 limits / algorithms - First draft done.
4. Special effects - Lists a few special effects, not all.
5. Geometry pass - Basic explanation of this added pass.
6. Blockmap builder - Incomplete
7. Nodes builder - Not written
8. Reject builder - Only rudimentary information
9. Other options - Not written
10. Compatibility - Not written
11. Usage together with other tools - Not written
12. Other resources - A few basic resources mentioned
13. Changelog - Simply refers to changelog.txt
14. Acknowledgements - Incomplete list, probably forgot some people.
15. Other node builders. - Very incomplete, should probably refer to wiki.

Hopefully this should cover most of the questions people ask me, and make it easier for others to use this tool as it can be a bit overwhelming currently. The manual for ZenNode isn't very good, so hopefully this can make it easier for mappers to build good maps and use the tool correctly.

If 1.0.10 is stable and the manual is complete, I might upload that version to the usual FTP location for general usage and wider distribution. The packaging and other things will need to be worked on a bit in order for this to be feasible.

[fabian]

fabian said:

Oops, good question. I am not really sure either, because there is no proper license applied to it. I somehow took it as granted, as it is released source code and the rest of the source code released by id has been licensed under the GPL. I am afreiad I will have to contact some id people to get clarification...

I have tried to contact both Jay Wilbur and John Carmack for clarification of this issue, both at their @idsoftware e-mail addresses which of course bounced. So, what now?

[Rachael]

fabian said:

I have tried to contact both Jay Wilbur and John Carmack for clarification of this issue, both at their @idsoftware e-mail addresses which of course bounced. So, what now?

It looks like you can contact Carmack via Facebook. I'd try that.

[fabian]

Rachael said:

It looks like you can contact Carmack via Facebook. I'd try that.

Thanks, but unfortunately (?) I am one of the few people without a Facebook account. Any other ideas?

[Jon]

Especially in light of the recent lawsuit involving Zenimax and Carmack, I doubt he'd be prepared to make any new pronouncement on the status of any ID IP. I'd instead try to contact a current ID employee and, regardless of what terms it was already released under, get them to bless it out as GPL now. It might be easiest to prepare a DoomBSP-as-GPL-archive in private, and basically see if you can get someone to rubber-stamp it.

[Rachael]

Normally I would offer to contact him on Facebook for you - but it seems Jon may be right. In which case - it's probably better to find whoever is the highest ranked of the organization that you can get in touch with.

[Quasar]

Nobody at id can or will make any statements about such things any more either, because ZeniMax owns all their stuff now. And ZeniMax doesn't accept public solicitations for licensing.

[Jon]

The window has probably closed then :(