Sign in to follow this  
Followers 0

Immediate noclip at level start

Interesting, it even affects Mocha (both when using its own and the prBoom+ loading code). For now I can say that P_BlockLinesIterator isn't even called at least when the player is in the first room, but clipping works for the distant smaller room. Forcing an internal blockmap rebuild with -blockmap doesn't seem to solve the problem.

The problem was in P_CheckPosition:

        // check lines
        xl = (tmbbox[BOXLEFT] - LL.bmaporgx)>>MAPBLOCKSHIFT;
        xh = (tmbbox[BOXRIGHT] - LL.bmaporgx)>>MAPBLOCKSHIFT;
        yl = (tmbbox[BOXBOTTOM] - LL.bmaporgy)>>MAPBLOCKSHIFT;
        yh = (tmbbox[BOXTOP] - LL.bmaporgy)>>MAPBLOCKSHIFT;
To express the difference between the blockmap origins and your current position, you actually need at least 9 UNSIGNED bits to express a maximum difference of 512 blocks = 512*128=64K map units.

However that signed shift destroys the top bit, resulting in a -256...255 range.

The starting room is actually at a block coordinate > 255 which results in negative block number (xl xh yl yh: -245 -245 0 1) , thus BlockLinesIterator is never called. It's a well-known limitation of the blockmap system which practically limits blockmaps to a maximum of 256 x 256 addressable blocks through MAPBLOCKSHIFT (=23), regardless of map extension.

The isolated room has a block coord of xl, yl : 21 21 so it has no problem clipping properly .

About solving it...a general solution that can remove ALL blockmap limits would require fixing a lot of stuff along the line.

HOWEVER, I came up with a quick and dirty hack:

First, in P_CheckLine, use an unsigned shift so that you get values
from 0..511 instead of -256...255 for the blockmap coords.
        // check lines
        xl = (tmbbox[BOXLEFT] - LL.bmaporgx)>>>MAPBLOCKSHIFT;
        xh = (tmbbox[BOXRIGHT] - LL.bmaporgx)>>>MAPBLOCKSHIFT;
        yl = (tmbbox[BOXBOTTOM] - LL.bmaporgy)>>>MAPBLOCKSHIFT;
        yh = (tmbbox[BOXTOP] - LL.bmaporgy)>>>MAPBLOCKSHIFT;
Then do this simple sanity check: If you get any blockmap coords that are clearly beyond the stated blockmap width/height, then you are actually outside of the blockmap (either too positive or too negative, doesn't matter. The check should be made more refined, I know, to understand whether you have just went from e.g. to -1,-1 from 0,0 in a decreasing fashion or whether you went beyond bmapwidth/bmapheight in an increasing fashion.
        // Maes's quick and dirty blockmap extension hack
        if (xl>LL.bmapwidth) xl=0;         // Broke width boundary
        if (xh>LL.bmapwidth) xh=0;         // Broke width boundary
        if (yh>LL.bmapheight) yl=0;        // Broke height boundary
        if (yl>LL.bmapheight) yl=0;        // Broke height boundary
In any case, this gives you an effective addressable blockmap size of 512*512 blocks, which means that you can now cover the full range of +/- 32K coords (512*128 = 64K). The only problem is that you can't express negative offsets relative to the blockmap, which may affect some tricks that rely travelling through the void. In order to do that you'd have to switch to a 10-bit signed blockmap index, of which you'd use the -512..-1 range to ensure void trick compatibility.

You could however leave the signed shift in-place, and interpret some particular negative values as being indicative of an extended blockmap, and others as simply being indicative of having moved before the blockmap origin.

E.g. for a blockmap of size 257 * 257, an index of -256 should be interpreted as +256, +256 while one of -128 simply as -128, thus preserving negativity. This would also fully preserve the behavior of blockmaps that don't exceed the 0.255 limits.

Share this post


Link to post

Sorry for the double post, but here's a method that seems a bit cleaner:

a) In whatever module you perform the level loading, add these two helper variables:

    // MAES: extensions to support 512x512 blockmaps.
    // They represent the maximum negative number which represents
    // a positive offset, otherwise they are left at -257, which
    // never triggers a check.
    // If a blockmap index is ever LE than either, then
    // its actual value is to be interpreted as 0x01FF&x.
    // Full 512x512 blockmaps get this value set to -1.
    // A 511x511 blockmap would still have a valid negative number
    // e.g. -1..510, so they would be set to -2
    // Non-extreme maps remain unaffected.
    
    public int blockmapxneg=-257;
    public int blockmapyneg=-257;

