Vertex based nodebuilder released, ZokumBSP 1.1

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:
 

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.

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.

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.

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.

 

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

E4M2 for good measure.

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.

7 hours ago, zokum said:

Nice screenshots. What tool are you using?

It's the node viewer from the DB2 family.

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.