Tile based line drawing algorithm efficiency

Question

Hello!

Here are two functions I have implemented that accepts two points and then creates a line of points between them. I intend to use this for line of sight calculations and the like in a tile based environment.

#Returns a set of points from p0 to p1 using linear interpolation
#use: interpolated_line([0, 0], [10, 10])
func interpolated_line(p0, p1):
    var points = []
    var dx = p1[0] - p0[0]
    var dy = p1[1] - p0[1]
    var N = max(abs(dx), abs(dy))
    for i in N + 1:
        var t = float(i) / float(N)
        var point = [round(lerp(p0[0], p1[0], t)), round(lerp(p0[1], p1[1], t))]
        points.append(point)
    return points

and:

#Returns a set of points from p0 to p1 using Bresenham's line algorithm
#use: line([0, 0], [10, 10])
func line(p0, p1):
    var points = []
    var dx = abs(p1[0] - p0[0])
    var dy = -abs(p1[1] - p0[1])
    var err = dx + dy
    var e2 = 2 * err
    var sx = 1 if p0[0] < p1[0] else -1
    var sy = 1 if p0[1] < p1[1] else -1
    while true:
        points.append([p0[0], p0[1]])
        if p0[0] == p1[0] and p0[1] == p1[1]:
            break
        e2 = 2 * err
        if e2 >= dy:
            err += dy
            p0[0] += sx
        if e2 <= dx:
            err += dx
            p0[1] += sy
    return points

The first one uses simple linear interpolation to find the points, while the second uses Bresenham's line algorithm. Now, common consensus is that the Bresenham line is going to be more efficient, because it only uses integer math, while the linear interpolation is going to be slower because it relies on floats.

However, when I do benchmarking on these two algorithms the linear interpolation one consistently comes out on top. I was just wondering why this is and whether I'm doing something wrong?

Comments

As far as I'm aware, and iirc, Bresenham's algorithm was developed back when CPUs were rather slow at dealing with floating point arithmetic, hence the use of integer values all the way through. That isn't the case anymore these days, computers have become fairly competent at dealing with floats, so we see a decline in the performance gain from his algorithm.

That said, when I compared my own adaptation of his algorithm to my own adaptation of RedBlobGames's algorithm, Bresenham was still considerably faster. I suppose part of that would be down to the overhead of using several functions in RedBlob's.
https://github.com/Skaruts/Godot-Basic-Roguelike/blob/master/scripts/autoload/utils.gd#L12 (this is in Godot 2)

Maybe you found a faster algorithm?

I could try to unearth my old roguelike project (not the one in the link) and get your algorithm in there and compare it to those. I don't have a proper way to benchmarking them other than comparing frame-rates...

---

Here is another alogorithm. Not sure if it is fast one, but it it guaranties that line should not pass through diagonal edges like in Bresenham's algorithm and Interpolation Line algorithm:

# Amit Patel’s algorithm ( https://www.redblobgames.com )
static func WalkGrid( p0,  p1):
    var dx = p1[0] - p0[0]
    var dy = p1[1] - p0[1]
    var nx = abs( dx )
    var ny = abs( dy )
    var signX = sign( dx )
    var signY = sign( dy )
    var p = p0
    var points : Array = [p]

    var ix = 0
    var iy = 0

    while ix < nx || iy < ny:
        if ( ( 1 + ( ix << 1) ) * ny < ( 1 + ( iy << 1) ) * nx ):
            p[0] += signX
            ix +=1
        else:
            p[1] += signY
            iy += 1
        points.append(p)
    return points

Because we are using integers for tile coordinates, you can "optimize" at least following things with your own abs() and sign() functions, if optimized in GDScript is faster than call to C++ functions :)

var nx = abs( dx ) ===> call: static func absInt(x : int) -> int: return (x ^ (x >> 31)) - (x >> 31)
var signX = sign( dx ) ===> call: static func signOf( x : int) -> int: return absInt( (x | -x) >>31 ) | (x >> 31)