pvdz.ee - Bresenham in JS

The Bresenham-based supercover line algorithm is a so called "super cover" algorithm. You take a grid of tiles and a line and it will tell you exactly which tiles the line touches. This is what I was initially using for raycasting but it's a super dirty port. Just wanted to put it here for keepsakes before I throw it out to replace it with my own.

Note that this is a modified variation of the original algorithm. It was taken from this page, which also describes it in more detail.

To use it define a single dimensional map and the dimensions of it (in tiles):

Code:

var map = [];
var WIDTH = 10;
var HEIGHT = 5;

bresenham(3, 5.6, 8.3, 1.2);

And the call will either return an object with x, y, index of the first solid tile the line hits or null if the line did not intersect with any solid tiles.

Below the "library" code. Again, this is UGLY and NOT OPTIMIZED. It's just a quick and dirty port.

Code:

function bresenham(x1, y1, x2, y2) {
  var dx = Math.abs(x2 - x1);
  var dy = Math.abs(y2 - y1);
  var deltaX = x1 < x2 ? 1 : -1;
  var deltaY = y1 < y2 ? 1 : -1;

  if (dy < dx) {
    var deltaProgress = dy / dx;
    var p = _bresenham1(x1, y1, x2, deltaX, deltaY, deltaProgress);
  } else {
    var deltaProgress = dx / dy;
    var p = _bresenham2(x1, y1, y2, deltaX, deltaY, deltaProgress);
  }

  return p;
}
function _bresenham1(a, b, limit, deltaA, deltaB, delta) {
  // compensate for fractional position
  var progress = b%1;
  if (deltaB < 0) progress = 1 - progress;
  // move y to nearest integer, depending on whether deltaY is positive or negative
  // increase error by amount of y moved
  var t = a%1;
  if (t && deltaA > 0) t = 1 - t;
  progress += delta * t;
  a = deltaA < 0 ? Math.floor(a) : Math.ceil(a);
  // check if error is already overflowing
  if (progress >= 1) {
    b += deltaB;
    --progress;
    var p = POINT(deltaA > 0 ? a-1 : a, b);
    if (p) return p;
  }

  var looper = 0;
  var slope = deltaA<0;
  while (slope?a>limit:a    if (++looper > 100) throw 'endless loop';
    progress += delta;
    var p = POINT(deltaA < 0 ? a-1 : a, b);
    if (p) return p;
    if (progress >= 1) {
      b += deltaB;
      --progress;
      var p = POINT(deltaA < 0 ? a-1 : a, b);
      if (p) return p;
    }

    a+=slope?-1:1;//deltaA
  }
}
function _bresenham2(b, a, limit, deltaB, deltaA, delta) {
  // compensate for fractional position
  var progress = b%1;
  if (deltaB < 0) progress = 1 - progress;
  // move y to nearest integer, depending on whether deltaY is positive or negative
  // increase error by amount of y moved
  var t = a%1;
  if (t && deltaA > 0) t = 1 - t;
  progress += delta * t;
  a = deltaA < 0 ? Math.floor(a) : Math.ceil(a);
  // check if error is already overflowing
  if (progress >= 1) {
    b += deltaB;
    --progress;
    var p = POINT(b, deltaA > 0 ? a-1 : a);
    if (p) return p;
  }

  var looper = 0;
  while (deltaA<0?a>limit:a    if (++looper > 100) throw 'endless loop';
    progress += delta;
    var p = POINT(b, deltaA < 0 ? a-1 : a);
    if (p) return p;
    if (progress >= 1) {
      b += deltaB;
      --progress;
      var p = POINT(b, deltaA < 0 ? a-1 : a);
      if (p) return p;
    }

    a+=deltaA
  }
}
function POINT(x, y) {
  if (x < 0 || y < 0 || x >= WIDTH || y >= HEIGHT) {
    return true; // true means OOB
  }

  x = Math.floor(x);
  y = Math.floor(y);

  var n = y*WIDTH+x;
  if (!map[n]) return {x:x,y:y,n:n};
}