ZDoom

Spoiler:

---

Code: Select all

template<unsigned tileWidth, unsigned tileHeight> struct DDALineWalker {
public:
  // worker variables
  // use doubles here for better precision
  int currTileX, currTileY;
  int endTileX, endTileY;
  double deltaDistX, deltaDistY; // length of ray from one x or y-side to next x or y-side
  double sideDistX, sideDistY; // length of ray from current position to next x-side
  int stepX, stepY; // what direction to step in x/y (either +1 or -1)
  int cornerHit; // 0: no; 1: return horiz cell; 2: return vert cell; 3: do step on both dirs; 4: abort
  int maxTileX, maxTileY;

public:
  inline DDALineWalker () noexcept {}
  inline DDALineWalker (int x0, int y0, int x1, int y1, int amaxtx, int amaxty) noexcept { start(x0, y0, x1, y1, amaxtx, amaxty); }

  void start (int x0, int y0, int x1, int y1, int amaxtx, int amaxty) noexcept {
    cornerHit = 0;
    maxTileX = amaxtx;
    maxTileY = amaxty;

    #if 0
    // this seems to be better for negative coords, but negatives should not arrive here
    const int tileSX = int(floor(double(x0)/double(tileWidth)));
    const int tileSY = int(floor(double(y0)/double(tileHeight)));
    endTileX = int(floor(double(x1)/double(tileWidth)));
    endTileY = int(floor(double(y1)/double(tileHeight)));
    #else
    const int tileSX = x0/tileWidth;
    const int tileSY = y0/tileHeight;
    endTileX = x1/tileWidth;
    endTileY = y1/tileHeight;
    #endif

    currTileX = tileSX;
    currTileY = tileSY;

    //GLog.Logf(NAME_Debug, "*** start=(%d,%d)", tileSX, tileSY);
    //GLog.Logf(NAME_Debug, "*** end  =(%d,%d)", endTileX, endTileY);

    // it is ok to waste some time here
    if (tileSX == endTileX || tileSY == endTileY) {
      if (tileSX == endTileX && tileSY == endTileY) {
        // nowhere to go (but still return the starting tile)
        //GLog.Logf(NAME_Debug, "  POINT!");
        stepX = stepY = 0; // this can be used as a "stop signal"
      } else if (tileSX == endTileX) {
        // vertical
        vassert(tileSY != endTileY);
        stepX = 0;
        stepY = (y0 < y1 ? 1 : -1);
        //GLog.Logf(NAME_Debug, "  VERTICAL!");
      } else {
        // horizontal
        vassert(tileSY == endTileY);
        stepX = (x0 < x1 ? 1 : -1);
        stepY = 0;
        //GLog.Logf(NAME_Debug, "  HORIZONTAL!");
      }
      //GLog.Logf(NAME_Debug, "  step=(%d,%d)!", stepX, stepY);
      // init variables to shut up the compiler
      deltaDistX = deltaDistY = sideDistX = sideDistY = 0;
      return;
    }

    // inverse length, so we can use multiply instead of division (marginally faster)
    const double absdx = double(1)/fabs(double(x1)-double(x0));
    const double absdy = double(1)/fabs(double(y1)-double(y0));

    if (x0 < x1) {
      stepX = 1;
      sideDistX = ((tileSX+1)*tileWidth-x0)*absdx;
    } else {
      stepX = -1;
      sideDistX = (x0-tileSX*tileWidth)*absdx;
    }

    if (y0 < y1) {
      stepY = 1;
      sideDistY = (double)((tileSY+1)*tileHeight-y0)*absdy;
    } else {
      stepY = -1;
      sideDistY = (double)(y0-tileSY*tileHeight)*absdy;
    }

    deltaDistX = double(tileWidth)*absdx;
    deltaDistY = double(tileHeight)*absdy;
  }

  // returns `false` if we're done (and the coords are undefined)
  inline bool next (int &tilex, int &tiley) noexcept {
    // check for a special condition
    if (cornerHit) {
      //GLog.Logf(NAME_Debug, "CORNER: %d", cornerHit);
      switch (cornerHit++) {
        case 1: // check adjacent horizontal tile
          if (!stepX) { ++cornerHit; goto doadjy; } // this shouldn't happen, but better play safe
          tilex = currTileX+stepX;
          tiley = currTileY;
          if (tilex < 0 || tilex >= maxTileX) { ++cornerHit; goto doadjy; }
          return true;
        case 2: // check adjacent vertical tile
         doadjy:
          if (!stepY) goto donextc;
          tilex = currTileX;
          tiley = currTileY+stepY;
          if (tiley < 0 || tiley >= maxTileY) goto donextc; // this shouldn't happen, but better play safe
          return true;
        case 3: // move to the next tile
         donextc:
          // corner case check (this shouldn't happen, but better play safe)
          if (currTileX == endTileX) stepX = 0;
          if (currTileY == endTileY) stepY = 0;
          // move through the corner
          sideDistX += deltaDistX;
          currTileX += stepX;
          sideDistY += deltaDistY;
          currTileY += stepY;
          // resume normal processing
          cornerHit = 0;
          break;
        default:
          return false; // no more
      }
    }

    // return current tile coordinates
    tilex = currTileX;
    tiley = currTileY;

    //GLog.Logf(NAME_Debug, "  000: res=(%d,%d); step=(%d,%d); sideDist=(%g,%g); delta=(%g,%g)", tilex, tiley, stepX, stepY, sideDistX, sideDistY, deltaDistX, deltaDistY);
    // check if we're done (sorry for this bitop mess); checks step vars just to be sure
    if (!((currTileX^endTileX)|(currTileY^endTileY)) || !(stepX|stepY)) {
      cornerHit = 4; // no more
    } else if (stepX && stepY) {
      // jump to next map square, either in x-direction, or in y-direction
      //print("  sdxy=(%s,%s); dxy=(%s,%s); stxy=(%s,%s)", sideDistX, sideDistY, deltaDistX, deltaDistY, stepX, stepY);
      if (sideDistX == sideDistY) {
        // this will jump through a corner, so we have to process adjacent cells first (see the code above)
        cornerHit = 1;
      } else if (sideDistX < sideDistY) {
        // horizontal step
        sideDistX += deltaDistX;
        currTileX += stepX;
        // don't overshoot (sadly, this may happen with long traces)
        if (currTileX == endTileX) stepX = 0;
      } else {
        // vertical step
        sideDistY += deltaDistY;
        currTileY += stepY;
        // don't overshoot (sadly, this may happen with long traces)
        if (currTileY == endTileY) stepY = 0;
      }
    } else {
      // horizontal or vertical
      currTileX += stepX;
      currTileY += stepY;
    }
    //GLog.Logf(NAME_Debug, "  001: res=(%d,%d); step=(%d,%d); sideDist=(%g,%g); delta=(%g,%g); cc=%d", tilex, tiley, stepX, stepY, sideDistX, sideDistY, deltaDistX, deltaDistY, cornerHit);

    return true;
  }
};

ketmar wrote: as Graf said, that code is one of the most important engine functions. how did id managed to screw it up so badly?! (obvious rhetorical question