纯JavaScript射线引擎DDA算法渲染方块间隙问题排查

问题描述 #

使用纯JavaScript开发射线投射引擎，基于DDA算法优化性能，但渲染时方块之间出现间隙（见截图）。经排查发现，当射线碰到方块角落时，会因错误检测方块导致穿透，推测mapX和mapY的坐标计算存在问题。

以下是实现DDA逻辑的getDistances函数代码：

function getDistances() {
    for (var i = 0; i < Game.rays.quantity; i++) {
      // 获取当前射线角度
      var angle = Game.toRad((Game.player.angle - (Game.rays.fov / 2)) + ((Game.rays.fov / Game.rays.quantity) * i));
      var rayX = Game.player.x;
      var rayY = Game.player.y;
      // 预计算角度的sin、cos和tan值
      var sin = Math.sin(angle);
      var cos = Math.cos(angle);
      var tan = Math.tan(angle);
      var hitWall = false;

      for (var j = 0; j < Game.rays.renderDistance; j++) {
        // 获取射线最近的X和Y坐标
        var stepX, stepY;

        if (sin < 0) {
          stepY = (Math.floor((rayY - 1) / Game.mapConfig.blockSize) * Game.mapConfig.blockSize) - rayY;
        } else {
          stepY = (Math.ceil((rayY + 1) / Game.mapConfig.blockSize) * Game.mapConfig.blockSize) - rayY;
        }
        if (cos < 0) {
          stepX = (Math.floor((rayX - 1) / Game.mapConfig.blockSize) * Game.mapConfig.blockSize) - rayX
        } else {
          stepX = (Math.ceil((rayX + 1) / Game.mapConfig.blockSize) * Game.mapConfig.blockSize) - rayX;
        }
      

        // 射线与方块相交的最近坐标对（取整到X和Y）
        var nearX = [rayX + stepX, (stepX * tan) + rayY]; // 蓝色
        var nearY = [(stepY / tan) + rayX, rayY + stepY]; // 紫色

        // 根据坐标获取Game.map.data中对应的方块
        // 问题可能出在这里
        var mapX, mapY;

        if (Game.distanceTo([rayX, rayY], nearX) < Game.distanceTo([rayX, rayY], nearY)) {
          // 击中方块侧面
          rayX = nearX[0];
          rayY = nearX[1];
          
          if (cos < 0) { // 朝向左侧
            mapX = Math.floor(rayX / Game.mapConfig.blockSize) - 1;
            mapY = Math.floor(rayY / Game.mapConfig.blockSize);
          } else { // 朝向右侧
            mapX = Math.floor(rayX / Game.mapConfig.blockSize);
            mapY = Math.floor(rayY / Game.mapConfig.blockSize);
          }
        } else {
          // 击中方块顶部/底部
          rayX = nearY[0];
          rayY = nearY[1];

          if (sin < 0) { // 朝向下方
            mapX = Math.floor(rayX / Game.mapConfig.blockSize);
            mapY = Math.floor(rayY / Game.mapConfig.blockSize) - 1;
          } else { // 朝向上方
            mapX = Math.floor(rayX / Game.mapConfig.blockSize);
            mapY = Math.floor(rayY / Game.mapConfig.blockSize);
          }
        }

        // 检查方块是否为实心；若是则停止射线
        if (Game.checkSolid(mapY, mapX)) {
          hitWall = true;
          var distance = Math.sqrt(Math.pow(rayX - Game.player.x, 2) + Math.pow(rayY - Game.player.y, 2));
          Game.rays.distances[i] = [distance, Game.map.data[mapY][mapX]];
          break;
        }
      }

      if (!hitWall) {
        Game.rays.distances[i] = [Infinity, " "];
      }
    }
  }

问题原因分析 #

1. 浮点精度误差：射线到达方块边界时，浮点计算的微小误差会导致rayX/rayY刚好落在方块边界线上，此时Math.floor的结果可能偏离实际应检测的方块。
2. 方块坐标映射错误：当前mapX/mapY的计算逻辑在边界场景下（比如射线朝左/朝下），减1的操作会错误指向相邻方块，而非实际碰撞的方块。
3. 角落碰撞未处理：当射线同时到达X和Y方向的方块边界（距离相等）时，仅检测其中一个方向的方块，会导致射线穿透角落。

解决方法 #

1. 修正方块坐标映射逻辑 #

通过引入微小偏移量（如1e-6）规避浮点精度问题，同时调整边界方向的方块索引计算：

// 修正侧面碰撞的mapX计算
if (cos < 0) { // 朝向左侧
  // 偏移后再取整，避免边界浮点误差
  mapX = Math.floor((rayX - 1e-6) / Game.mapConfig.blockSize);
} else { // 朝向右侧
  mapX = Math.floor((rayX + 1e-6) / Game.mapConfig.blockSize);
}
mapY = Math.floor(rayY / Game.mapConfig.blockSize);

// 修正上下碰撞的mapY计算
if (sin < 0) { // 朝向下方
  mapY = Math.floor((rayY - 1e-6) / Game.mapConfig.blockSize);
} else { // 朝向上方
  mapY = Math.floor((rayY + 1e-6) / Game.mapConfig.blockSize);
}
mapX = Math.floor(rayX / Game.mapConfig.blockSize);

2. 优化Step计算精度 #

移除rayX±1/rayY±1的冗余操作，直接基于当前射线位置计算方块边界：

if (sin < 0) {
  stepY = Math.floor(rayY / Game.mapConfig.blockSize) * Game.mapConfig.blockSize - rayY;
} else {
  stepY = (Math.floor(rayY / Game.mapConfig.blockSize) + 1) * Game.mapConfig.blockSize - rayY;
}
if (cos < 0) {
  stepX = Math.floor(rayX / Game.mapConfig.blockSize) * Game.mapConfig.blockSize - rayX;
} else {
  stepX = (Math.floor(rayX / Game.mapConfig.blockSize) + 1) * Game.mapConfig.blockSize - rayX;
}

3. 处理角落碰撞的边界情况 #

当nearX和nearY的距离相等时，同时检查两个方向的方块，任一方向检测到实心方块即停止射线：

var distX = Game.distanceTo([rayX, rayY], nearX);
var distY = Game.distanceTo([rayX, rayY], nearY);

if (distX < distY) {
  // 原侧面碰撞逻辑...
} else if (distY < distX) {
  // 原上下碰撞逻辑...
} else {
  // 同时检查两个方向的方块
  rayX = nearX[0];
  rayY = nearX[1];
  var sideMapX = cos < 0 ? Math.floor((rayX - 1e-6)/Game.mapConfig.blockSize) : Math.floor((rayX + 1e-6)/Game.mapConfig.blockSize);
  var sideMapY = Math.floor(rayY / Game.mapConfig.blockSize);
  
  rayX = nearY[0];
  rayY = nearY[1];
  var vertMapY = sin < 0 ? Math.floor((rayY - 1e-6)/Game.mapConfig.blockSize) : Math.floor((rayY + 1e-6)/Game.mapConfig.blockSize);
  var vertMapX = Math.floor(rayX / Game.mapConfig.blockSize);
  
  if (Game.checkSolid(sideMapY, sideMapX)) {
    mapX = sideMapX;
    mapY = sideMapY;
    hitWall = true;
  } else if (Game.checkSolid(vertMapY, vertMapX)) {
    mapX = vertMapX;
    mapY = vertMapY;
    hitWall = true;
  }
}

内容的提问来源于stack exchange，提问作者Blue Herring