Need help with fixing Optimized Raycasting / Line of Sight algorithm

Question

I'm trying to implement collision detection with raycasting for my 2D javascript game. The game uses equally-sized tiles as its level structure so to optimize collision detecton I'm trying to use a LOS algorithm very similar to the one at the bottom of this this article.

However, I've noticed that at certain angles, tiles that should be detected are not. I'm also noticing an overall "L" shape pattern where tiles that are beyond the ray's endpoint are being detected when they don't need to be. I don't think these are intended behaviors of the algorithm but I can't quite figure out what I could be doing wrong.

I've assembled a small jsfiddle here that includes the most relevant code and an additional visualization. You can click anywhere on the canvas to set a new ray origin.

Would appreciate any help. Thanks.

const GRID_HEIGHT = 10
const GRID_WIDTH = 10
const CELLSIZE = 32
const OUTLINE_COLOUR = 'green';
const FILL_COLOUR = 'red'
const RAY_COLOUR = 'blue';
const canvas = document.getElementById('demo');
const ctx = canvas.getContext('2d');
var mouseVector = new Vector2D([96, 0], [1, 0]);
canvas.height = GRID_HEIGHT * CELLSIZE;
canvas.width = GRID_WIDTH * CELLSIZE
canvas.addEventListener("mousemove", updateMouseVector);
canvas.addEventListener("click", setMouseVectorOrigin);

function Vector2D(point1, point2) {
  if (point2 != undefined) {
    this.p1 = point1;
    this.p2 = point2;
  } else {
    this.p1 = [0, 0];
    this.p2 = point1;
  };
};

function drawCellOutline(x, y) {
  ctx.fillStyle = OUTLINE_COLOUR;
  ctx.strokeRect(x, y, CELLSIZE, CELLSIZE);
};

function fillCell(x, y) {
  ctx.fillStyle = FILL_COLOUR;
  ctx.fillRect(x, y, CELLSIZE, CELLSIZE);
};

function drawGrid() {
  for (let y = 0; y < GRID_HEIGHT; y++) {
    for (let x = 0; x < GRID_WIDTH; x++) {
      drawCellOutline(x * CELLSIZE, y * CELLSIZE);
    };
  };
};

function clearCanvas() {
  ctx.clearRect(0, 0, ctx.canvas.width, ctx.canvas.height)
};

function getMouseCoordinates(e) {
  let mouseX, mouseY;

  if (e.offsetX) {
    mouseX = e.offsetX;
    mouseY = e.offsetY;
  } else if (e.layerX) {
    mouseX = e.layerX;
    mouseY = e.layerY;
  }
  return [mouseX, mouseY]
}

function updateMouseVector(e) {
  let mousePos = getMouseCoordinates(e);
  mouseVector.p2[0] = mousePos[0];
  mouseVector.p2[1] = mousePos[1];
}

function setMouseVectorOrigin(e) {
  let mousePos = getMouseCoordinates(e);
  mouseVector.p1[0] = mousePos[0];
  mouseVector.p1[1] = mousePos[1];
};

function drawRay(rayVector) {
  ctx.fillStyle = RAY_COLOUR;
  ctx.beginPath();
  ctx.moveTo(rayVector.p1[0], rayVector.p1[1]);
  ctx.lineTo(rayVector.p2[0], rayVector.p2[1]);
  ctx.stroke();
}

function raycastCollision(rayVector) {
  let dx = Math.ceil(Math.abs(rayVector.p2[0] - rayVector.p1[0]) / CELLSIZE);
  let dy = Math.ceil(Math.abs(rayVector.p2[1] - rayVector.p1[1]) / CELLSIZE);
  let x_inc = (rayVector.p2[0] > rayVector.p1[0]) ? 1 : -1;
  let y_inc = (rayVector.p2[1] > rayVector.p1[1]) ? 1 : -1;
  x_inc *= CELLSIZE;
  y_inc *= CELLSIZE;

  // "error" is The difference between the next horizontal cell vs the next vertical cell.
  // if error is positive then horizontal is closer, otherwise vertical.
  let error = dx - dy;

  let pos = [rayVector.p1[0], rayVector.p1[1]]; // Create copy because we're going to be mutating it.

  let n = 1 + dx + dy; // 1 represents thw tile we're starting from.
  for (; n > 0; --n) {

    fillCell(Math.floor(pos[0] / CELLSIZE) * 32, Math.floor(pos[1] / CELLSIZE) * 32);

    if (error > 0) {
      pos[0] += x_inc;
      error -= dy;
    } else {
      pos[1] += y_inc;
      error += dx;
    };

  };
};

function main() {
  clearCanvas();
  drawGrid();
  raycastCollision(mouseVector);
  drawRay(mouseVector);
  requestAnimationFrame(main);
};

requestAnimationFrame(main);

<canvas id="demo"></canvas>

Answer 1

const GRID_HEIGHT = 10
const GRID_WIDTH = 10
const CELLSIZE = 32
const OUTLINE_COLOUR = 'green';
const FILL_COLOUR = 'red'
const RAY_COLOUR = 'blue';
const X = 0;
const Y = 1;
const canvas = document.getElementById('demo');
const ctx = canvas.getContext('2d');
var mouseVector = new Vector2D([0, 0], [0, 0]);
canvas.height = GRID_HEIGHT * CELLSIZE;
canvas.width = GRID_WIDTH * CELLSIZE
canvas.addEventListener("mousemove", updateMouseVector);
canvas.addEventListener("click", setMouseVectorOrigin);

function Vector2D(point1, point2)
{
  if (point2 != undefined)
  {
    this.p1 = point1;
    this.p2 = point2;
  }
  else
  {
    this.p1 = [0, 0];
    this.p2 = point1;
  };
};

