class Node(object):
    def __init__(self, row, col):
        self.row = row
        self.col = col
        self.passable = passable
        self.parent = None
        self.g = 0
        self.h = 0
        self.f = 0

class AStar(object):
    def __init__(self):
        self.open = []
        heapq.heapify(self.open)
        self.closed = set()
        self.nodes = []

    # initialize node list
    def init_grid(self, ant_loc, target):
        for row in range(ants.rows):
            for col in range(ants.cols):
                if ants.passable((row, col)):
                    passable = True
                else:
                    passable = False
                self.nodes.append(Node(
                        row, col, passable))
        self.start = ant_loc
        self.end = target

    # return node from self.nodes based on row, col
    def get_node(self, row, col):
        return self.nodes[row * ants.rows + col]

    # retrieve adjacent nodes
    def get_adj_nodes(self, node):
        nodes = []
        if col < ants.cols - 1:
            nodes.append(get_node(
                    node.row,
                    node.col + 1))
        if col == ants.cols - 1:
            nodes.append(get_node(
                    node.row,
                    1))
        if row < ants.rows - 1:
            nodes.append(get_node(
                    node.row + 1,
                    node.col))
        if row == ants.rows - 1:
            nodes.append(get_node(
                    1,
                    node.col))
        if col > 0:
            nodes.append(get_node(
                    node.row,
                    node.col - 1))
        if col == 0:
            nodes.append(get_node(
                    node.row,
                    ants.cols - 1))
        if row > 0:
            nodes.append(get_node(
                    node.row - 1,
                    node.col))
        if col == 0:
            nodes.append(get_node(
                    ants.rows - 1,
                    node.col))
        return nodes

    # create list with path
    def create_path(self):
        path = []
        node = self.end
        while node.parent is not self.start:
            node = node.parent
            path.insert(0, (node.row, node.col))

    # score g, h and set parent node
    def score_node(self, adj, node):
        adj.g = node.g + 1
        # heuristic score: ants.distance()
        adj.h = ants.distance(adj.g, self.end)
        adj.parent = node
        adj.f = adj.g + adj.h

    # A* algorithm
    def find_path(self):
        heapq.heappush(self.open,
                       (self.start.f, self.start))
        # as long as there's stuff in
        # open list, process it
        while len(self.open):
            # get cell from heapq and
            # put it in closed list
            h, node = heapq.heappop(self.open)
            self.closed.add(node)
            # at target node, create path
            if node is self.end:
                self.create_path()
                break
            # otherwise, get_adj_nodes
            adj_nodes = self.get_adj_nodes(node)
            # check if adj_node is better
            # than previously found
            for adj in adj_nodes:
                if adj.passable and adj not in self.closed:
                    if adj in self.open:
                        if adj.g > node.g + 1:
                            # score_node and be done with it
                            self.score_node(adj, node)
                        else:
                            # score_node and add to open list
                            self.score_node(adj, node)
                            heapq.heappush(self.open,
                                           (adj.f, adj))