# -*- 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