title: Optimizing the A-Star (A*) Path Finding
body: <p>I recently coded the A* pathfinding algorithm in Python. This is based on a coordinate system where each coordinate has a value which is its elevation and there is a maximum elevation difference (the difference between the elevation of 2 adjacent nodes) which decides whether we can move to that node or not.
  How do I optimize this more?
  Also, any suggestions to improve the code or if you see any feedback if I am going wrong anywhere are welcome!</p>
  
  <p>I tried multiple heuristics like the distance formula but the one mentioned here seems to be working best for me. Correct me if I am wrong.</p>
  
  <pre><code>def astar(target_cord):
  
      def find_neighbor_astar(current):
          neighbor_mat = dict()
          current_matrix_cord = matrix[current[0]][current[1]]
          for x in neighbor_scope:
              for y in neighbor_scope:
                  x_cord = current[0]+x
                  y_cord = current[1]+y
                  if(x != 0 or y != 0):
                      if((x_cord) &gt;= 0 and x_cord &lt; max_cols and y_cord &gt;= 0 and y_cord &lt; max_rows and abs(current_matrix_cord - matrix[x_cord][y_cord]) &lt;= elevation_max):
                          if(x!=0 and y!=0):
                              neighbor_mat[x_cord, y_cord] = 14 + abs(current_matrix_cord - matrix[x_cord][y_cord])
                          else:
                              neighbor_mat[x_cord, y_cord] = 10 + abs(current_matrix_cord - matrix[x_cord][y_cord])
          return neighbor_mat
  
      def getheuristic(current, target_cord):
          # return (int(abs(((((target_cord[0]-current[0])**2)+((target_cord[1]-current[1])**2))**0.5))*10))
          dx = abs(current[0] - target_cord[0])
          dy = abs(current[1] - target_cord[1])
          return (dx + dy) + (2**0.5 - 2) * min(dx, dy)
  
      parent_cord = {start_cord: (None, 0)}
      frontier_nodes_heap = [(0, start_cord)]
      frontier_nodes = dict()
      frontier_nodes[start_cord] = 0
      node_gofx = dict()
      node_gofx[start_cord] = 0
      explored_nodes = set()
      while frontier_nodes_heap:
          curr_node = heapq.heappop(frontier_nodes_heap)[1]
          del frontier_nodes[curr_node]
          curr_cost = node_gofx[curr_node]
          if(curr_node == target_cord):
              return tracepath_ucs(parent_cord, target_cord)
          explored_nodes.add(curr_node)
          for x, step_cost in find_neighbor_astar(curr_node).items():
              gofx = curr_cost + step_cost
              path_cost = gofx + getheuristic(x, target_cord)
              if x in explored_nodes:
                  continue
              if(x not in frontier_nodes):
                  if(x not in parent_cord):
                      parent_cord[x] = (curr_node, step_cost)
                  heapq.heappush(frontier_nodes_heap,(path_cost,x))
                  frontier_nodes[x] = path_cost
                  node_gofx[x] = gofx
              elif(x in frontier_nodes and path_cost &lt; frontier_nodes[x]):
                  frontier_nodes_heap[frontier_nodes_heap.index((frontier_nodes[x],x))] = (path_cost, x)
                  frontier_nodes[x] = path_cost
                  parent_cord[x] = (curr_node, step_cost)
                  node_gofx[x] = gofx
      return []
  </code></pre>