# The Python Game Book

code games. learn Python.

### Site Tools

en:glossary:l:line_calculation

## Bresenham's Line Algorithm

calculates the tiles connected by a line in a 2D-array:

```def get_line(start, end):
"""Bresenham's Line Algorithm
Produces a list of tuples from start and end
source: http://www.roguebasin.com/index.php?title=Bresenham%27s_Line_Algorithm#Python

#>>> points1 = get_line((0, 0), (3, 4))
# >>> points2 = get_line((3, 4), (0, 0))
#>>> assert(set(points1) == set(points2))
#>>> print points1
#[(0, 0), (1, 1), (1, 2), (2, 3), (3, 4)]
#>>> print points2
#[(3, 4), (2, 3), (1, 2), (1, 1), (0, 0)]
"""
# Setup initial conditions
x1, y1 = start
x2, y2 = end
dx = x2 - x1
dy = y2 - y1

# Determine how steep the line is
is_steep = abs(dy) > abs(dx)

# Rotate line
if is_steep:
x1, y1 = y1, x1
x2, y2 = y2, x2

# Swap start and end points if necessary and store swap state
swapped = False
if x1 > x2:
x1, x2 = x2, x1
y1, y2 = y2, y1
swapped = True

# Recalculate differentials
dx = x2 - x1
dy = y2 - y1

# Calculate error
error = int(dx / 2.0)
ystep = 1 if y1 < y2 else -1

# Iterate over bounding box generating points between start and end
y = y1
points = []
for x in range(x1, x2 + 1):
coord = (y, x) if is_steep else (x, y)
points.append(coord)
error -= abs(dy)
if error < 0:
y += ystep
error += dx

# Reverse the list if the coordinates were swapped
if swapped:
points.reverse()
return points

``` 