Mommy, can you check if there's a visplane under my bed? Thoughts & research on visplane overflows and preventing them.

[anotak]

--------------------------------------------------------------------------------

"// Here comes the obnoxious 'visplane'."
- original Linuxdoom source release from id software

--------------------------------------------------------------------------------

Let's talk about the dreaded visplane, bane of vanilla mappers everywhere.
This post assumes you understand the basics of doom mapping (linedefs, sectors, etc).

 

We're going to examine elements of:
1) What they are
2) How they are created
3) How some visplanes merge
4) Why some that seem like they could merge, don't
5) Potential workarounds during mapping & nodebuilding.

 

First off, we need to make a few clarifications about terminology:
There are two types of coordinates at work in Doom (and most other games tbh):
World-space coordinates are where stuff is in the world, X representing east-west, and Y representing north-south. Most stuff in Doom has a Z coordinate that also represents up-down, though this gets a bit complicated and is outside the scope of this particular post.
Screen-space coordinates are, well, on the screen. X is left/right, Y is up/down. The top left corner is 0,0, and these increase as you go down and right. I know this is backwards from your middle school math class, but it's just how computers work.
This matters because for example:
Imagine 2 floor sectors with the same world-space height. The world-space farther one will be screen-space above the closer one. Farther objects will be closer to the horizon. So world-space farther ceilings with the same world-space height will be screen-space below the world-space closer ones.

Here we see floors with the same height in worldspace, but the worldspace farther ones are screenspace above the worldspace closer ones.

 

Rows are single continuous (as in, no gaps) screen-pixel wide horizontal line segments.
Columns are single continuous screen-pixel wide vertical line segments.
Subsectors are convex pieces that make up sectors. Convex geometry is a lot easier to deal with for the engine. We'll go into some (but not all) the reasons why in a bit.
The edges of subsectors are often called "segs", we're going to call them "World Segs" to avoid confusion because there are other things in The Doom engine called segs. World segs are derived from linedefs, but sometimes the node builder splits your linedefs in half to make the subsectors.
Drawsegs are the actual edges onscreen.
A Visplane Overflow is when the vanilla/choco engine runs out of space for new visplanes (limited to 128 originally). This results in a crash.

 

--------------------------------------------------------------------------------

"// Now what is a visplane, anyway?"
- original Linuxdoom source release from id software

--------------------------------------------------------------------------------

A visplane is a "visible plane", a region of the screen where a floor/ceiling flat is being drawn to. It's a data structure that tells the renderer where to put the flat's texture pixels on the screen.

 

Each visplane has 7 variables, first the 5 simple ones:
    floor/ceiling height
    flat texture
    light level
    minimum x in screen space
    maximum x in screen space

 

Surfaces with the same height, flat texture, and light level, can be drawn using the same calculations for what to do the texture, no matter where they are on the screen, so it makes it easier/faster to group together pixels in this manner.

 

The visplane is broken up into columns. So the last two variables are a pair of lists, one for the top of each column, and a corresponding one for the bottom. The columns are only defined by a screenspace top and a bottom number, and their *position* in the list is what determines where it is onscreen left-right.
There's a very important consequence of this: A visplane cannot have a screen-space vertical gap in it.
For example if we were to draw letters on the screen using visplanes: The letter U onscreen can be represented with 1 visplane, the letter O cannot.
O would require at least two visplanes.

 

So, the way this draws to the screen is relatively "simple":
The doom renderer goes row by row, and left-to-right in each row, and fills in the pixels that are within the boundaries of the visplane.

 

There are some nice videos of this in action (and more explanation) over at http://fabiensanglard.net/doomIphone/doomClassicRenderer.php

 

--------------------------------------------------------------------------------

Mommy, where do visplanes come from?

--------------------------------------------------------------------------------

Let's step through how visplanes get made.

The nodebuilder turns our map's sectors into subsectors. Subsectors are sectors chopped into convex pieces.
So, visplanes are built from subsectors. Remember how I said visplanes can't have a vertical hole in them? This is one of the many reasons convex subsectors are easier to deal with for the engine.
But let's backtrack a little, and figure out a bit more about the order in which it visits these subsectors.

 

The nodebuilder splits the map in half, then splits that half into another half, and then so on, a bunch of times. This lets us be a lot faster about rendering the map for reasons that are too complicated to go into here. What's important to know is that this does happen!
This creates what's known as the bsp "tree".
The "leaves" at the end of the tree are all subsectors.

 

