# ThePythonGameBook

learn Python. Create Games

### Site Tools

en:glossary:l:line_calculation

# Differences

This shows you the differences between two versions of the page.

 — en:glossary:l:line_calculation [2020/05/23 08:16] (current)Horst JENS created 2020/05/23 08:16 Horst JENS created 2020/05/23 08:16 Horst JENS created Line 1: Line 1: + ===== Bresenham'​s Line Algorithm ===== + + calculates the tiles connected by a line in a 2D-array: + + see also: https://​en.wikipedia.org/​wiki/​Bresenham%27s_line_algorithm + + + + 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 + see also: https://​en.wikipedia.org/​wiki/​Bresenham%27s_line_algorithm + + #>>>​ 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 + +
/var/www/horst/thepythongamebook.com/data/pages/en/glossary/l/line_calculation.txt ยท Last modified: 2020/05/23 08:16 by Horst JENS