GitHub Viewer
# -*- coding: utf-8 -*-
import copy
import math
# square root of 2 for diagonal distance
SQRT2 = math.sqrt(2)
def backtrace(node):
"""
Backtrace according to the parent records and return the path.
(including both start and end nodes)
"""
path = [(node.x, node.y)]
while node.parent:
node = node.parent
path.append((node.x, node.y))
path.reverse()
return path
def bi_backtrace(node_a, node_b):
"""
Backtrace from start and end node, returns the path for bi-directional A*
(including both start and end nodes)
"""
path_a = backtrace(node_a)
path_b = backtrace(node_b)
path_b.reverse()
return path_a + path_b
def raytrace(coords_a, coords_b):
line = []
x0, y0 = coords_a
x1, y1 = coords_b
dx = x1 - x0
dy = y1 - y0
t = 0
grid_pos = [x0, y0]
t_for_one = \
abs(1.0 / dx) if dx > 0 else 10000, \
abs(1.0 / dy) if dy > 0 else 10000
frac_start_pos = (x0 + .5) - x0, (y0 + .5) - y0
t_for_next_border = [
(1 - frac_start_pos[0] if dx < 0 else frac_start_pos[0]) * t_for_one[0],
(1 - frac_start_pos[1] if dx < 0 else frac_start_pos[1]) * t_for_one[1]
]
step = \
1 if dx >= 0 else -1, \
1 if dy >= 0 else -1
while t