Performance review
Your code.
You have a few inefficiencies. When implementing the same function many times with many iterations within the function, reducing the number of steps will provide worth while performance gains.
Some suggestions.
Use ===
rather than ==
as it is a little quicker
Change the sign of dy
, that means that the test if(e2 > -dy)
can be changed to if(e2 > dy)
saving the need to negate dy
each step.
Change the lines
// Change
dy = Math.abs(y1 - y0)
// to
dy = -Math.abs(y1 - y0)
// Change
err = dx - dy;
// to
err = dx + dy
// Change
if (e2 > -dy) {
err -= dy;
x0 += sx;
}
// to
if (e2 > dy) { // removes the - operation
err += dy;
x0 += sx;
}
Remove the double array index and use a column reference for the bitmap
// just before the loop
var column = bitmap[x0];
// then in the loop you only need to index the row
if (column[y0] === 1) {
return 1;
}
if (e2 > dy) {
err += dy;
x0 += sx;
column = bitmap[x0]; // and update the column only when x0 changes.
}
Not a performance thing, just a style note. You have left out the ;
after the return 0
and the locals declaration e2
.
Better yet
You could also flatten the bitmap array and use an index rather than a coordinate. You change the y step to a modulo size. This reduces the number of tests and eliminates the need to index into a 2D array.
// using bitmap as a flat array with width as the pixel width
// Assuming coords are ints
function collision(x0, y0, x1, y1, width) {
const dx = Math.abs(x1 - x0);
const dy = -Math.abs(y1 - y0);
const sx = x0 < x1 ? 1 : -1;
const sy = y0 < y1 ? width : -width;
const endIndex = x1 + y1 * width;
var e2, err = dx + dy;
var index = x0 + y0 * width;
// loop through line drawing
while (index !== endIndex) {
if (bitmap[index] === 1) { return 1 }
e2 = err << 1;
if (e2 > dy) {
err += dy;
index += sx;
}
if (e2 < dx) {
err += dx;
index += sy;
}
}
return 0;
}
Peformance
The function is out of context so performance improvements can not be suggested.
As a random line an improvement would be to step over a quad tree. But this would be a very complex bit of code and would depend on the content of the bitmap and how many pixels you are sampling. It would make major improvements when the ratio of "on" pixels is low and clumped, but poor as the ratio of "on" pixels approaches 50% and the distribution is non clumpy.
The are many other solutions but they all depend on what the line is looking for, how one line is related to the rest, and the distribution and content of the bitmap.