function drawCellOutline(cx, cy)
{
  ctx.fillStyle = OUTLINE_COLOUR;
  ctx.strokeRect(cx * CELLSIZE, cy * CELLSIZE, CELLSIZE, CELLSIZE);
};

function fillCell(cx, cy)
{
  ctx.fillStyle = FILL_COLOUR;
  ctx.fillRect(Math.floor(cx) * CELLSIZE, Math.floor(cy) * CELLSIZE, CELLSIZE, CELLSIZE);
};

function drawGrid()
{
  for (let y = 0; y < GRID_HEIGHT; y++)
  {
    for (let x = 0; x < GRID_WIDTH; x++)
    {
      drawCellOutline(x, y);
    };
  };
};

function clearCanvas()
{
  ctx.clearRect(0, 0, ctx.canvas.width, ctx.canvas.height)
};

function getMouseCoordinates(e)
{
  let mouseX, mouseY;

  if (e.offsetX) {
    mouseX = e.offsetX;
    mouseY = e.offsetY;
  } else if (e.layerX) {
    mouseX = e.layerX;
    mouseY = e.layerY;
  }
  return [mouseX, mouseY]
}

function updateMouseVector(e)
{
  let mousePos = getMouseCoordinates(e);
  mouseVector.p2[0] = mousePos[0]// + 0.5;
  mouseVector.p2[1] = mousePos[1]// + 0.5;
}

function setMouseVectorOrigin(e)
{
  let mousePos = getMouseCoordinates(e);
  mouseVector.p1[0] = mousePos[0]// + 0.5;
  mouseVector.p1[1] = mousePos[1]// + 0.5;
};

function drawRay(rayVector)
{
  ctx.fillStyle = RAY_COLOUR;
  ctx.beginPath();
  ctx.moveTo(rayVector.p1[0], rayVector.p1[1]);
  ctx.lineTo(rayVector.p2[0], rayVector.p2[1]);
  ctx.stroke();
}

function rayMarch(rayVector)
{
      let cellVector = {p1: [rayVector.p1[X] / CELLSIZE, rayVector.p1[Y] / CELLSIZE],
                                    p2: [rayVector.p2[X] / CELLSIZE, rayVector.p2[Y] / CELLSIZE]};
    
    let x0 = cellVector.p1[X];
    let x1 = cellVector.p2[X];
    let y0 = cellVector.p1[Y];
    let y1 = cellVector.p2[Y];
    
    let dx = x1 - x0;
    let dy = y1 - y0;
    dx = Math.abs(dx);
    dy = Math.abs(dy);
    //adjust dx / dy to avoid div-by-zero
    let dtDx = 1.0 / dx;
    let dtDy = 1.0 / dy;

    let xInc = 0//dx / steps;
    let yInc = 0//dy / steps;
    let txNext = 0;
    let tyNext = 0;

    let x = Math.floor(x0);
    let y = Math.floor(y0);

    let n = 1;

    if (dx == 0)
    {
      xInc = 0;
      txNext = dtDx; // infinity
    }
    else if (x1 > x0)
    {
      xInc = 1;
      n += Math.floor(x1) - x;
      txNext = (Math.floor(x0) + 1 - x0) * dtDx;
    }
    else
    {
      xInc = -1;
      n += x - Math.floor(x1);
      txNext = (x0 - Math.floor(x0)) * dtDx;
    }

    if (dy == 0)
    {
      yInc = 0;
      tyNext = dtDy; // infinity
    }
    else if (y1 > y0)
    {
      yInc = 1;
      n += Math.floor(y1) - y;
      tyNext = (Math.floor(y0) + 1 - y0) * dtDy;
    }
    else
    {
      yInc = -1;
      n += y - Math.floor(y1);
      tyNext = (y0 - Math.floor(y0)) * dtDy;
    }

    let t = 0;
    for (; n > 0; --n)
    {
        fillCell(x, y);

        if (tyNext < txNext)
        {
            y += yInc;
            t = tyNext
            tyNext += dtDy;
        }
        else
        {
            x += xInc;
            t = txNext;
            txNext += dtDx;
        }
    }
};

function main()
{
  clearCanvas();
  drawGrid();
  rayMarch(mouseVector);
  drawRay(mouseVector);
  requestAnimationFrame(main);
};

requestAnimationFrame(main);

<canvas id="demo"></canvas>

See also working fiddle. For your future reference:

• This algorithm is called DDA (digital differential analyser). The canonical implementation requires cell co-ordinates to be a floating point value with each increment of 1 denoting the width of a full cell. Thus in x, the start of the first cell's edge is 0, the middle of the second cell is 1.5, 2/3s through the third cell is 2.67, etc. The first thing you needed to do was to divide your mouseVector values by CELLSIZE and work only in this form, never in CELLSIZEd form.

• if you are learning from example code as in this case, do not change variable names within the function(s). Rather copy out your values from your custom vector into x0, y0, x1, y1 as per the original as this helps you avoid at least one class of mistakes / errors when transcribing the algorithm, i.e. it is easier to transcribe this way.

• use canonical / industry standard naming e.g. raycastCollision -> rayMarch.

• simplify your naming: drawCellOutline -> outlineCell (matches your fillCell)

• do not repeat yourself in function call parameters which you can include within the function itself e.g. fillCell(x * CELLSIZE, y * CELLSIZE) -> fillCell(x, y); since they are grid-aligned they must all be of CELLSIZE, not so?

• do not expect to use the advanced / optimised version of an algorithm until you have studied and understood the basic version.

• in my opinion, always use Allman indentation, as it is easier to understand your blocks visually.

Answer 2

The algorithm at the bottom of the article is for integer inputs (the components of rayVector are always integral multiples CELLSIZE ). As you are using floating-point numbers you may probably get an error result