 |
Attention | Topic was automatically imported from the old Question2Answer platform. |
 |
Asked By | aa |
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?
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…
woopdeedoo | 2018-11-03 10:53
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)
pospathos | 2018-11-10 01:27