ThePythonGameBook

learn Python. Create Games

User Tools

Site Tools


en:glossary:l:line_calculation

Differences

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

Link to this comparison view

en:glossary:l:line_calculation [2020/05/23 08:16] (current)
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
 +
 +
 +<code python>
 +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
 +
 +</​code>​
/var/www/horst/thepythongamebook.com/data/pages/en/glossary/l/line_calculation.txt ยท Last modified: 2020/05/23 08:16 by Horst JENS