Нарисуйте линию от начала (X, Y) до пункта назначения (X, Y)

Question

Я изо всех сил пытаюсь создать простую игру с картой мира, на которой игрок будет перемещаться, используя клик и вперед -линейный метод. Для этого я пытаюсь сделать простую функцию, чтобы вычислить список XY пикселей для прохода игрока.

Большинство из них отлично работает, но у меня возникают проблемы с этим, умножая один из результатов на 2, когда назначения X и Y не равны. У меня очень трудное время, чтобы устранить эту проблему, и если кто-то подумает о том, как ее улучшить или исправить, я был бы очень благодарен.

import math 

def linePath(start, finish): 
    if start[0] == finish[0]: 
     a = 1 
    else: 
     a = (finish[1] - start[1])/float((finish[0] - start[0])) 
    b = start[1] - (a * start[0]) 
    if abs(a) >= 1: 
     rng = xrange(start[1], finish[1] + 1) or reversed(xrange(finish[1], start[1] + 1)) 
    else: 
     rng = xrange(start[0], finish[0] + 1) or reversed(xrange(finish[0], start[0] + 1)) 
    for i in rng: 
     if abs(a) >= 1: 
      y = i 
      x = int(math.ceil((y - b)/ a)) 
     else: 
      x, y = i, start[1] + int(math.ceil(a * i + b)) 
     if start[0] != finish[0]: 
      yield x, y 
     else: 
      yield start[0], y 

start = (10, 10) 
destination = (15, 15) 

print list(linePath(start, destination)) 

#Bugs: when start[0] > start[1] and start > destination (eg. destination = (16, 15)) 
     #when start[0] < start[1] and start < destination (eg. destination = (5, 6)) 

Answer 1

К счастью, Джек Элтон Брешенхам решил эту проблему 1962 года для вас.

Вот реализация Bresenham's line algorithm, найденный в Roguebashin:

def get_line(x1, y1, x2, y2): 
    points = [] 
    issteep = abs(y2-y1) > abs(x2-x1) 
    if issteep: 
     x1, y1 = y1, x1 
     x2, y2 = y2, x2 
    rev = False 
    if x1 > x2: 
     x1, x2 = x2, x1 
     y1, y2 = y2, y1 
     rev = True 
    deltax = x2 - x1 
    deltay = abs(y2-y1) 
    error = int(deltax/2) 
    y = y1 
    ystep = None 
    if y1 < y2: 
     ystep = 1 
    else: 
     ystep = -1 
    for x in range(x1, x2 + 1): 
     if issteep: 
      points.append((y, x)) 
     else: 
      points.append((x, y)) 
     error -= deltay 
     if error < 0: 
      y += ystep 
      error += deltax 
    # Reverse the list if the coordinates were reversed 
    if rev: 
     points.reverse() 
    return points 

start = (10, 10) 
destination = (16, 15) 

print list(get_line(start[0], start[1], destination[0], destination[1])) 

Выход:

[(10, 10), (11, 11), (12, 12), (13, 12), (14, 13), (15, 14), (16, 15)]