Maximum Map Dimensions

Does anyone know the maximum size a map can be? I'd like to make a very large, open map and am running into problems. I am using GZDoom, if it matters.

The most important rule is that no two points within the map should be more than 32767 map units apart. Otherwise overflows can occur that result in strange behavior.

You should also avoid going too close to the edges of the coordinate range of +-32767. Best stay around 0,0.

The absolute limits are within the -32768:32767 range because Doom uses 16.16 fixed point format for its physics. Even if the game works in 32 bits, 16 are used up after the decimal point.

I used to bitch about this, but now I know why it's good to be fixed point: floating point numbers become less precise, the larger their integer part is. This would make gameplay at (100, 200) more accurate than the one at (1000000000, 2000000000), which allows fewer decimal points. With fixed point (provided the coordinates don't overflow), gameplay is (in theory) the same at any coordinate.

If the entire level is contained in a big cube that goes from -9400 to +9400 on each axis, you are assured that the maximum distance between any two point in that space will never be more than the cut-off value at which overflows happen. (sqrt(3*(18800^2)) == 32562)

printz said:

I used to bitch about this, but now I know why it's good to be fixed point: floating point numbers become less precise, the larger their integer part is. This would make gameplay at (100, 200) more accurate than the one at (1000000000, 2000000000), which allows fewer decimal points. With fixed point (provided the coordinates don't overflow), gameplay is (in theory) the same at any coordinate.

If you use doubles instead of floats those precision issues won't be as significant. But you have to factor in that your values don't get truncated to 0 if they become increasingly smaller. This must be handled if an engine switches numeric formats or very strange things may happen.

I wonder if the transition to 64bit systems will encourage a move in Doom from 16.16 numbers to 32.32. You could make city-sized maps within those limits. Or conversely, 7.28 picometre detail! Or with 48.16 precision, you could cover the entire Solar System!

Memorial.wad (it is within -16k..+16k square) showed that (g)zdoom has some unique troubles with big maps even near 0,0 coordinate. IIRC, DOS Boom has no such issues.

Also, prboom-plus has «fix clipping problems in large levels» setting, so probably you are able to play levels within -32k..+32k square without most of problems.

Large maps should not be rare for zdoom, so you have to apply those simple fixes :)

I don't think rjspace (32k x 32k square) had any clipping problems in zdaemon?

There is a red border around the map in doombuilder. Isn't it actually show that limitation? (heh, I always thought that this size limit is only one of vanilla limits)

DB2 doesn't show the grid and doesn't allow you do draw outside the possible map boundaries. That can be changed through the config files, though, if ports ever start to support bigger maps.

printz said:

I wonder if the transition to 64bit systems will encourage a move in Doom from 16.16 numbers to 32.32. You could make city-sized maps within those limits. Or conversely, 7.28 picometre detail! Or with 48.16 precision, you could cover the entire Solar System!

48.16 would be a more logical choice than 32.32 if you moved fixed_t from 32-bit to 64-bit. That way, you wouldn't need to shift all the values as you read them from wads.

And besides, the limited precision from .16 has been good enough for most things. Sub-map unit detailing is a rarer demand than very large levels.

entryway said:

Memorial.wad (it is within -16k..+16k square) showed that (g)zdoom has some unique troubles with big maps even near 0,0 coordinate. IIRC, DOS Boom has no such issues.

Also, prboom-plus has «fix clipping problems in large levels» setting, so probably you are able to play levels within -32k..+32k square without most of problems.

Large maps should not be rare for zdoom, so you have to apply those simple fixes :)

Simple, simple... I wouldn't know how to fix them! (And because of pesky license issues, I can't just copy from PrBoom+ code.)

Perhaps the problem is something else then. My map is smaller than these max dimensions and I've added some extra vertexes to subdivide the lines, but I'm using the line horizon effect and still getting idclip-style visual glitching. Is there some limit to ZDoom's line horizon feature?

Gez said:

48.16 would be a more logical choice than 32.32 if you moved fixed_t from 32-bit to 64-bit. That way, you wouldn't need to shift all the values as you read them from wads.

And besides, the limited precision from .16 has been good enough for most things. Sub-map unit detailing is a rarer demand than very large levels.

I think I'll open an experimental branch where I play with 64-bit fixed_t. I don't currently have a 64-bit system, so it will be slow and hacky, but worth testing if it really works :P

...May be troublesome because int will currently remain 32 bit.

Gez said:

Simple, simple... I wouldn't know how to fix them! (And because of pesky license issues, I can't just copy from PrBoom+ code.)

