import math
import heapq
import v2

def linearPath(start, end, facing=False):
    """ See http://www.gamedev.net/reference/articles/article1275.asp
    for explaination.
    """
    path = []

    x1,y1 = start
    x2,y2 = end
    dx,dy = v2.absDiff(start, end)

    if x2 >= x1: xi1,xi2 = 1,1
    else: xi1,xi2 = -1,-1

    if y2 >= y1: yi1,yi2 = 1,1
    else: yi1,yi2 = -1,-1

    if dx >= dy:
        xi1,yi2 = 0,0
        d = dx
        n = dx//2
        fraction = dy
        diff = dx
    else:
        xi2,yi1 = 0,0
        d = dy
        n = dy//2
        fraction = dx
        diff = dy

    x,y = x1,y1
    for i in range(diff + 1):
        path.append((x,y))
        n += fraction
        if n > d:
            n -= d
            x += xi1
            y += yi1
            if facing: path.append((x,y))
        x += xi2
        y += yi2
    return path

#-----------------------------------------------------------------
D_straight = 2
D_diagonal = 3
# global for debuging (paintAstar)
OPENED = []
OPENED_i = 0

class Node:
    def __init__(self, prevNode, pos, dest):
        self.prevNode = prevNode
        self.pos = pos
        self.dest = dest
        self.g = self.gDist()
        self.h = self.hDist()
        self.f = self.g + self.h
    def gDist(self):
        result = 0
        if self.prevNode is not None:
            d = D_straight
            if (self.prevNode.pos[0] != self.pos[0] and
                    self.prevNode.pos[1] != self.pos[1]):
                d = D_diagonal
            result = self.prevNode.g + d
        return result
    def hDist(self):
        dx, dy = v2.absDiff(self.pos, self.dest)
        minD = min(dx, dy)
        maxD = max(dx, dy)
        return D_diagonal * minD + D_straight * (maxD - minD)
    def __cmp__(self, other):
        cmp = self.f - other.f
        if cmp == 0:
            cmp = self.h - other.h
        return cmp

def shortPath(start, goal, maze):
    """ Computes shortes path by A*.
    Return empty path when there is no way.

    See the theory:
    http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html
    """
    global OPENED, OPENED_i
    OPENED = []
    OPENED_i = 0

    if maze.isWall(start):
        return []
    if maze.isWall(goal):
        return []

    opened_queue = []
    opened = {}
    closed = {}
    cur = Node(None, start, goal)
    opened[cur.pos] = cur
    heapq.heappush(opened_queue, cur)
    while len(opened):
        cur = heapq.heappop(opened_queue)
        if cur.pos not in opened: continue
        del opened[cur.pos]
        closed[cur.pos] = cur
        OPENED.append(cur)
        if cur.pos == goal: break
        for dx,dy in ((0,-1),(1,0),(0,1),(-1,0), (-1,-1),(1,-1),(-1,1),(1,1)):
            pos = cur.pos[0]+dx,cur.pos[1]+dy
            if maze.isWall(pos): continue
            #check for blocks of diagonals
            if maze.isWall((cur.pos[0], cur.pos[1]+dy)): continue
            if maze.isWall((cur.pos[0]+dx, cur.pos[1])): continue
            new = Node(cur,pos,goal)
            if pos in opened and new.f >= opened[pos].f: continue
            if pos in closed and new.f >= closed[pos].f: continue
            if pos in closed:
                del closed[pos]
            opened[pos] = new
            heapq.heappush(opened_queue, new)

    if cur.pos != goal:
        print "no way to the goal, start=%s, goal=%s" % (start, goal)
        return []

    path = []
    while cur.prevNode is not None:
        path.append(cur.pos)
        cur = cur.prevNode
    path.reverse()
    return path