# Bresenham in JS

2015-03-03

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};}`