Actually that part of the code was developed jointly by me and entryway in collab, and is present also in Mocha Doom (read entire story here). As you can see the "fix" is quite open and fine by me, if anyone adopts it. No license or anything.

Compared to moving to an extended fixed point or full floating-point model like Eternity, it has the advantage of relative simplicity and major compatibility with standard 16.16 linuxdoom/boom code. On the downside, it "only" extends full functionality within the -32K~32K limits (or 512x512 blockmap blocks, instead of 256x256).

I tried that, but wasn't successful. :/

But entryway and I were ;-)

Gez said:

I tried that, but wasn't successful. :/

Can you check why I can't shoot line №2730 (submap05) in memorial.wad?



No problem with this line in prboom -complevel 9/2

Btw, why zdoom does not apply gamma to screenshots? It annoys a lot.
Probably something like this?

void ApplyGammaRamp(byte *buf, int pitch, int width, int height)
{
  int w, h;
  byte *pixel;
  Uint16 r[256], g[256], b[256];

  SDL_GetGammaRamp(&r[0], &g[0], &b[0]);

  for (h = 0; h < height; h++)
  {
    for (w = 0; w < width; w++)
    {
      pixel = buf + h * pitch + 3 * w;

      *(pixel + 0) = (byte)(r[*(pixel + 0)] >> 8);
      *(pixel + 1) = (byte)(g[*(pixel + 1)] >> 8);
      *(pixel + 2) = (byte)(b[*(pixel + 2)] >> 8);
    }
  }
}

entryway said:

Can you check why I can't shoot line №2730 (submap05) in memorial.wad?

No problem with Mocha either....it must lie just at the "frontier" where bad things start happening to the blockmap ;-)

I found a lot of zones in MAP05 where the shots don't go through -- though the glitch is only in one direction.

entryway said:

Btw, why zdoom does not apply gamma to screenshots? It annoys a lot.

What is your value of png_gamma?

Gez said:

What is your value of png_gamma?

png_gamma=0



P.S.
I made two screenshots of same scene with different gamma and yes, 'gAMA' chunks are not equal, but I do not see any differences in my viewer (XnView) and browser.

Gez said:

I found a lot of zones in MAP05 where the shots don't go through -- though the glitch is only in one direction.

The symptoms you described are exactly those caused by blockmap index overflows, including unidirectionality - remember, the -32K/32K limit on fixed point arithmetic is only part of the problem.

Actual thing/projectile clipping is performed using the blockmap, not direct LOS, so you'd think that since blockmap indexes are much smaller in value(0.255 normally, minus a blockmap starting offset), that wouldn't be a problem.

Except that they are, for reasons amply documented in that other thread, and can be fixed -but make sure you read it all the way through, not just the first page! The fix must be applied in several places that access the blockmap, it's not simply a matter of changing one line of code, but it's much more minor than Eternity's approach.

Another option is to grab the latest Mocha source, or prBoom+'s and look for "Maes" ;-)

Then again, I don't know if ZDoom makes it impractical/hard to adopt Boom-like code...so maybe the fix wouldn't be so straightforward. But if it worked in a Java-derivative of linuxdoom and prBoom+, then maybe it's not as hard as it seems.

Well, if you want to laugh at me, here's what I did, which resulted in a catastrophic failure of absolutely all clipping. :p

Gez said:

here's what I did, which resulted in a catastrophic failure of absolutely all clipping. :p

-#define SHIFTBLOCKMAPX/Y(val) [...] :-257)
+#define SHIFTBLOCKMAPX/Y(val) [...] :((val)>>MAPBLOCKSHIFT))

?

I don't like the looks of that -257 constant there. There should be a pair of blockmapxneg/blockmapyneg coords, which indicate which is the smallest negative blockmap coordinate which really is an outside-of-map negative index, and are computed at level load-time. Using a constant value of -257 is incorrect.

 (from modified P_LoadBlockMap in Mocha)
        // 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;
        
        blockmap = blockmaplump;

and here's how they are used:

/** Gets the proper blockmap block for a given X 16.16 Coordinate, sanitized
     *  for 512-wide blockmaps. 
     * 
     * @param blockx
     * @return
     */

    public final int getSafeBlockX(int blockx){
        blockx>>=MAPBLOCKSHIFT;
        return (blockx<=this.blockmapxneg)?blockx&0x1FF:blockx;
    }
    
    public final int getSafeBlockX(long blockx){
        blockx>>=MAPBLOCKSHIFT;
        return (int) ((blockx<=this.blockmapxneg)?blockx&0x1FF:blockx);
    }
    
    /** Gets the proper blockmap block for a given Y 16.16 Coordinate, sanitized
     *  for 512-wide blockmaps. 
     * 
     * @param blocky
     * @return     */

    
    public final int getSafeBlockY(int blocky){
        blocky>>=MAPBLOCKSHIFT;
        return (blocky<=this.blockmapyneg)?blocky&0x1FF:blocky;
    }
    
    public final int getSafeBlockY(long blocky){
        blocky>>=MAPBLOCKSHIFT;
        return (int) ((blocky<=this.blockmapyneg)?blocky&0x1FF:blocky);
    }

