import heapq

 grid.obstacles = [partner.pos]
    
    def is_passable(self, x, y):
        return self.at(x, y) in (FLOOR_CELL, "0", "1") and not (x, y) in self.obstacles
    
    
class NoPathFound(Exception):
    pass

class Node(tuple):
    def __new__(self, x, y, parent=None):
        n = tuple.__new__(self, (x, y))
        n.parent = parent
        n.cost = 0
        return n

class NodesHeap():
    def __init__(self):
        self._lst = []

    def push(self, node, priority):
        heapq.heappush(self._lst, (priority, node))

    def pop(self):
        return heapq.heappop(self._lst)[1]


class Pathfinder():

    @staticmethod
    def a_star(grid, origin, target):
        nodes = NodesHeap()
        origin = Node(*origin)
        nodes.push(origin, 0)

        while nodes:
            current = nodes.pop()
            if current == target:
                break

            for x, y in grid.neighbors(*current):

                node = Node(x, y, current)

                # get the moving cost to this node
                movingcost = grid.movingcost(*current, *node)
                if movingcost < 0:
                    continue

                # cost of the node is the accumulated cost from origin
                node.cost = current.cost + movingcost

                # priority of the node is the sum of its cost and distance to target
                # (the lower the better)
                priority = node.cost + grid.geometry.manhattan(*node, *target)

                # (?) would it be necessary to check if there is already a
                # node with same coordinates and a lower priority?

                # append to the checked nodes list
                nodes.push(node, priority)
        else:
            # all the reachable nodes hve been checked, no way found to the target
            raise NoPathFound("no path were found to the targetted location {}".format(target))

        # build the result by going back up from target to origin
        result = [target]
        while current != origin:
            result.append(tuple(current))
            current = current.parent
        result.append(origin)
        result.reverse()

        return result