Modifying Bresenham's line algorithm
        Posted  
        
            by sphennings
        on Stack Overflow
        
        See other posts from Stack Overflow
        
            or by sphennings
        
        
        
        Published on 2010-04-29T04:05:20Z
        Indexed on 
            2010/04/29
            4:07 UTC
        
        
        Read the original article
        Hit count: 607
        
I'm trying to use Bresenham's line algorithm to compute Field of View on a grid. The code I'm using calculates the lines without a problem but I'm having problems getting it to always return the line running from start point to endpoint. What do I need to do so that all lines returned run from (x0,y0) to (x1,y1)
def bresenham_line(self, x0, y0, x1, y1):
steep = abs(y1 - y0) > abs(x1 - x0)
if steep:
    x0, y0 = y0, x0  
    x1, y1 = y1, x1
if x0 > x1:
    x0, x1 = x1, x0
    y0, y1 = y1, y0
if y0 < y1: 
    ystep = 1
else:
    ystep = -1
deltax = x1 - x0
deltay = abs(y1 - y0)
error = -deltax / 2
y = y0
line = []    
for x in range(x0, x1 + 1):
    if steep:
        line.append((y,x))
    else:
        line.append((x,y))
    error = error + deltay
    if error > 0:
        y = y + ystep
        error = error - deltax
return line
© Stack Overflow or respective owner