What's wrong with my 2D ray-tracing function?

Question

I've written a simple function which uses the DDA algorithm to implement 2D ray tracing (named findCollision), however it seems to act weirdly in certain circumstances;

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);

As you can see from the output, any rays pointing towards the top or left of the canvas extend too far past the collision area by 1 block (i.e. 1 increment). What is wrong with my algorithm?

Answer 1

Your function seems fine.

First problem is that your world has no center. I added one column and one row. That way a picture should be symmetrical and nice.

Second problem is walls drawing. Always positive width and height cause walls to propagate from the center in one directions and to the center in others. I added width and height sign calculation depending on direction (but part of walls is out of canvas boundaries that way).

Update

I expanded the world for walls to be visible. It seems that algorithm has a precision problem. If I set an observer not in the center, there are points at corners that do not look good. For lazy solving you can make steps in the algorithm significantly shorter then grid steps.

Currently an algorithm steps to a next only vertical or only horizontal grid line. You can try to change an algorithm for it to step to a next closest grid line.

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);