original_docstring:  This function performs A* on input data 
docstring: This function performs A* on input data
docstring_tokens: This function performs A * on input data
code: def astar(grid, start, target, max_height_delta):
      """ This function performs A* on input data """
      # create start node
      w = grid.shape[1] # width of grid
      h = grid.shape[0] # height of grid
      neighbor_matrix = np.array([[1, -1], [1, 0], [1, 1], 
                                  [0, -1], [0, 1],
                                  [-1, -1], [-1, 0], [-1, 1]])
      start_height = find_height(grid, start)
      start_node = Node(start, start_height)
      node_id = 1 # initialize unique node id 
      start_node.id = node_id
      # add start_node to queue
      open_queue = deque()
      open_queue.append(start_node)
      closed = {} # initialize closed dictionary
      loop_count = 1 # for testing 
      # loop until queue empty or target found
      start_loop_time = time.time()
      #while True:
      while loop_count < 1001:
      #for i in range(2): # testing 
          #start_loop_time = time.time()
          if len(open_queue) == 0: # return fail if queue is empty
              result = 'FAIL'
              print('result: ', result) # test print
              print('cost: ', 2147483647) # for testing
              return result
          active_node = open_queue.popleft()
          #print('ACTIVE NODE: ', active_node.coord) #FOR TESTING
          if np.array_equal(active_node.coord, target): # return path when target is reached
              result = get_path(active_node, closed) # calls function to print full solution path
              print('result: ', result) # test print
              print('cost: ', active_node.cost) # for testing 
              return result
          for j in range(8): # loop through all 8 potential neighbors
              neighbor_coord = active_node.coord + neighbor_matrix[j]
              unit_path_cost = calc_unit_path_cost(neighbor_matrix[j])
              if bound_check(neighbor_coord, w, h): # boundary check
                  neighbor_height = find_height(grid, neighbor_coord)
                  mud_cost = find_mud_cost(grid, neighbor_coord, neighbor_height)
                  #print('mud cost: ', neighbor_coord, mud_cost) #testing
                  if height_check(neighbor_height, active_node.height, max_height_delta): # height check
                      height_change = abs(neighbor_height - active_node.height)
                      node_id += 1   
                      neighbor = Node(neighbor_coord, neighbor_height)
                      neighbor.id = node_id
                      neighbor.parent = active_node.id
                      neighbor.cost = active_node.cost + unit_path_cost + mud_cost + height_change # cumulative path cost
                      neighbor.heuristic = calc_heuristic(neighbor_coord, target)
                      open_queue, closed = loop_check(neighbor, closed, open_queue) # performs loop check and modifies open/closed as needed
          closed[active_node.id] = active_node # add node to closed dictionary
          open_queue = astar_sort(open_queue) # sort open queue
          end_loop_time = time.time()
          # if loop_count % 1000 == 0: # for testing 
          #     print('still looping...just passed loop #', loop_count)
          #     print('time spent in loop #', loop_count, ': ', end_loop_time - start_loop_time, 'seconds')
          # loop_count += 1
          if loop_count % 10 == 0: # for testing 
              print('======================= loop #', loop_count, "=======================")
              print('Popped node ID: ', active_node.id)
              print('Popped node coord: ', active_node.coord)
              print('Parent of popped node: ', active_node.parent)
              print('elapsed time: ', end_loop_time - start_loop_time, 'seconds')
          loop_count += 1
          #print('closed coord: ', closed[active_node.id].coord) #FOR TESTING 
code_tokens: def astar ( grid , start , target , max_height_delta ) : w = grid . shape [ 1 ] h = grid . shape [ 0 ] neighbor_matrix = np . array ( [ [ 1 , - 1 ] , [ 1 , 0 ] , [ 1 , 1 ] , [ 0 , - 1 ] , [ 0 , 1 ] , [ - 1 , - 1 ] , [ - 1 , 0 ] , [ - 1 , 1 ] ] ) start_height = find_height ( grid , start ) start_node = Node ( start , start_height ) node_id = 1 start_node . id = node_id open_queue = deque ( ) open_queue . append ( start_node ) closed = { } loop_count = 1 start_loop_time = time . time ( ) while loop_count < 1001 : if len ( open_queue ) == 0 : result = 'FAIL' print ( 'result: ' , result ) print ( 'cost: ' , 2147483647 ) return result active_node = open_queue . popleft ( ) if np . array_equal ( active_node . coord , target ) : result = get_path ( active_node , closed ) print ( 'result: ' , result ) print ( 'cost: ' , active_node . cost ) return result for j in range ( 8 ) : neighbor_coord = active_node . coord + neighbor_matrix [ j ] unit_path_cost = calc_unit_path_cost ( neighbor_matrix [ j ] ) if bound_check ( neighbor_coord , w , h ) : neighbor_height = find_height ( grid , neighbor_coord ) mud_cost = find_mud_cost ( grid , neighbor_coord , neighbor_height ) if height_check ( neighbor_height , active_node . height , max_height_delta ) : height_change = abs ( neighbor_height - active_node . height ) node_id += 1 neighbor = Node ( neighbor_coord , neighbor_height ) neighbor . id = node_id neighbor . parent = active_node . id neighbor . cost = active_node . cost + unit_path_cost + mud_cost + height_change neighbor . heuristic = calc_heuristic ( neighbor_coord , target ) open_queue , closed = loop_check ( neighbor , closed , open_queue ) closed [ active_node . id ] = active_node open_queue = astar_sort ( open_queue ) end_loop_time = time . time ( ) if loop_count % 10 == 0 : print ( '======================= loop #' , loop_count , "=======================" ) print ( 'Popped node ID: ' , active_node . id ) print ( 'Popped node coord: ' , active_node . coord ) print ( 'Parent of popped node: ' , active_node . parent ) print ( 'elapsed time: ' , end_loop_time - start_loop_time , 'seconds' ) loop_count += 1
short_docstring: This function performs A* on input data
short_docstring_tokens: This function performs A * on input data
comment: """ This function performs A* on input data """$SEP$# create start node$SEP$# width of grid$SEP$# height of grid$SEP$# initialize unique node id $SEP$# add start_node to queue$SEP$# initialize closed dictionary$SEP$# for testing $SEP$# loop until queue empty or target found$SEP$#while True:$SEP$#for i in range(2): # testing $SEP$#start_loop_time = time.time()$SEP$# return fail if queue is empty$SEP$# test print$SEP$# for testing$SEP$#print('ACTIVE NODE: ', active_node.coord) #FOR TESTING$SEP$# return path when target is reached$SEP$# calls function to print full solution path$SEP$# test print$SEP$# for testing $SEP$# loop through all 8 potential neighbors$SEP$# boundary check$SEP$#print('mud cost: ', neighbor_coord, mud_cost) #testing$SEP$# height check$SEP$# cumulative path cost$SEP$# performs loop check and modifies open/closed as needed$SEP$# add node to closed dictionary$SEP$# sort open queue$SEP$# if loop_count % 1000 == 0: # for testing $SEP$#     print('still looping...just passed loop #', loop_count)$SEP$#     print('time spent in loop #', loop_count, ': ', end_loop_time - start_loop_time, 'seconds')$SEP$# loop_count += 1$SEP$# for testing $SEP$#print('closed coord: ', closed[active_node.id].coord) #FOR TESTING 