So when the renderer wants to draw the screen, it uses this BSP tree. It goes down the paths of the tree that are visible, and then once it reaches a subsector, it tries to draw it. It does this in what's called depth-first order, as in, it visits all the nodes on the front side of the tree, before going down the back side.

 

--------------------------------------------------------------------------------

"We've got to find that plane."
- Sean Connery as James Bond, Thunderball, 1965

--------------------------------------------------------------------------------

When each frame starts, the engine empties the list of visplanes, so all visplanes you deal with only exist in that frame.

When the engine goes to draw each subsector, it runs a function called R_FindPlane twice (once for the floor, once for the ceiling). R_FindPlane looks over the list of visplanes we already have in order from oldest-to-newest, and looks for the first (oldest) visplane with the same flat texture, height, and light level. If it can't find a match, it makes a new visplane. This is the first place an overflow can happen.

 

Notice how it looks for an existing visplane first, meaning that "potential visplanes" can get merged in a way. It finds a "current" floor visplane, and a current ceiling visplane, and the engine keeps track of these from this step forth.

 

Next, the engine tries to add all the world segs to be rendered for that subsector. This is a complicated process, which we won't go into all the details of.
But it lets us define the edges of the potential visplane on screen-space.
It checks if those edges have certain properties that will change the resulting visplane. For example, if the subsectors on both sides of the world seg have the same height/light level/flat texture, it knows not to limit the visplane by them. On the other hand, if the edge corresponds to a world seg that is a 1-sided linedef wall, then it knows this will limit the visplane.

If the current world seg would limit the edge of the visplane in some way, it has to recheck the current floor/ceiling visplanes we have to make sure this won't create any of those nasty vertical holes we were talking about earlier. So it calls a function called R_CheckPlane (up to twice, once for floor and ceiling). R_CheckPlane looks over the lists of columns in the visplane already to see if they've been set to a number. If there is any overlap, R_CheckPlane adds a new visplane in the list, and makes that the current visplane. The engine just forgets about the last visplane as far as the current subsector is concerned. This is the other place where an overflow can happen.

 

--------------------------------------------------------------------------------

"Visplane overflows have long been a mystery (and a source of
    controversy) in the Doom editing community."
- Lee Killough, The truth about Visplane Overflows

--------------------------------------------------------------------------------

So, at first glance, it seems like visplanes should nicely merge with each other if they are nearby each other, but in practice Doom seems to waste visplanes. What's the deal?

 

Well, it comes down to a simple problem. Doom only tries to merge with: The first & oldest visplane it encounters in the list with the same properties, and then following that, it only remembers the last one it's worked on.
Imagine the first visplane of a given type drawn on the screen is a particularly bad one, like a long horizontal strip. Then all further visplanes can't merge with each other in a good way. They only check against that first one.
Here's a simple example:

You see that vertical line splitting the floor there, despite it being seemingly possible to merge those two visplanes? They aren't merging because they only check against a subsector of the closer part below your feet. To illustrate this, let's replace the texture of the far one. Traditional wisdom would tell us this will increase the number of visplanes in the scene.

Apparently, traditional wisdom is wrong in this case.

This means that sometimes you can improve visplane counts by changing a flat, or moving a height by 1. I don't recommend you use lighting because it affects both floors and ceilings, which contribute to visplane counts separately.

 

While discussing this, Linguica brought forward the idea that perhaps reversing the order of the visplane search (newest-to-old) would improve merging, because newer subsectors would likely be nearer to other recent ones. I thought this was an idea I agree with, so I tried it in my choco render limits fork.
The results were definitely much better.

Here's alien vendetta map01 on default:

Here it is with the reversed order:

 

Note that this method still is imperfect and results in splits which aren't ideal.

I also experimented with reversing world seg order, which sometimes made things worse, and sometimes made them better. It's rather inconsistent, and I'm not sure of a definitive way to understand how yet.

 

While engine source code modification is beyond the scope of a vanilla mapping project unfortunately, it does give an idea of how much the merging can be improved by providing the segs/subsectors in a different order.
As we saw earlier, the nodebuilder has some control over seg order, subsector order, and just the general shape of subsectors.
This perhaps suggests we can improve visplane counts by having the nodebuilders construct subsectors to be long-parallel to hallways for example? This is still unclear at this time.

 

Most of this was written through discussion with Linguica,

However, further alphabetical thanks to either discussion with or resources provided by:
AlexMax, Altazimuth, Esselfortium, Fraggle, Lee Killough, Jazz Mickle, Quasar, RestlessRodent, SoM, Fabien Sanglard, and Zokum
and of course, id software.