entryway said:

-#define SHIFTBLOCKMAPX/Y(val) [...] :-257)
+#define SHIFTBLOCKMAPX/Y(val) [...] :((val)>>MAPBLOCKSHIFT))

?

Yeah, that was stupid of me. I shouldn't write code past midnight, apparently.

Also forgot to compute the negs in P_CreateBlockmap.

Still doesn't work, though. :/

Maes said:

I don't like the looks of that -257 constant there. There should be a pair of blockmapxneg/blockmapyneg coords, which indicate which is the smallest negative blockmap coordinate which really is an outside-of-map negative index, and are computed at level load-time. Using a constant value of -257 is incorrect.

Yeah, I have that in p_setup:

	bmapnegx = bmapwidth  > 255 ? bmapwidth  - 512 : -257;
	bmapnegy = bmapheight > 255 ? bmapheight - 512 : -257;
	Printf("bmapwidth %i, bmapheight %i, bmapnegx %i, bmapnegy %i\n",
		bmapwidth, bmapheight, bmapnegx, bmapnegy);

I've just added the Printf line.

It tells me:

Console logged:
MAP01 - Hell on Earth - Memorial

bmapwidth 251, bmapheight 233, bmapnegx -257, bmapnegy -257
bmapwidth 251, bmapheight 233, bmapnegx -257, bmapnegy -257

So the blockmap is not actually larger than 255 in either axis? But the clipping bug with hitscans still happens.

So at the moment I'm thinking that there's another bug somewhere else.

Gez said:

So the blockmap is not actually larger than 255 in either axis? But the clipping bug with hitscans still happens.

So at the moment I'm thinking that there's another bug somewhere else.

Yeah, issue on memorial.wad is zdoom specific. PrBoom does not have it (without any fixes)

The hitscan bug in ZDoom does have some problems of its own, mostly due to the extended hitscan range. It's very, very easy to make it overflow and probably should be tossed in favor of a floating point trace function.

Gez said:

Still doesn't work, though. :/

Check it with wad below, not on memorial.wad.
http://prboom-plus.sf.net/test272.wad.zip

-257 is a special value only used for maps that are not >= 255 blocks in length, correct (this means the majority of maps).

If you get the clipping bug ONLY for projectiles and not for player walking, then yeah, the bug might be somewhere else.

I also have this in P_CheckPosition before the actual call to the BlockLinesIterator

        // Maes's quick and dirty blockmap extension hack
        // E.g. for an extension of 511 blocks, max negative is -1.
        // A full 512x512 blockmap doesn't have negative indexes.
        
        if (xl<=LL.blockmapxneg) xl=0x1FF&xl;         // Broke width boundary
        if (xh<=LL.blockmapxneg) xh=0x1FF&xh;    // Broke width boundary
        if (yl<=LL.blockmapyneg) yl=0x1FF&yl;        // Broke height boundary
        if (yh<=LL.blockmapyneg) yh=0x1FF&yh;   // Broke height boundary     
       
        for (bx=xl ; bx<=xh ; bx++)
        for (by=yl ; by<=yh ; by++)
            if (!BlockLinesIterator (bx,by,CheckLine))
            return false;

There's also a LOT of special attention due to P_PathTrasverse. Without that, the rest of the fixes won't work consistently. Make sure you read till the end of the thread, though, to avoid implementing half-baked proposals while a better one can be found just a few posts below ;-)

Explicitly, here's how P_PathTrasverse looks like in Mocha (prBoom+ version is not very different). Notice how LONGS are used for certain computations.

entryway said:

Check it with wad below, not on memorial.wad.
http://prboom-plus.sf.net/test272.wad.zip

Doesn't work either.

(Using FOV 120 to make screenshot.)
Console said:

Loading blockmap with bmapwidth 269, bmapheight 24, bmapnegx -243, bmapnegy -257

Maes said:

If you get the clipping bug ONLY for projectiles and not for player walking, then yeah, the bug might be somewhere else.

Projectiles work; hitscans don't. I guess that's what you meant, though.

I'll try messing with P_CheckPosition and see if I get somewhere.