b) After you have loaded and parsed the blockmap, set them as follows:
        // MAES: set blockmapxneg and blockmapyneg
        // E.g. for a full 512x512 map, they should be both
        // -1. For a 257*257, they should be both -255 etc.
        if (bmapwidth>255)
            blockmapxneg= bmapwidth-512;
        if (bmapheight>255)
            blockmapyneg= bmapheight-512;
c) In P_CheckThings, leave everything as is (including signed shifts), but add these lines before every bx/by iterator (this includes checking for things).
      
// If x is LE than those special values, interpret as positive.
// Otherwise, leave it as it is.
        if (xl<=LL.blockmapxneg) xl=0x1FF&xl;
        if (xh<=LL.blockmapxneg) xh=0x1FF&xh;
        if (yl<=LL.blockmapyneg) yl=0x1FF&yl;
        if (yh<=LL.blockmapyneg) yh=0x1FF&yh;
d) *cough* credit me, if you ever use it ;-) *cough*

I don't guarantee it won't break any vanilla demos, but it seems to fix both the test272 maps and leave vanilla maps operating normally. Then again this is Doom...and we all know how fucked up things can get. In any case, if you simply disable those specific P_CheckThings checks with a complevel or something, it should be fine.

IMHO this leads to much cleaner code and much less intrusive/more easily switchable on/off modifications than the patch mentioned in that other thread, can be implemented in many source ports, and preserves negative indexes, if need be. Of course, a full 512x512 blockmap will have no valid negative indexes (all indexes will be interpreted as positive), while a 511x511 will have at least -1 as a valid negative index, so it's still possible to get into a void region.

Share this post


Link to post

Although this fudging will resolve the blockmap issues, it still won't make maps work right if coordinates are outside (-16383, 16383).

Distance calculations may overflow and cause all sorts of weird glitches, among them problems with the automap, sounds not playing at correct volume, monsters doing strange things and whatever else needs to do distance checks.

The general rule should be that no 2 points in a map are more than 32767 map units apart.

Share this post


Link to post

Yeah, I just realized that this same check needs to be added into pretty much every piece of code that uses >>MAPBLOCKSHIFT, plus there are some more arcane checks in there that are used for actual projectile collisions.

Using the trick above, I managed to make at least the lines and thing pickups of europe.wad to clip correctly even in the troublesome caco ledge beyond y>14176 (after rebuilding the broken blockmap, of course), however monsters shooting at you didn't seem to work correctly just with the changes I made (at least where I could see that >>MAPBLOCKSHIFT was used). Those cacos found on the troublesome ledge could target me, but only hit me if I was below the y=14176 frontier or if they got close enough for a melee attack.

Share this post


Link to post

Although this fudging will resolve the blockmap issues, it still won't make maps work right if coordinates are outside (-16383, 16383).
[...]
The general rule should be that no 2 points in a map are more than 32767 map units apart.


This confuses me. I have a Boom+ map with y coordinates ending up in the 22000 range, would I be better off moving it so it's all within (-16383, 16383), or does it not matter as long as no two points are more than 32767 units apart? Haven't noticed any problems so far, but it could be that I haven't looked hard enough.

Edit: thanks.

Share this post


Link to post
Phml said:

This confuses me. I have a Boom+ map with y coordinates ending up in the 22000 range, would I be better off moving it so it's all within (-16383, 16383), or does it not matter as long as no two points are more than 32767 units apart? Haven't noticed any problems so far, but it could be that I haven't looked hard enough.


The latter.

Share this post


Link to post

Update: I checked a bit more carefully and now I got both pickups, monsters and monster projectiles to work with the extended blockmap system. Essentially, you only need to do what I said: search for where >>MAPBLOCKSHIFT is used, and apply those special checks to whatever depends on them.