Edited August 2, 2019 by anotak

[esselfortium]

This stuff is amazing to read about, and the Doom engine continues to be a horrifying nightmare mess. Thanks for doing this research! It'd indeed be interesting to see if nodebuilders can make use of this knowledge somehow for more vanilla-efficient builds.

[Linguica]

11 minutes ago, anotak said:

While discussing this, Linguica brought forward the idea that perhaps reversing the order of the visplane search (newest-to-old) would improve merging, because newer subsectors would likely be nearer to other recent ones. I thought this was an idea I agree with, so I tried it in my choco render limits fork.
The results were definitely much better.

 

Because this involves one of Carmack's algorithms, and it turns out he reversed the order of the loop from the way that would work better, this bug should be called "Carmack's Reverse." I foresee no possible problems with this name.

 

I was hoping to produce a hex-edited doom2.exe that implements this change to accompany its, uh, announcement, but I got jammed up when I realized I might have to do more heavy duty hex editing than I first hoped.

[anotak]

oh yea, sorry about the screen edges being visible in the screenshots, haven't gotten around to figuring out what i need to do to get my fork of CRL to produce png screenshots and nothing reads pcx files in 2018 anymore

[Linguica]

Another dramatic example of visplane shrinking (lower left corner again).

 

["JL" was too short]

Like quantum physics, this is one of those things that's great fun to read about even if I could never actually work with it myself.  Thank you for writing this up!

 

[Urthar]

1 hour ago, anotak said:

oh yea, sorry about the screen edges being visible in the screenshots, haven't gotten around to figuring out what i need to do to get my fork of CRL to produce png screenshots and nothing reads pcx files in 2018 anymore

 

Paint.net will, but you have to download an extension.

[Gez]

I generally use IrfanView for quickly converting exotic image formats, but I thought it'd be funnier to point out that SLADE 3 can convert PCX to PNG just fine.

[Nevander]

It still amazes me how Carmack and the rest of the id guys figured out all this shit in the 90s. The 90s! Incredible. Right talent at the right time makes amazing things.

Edited September 9, 2018 by Nevander

[riderr3]

Useful info, but why no renderlimits for Heretic? I waited this for ages.

[anotak]

3 hours ago, riderr3 said:

Useful info, but why no renderlimits for Heretic? I waited this for ages.

i feel like this was meant to be well-intentioned comment that ended up in a quite rude spot.

ultimately, it feels incredibly dismissive of the hard work i did. it is also saying "do more hard work for no pay, particularly for a game you don't even like".

 

anyway, me working on heretic support is very unlikely. i only took up work on CRL because i was approached to work on a vanilla doom map. the SDL2 version of CRL is missing some features. the old SDL1 version doesn't work right on my machine because of windows 10 updates. so i need the proper tools to work on a map. so me and Altazimuth's fork is meant to be a relatively quick project to address these problems.

[kb1]

On 9/8/2018 at 11:38 PM, anotak said:

Let's talk about the dreaded visplane, bane of vanilla mappers everywhere.

 

 

On 9/8/2018 at 11:49 PM, Linguica said:

Because this involves one of Carmack's algorithms, and it turns out he reversed the order of the loop from the way that would work better, this bug should be called "Carmack's Reverse." I foresee no possible problems with this name.

Nice one :)

 

