zokum

Members
  • Content count

    84
  • Joined

  • Last visited

Everything posted by zokum

  1. Sorry for necro bumping, but I just finished a new ENDOOM screen for a project. You'll hopefully be able to see it "soon" :) I spent maybe 8-10 hours on it.
  2. There's an article about av map 01, 03 and 20 on my ZokumBSP project site: http://doom2.net/zokum/zokumbsp/case-av TLDR for av map20: *MAP20 : BLOCKMAP - 51408/65114 (78.95%) Compressed: 84.85%288.083 secs Two things should be noted. This is done with an older version than what is on GitHub, so the output is harder to read and I am aware of techniques that can make this go even further down, but these have a few drawbacks. :)
  3. E - strafeleft R - strafe right W - move left, strafe on A or F - use (sp) space - move back, use (dm) Mouse handles move forward and shoot as well as turning and glide moves. If a Doom port doesn't support this, it's inherently broken and not usable for serious play.
  4. One of the reasons I made ZokumBSP was to enable the construction of bigger vanilla-compatible maps. It should be possible to make even more complex maps than previously possible. AV map20 is a good example of a near-limit-map that with better tools is much more comfortably below the limits. The BTSX guys are aware of my fork of ZenNode, and they might have to use it on some maps. I am working on some other tweaks to the code, but it's currently not working like I hoped it would. Once I get it to work, building even bigger maps could be possible due to better optimizations of the node tree. We're nowhere near the theoretical limit for vanilla-compatible maps, there's been far too little research done in this field.
  5. Doom uses palette 0, 2-8 and 10-13. 1 and 9 are unused. There's also an error in the palette format. The format is 24 bpp, but vga only supports 18bpp so there could be some rounding down. The two unused ones should lower it by about 500. The rounding error is a bit harder to calculate properly.
  6. I don't think you have removed all the duplicates.
  7. For a good demonstration what can be done with color cylcing and palette swaps, take a look at: http://www.effectgames.com/demos/canvascycle/?sound=0 Try looking at the same image with different palette versions. the image is the same, only the colors change. It should be possible to make a doom wad with a custom palette where you would only see certain details when you're wearing a rad suit or taking damage. A very simple demonstration of this would be to map a few colors to all black in the default palette, but when you're wearing the raid suit the colors map to different shades, allowing you to see hidden writing. Step it up a notch and you could hide demonic messages and pentagrams that only show up when you take damage...
  8. The duplicate entries are because id screwed up, I don't remember the exact number. The palette is less than optimal. It's a lot better than Wolfenstein 3d, which uses the default colors from Deluxe Paint, this explains the slightly odd color scheme in that game. The 18 bit stuff is part of how some VGA mode(s) work. Doom tells the graphics card which colors each index is mapped to. So when you get hit in Doom by a bullet, pick up an item, wear a rad suit etc, all it does is upload a new palette and draw with this palette instead of the default one until it swaps to another palette again. This technique is called palette swapping and is very common in many games of the era. Doom doesn't really tell the gfx card to render something in red or dark red, it tells it to render that pixel with the color in palette position X. Change the palettes and you change the color of the entire game. Storing each color as 18 bits would probably be easier on the hardware they had at the time and would use less memory. Since you can only use 256 different colors at once anyway, there wouldn't be much added fidelity in going from 6 to 8 bits per channel. If I'm not mistaken older versions of doom use mode 13h while later uses a 'mode x'. Read up on Abrash Black Book for more information about this, it's freely available as pdf.
  9. If I'm not mistaken Doom has up to about 250 different colors on the screen at any time, most/all the different palettes contain duplicate entries. The colors are chosen from a 18 bit color space, 6bits per color. So 262144 different colors to choose from. If one adds all the colors from all the palettes it uses and remove duplicates I reckon Doom has somewhere between 1200 and 1500 different colors. Regular + green tint + pickup tints + blood tints. It would be interesting to see if anyone could parse the wad file color palette entries and give us the exact result.
  10. I'll check if this applies to ZokumBSP, and if so, try to fix it. Nice info!
  11. I would have to look at the source, this is pure speculation, but it would be an awesome hack to allow for much larger maps. If we have a map that covers say 64*64 blocks, could we then define the blockmap to be 256*320? Put the actual play are at the upper right corner of this area, from blocks X: 192-256 and Y: 256-320 and shove all the lookup lists in the first ~65k bytes (minus header etc). This could lead to crashes / problems IF there are objects outside the normal play area. Actual numbers will vary, but we can use these as a rough estimate. Care would have to be taken to handle all the wraparounds of 16 bit data. If this works, a maps could easily be much bigger, since it would mean that only the linedef lists have to be kept within the ~65k limit. There would have to be some tweaking of coordinates, translating them to a different location to fit all of this, but a blockmap rebuilder could in theory do all that automatically. This would of course mean that some of the lookup pointers are "garbage" since they're really list data. As long as there is a FF end marker at the end of the blockmap, we'd hopefully have a worst case of slow lookups when travelling outside the 'playable map area'. There's also the idea of interleaving the data in such a way that the lookup offsets also happen to be valid lists, putting end markers outside the normal play area or relying on a header that is valid to parse. This would mean the blockmap builder would rearrange the linedefs numbers etc. You'd start by putting as much data inside the lookup lists as possible, and only fall back to putting lists in the list area when there's no good positions left in the offset area.
  12. I am well aware of the thread. My point is that the optimizations are all theoretical while ZokumBSP does some of those things, and stuff not mentioned in that thread.
  13. I got to clarify some errors here. The 256 block width problem isn't as far as I know related to the blockmap. It is caused by the data types not handling values bigger than 128*256, 32768, something that was mentioned earlier. The blockmap on disk limit is roughly 64kib. It can be bigger, but no "offset" kan point to data over this limit. The first element in the list has to be within that 64kib range. Ports that generate blockmaps internally can screw up special effects and will ruin demo compatibility in many cases. ZokumBSP has code to produce more efficient blockmaps than ZenNode due to fixing errors and using various optimization techniques. Further compression can also be done by removing non-collidable lines, skipping the 0-header and by manually excluding lines from the blockmap from the map editor by using special linedef types. This allows one to in many cases greatly decrease the blockmap size and speed up the game. A clever mapper could easily hand-edit a map to reduce the blockmap by using tricks such as removing the linedef of door backsides if the door has a stay open type and is only approachable from one side etc (exit doors etc). Many decorative elements also have lines one cannot collide with. A good example here would be some of the sides of the bars on the Doom 2 map06 elevator. It's very unlikely that you can collide with those facing the wall. If I had to choose between the wad crashing the game and not colliding with those lines, I know what I would choose. Johnsen also pointed out to me that a lot of maps have details in the ceiling but not the floor, to avoid affecting gameplay. Such lines can in many cases also be removed from the blockmap.
  14. The amount of segs have to do with the architecture on your map, diagonal lines do not inherently cause more splits. Splits on diagonal lines are however more problematic, since they might lead to slime trails. It's generally easier to avoid splits IF you have no diagonal lines OR all lines are diagonal and only heading along two directions, being offset 90" to eachother. Basically a non-diagonal map rotated. ZokumBSP has code to reduce visplane causing subsectors OR segs. The user can optionally tweak which parameter to go for. If the map is close to the SEGS limit, using that metric could help you reduce the SEGS count. The latest tweaks aren't out as a beta or rc, but source is available at GitHub. For more info contact me on irc and read the docs and info at http://doom2.net/zokum/zokumbsp/
  15. The best thing about this thread is the myriad of ways I am learning about how to be an asshole to people using ports that break the gameplay in Doom. Loads of things in this thread will come in handy when I work on vanilla maps. :) Keep the ideas and findings coming, I'm loving it!
  16. You're free to compare whatever you want, but it might not always be the best comparisons :D
  17. I think it all depends on what we precisely mean by the various term. I've always thought of it as Doom, Doom 2, Final Doom as one branch. Heretic and Hexen as another, Strife as a third and chex quest, hacx etc as other branches. I agree that Hexen has a lot of changes, but it is a sequel set in the same universe, by the same developer, using an updated engine based on the previous game, just like Doom 2 and Final Doom etc. I think it's a bit arbitrary to allow for the inclusion of all the 3 games in the original Doom trilogy and disallow Hexen. And like many have pointed out, Doom 2 does have a slight mission pack feel to it, and Final Doom even more, but they are still standalone games with a lot of new content, and more maps than the original games had. As for flaws in Heretic, there's substantially less artwork in the game compared to Doom. The color scheme is a bit too colorful and cartoony for my taste. It often feels like it's doom, with a twist, which isn't always an improvement over the original. To me the gameplay was slow, it lacked the speed and instant feedback you had with chainguns and shotguns. I find the overall theme in Doom to be more interesting. And by the time Heretic was out, id had released a sequel that had much better deathmatching and much grander and bigger maps than the original game had. The original Doom didn't really ship with any good deathmatch maps, Doom 2 did. Heretic was for me always more of a single player game, which is fine. They really refined the fantasy in a 3D engine-concept with Hexen. I have barely played Heretic and Hexen, The Doom games I have played on and off since the mid 90s. I think one of the main reasons Doom has a lot more artwork is that it is often based on retouched photographs, instead of having to painfully slowly draw everything from the ground up. This made it possible to quickly get a lot of quality artwork into the game. Heretic does suffer a bit from that, having much less varied scenery and a less realistic feel to what is in the game. Heretic is a more whimsical and humor-filled game, with it's bright sprites and powerups that turn monsters into chickens. That doesn't appeal as well to me, I prefer the more serious tone found in Doom. That is one of the reasons why I dislike Duke Nukem 3d, Redneck Rampage etc. I can laugh at things in Doom, but that is from funny situations that emerge from serious settings, not a more canned laughter approach of turning monsters into chickens.
  18. Because Doom and Doom 2 are different games. Original and sequel. Hexen is the sequel to Heretic. The games diversified from the original source, the Doom engine. Heretic added some things, Doom 2 other things. Hexen added more to the Heretic engine. Why do we allow for Doom's sequel to be considered the same, but not Heretic's sequel? The topic says Doom, not Doom 2 or the original Doom trilogy. John Romero was the producer of Heretic and he most likely wanted the games to go in different directions. Some ideas went into Doom 2, some into Heretic. After the success of Heretic, they further refined the concept, just as with Doom to Doom 2, and made Hexen. He clearly didn't want a simple fantasy reskin of Doom. Heretic is much more interesting evolution of the Doom engine than Doom 2 was. Some of the potentially coolest bits like horisontal doors just didn't work. As for Doom 2 VS Doom, Doom 2 also lost a lot of stuff that Doom originally had. Episodes, progression map, left and right views in v1.0 etc. Doom 2 is a much more bare bones experience than Doom, with focus on good abstract levels and a larger cast of monsters and textures. I'd say Raven's definitive 'Doom engine' is the Hexen engine, not Heretic. I'm not a big fan of Heretic myself, but the engine is a nice twist on the Doom engine. The gameplay and design just isn't quite my cup of tea.
  19. I haven't read every post in this somewhat odd thread. If you're comparing Heretic to Doom, compare it to Doom, not Doom 2 or The Ultimate Doom or Final Doom etc. If you're gonna throw in the sequels, you should also add Hexen to the feature set of Heretic. Hexen is quite a bit more advanced when it comes to linedefs than any of the original Doom trilogy games. As for linedefs, Heretic inherited Doom's, and did some minor tweaks. Doom 2 added a whole load of new ones, and those are also used in some of the episode 4 stuff in The Ultimate Doom. The "non door" switches in Doom 2 are merely doors with a different message. Just go check the yellow-skull switch on e4m2.
  20. TLDR: A new way to build doom maps, spend more time, and you might just get a better built map. Spend a lot of time on your final build for release for a better result with fewer bugs and higher frame rate. Possibly less VPO and HOM as well. I have been working on a new and novel approach for node building in ZokumBSP. Node builders generally pick one dividing line and use that one to split the play area in roughly two equal parts. Each line picked after that splits the remaining are on each side of the parent line into two more areas. Picking the best splitting line is very important and is something a node builder needs a good algorithm to do well. Initially I wanted to check how good the algorithm was and added a small hack to pick the second best line at every decision. As expected this was produced overall not as well built trees, but not in all cases. For Doom 2 map07, the tree was noticably better. Obviously one or more of the top picks was not the best one with the default algorithm. So after a lot of testing and tweaking I finally figured out a decent approach to checking more than one line. I basically treat the node builder as a state machine and makde backups of all the important data, build a left and a right sub tree, then restore the state, pick a different line and build two more trees. This approach makes the node building time sky rocket. The approach I got is far from ideal and there's a lot of room for speed optimizatiosn, and there might be subtle bugs in the code. Only time and testing will tell. I had already tweaked the old Zennode algorithm to produce better results. Here are my results of how it fares when node building all of doom2.wad: MAP01 Old New %Change %Limit Time Elapsed Segs: 601 => 593 98.67% 1.81% * Subsecs: 194 => 182 93.81% 0.56% 0.017 secs MAP02 Old New %Change %Limit Time Elapsed Segs: 797 => 772 96.86% 2.36% * Subsecs: 224 => 208 92.86% 0.63% 0.015 secs MAP03 Old New %Change %Limit Time Elapsed Segs: 980 => 962 98.16% 2.94% * Subsecs: 301 => 280 93.02% 0.85% 0.023 secs MAP04 Old New %Change %Limit Time Elapsed Segs: 812 => 806 99.26% 2.46% * Subsecs: 249 => 226 90.76% 0.69% 0.018 secs MAP05 Old New %Change %Limit Time Elapsed Segs: 1391 => 1368 98.35% 4.17% * Subsecs: 409 => 387 94.62% 1.18% 0.041 secs MAP06 Old New %Change %Limit Time Elapsed Segs: 1551 => 1530 98.65% 4.67% * Subsecs: 484 => 462 95.45% 1.41% 0.052 secs MAP07 Old New %Change %Limit Time Elapsed Segs: 325 => 317 97.54% 0.97% * Subsecs: 97 => 97 100.00% 0.30% 0.004 secs MAP08 Old New %Change %Limit Time Elapsed Segs: 919 => 915 99.56% 2.79% * Subsecs: 276 => 264 95.65% 0.81% 0.026 secs MAP09 Old New %Change %Limit Time Elapsed Segs: 992 => 965 97.28% 2.94% * Subsecs: 325 => 312 96.00% 0.95% 0.034 secs MAP10 Old New %Change %Limit Time Elapsed Segs: 1417 => 1397 98.59% 4.26% * Subsecs: 455 => 417 91.65% 1.27% 0.062 secs MAP11 Old New %Change %Limit Time Elapsed Segs: 1309 => 1276 97.48% 3.89% * Subsecs: 430 => 403 93.72% 1.23% 0.040 secs MAP12 Old New %Change %Limit Time Elapsed Segs: 1277 => 1225 95.93% 3.74% * Subsecs: 423 => 377 89.13% 1.15% 0.035 secs MAP13 Old New %Change %Limit Time Elapsed Segs: 1837 => 1784 97.11% 5.44% * Subsecs: 557 => 511 91.74% 1.56% 0.067 secs MAP14 Old New %Change %Limit Time Elapsed Segs: 2815 => 2752 97.76% 8.40% * Subsecs: 851 => 768 90.25% 2.34% 0.146 secs MAP15 Old New %Change %Limit Time Elapsed Segs: 2647 => 2578 97.39% 7.87% * Subsecs: 875 => 814 93.03% 2.48% 0.148 secs MAP16 Old New %Change %Limit Time Elapsed Segs: 1230 => 1185 96.34% 3.62% * Subsecs: 421 => 382 90.74% 1.17% 0.044 secs MAP17 Old New %Change %Limit Time Elapsed Segs: 1980 => 1962 99.09% 5.99% * Subsecs: 615 => 581 94.47% 1.77% 0.091 secs MAP18 Old New %Change %Limit Time Elapsed Segs: 1132 => 1113 98.32% 3.40% * Subsecs: 416 => 395 94.95% 1.21% 0.042 secs MAP19 Old New %Change %Limit Time Elapsed Segs: 2117 => 2039 96.32% 6.22% * Subsecs: 721 => 667 92.51% 2.04% 0.110 secs MAP20 Old New %Change %Limit Time Elapsed Segs: 1678 => 1614 96.19% 4.93% * Subsecs: 577 => 540 93.59% 1.65% 0.077 secs MAP21 Old New %Change %Limit Time Elapsed Segs: 640 => 626 97.81% 1.91% * Subsecs: 229 => 225 98.25% 0.69% 0.014 secs MAP22 Old New %Change %Limit Time Elapsed Segs: 995 => 993 99.80% 3.03% * Subsecs: 316 => 303 95.89% 0.92% 0.023 secs MAP23 Old New %Change %Limit Time Elapsed Segs: 586 => 579 98.81% 1.77% * Subsecs: 197 => 187 94.92% 0.57% 0.014 secs MAP24 Old New %Change %Limit Time Elapsed Segs: 1954 => 1925 98.52% 5.87% * Subsecs: 697 => 665 95.41% 2.03% 0.109 secs MAP25 Old New %Change %Limit Time Elapsed Segs: 1164 => 1159 99.57% 3.54% * Subsecs: 407 => 389 95.58% 1.19% 0.038 secs MAP26 Old New %Change %Limit Time Elapsed Segs: 1305 => 1288 98.70% 3.93% * Subsecs: 453 => 428 94.48% 1.31% 0.057 secs MAP27 Old New %Change %Limit Time Elapsed Segs: 1522 => 1503 98.75% 4.59% * Subsecs: 484 => 458 94.63% 1.40% 0.050 secs MAP28 Old New %Change %Limit Time Elapsed Segs: 1181 => 1155 97.80% 3.52% * Subsecs: 456 => 443 97.15% 1.35% 0.072 secs MAP29 Old New %Change %Limit Time Elapsed Segs: 1911 => 1862 97.44% 5.68% * Subsecs: 751 => 704 93.74% 2.15% 0.139 secs MAP30 Old New %Change %Limit Time Elapsed Segs: 137 => 137 100.00% 0.42% * Subsecs: 43 => 38 88.37% 0.12% 0.001 secs MAP31 Old New %Change %Limit Time Elapsed Segs: 814 => 805 98.89% 2.46% * Subsecs: 229 => 221 96.51% 0.67% 0.016 secs MAP32 Old New %Change %Limit Time Elapsed Segs: 308 => 305 99.03% 0.93% * Subsecs: 91 => 87 95.60% 0.27% 0.003 secs As you can see, it will generally improve on the size and complexity of every single tree in the game. So with that in mind, I will now show the results of a few more builds. This time I specified to use a width of 2. In order to speed things up, I made it not try wider trees when the depth is above 10. As the algorithm improves, this is something I cand and will tweak. MAP01 Old New %Change %Limit Time Elapsed Segs: 593 => 593 100.00% 1.81% * Subsecs: 182 => 182 100.00% 0.56% 6.051 secs MAP07 Old New %Change %Limit Time Elapsed Segs: 317 => 316 99.68% 0.96% * Subsecs: 97 => 96 98.97% 0.29% 0.592 secs MAP15 Old New %Change %Limit Time Elapsed Segs: 2578 => 2562 99.38% 7.82% * Subsecs: 814 => 798 98.03% 2.44% 66.626 secs Ok, let's try it with width = 3 then, and try to improve on the existing width = 2. Can we do any better? MAP01 Old New %Change %Limit Time Elapsed Segs: 593 => 592 99.83% 1.81% * Subsecs: 182 => 173 95.05% 0.53% 258.747 secs MAP07 Old New %Change %Limit Time Elapsed Segs: 316 => 311 98.42% 0.95% * Subsecs: 96 => 92 95.83% 0.28% 32.398 secs MAP15 Old New %Change %Limit Time Elapsed Segs: 2562 => 2558 99.84% 7.81% * Subsecs: 798 => 766 95.99% 2.34% 3584.205 secs Ok, it seems we are definitively seing that there's more to get, but the total build time was reported as: 3 Levels processed in 64 minutes 35.350 seconds - 3 Levels needed updating. I think a slightly different approach and less stringent cutoff could yield similar data in a more reasonable amount of time. My hunch is that the big decisions early on matter more than the later splits. So with that I tried the following approach: width is X - nodedepth / 3. So if we set it to 4, it would do 4 different split lines until the depth was 3, where it would start doing 3 until the depth was 6 etc. I tried it with 3, very fast but results are not nearly as good: MAP01 Old New %Change %Limit Time Elapsed Segs: 592 => 593 100.17% 1.81% * Subsecs: 173 => 182 105.20% 0.56% 0.693 secs MAP07 Old New %Change %Limit Time Elapsed Segs: 311 => 317 101.93% 0.97% * Subsecs: 92 => 96 104.35% 0.29% 0.136 secs MAP15 Old New %Change %Limit Time Elapsed Segs: 2558 => 2571 100.51% 7.85% * Subsecs: 766 => 807 105.35% 2.46% 6.696 secs Let's try it with 4, see how much better it performs than 3. MAP01 Old New %Change %Limit Time Elapsed Segs: 593 => 592 99.83% 1.81% * Subsecs: 182 => 178 97.80% 0.54% 26.099 secs MAP07 Old New %Change %Limit Time Elapsed Segs: 317 => 315 99.37% 0.96% * Subsecs: 96 => 93 96.88% 0.28% 3.670 secs MAP15 Old New %Change %Limit Time Elapsed Segs: 2571 => 2561 99.61% 7.82% * Subsecs: 807 => 789 97.77% 2.41% 260.086 secs Total build time is a much more reasonable 4 minutes 49.855 seconds. We're not doing as well as the previous approach width = 3, but we're at a fraction of the time spent, 4 minutes instead of 64. Map01 has the same amount of segs, but 5 more sub sectors. Map15 has 3 more segs and 23 more sub sectors. We could be doing this all night, and I have been at this for well, weeks now. There's a lot of interesting things to learn here. Chief among them is to try to make a better heuristic so that the first pick is the best pick, but also to try to optimize the overall approach since there's plenty of room for making maps that are more complex, bigger and has more details visible. Maps with fewer sub sectors could in many cases need fewer vis planes to render. Maps with fewer segs would lead to less HOM in complex scenes. Code has been added to tweak the metric as to what is a better tree. -nm=u for setting fewer sub sectors as the metric and -nm=s for setting fewer segs as the metric. Use what you need to get YOUR map under the limit. If you're interested in beta releases, contact me on irc or build from GitHub sources. None of this is available in the stable releases.
  21. Reminds me, when it comes to vertex pair algorithms, it could be between any two vertices in the map. A nice good-enough optimization would be to only check between those in the same sectors as it is highly unlikely that vertices far away from eachother would make for better split lines without passing through vertices in the same sector anyway. It's on my list of things to research into, but I wanted to get my wider search working first, and there are still some bugs that need fixing, but I got a bit of progress tonight.
  22. I've been looking into different metrics, and I found that going for a secondary characteristic sometimes hurt the primary characteristic. I had initially set it up so that if the metric was subsectors, it would take a line with fewer splits if it existed as long as the amount of subsectors was the same. That turned out to end up with more subsectors in the end due to favoring unbalanced trees. I have considered researching into the root node split (and maybe 1-2 levels more) to favour a good balance over pretty much anything else for a big map in order to greatly reduce the amount of bad divisions in later data. There are cases where a split line might actually be quite unbalanced, but be alongside a line that splits the map neatly into two parts without adding anything in the way of segs or subsectors. So in those cases, cutting off a "perfect" part of the map might look really unbalanced, but would make the remaining areas simpler, thus simplifying the original split. A map like map32 has some of those charateristics. Splitting the map into two alongside the door near the start should not lead to any more sub sectors or segs as far as I can tell, but would be a very badly balanced tree. A perfect uneven split, a split that reduces complexity without adding any complexity in the form of new ssectors or segs. With a vertex pair algorithm, I think a lot of map designs might have many of these. The map01 example i posted a while ago is a good example, and they most likely exist on many other maps, or at least occur often in sub trees.
  23. Yeah, I thought about that as well, at least for the initial splits until you're left with just a few lines. ZokumBSP has code to favour non-diagonal lines over diagonal lines. If all else is equal, it will go for the vertical or horisontal lines :).
  24. Well, if you start with a good set of convex sub sectors, you will end up with the smallest possible amount of splits, possibly none. You could then apply your idea on top of that and end up with the sub sectors created early on.
  25. Scifista42: I still want to do it from top to bottom, but I'd want the end result to be a very good set of sub sectors. Having no splits is all nice and dandy, but fewer subsectors could mean less vis planes. And too many vis planes is a much more serious problem than too many split segs unless one is aiming for a 32kib seg map.