Jump to content
Search In
  • More options...
Find results that contain...
Find results in...

Vertex based nodebuilder released, ZokumBSP 1.1

Recommended Posts

It's 24.12.2018 and as promised, here is the new ZokumBSP release, with a vertex based nodebuilder algorithm.

This algorithm uses a new way to build nodes. Instead of extending existing partition lines to create partition lines, partition lines will be computed from pairs of vertices. This increases the amount of possible partition lines enormously. Without going into the math, any other partition lines other than a vertex par is inferior as it offers no other benefit other than an additional split.

As far as I can tell, no other mainstream, if any, nodebuilder has ever tried to use this approach. With some refinements, it should produce superiour BSP trees to all existing nodebuilders in the general case. Nodebuilders that do not produce BSP trees may still be superior in some cases.

What are the benefits?

This can produce maps without any split segs at all, or with a very low split count. Here's some data about maps that will be built with very few splits:


Here is a list of maps that can be built without ANY splits:

doom.wad: e2m8, e3m1, e4m2 and e4m4.
doom2.wad: map30 and map31

1-2 splits:


doom.wad: e1m9, e3m5, e3m8, e3m9 and e4m8.
doom2.wad: map04, map07, map22, map25, map28 and map32.

The current version of the algorithm, an early test version, uses a more modular design when finding partition lines. Using various methods to pick a line until it finds an acceptable one, starting with the most stringent line algorithms first. This should make it easier to write good algorithms as code can be shared more easily and special cases handled much or easily.

A split is when a wall is divided into two halves due to the way Doom maps are processed in order to render them quickly. It is at these splits that various problems like slime trails and straight walls no longer being straight due to rounding errors occur. Wall segments (SEGS) can only end and start on vertices with whole number coordinates. This causes problems when a diagonal line is split, or when a partition line is diagonal.

What are the downsides?


In general, fewer splits mean more subsectors. This apprach will often generate a lot more sub sectors, and could in some cases produce visplane overflows on maps that previously had no such problems.

The build time is higher when using this algorithm, but not as high as the multi algorithm. With time and research, this should get better. As of now, I would only recommend using this approach on the final build of a map. On my system doom.wad and doom2.wad took about 96 minutes to build, instead of the usual 3-4 seconds.

The algorithm is sometimes a bit weak on big maps or certain types of complex architecture. In these cases it isn't unusual for it to produce a worse result than the old HQ balanced algorithm. I know why it happens, coding a fix that prevents this from happening on the other hand is a lot more complex.

Not only has this new approach let me build maps in a really interesting way, but it has also given me some insights into how I can improve the other algorithms. I believe I have found one missing factor that isn't accounted for in the older algorithms. That factor may explain why the wide algorithm works as well as it does.

Project web page: http://doom2.net/zokum/zokumbsp/

Documentation: http://doom2.net/zokum/zokumbsp/documentation

Direct Win 64 download link: http://www.doom2.net/zokum/zokumbsp/releases/zokumbsp-1.1-win64-mingw.zip


I will try to answer any questions people might have, but with the holidays being in full swing, don't expect a quick reply.

Share this post

Link to post

Episode 1 and 2 of The Ultimate Doom. Some interesting numbers apart from the splitless ones are e1m1, e1m5, e1m9 and e2m3. Any map with splits is not guaranteed to be the lowest amount of splits, merely that splits HAVE to be made on that map in order to build a BSP tree. The true lower bound is somewhere from 1 up to the number of current splits. I will post some numbers from Doom 2 soon. It is possible to tweak some numbers to get better numbers for some maps, but not others. I most likely do not have the ideal numbers or formulas yet.


Share this post

Link to post

I would love to try this but I can't find any examples of how to actually write the proper commands on the command line.

Share this post

Link to post


8 minutes ago, Linguica said:

I would love to try this but I can't find any examples of how to actually write the proper commands on the command line.

./zokumbsp -b- -r- -na=v wadfile.wad

The 'b and 'r' are just to skip making blockmap and reject entries. The conventional algorithm is selected with a=d. I know the help output when you invoke zokumbsp has gotten a tad unwieldy with all of the things I have added. It's probably still listed as N/A, but that is due to lack of testing. I don't consider it production ready until there's been more testing done.

I am currently running builds of Alien Vendetta and Scythe 2.


Edited by zokum

Share this post

Link to post

Nice screenshots. What tool are you using? I would love to see some of the non-split maps, like e3m1.

Share this post

Link to post

E4M2 for good measure.


Screen Shot 2018-12-24 at 7.00.05 AM.crushed.pngScreen Shot 2018-12-24 at 6.59.31 AM.crushed.png


I want to point out that the "real" E4M2 and the zokumified one ended up with precisely the same number of subsectors, and ZokumBSP managed to make the map *completely seg split free*. With some work to make it more balanced it would be a win in every aspect.

Share this post

Link to post
7 hours ago, zokum said:

Nice screenshots. What tool are you using?


It's the node viewer from the DB2 family.

Share this post

Link to post

Cheers. I have had some fun with this tool. I had to use gzdbbfdhaxxupdate instead of my usual editor, dbx.

I have learnt a few more things during the christmas, having researched and looked into BSP technology. I will try to incorperate some of that into some of the code I am working on. Using this tool, it is a lot easier to debug the nodes generated.

Share this post

Link to post

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now