Lots of credits to both of you, for some solid research, and of course, for this write-up. I have a few thoughts on visplanes (if anyone's interested):

 

I think Carmack had a few motivations for building his visplane scheme:

• Performance, of course. The flat line renderer is quite fast, but the pre-calculations involved in setting up the line drawer are expensive, performance-wise. Every merge eliminates at least one set of pre-calc.
• Seam elimination. Do you remember the floor wobble that occurred in the vanilla engine, and some of the older ports, when they rendered a room where there were sectors with flashing lights? A good example is E1M2, right outside of the backpack secret. Every time the light would flash, if you stood at the right angle, you could see the floor texture jitter a pixel or two. When the light is out, those sectors' get merged into one visplane, but get split into two or three when the light turns on. The use of fixed-point stepping variables caused a lot of pixel aliasing. Visplane merging probably improves seams in a lot of places, by "spreading the error out" amongst the entire visplane.

I've been wanting to do a deep analysis of visplanes and other features of the Doom renderer for a long time, and have not yet been able to concentrate on visplanes as a concept. However, I did do some isolated studies of a set of visplane-rich (multi-thousand visplanes) maps. Those studies, combined with this post allows me to draw some conclusions, and raise some questions:

 

Conclusion #1: The test for "mergability" becomes more complex (and slower) as engine features are added: Boom deep water, colored light sectors, 3D floors, fog, etc.

 

Conclusion #2: Building and merging visplanes is not cheap, performance-wise.

 

Questions that require some research:

• How much render time is saved per merge?
• How much time is lost building a visplane, vs. a direct draw?
• How much time spent merging each visplane?
• Does this process scale linearly with # of visplanes, or does the time grow exponentially?
• How much slower would the merge process be, if it were modified to perform a "perfect merge"?

You can tell where I'm going with all of this. I believe there's a "sweet spot" # of visplanes where performance is at its best. There's a lot of ways to skin a cat, and there's more than one way to do the merge. For example, it may be possible to pre-determine strings of planes that might merge well. But sectors can change, so you'd have to be very careful here.

 

Then again, maybe it's too expensive to do "perfect" merging. And, maybe there's a way to reduce the cost of calculating planes, supporting the elimination of visplanes altogether. And, finally, it make make sense to switch to a different algorithm when the current visplane count hits a certain value.

 

Anyway, thanks for the interesting post! Clearly, some research is in order. Sounds like fun!

 

 

Edited September 11, 2018 by kb1

[Linguica]

Hex editing the DOS EXE continues to elude me, so instead here's a graph showing the number of visplanes rendered in 30nm2154 with normal visplane search (green) versus a reversed search (blue). So any green you see is savings you achieve from doing it from the rear end oh uh wai

 

 

and for completeness, here is the reverse view, showing normal nodes in blue and reversed nodes in green, so any green you see is times when the reverse search generated MORE visplanes:

 

 

As you can see, it appears that a reverse node search works especially well in scenes that would otherwise see a big visplane spike, and otherwise only helps a little if at all. I assume the big green spikes are some sort of degenerate case where a whole bunch of new visplanes are generated that reverse search manages to merge together.

[zokum]

I've done a few "thought" experiments on the creation of subsectors in a way that minimizes the number of visplanes. These assumed that the visplane search was quite good. Knowing it isn't very good opens up a whole new avenue of optimizations. It's fairly trivial to flip a partition, and if that affects the order, we might just have a winner :)

In general fewer subsectors mean fewer visplanes. Experimenting with ZokumBSP i know I can tweak it to favor one over the other. I'll need to draw up a lot of graphics to show you some good examples of my ideas and my hypothesis about improving merging. I think there's some sound analytical geometry in there, and some interesting ideas. Some of them might be tested in code soon.

One I'd like to test is this:
Whenever one creates a partition line that results in just two subsectors (leaves of the tree). Make them as uneven in size as possible. It is generally easier to merge smaller ones than bigger ones. Ideally you have some subsectors that are large, and cover a lot of the screen, and a few bits and pieces that cover the remaining smaller areas.

In this example, it should be 3 visplanes for version the leftmost configuration, and possibly only 2 for the rightmost one. (I know my mspaint "drawing" skills suck). Imagine this is a 3-level area in the middle of an arena. I've left out the outer area, but the player is free to view it from any angle and it's only one sector, but it gets split into 3 convex subsectors.

It should be noted that an area can be viewed from any angle, and in this example you can of course make the rightmost guarantee 3 visplanes as well. If we imagine a 360 degree circle, we could make arches representing areas where there are two or three visplane geometry visible However, with smaller areas, the area of the circle that is 2-visplane, would be bigger. If we do this for everything in the map, we should end up with statistically fewer visplanes in any random scene, since in most cases we run into more optimal cases.

Conventional algorithms usually try to balance the amount of segs on each side of a partition to get a balanced tree, but this might actually be bad when one or both of the children are subsectors. This might even harm performance, since we are more likely to have to render two subsectors instead of just one.

As a side note, you can run ZokumBSP, the latest beta, with wide mode. It will try literally millions of trees to find the map with fewer subsectors. It would be interesting to see how these optimizations affect the amount of visplanes. I haven't had time to look into it yet. I wouldn't try it on a larger map unless you have a super computer available. I've mostly played around with map07, map11 and map32. These run well. Some maps with similar amount of geometry, take much longer.

Edited September 11, 2018 by zokum

[Linguica]

58 minutes ago, zokum said:

As a side note, you can run ZokumBSP, the latest beta, with wide mode. It will try literally millions of trees to find the map with fewer subsectors. It would be interesting to see how these optimizations affect the amount of visplanes.

 

I cloned the Github and tried running it but I can't figure out how to turn on wide mode or how to tell if it's working properly.

[indigotyrian]

Fascinating how simply reversing the order offers massive (if situational) benefits! Though I have to wonder (and please forgive me if my question's already answered, I'm still trying to figure out what all of this even means and how it all works), why wasn't the order reversed to begin with? Surely Carmack or somebody else must've thought to try reversing the render order. This seems too simple to be an oversight.

[zokum]

Progress bar only works if your terminal supports ansi escape sequences, Linux does it fine in most cases.
 

./zokumbsp -b- -r- -na=mw=1 -t doom2.wad map07

MAP07*   Lump          Old         New     %Change      %Limit      Time Elapsed
         Segs          325  =>     317      97.54%       0.97%
         Subsecs        97  =>      97     100.00%       0.30%        0.003 secs

-b- (Turns off blockmap generation)
-r- (Turns off reject generation)
-na=m (Use multi tree algorithm)
w=1 (Only one subtree)
-t (Test only, do not write to disk)
 

./zokumbsp -b- -r- -na=mw=2 -t doom2.wad map07

MAP07*   Lump          Old         New     %Change      %Limit      Time Elapsed
         Segs          325  =>     311      95.69%       0.95%
         Subsecs        97  =>      92      94.85%       0.28%       15.838 secs

Here I changed w=1 to w=2. It would then try two partitions and compare and pick the "best" one. It took substantially longer though.

With w=3 it takes a LOT longer. I know a bit about how I can optimize this to be faster, but I haven't had time to look into it too much. Having it actually work was more important. :)
 

[zokum]

Oh that reminds me. If your terminal supports color, like most do, you can add the switch -c. It will make the map header stand out more and color code the difference and limit data in such a way that it's easier to see if this change was an improvement or not. I think this is the Gain from w=1 to w=2, it was an old screenshot I had lying around and the numbers seem to be the same.

[kb1]

4 hours ago, Linguica said:

Hex editing the DOS EXE continues to elude me, so instead here's a graph showing the number of visplanes rendered in 30nm2154 with normal visplane search (green) versus a reversed search (blue). So any green you see is savings you achieve from doing it from the rear end oh uh wai

 

 

and for completeness, here is the reverse view, showing normal nodes in blue and reversed nodes in green, so any green you see is times when the reverse search generated MORE visplanes:

 

 

As you can see, it appears that a reverse node search works especially well in scenes that would otherwise see a big visplane spike, and otherwise only helps a little if at all. I assume the big green spikes are some sort of degenerate case where a whole bunch of new visplanes are generated that reverse search manages to merge together.

I was going to ask for your 'Ling's Reverse' code, and attempt the hex edit, but I can't get my other Doom projects released :(

Anyway, am I reading your terminology backwards? As far as I can tell, less visplanes = more merges = better performance, right? Chart #2 looks like chart #1 with the green turned into blue, so, does the green represent extra merging that happens when merging in reverse?

 

Aw, hell, what is the reverse algo?

 

@zokum Nice colored console output! I find your algorithm to try tons of variants fascinating. But the idea of using a general algorithm to estimate visplanes worries me...or, let's say that it seems like a shot in the dark, precisely because of the 360-degree nature of visplane creation. For better results, a primitive line-intersection 90-degree "eye" could walk the level, by scanning a grid of blockmap-sized steps, left to right, top-to-bottom, in, say 8 or 16 rotations, with each "gaze" performing a mock visplane merge. Finally, add up the total number of merged visplanes for the level.

 

Use this final sum to judge the quality of your current variant. Do this after each variant, and retain the variant with the lowest count. This could be the basis for a genetic algorithm that finds the best configuration. But, it's a whole lot of work!

 

A demo could be made easier with the help of a source port. The port could load the map using the "-wart" hack, calculate the visplane sum, and write it to file. But, again, yikes :)

 

An efficient runtime "perfect merge" algorithm would be the most ideal solution, I would think. Hex-editing that into Doom.exe would be the most "fun".

 

Damn it, you guys are having all the fun, and I'm stuck writing order entry programs - grrrr.-

Edited September 11, 2018 by kb1
added more stuff

[zokum]

I am unsure whether what you describe would be feasible. I think it would simply take too long to compute. My point is that the current algorithms are not taking any sort of visplane reduction into account, a better algorithm could add some counter measures. They need not be perfect, only statistically better than what we previously have done. I like your idea on theoretical grounds, I just think it's impractical :)

Thanks for the feedback on the colors. We had several people trying out different schemes until we found a decent one. I am currently building map06, and I have been at it for about 6 hours and I am 25% done on the progress bar. It might take a day or two to build the map properly. Map06 is one of those maps I have never finished building. I am giving it an honest try now :) Here's my build 'script'.

 