E.g. to properly set things on the map in P_SetThingPosition (pardon the Javisms):

        // link into blockmap
        if (!flags(thing.flags, MF_NOBLOCKMAP)) {
            // inert things don't need to be in blockmap
            blockx = (thing.x - bmaporgx) >> MAPBLOCKSHIFT;
            blocky = (thing.y - bmaporgy) >> MAPBLOCKSHIFT;

            if (blockx<=blockmapxneg) blockx=0x1FF&blockx;         // Broke width boundary
            if (blocky<=blockmapyneg) blocky=0x1FF&blocky;    // Broke heightboundary

This enables both correct pickups and correct monster clipping.

Now, I gotta check if more weird things like sound distances etc. don't work correctly. Other things that use blockmap shifts are archvile iterators, teleporter checks, etc. and any function updating thing blocklinks. They are only a few well-defined ones actually, and the blockmap doesn't seem used outside of the P_ modules anyway. The only way it might affect the sound system is in P_GroupLines, where there are also shifts.

Share this post


Link to post
Graf Zahl said:

Distance calculations may overflow and cause all sorts of weird glitches, among them problems with the automap, sounds not playing at correct volume, monsters doing strange things and whatever else needs to do distance checks.

How about, um, using an unsigned type?

Share this post


Link to post
Maes said:

Now, I gotta check if more weird things like sound distances etc. don't work correctly. Other things that use blockmap shifts are archvile iterators, teleporter checks, etc. and any function updating thing blocklinks. They are only a few well-defined ones actually, and the blockmap doesn't seem used outside of the P_ modules anyway.

Have you considered the "telescratching" phenomenon seen in void-glide demos? It must be due to overflows in the distance check. You won't get away with modifying just blockmap functions.

Share this post


Link to post
tempun said:

How about, um, using an unsigned type?



Do you want to find all places in the code where this may be an issue. Good luck hunting!

Phml said:

This confuses me. I have a Boom+ map with y coordinates ending up in the 22000 range, would I be better off moving it so it's all within (-16383, 16383), or does it not matter as long as no two points are more than 32767 units apart? Haven't noticed any problems so far, but it could be that I haven't looked hard enough.

Edit: thanks.



To be on the safe side, do not go beyond ca. 24000 but centering the map will certainly reduce some potential overflows. I can remember that some maps in the WolfenDoom mods - mostly Astrostein and Arctic Wolf had maps with abnormal coordinates and they did have issues with it.

Share this post


Link to post
tempun said:

Have you considered the "telescratching" phenomenon seen in void-glide demos? It must be due to overflows in the distance check. You won't get away with modifying just blockmap functions.


Only testing can show that. At first sight, it may appear that CheckMeleeRange doesn't use blockmaps at all, but it depends on ApproxDistance and if that gives the green light, it also checks the REJECT table for a final chance of aborting a melee attack. Assuming that ApproxDistance isn't periodic or unstable (?) at extreme distances, this leaves the EN_CheckSight function to blame.

However EN_CheckSight uses thing.subsector, which is set by functions that do depend on the blockmap such as SetThingPosition and UnsetThingPosition, so by induction, fixing blockmap aliasing problems should also eliminate telescratching, if it's dependent ONLY on the blockmap.

Of course, if telescratching is purely (or also) the fault of ApproxDistance, then just fixing the blockmap won't be enough. But shouldn't fixing nearly everything else blockmap-related be worth something?

Edit: a convenient way to add the check is to use these helper functions whenever you need to convert a coord to a block:

    public final int getSafeBlockX(int coord ){
        coord >>=MAPBLOCKSHIFT;
        return (coord <=this.blockmapxneg)?coord &0x1FF:coord ;
    }

    public final int getSafeBlockY(int blocky){
        coord >>=MAPBLOCKSHIFT;
        return (coord <=this.blockmapyneg)?coord &0x1FF:coord ;
    }
E.g. instead of doing this:
blocky=(bbox[BOXTOP] - bmaporgy + MAXRADIUS)>>MAPBLOCKSHIFT;
do this:
blocky=getSafeBlockY(bbox[BOXTOP] - bmaporgy + MAXRADIUS);
In C/C++ you can easily use a macro/ifdef to select either the one or the other with ease, so it should be easy to experiment with it.

Share this post


Link to post

Fixing the blockmap in the way I proposed should not affect maps not exceeding the blockmap limits in a detectable way, so such maps would not change behavior. Maps that DO exceed the limits and rely on negative blockmap indexes being interpreted as always negative will of course be affected.

Actually, if a blockmap index ends up being negative or greater than the blockmaps' bound, normal Doom code will simply ignore it. This will cause of course checks to be skipped, objects not to be linked and so on. In any case, the way I proposed to do it it's an easily toggleable fix, I see no reason why it could not be part of e.g. the next prBoom+ version.

Share this post


Link to post
Maes said:

In any case, the way I proposed to do it it's an easily toggleable fix, I see no reason why it could not be part of e.g. the next prBoom+ version.

Toggleable fix for toggling between what? We can do such things only for the next complevel, but it has no sense, because nobody (should) play without complevel and new complevel will never be introduced I think. We only could 'fix' it for all complevel if doom/boom would crash on such situations (then we 'just' fix a crash)

Share this post


Link to post
entryway said:

Toggleable fix for toggling between what?


For toggling between 0...255 and 0..511 blockmap size limit. In any case, it can be a simple "Enable extended blockmap support" switch hidden somewhere in the menus which is not enabled by default on any of the existing complevels. Anyone wishing to use it will be able to do so, and that's about it.

Share this post


Link to post

Actually, I don't think that is what you should be toggling. Fix the blockmap outright, as you suggest, then apply your option to the boundary clip geometry (changing the dimensions). This way, you can change the option in-game without having to rebuild the blockmap.

Share this post


Link to post

The thing is, there will still be problems that come up related to the 32K distance limit, right? Even with this blockmap fix. As long as there are issues and glitches that come up when you make maps "too big", the only solution is still going to be to keep the size down.

So it would seem to me that this particular fix creates another layer of compatibility level cruft without adding any new capabilities, as the practical map-size limit is still about the same.

(This is basically the conclusion I came to after my "5 minute fix" both desync'd many existing demos as well as still had glitches, just not quite the same ones, on huge maps.)


Now if a solution was thoroughly tested on 60K x 60K size maps, then that's different.

Share this post


Link to post

The only *real* fix for something like this is to say fuck compatibility and use floating point coordinates.

Share this post


Link to post

@DaniJ

Ehmm.... fixing the blockmap needs to be done anyway in the case of Europe.wad (and possibly other maps) simply because it's too big to fit in 128Kbytes, which is the on-disk structure's limit. If somehow a fixed blockmap could be saved on-disk by existing tools (and supported by ports), then that part wouldn't be necessary.

However, even if you save it and load it correctly, the problem with the block indexes at runtime lies in the way they get interpreted by the vanilla code (and all of its derivatives): the blockmap should be able to be addressable with 9 bit indexes, since there can be 512 blocks per map dimension (512*128 = 64K), however they way most routines are written interpret the 0..511 range as -256...255, and negative indexes get clipped outright by most -if not all- standard vanilla Doom routines.

So a fix during runtime is still necessary, otherwise you hit blockmap-related limits even with a 100% correct blockmap, simply because the routines can't use indexes >255 correctly. The map entryway posted is a perfect example, without having the complexity of something like Europe.wad

@natt: By fixing every part in the code where coordinates in 16.16 format are transformed into blockmap indexes, this automatically solves all problems caused by some of them being treated as negative numbers (which should normally never occur). So anything depending on the DIFFERENCE between blockmap indexes will now be correct, since negative numbers can't occur when they shouldn't, and most operations done on blockmap indexes are done through 32-bit integers, which can very well accomodate a 9-bit unsigned value.

Of course there might be other sources of errors not related to the blockmap, but that's not the point. Entryway asked how this particular problem can be fixed, and hey presto, here's how.

The only other way the distance limit may "strike", once the blockmap is out of the equation, is the behavior of the ApproxDist function. Once I or someone else produces a plot of it which demonstrates how/if it can fuck up, then yeah, we have a case.

The most obvious one is that it takes two signed coordinates in 16.16 and it returns a SIGNED result in the same format. Of course this limits its usefulness to distances not exceeding 32K. The only way to fix that would be to rewrite it completely, and also change any code using it. A relatively minor fix would be to clip its maximum output to 32K so that it doesn't ever return negative numbers, or interpret it as an unsigned 16.16 number rather than a signed 15.16.

Share this post


Link to post

@Maes Ah, I see you are talking about the situation where you want to preserve the use of the existing BLOCKMAP data? In that case yeah, doing it up front makes sense I suppose.

I really should refrain from getting involved in these discussions because we do things so very differently in Doomsday, I tend to forget how vanilla works on a technical level.

Share this post


Link to post
Maes said:

For toggling between 0...255 and 0..511 blockmap size limit. In any case, it can be a simple "Enable extended blockmap support" switch hidden somewhere in the menus which is not enabled by default on any of the existing complevels. Anyone wishing to use it will be able to do so, and that's about it.

I think the only place for such fixes is:



They do not applied during demo recording.

Share this post


Link to post

@DaniJ: even using the extended blockmap that all Boom and MBF derivatives build internally is not enough to remove those limits we're talking about. Similarly, I'm not familiar with how Doomsday works and whether it would be able to run entryway's test272.wad without a problem. Can it? However standard Doom and Boom surely can't, even with a fixed blockmap lump, because the problem is actually in how runtime indexes to the blockmap are computed, and it's all over the damn code. Has Doomsday modified this aspect? E.g. you are not affected by the MAPBLOCKSHIFT bug at all?

@entryway: yeah, that would be a perfect place if it was made into a run-time toggleable feature.

That's another interesting part: by adopting the fixes I proposed, you are simply switching between blockmap index interpretations, without changing the blockmap data itself. The loader code stays as it is, but anything that uses the >> MAPBLOCKSHIFT construct gets changed to use the getSafeBlockX/getSafeBlockY functions instead. To disable the "fixing", simply put a global blockmap_extension boolean or something so that you can change index interpretation on demand.

e.g.

    public final int getSafeBlockX(int coord ){
      coord >>=MAPBLOCKSHIFT;
      if (blockmap_extension){
        return (coord <=this.blockmapxneg)?coord &0x1FF:coord ;
        } else
      return coord;   
    }

Share this post


Link to post

What about it? The same of course. At that point byte order has no effect.

Share this post


Link to post
Maes said:

@DaniJ: even using the extended blockmap that all Boom and MBF derivatives build internally is not enough to remove those limits we're talking about. Similarly, I'm not familiar with how Doomsday works and whether it would be able to run entryway's test272.wad without a problem. Can it? However standard Doom and Boom surely can't, even with a fixed blockmap lump, because the problem is actually in how runtime indexes to the blockmap are computed, and it's all over the damn code. Has Doomsday modified this aspect? E.g. you are not affected by the MAPBLOCKSHIFT bug at all?

Current Doomsday is not affected by it no. We switched the whole map data and collision detection to floating point several years ago now. Doomsday is not affected by either the fixed precision or range limits that standard Doom is. Neither does Doomsday read the BLOCKMAP data should it be provided by a map, we always generate new blockmaps during map load (we similarly ignore any pre-built BSP and GL-node data).

The current release of Doomsday does however exhibit a fatal error trying to load entryway's test272.wad whilst constructing our "object-link blockmap" (a structure that records object => world surface references). That error has already been fixed for Monday's build.

That's another interesting part: by adopting the fixes I proposed, you are simply switching between blockmap index interpretations, without changing the blockmap data itself. The loader code stays as it is, but anything that uses the >> MAPBLOCKSHIFT construct gets changed to use the getSafeBlockX/getSafeBlockY functions instead. To disable the "fixing", simply put a global blockmap_extension boolean or something so that you can change index interpretation on demand.

That is precisely what I was suggesting earlier.

Share this post


Link to post

@DaniJ: thanks, that makes everything clearer. For the ports of Doom that still preserve the fixed_t calculations however, there are still a lot of sore points, including but not limited to the aforementioned blockmap limits, the visplane bleeding bugs, ApproxDistance failures etc.

The blockmap limits actually have little to do with using fixed_t: the on-disk structure was de-facto limited to 128KB because of short-sighted assumptions about its contents (but is fixable during runtime) and also because of the hare-brained interpretation of the >>MAPBLOCKSHIFT calculations. Essentially the Doom engine ruins what were perfectly adequate unsigned 9-bit integers by interpreting them as signed. Fail. Even more so since negative/overflowing blockmap indexes get rejected anyway in all places where they may show up. Luckily, even this is fixable during runtime, and much more trivially than rebuilding the blockmap was.

Share this post


Link to post

DOOM, as I'm sure you'll know (after having picked through every last shift and unsigned discrepancy in the process of developing Mocha) is choc full of such little idiosyncrasies. This was ultimately the most compelling reason why we switched to floating point (although there are other obvious advantages, however I appreciate that its not an option for all ports (particularly those which value vanilla demo compatibility)).

FYI: I've been planning to replace our blockmaps entirely, with a much more performant data structure (most likely a derivative of a region quadtree). In the case of test272.wad such a structure would avoid the need to allocate an "enormous" continuous area of memory to contain a mere twelve blocks of useful data.

Share this post


Link to post

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0