zokum

Members
  • Content count

    58
  • Joined

  • Last visited

2 Followers

About zokum

  • Rank
    Mini-Member

Recent Profile Visitors

199 profile views
  1. The Doomwiki page is unfortunatly polluted with Boom, Heretic, Hexen and Strife filth. It's somewhat hard to read due to that. Several important limits are missing. That page ought to be redone, same with the linedef specials page which is also a mess. They're not good references to use for Doom mapping.
  2. Sorry of necrobumping, I was looking for some info about such a desync on my own project, and figured things out. Demos with revenant missiles can desync because the type of missile, homing or not, depends on how long doom has been running. A demo can play back fine if you use -file map.wad -playdemo demo1 but not if you just let it start on its own.
  3. It should be noted that this technique might help in other node builders as well. Feel free to experiment.
  4. This might not be quite the correct thread, but I didn't want to start up another thread. I did some research just to see what _could_ be done manually to improve a map, so that I knew what the code i wrote should aim for. The idea was to manually add a linedef on a map that would make it easier for the node builder to partition the map into two parts. Basically, I added a new linedef on map01, it went from the corner of the lift near the plasma on multiplayer to the corner of the hallway leading to the large plasma room. Here are my results: ./zokumbsp -b- -r- -sm -na=dt=xq doom2.wad map01 MAP01 Old New %Change %Limit Time Elapsed Nodes: 185 => 185 100.00% 0.56% 0.010 secs Segs: 611 => 611 100.00% 1.86% And now with my new "hint" line: ./zokumbsp -b- -r- -sm -na=dt=xq map01hnt.wad map01 MAP01 Old New %Change %Limit Time Elapsed Nodes: 184 => 184 100.00% 0.56% 0.010 secs Segs: 598 => 598 100.00% 1.82% That is a reduction of 13 SEGs by _adding_ a two-sided linedef. I've added a screenshot of me doodling a bit, the line in question is the red one. Ignore the other ones.
  5. The face stuff is probably a colorized black and white pencil drawing, similar to the other skin, snake, tentacle, etc textures. Have look at this as an example off the technique: https://www.doomworld.com/linguica/doom-textures/hell2.html
  6. I just added a summary of the node/seg stuff done for all maps when using ZenNode. This makes it much easier to run new code over a large data set and see if it is an optimization or not. I am working on some very minor splits-algorithm optimizations.
  7. I wonder if your tree can be considered the bastard child of a ternary-like tree. I think we could say that we are grouping SEGs into left, right or both sides. Any SEG that is on both lines of the partition line is instead put into both child nodes, to be handled later. Thus we're avoiding all splits and instead have 'duplicate' entries several places in the child nodes, and the same partition lines are used in several places in the tree, but with different children. I could wrong here, but would this be an ok explanation of the type of sorting we see here. I'd like a good formal and rigid description that makes writing an algorithm possible.
  8. Yeah, this is no longer a BSP tree, it's like you say an acyclical graph. My point still stands for a tree, but a different data structure that is more like a location finder graph might work. It reminded me of how gps works by narrowing down your location from various data points and then figuring out your position and what is around you :)
  9. Thanks :) I figured a short, small and informative post would make it easier to understand why this happens. If you know why it happens, it's usually easier to avoid or reduce the problem. If you have a section with HOM in it, if you got any long lines in that area that goes "across" the screen, tell the node builder to not split that line, it might help with reducing the splits in that specific hot-spot. I'll add a linedef type for that in ZokumBSP so that people can easily do it from a map editor as the current way of doing it is a bit cumbersome.
  10. Lately there's been some talk on irc and discord about node builders and SEG and SEG splits etc. The main reason for avoiding splitting SEGs is to lower the SEG count and have less than 256 SEGs in view to avoid HOM. A map built without splits could have more detail than one with splits. Ideas have been tossed around about by transforming a map into all convex subsectors and build the BSP tree from ground up. This simple example proves that such an endavour and all other no-split ideas are impossible to do on all maps. It might be possible on some maps, but most maps will realistically have geometry that makes it impossible to have no splits. Still, fewer splits should be within reach, I have started working on building a special low-split algorithm. Here is a nice proof that it is impossible to make this simple two-sector map split-free. This is basically a disproof of the hypothesis that all maps can be divided into two halves in such a way that no SEGs are split. We construct a map with a concave polygon with 4 edges sharing two sides with a threesided polygon. 1. Any line that is on the 'edge' will sort all segs on one side of the line, and is not viable as a dividing line, since it has not divided the SEGs into a left and right side. 2. Lines must go from vertex to vertex, since a line going through any other location, will split a line. 3. The only possible split lines from the 3 outer vertices that go through another vertex that doesn't form an edge, are lines that go through the central vertex. 4. Any line that goes from an outer vertex through the inner vertex, will split one of the sides. Thus it is proven that it is possible to construct maps where split SEGs are unavoidable and any work done towards split-free bsp trees is futile. At best one can have a really low amount, and that is a worthwhile pursuit.
  11. Fair enough kb1, as for reinventing the wheel, what we got now is a horrible square wheel, I just want a nice small round one. As for ZokumBSP i just added another one: 1084 - Do not render seg on the backside. This one is very useful for a lot of cases, and I even added some code that allows you to auto detect where this behaviour would be nice, like sky sectors with 0 height. I plan to have it togglable as part of the geometry pass that is done before blockmap, node and reject. Default will be off. As for how efficient this is by mere auto detection, doom2.wad: MAP01 Old New %Change %Limit Time Elapsed Linedefs: 381 => 381 100.00% 1.16% 0.000 secs Sectors: 59 => 59 100.00% 0.18% Nodes: 185 => 184 99.46% 0.56% 0.017 secs * Segs: 611 => 602 98.53% 1.84% MAP23 Old New %Change %Limit Time Elapsed Linedefs: 391 => 391 100.00% 1.19% 0.000 secs Sectors: 69 => 69 100.00% 0.21% Nodes: 185 => 185 100.00% 0.56% 0.022 secs * Segs: 580 => 567 97.76% 1.73% And a few extremely cherry picked ones in av.wad: MAP12 Old New %Change %Limit Time Elapsed Linedefs: 3193 => 3193 100.00% 9.74% 0.001 secs Sectors: 596 => 596 100.00% 1.82% Nodes: 1489 => 1475 99.06% 4.49% 0.487 secs * Segs: 5071 => 4953 97.67% 15.12% MAP16 Old New %Change %Limit Time Elapsed Linedefs: 3110 => 3110 100.00% 9.49% 0.001 secs Sectors: 482 => 482 100.00% 1.47% Nodes: 1746 => 1704 97.59% 5.18% 0.627 secs * Segs: 5299 => 5055 95.40% 15.43% I just want a bit of linedef speicals range reserved for mapper stuff, custom behaviour and scripting. All ports can utilize it, but not for anything in-built. If we all agree on a range for this, things will be much more future proof. The example I gave was just to show there is merit for such a system. I have many more planned, and since this is the documentation thread, this stuff might be of interest to ports that want to optimize without relying on the vanilla data formats so much.
  12. Here comes the final batch of numbers. The threshold for map20 really surprised me, being 231. That was until I saw map25 with 498, map28 with 493 and map29 with 360. Finding a "best" threshold or a reasonable range isn't very easy. Map20 sees a reduction of 30 segs, not that much, but every bit does help. Map28 got a reasonable 25 segs reduced, and is a noticably smaller map. All in all I would categorize this kind of optimization as a very minor and time consuming optimization. I wouldn't go for this unless one really wanted to cram the last few segs out of a vanilla format map. It should be noted that the various cutoffs might change the way a map is split drastically, so if you got a map where an area is plagued with HOM due to the 256 limit, some of the BSP trees might be a better build. I think you'd be much better off just marking off lines as do-not-split though to help on such cases. All in all, it's a tool that is soon out there, people can play around with it and for those wanting the "perfect" final build of a map, this might be the setting of choice. I plan on adding a paramter -t for thoroughness allowing you to test different ranges. Most likely ranges along the lines of 3-10, 3-25, 3-75, 3-150, 3-300, 3-500, 3-750, 3-2000, 3-4000, 3-8000, 3-16000 and 3-32678. I think a better split reduction algorithm would make all of this moot, but here is the data of what can be done today, and code people can play with. I just committed code for checking from 3 to 500, just use -na=a to select the adaptive algorithm. https://github.com/zokum-no/zokumbsp MAP20 Old New %Change %Limit Time Elapsed Linedefs: 14839 => 14839 100.00% 45.29% 0.001 secs - 231 - Nodes: 9943 => 10021 100.78% 30.48% 6113.413 secs * Segs: 27997 => 27967 99.89% 85.35% MAP21 Old New %Change %Limit Time Elapsed Linedefs: 4366 => 4366 100.00% 13.32% 0.001 secs - 42 - Nodes: 2649 => 2657 100.30% 8.08% 378.928 secs * Segs: 7228 => 7216 99.83% 22.02% MAP22 Old New %Change %Limit Time Elapsed Linedefs: 2223 => 2223 100.00% 6.78% 0.000 secs - 0 - Nodes: 1176 => 1176 100.00% 3.58% 101.642 secs Segs: 3710 => 3710 100.00% 11.32% MAP23 Old New %Change %Limit Time Elapsed Linedefs: 5295 => 5295 100.00% 16.16% 0.000 secs - 16 - Nodes: 3479 => 3484 100.14% 10.60% 764.453 secs * Segs: 9701 => 9687 99.86% 29.56% MAP24 Old New %Change %Limit Time Elapsed Linedefs: 3982 => 3982 100.00% 12.15% 0.000 secs - 15 - Nodes: 2697 => 2701 100.15% 8.22% 424.636 secs * Segs: 7418 => 7414 99.95% 22.63% MAP25 Old New %Change %Limit Time Elapsed Linedefs: 7095 => 7095 100.00% 21.65% 0.001 secs - 498 - Nodes: 3919 => 4000 102.07% 12.17% 875.905 secs * Segs: 12205 => 12190 99.88% 37.20% MAP26 Old New %Change %Limit Time Elapsed Linedefs: 4710 => 4710 100.00% 14.37% 0.000 secs - 6 - Nodes: 2386 => 2386 100.00% 7.26% 373.239 secs * Segs: 7807 => 7806 99.99% 23.82% MAP27 Old New %Change %Limit Time Elapsed Linedefs: 7328 => 7328 100.00% 22.36% 0.001 secs - 30 - Nodes: 4023 => 4033 100.25% 12.27% 1172.359 secs * Segs: 12181 => 12180 99.99% 37.17% MAP28 Old New %Change %Limit Time Elapsed Linedefs: 6700 => 6700 100.00% 20.45% 0.001 secs - 493 - Nodes: 3651 => 3730 102.16% 11.34% 834.532 secs * Segs: 11612 => 11608 99.97% 35.42% MAP29 Old New %Change %Limit Time Elapsed Linedefs: 4111 => 4111 100.00% 12.55% 0.001 secs - 360 - Nodes: 2605 => 2626 100.81% 7.99% 545.751 secs * Segs: 7407 => 7382 99.66% 22.53% MAP30 Old New %Change %Limit Time Elapsed Linedefs: 1952 => 1952 100.00% 5.96% 0.001 secs - 101 - Nodes: 1123 => 1123 100.00% 3.42% 120.131 secs * Segs: 3415 => 3411 99.88% 10.41% MAP31 Old New %Change %Limit Time Elapsed Linedefs: 4816 => 4816 100.00% 14.70% 0.000 secs - 5 - Nodes: 2477 => 2477 100.00% 7.53% 327.312 secs * Segs: 8053 => 8052 99.99% 24.57% MAP32 Old New %Change %Limit Time Elapsed Linedefs: 914 => 914 100.00% 2.79% 0.000 secs - 5 - Nodes: 530 => 530 100.00% 1.61% 16.702 secs * Segs: 1658 => 1657 99.94% 5.06%
  13. You are correct, but they're not all that useful nor important when trying to limit segs, since 0-sided ones do not generate segs. I should have said "most linedefs".
  14. I'm working on tweaking the node builder code in ZokumBSP to produce better trees for large maps. A lot of this is specific to ZokumBSP 1.0.10 which is not out yet, and some of the code isn't even on GitHub yet, but some is. As some of you know, vanilla maps have something called segs. That is shorthand for linedef segments. A linedef has at least one seg, two segs if it's two-sided. Additional segs are added if a linedef is split as part of the node building. A good rule of thumb is to assume you'll have about twice as many segs as you have linedefs. My go-to map for testing is as always av.wad map20. That map has 14839 linedefs and 27997 segs if built with -na=d, a ratio of about 1.886 segs per linedef. The released map is built with the seg split partition algorithm, which aims to pick partition at the line with the least amount of splits. In general however, the second algorithm, the divide evenly one tends to produce fewer splits. This is a bit counter-intuitive. The reason this most like happens for is that the fewer-splits algorithm will often pick lines that down the road lead to more splits. It's basically painting itself into a corner, all the time. The balanced-tree approach will overall lead to less split segs and thus fewer segs. The way ZenNode's seg partition algorithm works is that it's an inter-changable method. It's possible to swap algorithm while building nodes. I figured I could use an approach similar to the one quick sort uses. Use the good even dividing partitioner on the top level and go with the split reducer when there are very few segs left. I tried a fairly arbitrary value of 30, and tested this on every map in av.wad. This produced some maps with more segs, some with less, but not much. We're talking about less than half a percent in most cases. Still, some gain over no gain is always beneficial. We are after all talking about a lower amount than any of the ones found in ZokumBSP. So i tried a few different thresholds, and results varied in all directions. What was good for one map was bad for another, and vice verca with another value. Time to use brute force! I then made a nice little hack where it would try values starting with 0 and going up to 50 and remember the best tree, the one with the lowest seg count. This worked better, several maps now saw improvements. The values for some of the thresholds were pretty high, so i figured i'd try all the values from 50 to 100. Turns out some of them also got reductions with those numbers as well, and in one case, even better reduction. Judging by this I figured I'd try all the way from 0 to 250 on the smaller maps. That gave me a map with a rather high best threshold, 237. So I caved in and tried building all the maps with values from 0 to 500 as threshold, and here is the output. It contains a small printf-debug showing the best threshold with some "-" around it. It takes a while to compute these, so here are the first 19 maps. It's still working on map20 and it will for another hour or so... As for the output, the important columns are column 2,3,4 with 4 showing overall how much of an improvement it is. The %Limit column shows how near one is the maximum size in vanilla Doom. ZokumBSP Version: 1.0.10-beta1 (c) 2016-2017 Kim Roar Fold√ły Hauge Based on: ZenNode Version 1.2.1 (c) 1994-2004 Marc Rousseau Working on: av.wad MAP01 Old New %Change %Limit Time Elapsed Linedefs: 1359 => 1359 100.00% 4.15% 0.000 secs - 141 - Nodes: 723 => 724 100.14% 2.20% 42.774 secs * Segs: 2310 => 2303 99.70% 7.03% MAP02 Old New %Change %Limit Time Elapsed Linedefs: 1203 => 1203 100.00% 3.67% 0.000 secs - 70 - Nodes: 608 => 611 100.49% 1.86% 36.795 secs * Segs: 1946 => 1939 99.64% 5.92% MAP03 Old New %Change %Limit Time Elapsed Linedefs: 2549 => 2549 100.00% 7.78% 0.000 secs - 30 - Nodes: 1545 => 1551 100.39% 4.72% 135.034 secs * Segs: 4880 => 4873 99.86% 14.87% MAP04 Old New %Change %Limit Time Elapsed Linedefs: 2418 => 2418 100.00% 7.38% 0.001 secs - 237 - Nodes: 1255 => 1277 101.75% 3.88% 101.390 secs * Segs: 4160 => 4152 99.81% 12.67% MAP05 Old New %Change %Limit Time Elapsed Linedefs: 2328 => 2328 100.00% 7.10% 0.000 secs - 26 - Nodes: 967 => 972 100.52% 2.96% 74.430 secs * Segs: 3718 => 3715 99.92% 11.34% MAP06 Old New %Change %Limit Time Elapsed Linedefs: 2192 => 2192 100.00% 6.69% 0.000 secs - 13 - Nodes: 1315 => 1316 100.08% 4.00% 104.263 secs * Segs: 3857 => 3855 99.95% 11.76% MAP07 Old New %Change %Limit Time Elapsed Linedefs: 1355 => 1355 100.00% 4.14% 0.000 secs - 23 - Nodes: 767 => 771 100.52% 2.35% 51.561 secs * Segs: 2222 => 2219 99.86% 6.77% MAP08 Old New %Change %Limit Time Elapsed Linedefs: 2602 => 2602 100.00% 7.94% 0.000 secs - 0 - Nodes: 1633 => 1633 100.00% 4.97% 194.176 secs Segs: 4653 => 4653 100.00% 14.20% MAP09 Old New %Change %Limit Time Elapsed Linedefs: 3729 => 3729 100.00% 11.38% 0.000 secs - 11 - Nodes: 2187 => 2188 100.05% 6.65% 361.752 secs * Segs: 6433 => 6429 99.94% 19.62% MAP10 Old New %Change %Limit Time Elapsed Linedefs: 7555 => 7555 100.00% 23.06% 0.000 secs - 0 - Nodes: 4163 => 4163 100.00% 12.66% 1120.114 secs Segs: 12660 => 12660 100.00% 38.64% MAP11 Old New %Change %Limit Time Elapsed Linedefs: 8299 => 8299 100.00% 25.33% 0.001 secs - 437 - Nodes: 5140 => 5226 101.67% 15.90% 1868.975 secs * Segs: 14707 => 14687 99.86% 44.82% MAP12 Old New %Change %Limit Time Elapsed Linedefs: 3193 => 3193 100.00% 9.74% 0.001 secs - 67 - Nodes: 1489 => 1504 101.01% 4.57% 148.859 secs * Segs: 5071 => 5060 99.78% 15.44% MAP13 Old New %Change %Limit Time Elapsed Linedefs: 3005 => 3005 100.00% 9.17% 0.001 secs - 0 - Nodes: 1748 => 1748 100.00% 5.32% 167.719 secs Segs: 5380 => 5380 100.00% 16.42% MAP14 Old New %Change %Limit Time Elapsed Linedefs: 3991 => 3991 100.00% 12.18% 0.001 secs - 0 - Nodes: 1959 => 1959 100.00% 5.96% 299.936 secs Segs: 6390 => 6390 100.00% 19.50% MAP15 Old New %Change %Limit Time Elapsed Linedefs: 3435 => 3435 100.00% 10.48% 0.000 secs - 13 - Nodes: 1754 => 1756 100.11% 5.34% 194.456 secs * Segs: 5571 => 5570 99.98% 17.00% MAP16 Old New %Change %Limit Time Elapsed Linedefs: 3110 => 3110 100.00% 9.49% 0.001 secs - 72 - Nodes: 1746 => 1755 100.52% 5.34% 178.603 secs * Segs: 5299 => 5289 99.81% 16.14% MAP17 Old New %Change %Limit Time Elapsed Linedefs: 2099 => 2099 100.00% 6.41% 0.000 secs - 0 - Nodes: 1004 => 1004 100.00% 3.05% 77.442 secs Segs: 3283 => 3283 100.00% 10.02% MAP18 Old New %Change %Limit Time Elapsed Linedefs: 4817 => 4817 100.00% 14.70% 0.000 secs - 0 - Nodes: 2812 => 2812 100.00% 8.55% 462.239 secs Segs: 8440 => 8440 100.00% 25.76% MAP19 Old New %Change %Limit Time Elapsed Linedefs: 5353 => 5353 100.00% 16.34% 0.001 secs - 11 - Nodes: 2736 => 2743 100.26% 8.34% 511.833 secs * Segs: 8722 => 8719 99.97% 26.61% I know how to write a better split reduction algorithm, it's fairly easy to do in pseudo code. Getting it into code is a whole different project, but I might do just that, seing how this simplistic approach did do better, albeit not much. As for now, it should be possible to reduce the seg count by a little for most maps in the next release. When I get more numbers, I can post them in this thread if it is of interest to people. I think map20 will be the most interesting one of the bunch.
  15. Version numbers are important. The reason I suggested using the year as versioning number is that you immediatly get a hint at what kind of port you need to run this. If a wad requires DSPE-17 and your source port is from 2016, you can be pretty sure that the support might not be perfect...