#!/bin/bash
./zokumbsp -c -na=mw=1 -r- -b- doom2.wad

# Fast enough
#./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map30
#./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map07
#./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map02
#./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map32
#./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map31
#./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map04

# 2388 secs
#./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map05

# 329.295 secs
#./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map11

./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map06
./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map08
./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map09
./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map10
./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map12
./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map13
./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map14
./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map15
./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map16
./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map17
./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map18
./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map19
./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map20
./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map21
./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map22
./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map23
./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map24
./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map25
./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map26
./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map27
./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map28
./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map29

# Slow, never finished building these ones.
./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map01
./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map03

 

[kb1]

10 hours ago, zokum said:

I am unsure whether what you describe would be feasible. I think it would simply take too long to compute. My point is that the current algorithms are not taking any sort of visplane reduction into account, a better algorithm could add some counter measures. They need not be perfect, only statistically better than what we previously have done. I like your idea on theoretical grounds, I just think it's impractical :)

Oh, it's way impractical! Then again, you've already gone to great lengths to improve ZokumBSP output (which is pretty damn cool). And, yeah, it'd be slow, but not horribly slow.

 

The idea of using a source port was that you could get some demonstrable results without a lot of coding. It would be much better to emulate visplane creation within the node builder directly, allowing it to be lean and highly optimized.

 

