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

zokum

Members
  • Content count

    237
  • Joined

  • Last visited

Everything posted by zokum

  1. I'm posting here since this is a very broad topic which I really would like to hear the ffedback from the entire community. I want to hear people's opinion on how to solve a problem with no real solution. Here's some background to better explain the problem. Those familiar with Doom engine rendering and seg splits can skip this section. When segs are split, the length can subtly changeby +/- ~1.1 pixels. This can lead to each seg becoming 1 pixel longer for each split. This means that a linedef might be 170 pixels inside the editor, but will be 172 pixels long in game. ZokumBSP and possibly other nodebuilders currently compute the offset based on the seg, so multiple splits can increase the error even more. Due to some other changes I am changing the code to compute it based on the original linedef's origin, not the split seg. This leads to the following rare changes that can crop up in some corner cases. 1. Textures should be at most 1 pixel off by the end, they can no longer be off by number of segs pixels. 2. Textures can now gain repeating lines in the middle of textures. 3. Aligning diagonal textures will be easier, since textures are much less likely to be off at the linedef ends compared to the editor. 4. In many cases problematic walls can be cured by marking it as do-not-split. Then it will only be split if there is no other way to build the map. This is a very rare occurence, and it almost never occurs. It should be noted that there will always be some wonkiness when splitting a seg. The question is, what kind of wonkiness is best?. Here's some debug output from a build of Doom 2 MAP15: I haven't checked, maybe some engine freak can correct me if I am wrong. When rendering diagonal lines, it can render the last "pixel" as a less wide column. This means that some pixel columns today will be "wider" or "narrower" depending on the rounding in the seg, since a seg ends on a non-integer pixel coordinate, but the new one starts on an integer value. Values below 0.5 pixels get round down, we get a "wide" pixel colum since it renders say 0.4 of a column, then 1.0 of the same column in the new seg, giving us 1.4 columns worth of the same pixels. It at least looks like that on the diagonal grey big brick walls on map15. So what do you guys and gals think? Is this more or less correct than the old method?
  2. Here's the last file in this saga, I think it's fairly well documented by now. It's a 4 kilobyte recording of me going straight to such a seg split on map01. I recorded it in Chocolate Doom, this will not show up in PrBoom+ and most likely won't show up in many other ports either. http://doom2.net/zokum/demos/d2split.lmp I think that in most cases, these splits aren't noticable in normal gameplay. If you're unlucky to get such a split it in a spot with a big change in color, brightness, lettering, etc, they might be a problem if you're really picky. I plan to one day add an option to try to build maps without this type of split, so they occur a lot less or not at all. I think it would be a worthwhile addition to a nodebuilder. They're usually not too hard to find with slade. These splits tend to have the occasional strip of pixels from the neighbouring column as well. This column might be related to bad seg angles, I haven't checked. If anyone ever has weird texture issues on diagonal walls, point them to this thread. This effect here might just be the culprit. They're not too hard to fix either, just tag the wall with do-not-split.
  3. Here's what the end of the line looks like. There's a clear difference between Prboom+ and Chocolate Doom here. I might have changed the alingment if I playtested this in prboom, but I would probably have let it be if I tested with Chocolate Doom. Chocolate Doom is the top one. The shots aren't from the exact same position, but it's near enough.
  4. Here's a mid-lindedef-seg-alignment-anomaly. Took me a few inutes to find. These errors do not show up in prboom+, but they are quite visible in Chocolate Doom. I browsed through the list of segs in slade 3 and found one where the offset was 21 on the front side, looked it up in an editor and went and looked in Doom and took some screenshots. The shot is from the inaccessible lava area in the exit area, roughly facing the exit teleporter. The third show is thre to show it's visible from multiple locations and different angles, and to make it easier to find the spot yourself. The seg split is at 21 units into linedef 1500. There's also an additional anomaly that sometimes turns up due to rounding errors, shown in the second screenshot. This anomaly is visible from a multitude of angles and flickers in and out of the rendering when you move around. This isn't very pretty. Maybe avoiding splitting diagonal lines on problematic rounding points or in general should be a nodebuilder option?
  5. We probably do see mid-linedef-half pixels, but it's a very rare occurence. I can't remember any, but I haven't looked for them. The second screenshot is a 1-seg-cutoff. The problem I am talking about is that several seg splits CAN lead to more than that 0.5 pixel difference. That's when aligning can end up looking odd. In many cases it's hard to spot since different linedefs often change texture, making the alignement problem non-existant. In your example I presume there won't be any split, unless you have a normal texture on that loose linedef. Lines where the back and front side belong to the same sector can't render upper or lower textures, and get removed from the BSP tree unless they have a normal texture, a common optimization. I'll go scour map15 and see if I can't find a mid-linedef-non-integer-pixel. Might be hard though, since doombsp gets the angle wrong, that might null out the effect a bit, but that also leads to otger errors like the map09 star problem.
  6. zokum

    ZokumBSP development

    Figured I should post/blog a bit about my ongoing development of ZokumBSP and the proces around it. I'll mostly cover thing that are specific to ZokumBSP, but there will be the occasional post about code and algorithms that can be used in other nodebuilders. The current release version is 1.0.9. There's a beta version 1.0.10 bundled with Doombuilder X with a few more features.
  7. zokum

    ZokumBSP development

    Balanced mode has had the minor speed problem fixed. Here are numbers from Doom 2 map11 with different metrics. m=b - Balanced: Trees are better IF they score lower with the formula: SubsectorCount * 2 + SegCount. m=s - Splits: Trees are better IF they score lower with the formula: SegCount. m=u - SubSectors: Trees are better IF they score lower With the formula: SubSectorCount. ./zokumbsp -b- -r- -na=mw=2m=b doom2.wad map11 MAP11* Entry Old New %Change %Limit Time Elapsed Segs 1309 => 1267 96.79% 3.87% Subsecs 430 => 368 85.58% 1.12% 2m 36s 898ms ./zokumbsp -b- -r- -na=mw=2m=s doom2.wad map11 MAP11* Entry Old New %Change %Limit Time Elapsed Segs 1309 => 1260 96.26% 3.85% Subsecs 430 => 375 87.21% 1.14% 2m 15s 707ms ./zokumbsp -b- -r- -na=mw=2m=u doom2.wad map11 MAP11* Entry Old New %Change %Limit Time Elapsed Segs 1309 => 1273 97.25% 3.88% Subsecs 430 => 366 85.12% 1.12% 2m 37s 207ms Depending on what you look for, different algorithms will give slightly different results. The old one is the doom2.wad data. Splits go slightly faster as it lends itself towards less data due to fewer lines to handle.
  8. Here's an example of a column of pixels that is like 0.8 of a pixel or so. Very easy to locate. The point is. The more a seg is split, the more the rendered length can deviate from the expected length. The question is, how should it be handled when lines become longer? It should be noted that it might be possible that splits cancel out the effect of eachother. Anything below 0.5 will be rounded down.
  9. This is actually quitre easy to find in many maps. Here's from the end of the long diagonal wall on d2 map15. You can find plenty of such oddities if you just know where to look and what to look for. This is taken in prboom-plus, but it shows up in chocolate doom as well. It's visible from a wide range of locations near the "corner".
  10. zokum

    ZokumBSP development

    I found he 32bit error. It now produces the same output as a 64bit executable does. Added a new default tree assessment mode. It will now value 2 seg splits as equal to one extra subsector. A tree with 3 extra splits but one less subsector will therefore be considered a worse tree. This is now the default mode, not subsector reduction. This only applies for the multi-tree mode. Minor tweaks to the output code made it slightly more readable on win32, but still an unromeroish mess. Still loads of debugging left to do. The case study is chugging along. With the new 32bit fix, I have set up a 15 year old Pentium 4 machine to work on doom.wad. It's chugging along nicely. I am currently at a computer party, but It had been computing for about a day when I left and had already finished e1m5. E1m3 took over 13 hours. I was thinking this wouldn' take so long..... Currently at the computer party and just logged in to my P4! E1m6 seems to go really slow. It's been at it for over 60 hours and is still only finished with 1.27% of the total bsp trees it needs to calculate. This looks like a long haul, maybe worse than the 6 days i spent on Doom 2 map21. Anyone got a spare super computer? Just got back from the computer party and got my computer set up. Computations are now at 1.46%. Any wagers on how long this will take? :)
  11. zokum

    Things about Doom you just found out

    A close range just makes it statistically more likely that a specific target will be hit with multiple rays. The actual range from impact doesn't matter. This is unlike how most aoe/explosive weapons work in games. With those you get hit if you are in a certain area, often with less damage applied when far away from the center. With the bfg you may get hit in position X, but not in position Y, even if Y is closer to the player. It's not random. A bfg secondary firing is more like a cross between a doom shotgun and a rail gun. You either get hit by a ray or don't get hit. If you call a bfg an aoe weapon, you would also have to call a shotgun an aoe weapon. An important part about BFG usage is knowing that since those tracers do not have travel time, a well timed shot can hit an oponent far away instantly. In deathmatch using the rays to kill someone is the primary use of the weapon. When that is how it's used, thinking of it as an aoe weapon just breaks down as a model. A well-known example is the map01 ledge kill. Aim a bfg ball straight from the chaingun hall down towards the plasma room. Quickly go to the other end of the hallway, and have your back to the start ledge. You can hit a player up on that ledge when the main bfg ball detonates. How much damage the other player takes, depends on how many, if any rays hit that player. Sometimes you're luck in deathmatch and hit a player very far away with a ray. This happens on map07, especially in games with more than one player where it's often an acceptable strategy to fire of a continuous barrage of oportunistic BFG shots in order to score a cheap kill. In my opinion, the BFG is a very quirky weapon, and very hard to master compared to the usual fare. Grenade weapons come close, with bouncing and 'mine laying' potential.
  12. zokum

    Things about Doom you just found out

    The distance doesn't matter. How many rays that hit is all that matters. In a crowded room with monsters covering the screen, all rays will easily hit something. The BFG is not an area of effect weapon, it is a single target projectile + a shotgun like spread from the player when the ball detonates. If you are very close to a monster, and the angle is right, all the tracers will hit that monster. Range does not play a part. It's all about statistics, it's easier to not waste any rays when you got the screen covered with a single monster, and the effect is also more noticable.
  13. zokum

    Things about Doom you just found out

    Doom 64 uses a classic technique. The Lemmings games used a similar scheme, you can find some info about it here: http://www.the-spoiler.com/OTHER/Psygnosis/lemmings.2.html
  14. zokum

    ZokumBSP development

    I have a few broken things I need to fix for 1.0.10-rc1. * Something breaks on 32bit systems or newer gcc, producing very odd nodes. * Some minor errors here and there caught by linters that need fixing. * Screwed up progress bar on non-vt220-style terminals. (Win32 etc). Once these are handled, I think I will release 1.0.10-rc1. I have already started working on a new case study, compiling data for multi-tree builds of most Doom 2 maps. There are some pretty interesting numbers.
  15. zokum

    ZokumBSP development

    @kb1 I don't know of any such tricks either. I have however added a few. It's now really easy to speed up the speed on scrolling walls and make scolling walls have a type. You can now have scrolling walls that are switches, doors, etc easily. I've also added some bam trickery, neat for secrets or the infinite sky trick. The documentation explains it all. There's more to come later :) I have some ideas, hehe.
  16. zokum

    ZokumBSP development

    How the progress bar works for BSP generation (nodes). Single-tree algorithms: I have added a new way to calculate progress for the BSP calculations. This only applies for single tree computations. The new mode will take into account how many segs have been assigned to a subsector compared to the total amount of segs in the map. There is a short delay before it gets to the bottom of the tree and creates the first subsector. The good thing about this approach is that unbalanced trees do not make the progress bar progress unevenly. Segs splits will create more segs. To avoid a progress bar going backwards, progress is therefor only updated when the fraction of work done is higher. This results in a very smooth progress bar that accuratly reflects the progress with a fairly even speed. Multi-tree algorithm. The second method is used when the multi-tree algorithm is used and width is 2 or higher. Here it will look at how much of the tree has been computed, down to 7 levels deep. This method can give a somewhat erratic progress bar when the tree isn't balanced. A bigger unbalance leads to a more uneven progress. The progress bar in this case represents how much of the actual tree is complete, without considering the amount of children a node has, or the amount of segs. This is needed to avoid the progress bar going up and down when new subtrees are being tested, compared and possibly rejected or used as a replacement for the old best subtree. Common for them both is support for colors invoked with -c. If one uses -cc instead, 24bit color output will be produced. In the current beta this is what 24bit color looks like: Hopefully this makes it a bit more clear what exactly is going on and why the progress is a bit wonky when using the multi-tree algorithm. 24bit color will make it easier to color code the limit and changes data without having to resort to a few threshhold values. The reason that the reject data is green here is due to the value being slightly lower, but being rounded off to 100.00%. The real value is probably something like 99.99999596%. This is also something I will look into. If a value is lower, but rounded to 100.00% i could just display it as 99.99%.
  17. zokum

    A quick thought on the "Is Doom 3D" debate

    A vertex in Doom has a specific X and Y stored, that is correct. However, this can be viewed as a form of compression. The Z-coordinates of all the vertices in that X,Y position can be derived from the height of sectors. Walls are rendered spanning from a X,Y,Z coordinate to another X,Y,Z coordinate with quad-polyogons. This is what it looks like in-game, any optimizations, clever trickery, etc doesn't change that. You can clearly find a X,Y,Z coordinate for any pixel in the 3D part of the game. The only 2D stuff are things like the status bar, automap, menus etc. Quake 3 Team Arena has an outdoor terrain map mode, allowing for really big map via the use of terrain maps. As far as I know, you can't have terrain in different heights at the same x,y-position. Dos that make Q3TA a 2D game?
  18. Without having looked into this problem very much, here are some ideas: I would assume that in most cases, the drawing order doesn't change much, any algorithm that has good performance on mostly sorted data could excel. You could use this algorithm in most cases and switch to a special case algorithm the when view / position has changed drastically (teleport). The sorting algorithm should take into account the accuracy of the z-buffer or whatever means you use in software for clipping. Sorting more accuratly than what is possible to render might be pointless. Lower precision might lead to flickering, but that would only happen on somewhat distant sprites. Do you really need to update the sprite order on object that are really far away every frame? If their rendering ends up being only 2 pixels tall, I'd rather have a better frame rate than theoretical high accuracy. Split your sprites into three categories. Close, distant, really distant. Always sort close and one of the other categories for each update. There might be need for some trickery for adjusting the partition between distant and really distant, to even out the load. Multi threading this could be a possibility, the sorting can run while other things in the engine are done. This won't work on ancient machins, but relatively few people run "horde" maps on low-end machines so old they do not have some form for threading/multi core-support on the cpu.
  19. zokum

    ZokumBSP development

    Your point is actually pretty important. The nodebuilder process is mostly voodoo to the average mapper. There are pieces in my code with ZenNode origins I still don't want to touch. There hasn't been much research done on making better node builders. I've been working on and off for some time on improving the algorithms. I have also tried to document my research in the manual and on the web site. It's not exactly brilliant, but people like @Vorpal have made guides and helped me with the web site etc. That stuff helps a lot! If there's any documentation you feel is lacking, or concepts that could use some clarification, I might be able to do something with that :) A lot of the color and output stuff is done to make it easier to understand the output. If you're working on making cutting-edge large doom maps, the %Limit-column will tell you exactly how close you are to the maximum size. I have also updated the manual with a bit of information. There will also be a wad showing a few special effects included. I just finished a nice optimization. Map11 is now down to 291 seconds, from 326 seconds last week. There are still a few nice optimizations that can be done which will lower this even more. After that though, things will be harder to optimize. I have one idea for an optimization I want to try out. If a seg is an edge (all the other segs in the map are on one side), it's unusable as a partition line. No matter how many subdivions we do further down, it will always be unusuable as a partition line. By flagging such lines, we could perhaps cut down on a lot of partition testing.
  20. zokum

    ZokumBSP development

    I recently added truecolor support which uses 'Romero Blue', similar to the color scheme in the original setup.exe. Using this also enables a gradient style progress bar. This will most likely only work on Linux.
  21. zokum

    ZokumBSP development

    I am working on optimizing a few things in ZokumBSP for the multi-tree algorithm. The nodebuilder subsector creator algorithm has a sorting of the segs for in the order of the lowest linedef first, as some special effects require this. I am not sure which ones, if anyone knows, do tell me more about this. However, this is normally done for every subsector, and if this subsector is discarded, the sorting was pointless. It shouldn't be hard to do the sorting afterwards. I hacked up a quick test where I computed map11 of doom 2 WITH the current sorting: MAP11* Lump Old New %Change %Limit Time Elapsed Segs 1276 => 1273 99.76% 3.88% Subsecs 403 => 366 90.82% 1.12% 335.310 secs And here is a build where i simply commented out the call to qsort: MAP11* Lump Old New %Change %Limit Time Elapsed Segs 1276 => 1273 99.76% 3.88% Subsecs 403 => 366 90.82% 1.12% 326.254 secs Currently ZokumBSP does a lot of stuff in-place when making the nodes structure. By delaying the computations till the main nodes structure is done, we can do those doing operations only once, instead of thousands of times. In most of the cases, the result will be discarded, due to another tree being better. This one is only ~2.5% faster, but if we can find a few more such optimizations, it starts to get very noticable. In case anyone is wondering. Doing a complete nodebuild without width-algorithm of map11 takes 0.02 seconds with sorting in place. The sorting algorithm is only a tiny fraction of the time spent building the map. There are a few more of these optimizations that are possible. These kinds of optimizations move work out of the main nodes-loop and into separate work loads that run sequentially afterwards. I reckon the next one, a possible vertex-optimization will reduce memory consumption and speed things up somewhat more noticably. They also reduce code complexity, so they're a win-win in more than one regard.
  22. It's actually not a trivial problem. I would have to code something that understands the Doom texture definition entries. And it would also mean that when building a map, you would also have to supply any additional texture wad(s) you are using. I'm gonna spew a bit of "thoughts" on BSP I have had lately in the ZokumBSP thread. I have a few ideas and pointers on how to improve the build process.
  23. Actually, not generating segs for lines that have the same sector on both sides is a bit of an optimization when it comes to segs. ZokumBSP can also does such stuff for a few more edge cases, like removing sides facing a wall that is 0 units tall and doesn't have a tag nor is connected to any know linedefs with a special Dx type. It should however be possible to programmatically "merge" lines split by trigger lines in the node builder IF the texture alignment is correct. That's a pretty problematic one though, since you'd have to know the width of the texture. That is not a trivial question when custom textures are involved. I don't see any point in adding any code for this, just put the vertex 1 unit away from the wall and the problem is gone. ZokumBSP does have an option for merging split lines in the blockmap. On map01 in Doom 2, this replaces the alternating textures in the main corridor on the map with solid long lines, simplifying collission detection and allowing for bigger maps. This is done in the geometry step, before the blockmap is built.
  24. zokum

    What the fuck's a nodebuilder?

    I have painstakingly kept all of the old ZenNode argument stuff working. The algorithm and handling of command line isn't very pretty and people / tools might have invoked Zennode in an unintended way, and that MAY have broken something when using ZokumBSP. Do you have an example of a commandline that works in Zennode, but breaks in ZokumBSP? I've tried to let the default settings be sane settings that will build a usable map within a reasonable timeframe. There are a lot of knobs to tweak if you're interested in tweaking the process. The help screen is a bit unwieldy, I'd use the documentation instead.
  25. zokum

    What the fuck's a nodebuilder?

    I wouldn't use Zennode for anything these days. ZokumBSP is a fork of Zennode with a lot of enhancements and bug fixes. It will build maps that Zennode would crash on. It will also in many cases do a better job due to better and enhanced algorithms. The level of Boom support is roughly the same as Zennode's, it's not something I have tested at all, instead focusing on Doom support. Hexen, Heretic and Strife are also untested. @riderr3 I am bit puzzled by "Al´╗┐so in my WIP mapset I've encountered HOM when used ZokumBSP, so I've afraid to use that nodebuilder before it being stable." Homs are very rarely an artifact caused by improper nodebuilding. They're usually caused by improperly designed maps or too complex maps. If the maps are too complex and you're hitting the drawsegs-limit, try using the segs-reduction emphasis. This might lead to slightly more subsectors, and possibly more visplanes. I would love to get my hands on a map that has HOMs in ZokumBSP but not BSP or Zennode, so if yours got that, please send it to me. ZokumBSP should be considered stable, and it also builds maps more correctly than DoomBSP, Zennode or BSP does. Just use the latest beta, the only known problem is with output to the screen on some windows terminal types. It was put out as beta quickly due to problem with bad angles on segs. This bug is present even in Id's maps. Rebuilding with ZokumBSP fixes the maps with this bug.
×