javascript - 我的 2D 光线追踪功能有什么问题？

Question

我写了一个简单的函数，它使用 DDA 算法实现 2D 光线追踪(名为 findCollision)，但是在某些情况下它似乎表现得很奇怪；

function findCollision(position, direction, world, maxDistance = 10) {
  const steps = Math.max(
    Math.abs(direction.x),
    Math.abs(direction.y),
  );

  const increment = {
    x: direction.x / steps,
    y: direction.y / steps,
  };

  let x = position.x;
  let y = position.y;

  for (let i = 0; i < maxDistance; i++) {
    const roundedX = Math.round(x);
    const roundedY = Math.round(y);

    if (world[roundedX] && world[roundedX][roundedY]) {
      return { x, y };
    }

    x += increment.x;
    y += increment.y;
  }

  return null;
}

const CELL_SIZE = 32;

const canvas = document.createElement('canvas');
const context = canvas.getContext('2d');
const center = { x: 4, y: 4 };

const map = [
  [1, 1, 1, 1, 1, 1, 1, 1],
  [1, 0, 0, 0, 0, 0, 0, 1],
  [1, 0, 0, 0, 0, 0, 0, 1],
  [1, 0, 0, 0, 0, 0, 0, 1],
  [1, 0, 0, 0, 0, 0, 0, 1],
  [1, 0, 0, 0, 0, 0, 0, 1],
  [1, 0, 0, 0, 0, 0, 0, 1],
  [1, 1, 1, 1, 1, 1, 1, 1],
];

Object.assign(canvas, {
  width: 500,
  height: 500,
});

function draw() {
  for (let i = 0; i < Math.PI * 2; i += Math.PI / 32) {
    const dX = Math.cos(i);
    const dY = Math.sin(i);

    const collision = findCollision(center, { x: dX, y: dY }, map, 64);

    if (!collision) {
      continue;
    }

    context.strokeStyle = 'rgba(0, 0, 0, 0.5)';
    context.beginPath();
    context.moveTo(center.x * CELL_SIZE, center.y * CELL_SIZE);
    context.lineTo(collision.x * CELL_SIZE, collision.y * CELL_SIZE);
    context.stroke();

    context.fillStyle = 'rgba(0, 0, 0, 0.1)';
    context.fillRect(collision.x * CELL_SIZE, collision.y * CELL_SIZE, CELL_SIZE, CELL_SIZE);
  }
}

requestAnimationFrame(draw);

document.body.appendChild(canvas);

正如您从输出中看到的那样，任何指向 Canvas 顶部或左侧的光线都会超出碰撞区域 1 个方 block (即 1 个增量)。我的算法有什么问题？

Answer 1

你的函数看起来没问题。

第一个问题是你的世界没有中心。我添加了一列和一行。这样一来，图片就应该对称且美观。

第二个问题是墙壁绘制。始终为正的宽度和高度会导致墙壁从一个方向的中心传播到其他方向的中心。我根据方向添加了宽度和高度符号计算(但部分墙壁超出了 Canvas 边界)。

更新

我扩展了世界，让墙壁可见。看来算法有精度问题。如果我将观察者设置在不在中心的位置，则 Angular 落处的点看起来不太好。对于惰性求解，您可以使算法中的步骤明显短于网格步骤。

目前，一种算法会步进到下一条仅垂直或仅水平的网格线。您可以尝试更改算法，使其步进到下一条最近的网格线。

function findCollision(position, direction, world, maxDistance = 10) {
  const steps = Math.max(
    Math.abs(direction.x),
    Math.abs(direction.y),
  );

  const increment = {
    x: direction.x / steps,
    y: direction.y / steps,
  };

  let x = position.x;
  let y = position.y;

  for (let i = 0; i < maxDistance; i++) {
    const roundedX = Math.round(x);
    const roundedY = Math.round(y);

    if (world[roundedX] && world[roundedX][roundedY]) {
      return { x, y };
    }

    x += increment.x;
    y += increment.y;
  }

  return null;
}

const CELL_SIZE = 32;

const canvas = document.createElement('canvas');
const context = canvas.getContext('2d');
const center = { x: 4, y: 4 };

const map = [
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0],
  [0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0],
  [0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0],
  [0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0],
  [0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0],
  [0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0],
  [0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0],
  [0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0],
  [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
];

Object.assign(canvas, {
  width: 500,
  height: 500,
});

function draw() {
  for (let i = 0; i < Math.PI * 2; i += Math.PI / 32) {
    const dX = Math.cos(i);
    const dY = Math.sin(i);

    const collision = findCollision(center, { x: dX, y: dY }, map, 64);

    if (!collision) {
      continue;
    }

    context.strokeStyle = 'rgba(0, 0, 0, 0.5)';
    context.beginPath();
    context.moveTo(center.x * CELL_SIZE, center.y * CELL_SIZE);
    context.lineTo(collision.x * CELL_SIZE, collision.y * CELL_SIZE);
    context.stroke();

    context.fillStyle = 'rgba(0, 0, 0, 0.1)';
    context.fillRect(collision.x * CELL_SIZE, collision.y * CELL_SIZE,
                     dX / Math.abs(dX) * CELL_SIZE,
                     dY / Math.abs(dY) * CELL_SIZE);
  }
}

requestAnimationFrame(draw);

document.body.appendChild(canvas);