text: def heuristic(start, goal):
      # Use Chebyshev distance heuristic if we can move one square either
      #adjacent or diagonal
      D = 1
      D2 = 1
      dx = abs(start[0] - goal[0])
      dy = abs(start[1] - goal[1])
      return D * (dx + dy) + (D2 - 2 * D) * min(dx, dy)
  
  
  def get_vertex_neighbours(pos, diameter, width, height):
      n = []
      # Moves allow link a chess king
      for dx, dy in [(diameter, 0), (-diameter, 0), (0, diameter), (0, -diameter)]:
          x2 = pos[0] + dx
          y2 = pos[1] + dy
          if x2 < 0 or x2 > width-1 or y2 < 0 or y2 > height-1:
              continue
          n.append((x2, y2))
      return n
  
  
  def astar_search(start, end, graph, diameter, width, height):
  
      G = {}  # Actual movement cost to each position from the start position
      F = {}  # Estimated movement cost of start to end going via this position
  
      # Initialize starting values
      G[start] = 0
      F[start] = heuristic(start, end)
  
      closedVertices = set()
      openVertices = set([start])
      cameFrom = {}
  
      # Adding a stop condition
      outer_iterations = 0
      max_iterations = (len(graph[0]) * len(graph) // 2)
  
      while len(openVertices) > 0:
          outer_iterations += 1
  
          # Get the vertex in the open list with the lowest F score
          current = None
          currentFscore = None
          for pos in openVertices:
              if current is None or F[pos] < currentFscore:
                  currentFscore = F[pos]
                  current = pos
  
          # Check if we have reached the goal
          if current == end:
              # Retrace our route backward
              path = [current]
              while current in cameFrom:
                  current = cameFrom[current]
                  path.append(current)
              path.reverse()
              return path  # Done!
  
          # Mark the current vertex as closed
          openVertices.remove(current)
          closedVertices.add(current)
  
          # Update scores for vertices near the current position
          for neighbour in get_vertex_neighbours(current, diameter, width, height):
              if neighbour in closedVertices:
                  continue  # We have already processed this node exhaustively
              x = neighbour[0]
              y = neighbour[1]
              if graph[x][y] != 150:
                  continue
              else:
                  candidateG = G[current] + 1
  
              if neighbour not in openVertices:
                  openVertices.add(neighbour)  # Discovered a new vertex
  
              elif candidateG >= G[neighbour]:
                  continue  # This G score is worse than previously found
  
              # Adopt this G score
              cameFrom[neighbour] = current
              G[neighbour] = candidateG
              H = heuristic(neighbour, end)
              F[neighbour] = G[neighbour] + H
  
      raise RuntimeError("A* failed to find a solution")
  
  def astar_path(M, Memory, path):
      for q in path:
          x=q[0]
          y=q[1]
          Memory.append((x, y))