The thing about genetic algorithms is that they bear fruit pretty quickly, if they have a reliable scoring mechanism. That's where the visplane counter comes into play. That has to be highly accurate, otherwise the genetic algorithm oscillates between slight differences, and never gets a foothold.

 

At any rate, it would be fun to build. Please keep us informed on the results of your future tests.

[zokum]

I am currently working on map06. I have been at it for about 19 hours and I am only 25.63% done. The progress is still going up though, so it's not stuck. I have a good hunch as to why some of these maps take such a long time.

[therektafire]

Would manually convexifying the map by hand cause less subsectors to be generated, or would you just have a ton more sectors with 0 benefit whatsoever?

 

At any rate I think @Pan should read this before they make a new map...

Edited September 12, 2018 by therektafire

[zokum]

Manually convexifying a map could yield a much better result than the current nodebuilders yield. The basic algorithm found in all of them, as far as I can tell, is pretty bad. It's horribly complex stuff to do though, and takes a LONG time for anything but a trivial map.

 

[therektafire]

6 minutes ago, zokum said:

Manually convexifying a map could yield a much better result than the current nodebuilders yield. The basic algorithm found in all of them, as far as I can tell, is pretty bad

Oh wow I didn't know that :v what shape counts as "convex" as far as nodebuilding is concerned? Would any shape suffice or is it only a particular kind like squares or triangles?

[zokum]

Any shape that is convex. It should be noted that it doesn't have to have segs on all sides either. Partition lines can act as edges.

[therektafire]

Alright. Also as far as being complicated goes I feel like it would be more tedious than complicated. If any convex shape is allowed that makes things way simpler, you can just look over the map and usually easily eyeball where to split. Of course like you said if you have a really big map with lots of big sectors with wonky shapes  with lots of stuff around it could take a while to figure out  where to divide it which is probably why almost no one if anyone at all ever does it

 

Would you happen to have any:"before and after" pictures of maps in their original form in the editor then after they have been built? I would be really interested to see it :)

Edited September 12, 2018 by therektafire

[zokum]

I don't have any tools that display the subsector data. They must exist, since there are screenshots of such stuff on doomwiki.org. It is something I have thought about putting into the nodebuilder as an output thing. It already has support for html output that I used to debug blockmap stuff. It's a bit hackish, but it is available.

[boris]

The DB2 family has a mode that shows subsectors (and splits). If you want to add subsector visual output to ZokumBSP I guess SVG would be a good format.

[zokum]

The DB2 stuff isn't of much use as it recomputes the subsectors with an interal node build. I agree that svg is probably the ideal format for this. I have some ideas about a nice smooth map output rendering with several interesting additions to make it easier to "read" maps.