text: # -*- coding: utf-8 -*-
  import heapq  # used for the so colled "open list" that stores known nodes
  from pathfinding.core.heuristic import manhatten, octile
  from pathfinding.core.util import backtrace, bi_backtrace
  from pathfinding.core.diagonal_movement import DiagonalMovement
  from .finder import Finder, TIME_LIMIT, MAX_RUNS, BY_END
  
  
  class AStarFinder(Finder):
      def __init__(self, heuristic=None, weight=1,
                   diagonal_movement=DiagonalMovement.never,
                   time_limit=TIME_LIMIT,
                   max_runs=MAX_RUNS):
          """
          find shortest path using A* algorithm
          :param heuristic: heuristic used to calculate distance of 2 points
              (defaults to manhatten)
          :param weight: weight for the edges
          :param diagonal_movement: if diagonal movement is allowed
              (see enum in diagonal_movement)
          :param time_limit: max. runtime in seconds
          :param max_runs: max. amount of tries until we abort the search
              (optional, only if we enter huge grids and have time constrains)
              <=0 means there are no constrains and the code might run on any
              large map.
          """
          super(AStarFinder, self).__init__(
              heuristic=heuristic,
              weight=weight,
              diagonal_movement=diagonal_movement,
              time_limit=time_limit,
              max_runs=max_runs)
  
          if not heuristic:
              if diagonal_movement == DiagonalMovement.never:
                  self.heuristic = manhatten
              else:
                  # When diagonal movement is allowed the manhattan heuristic is
                  # not admissible it should be octile instead
                  self.heuristic = octile
  
      def check_neighbors(self, start, end, grid, open_list,
                          open_value=True, backtrace_by=None):
          """
          find next path segment based on given node
          (or return path if we found the end)
          """
          # pop node with minimum 'f' value
          node = heapq.nsmallest(1, open_list)[0]
          open_list.remove(node)
          node.closed = True
  
          # if reached the end position, construct the path and return it
          # (ignored for bi-directional a*, there we look for a neighbor that is
          #  part of the oncoming path)
          if not backtrace_by and node == end:
              return backtrace(end)
  
          # get neighbors of the current node
          neighbors = self.find_neighbors(grid, node)
          for neighbor in neighbors:
              if neighbor.closed:
                  # already visited last minimum f value
                  continue
              if backtrace_by and neighbor.opened == backtrace_by:
                  # found the oncoming path
                  if backtrace_by == BY_END:
                      return bi_backtrace(node, neighbor)
                  else:
                      return bi_backtrace(neighbor, node)
  
              # check if the neighbor has not been inspected yet, or
              # can be reached with smaller cost from the current node
              self.process_node(neighbor, node, end, open_list, open_value)
  
          # the end has not been reached (yet) keep the find_path loop running
          return None
  
      def find_path(self, start, end, grid):
          """
          find a path from start to end node on grid using the A* algorithm
          :param start: start node
          :param end: end node
          :param grid: grid that stores all possible steps/tiles as 2D-list
          :return:
          """
          start.g = 0
          start.f = 0
          return super(AStarFinder, self).find_path(start, end, grid)
  