A priority queue removes or presents elements by priority instead of insertion order. Unlike a stack or ordinary queue, it keeps the most promising item at the front. section 3.3
In A* search, the priority queue holds nodes waiting to be explored. It selects the node with the lowest estimated total cost, allowing the search to switch between branches when a cheaper path appears. section 3.3 section 3.4
A typical priority-queue search proceeds by:
- Adding the root node, then repeatedly checking whether the queue is empty. section 3.4
- Popping the lowest-cost node as the current node and skipping it if it was already visited. section 3.4
- Marking the node visited, testing for the goal, and returning the path through parent links when successful. section 3.4
- Calculating each neighbor's cost and adding it to the queue, which maintains the ordering without manual sorting. section 3.4
A* through a maze
Suppose several maze positions are waiting to be explored. A* adds the start position, removes the position with the lowest estimated total cost, and adds its neighbors with calculated costs. If a cheaper neighbor from another branch enters the queue, it rises ahead of more expensive positions and is explored next. Repeating this process either reaches the goal or exhausts the queue and reports that no path exists. section 3.3 section 3.4
def run_astar(maze_game, start_point):
visited_points = []
goal_point = find_goal_point(maze_game)
priority_queue = []
tie = itertools.count() #A
start_point.cost = 0
heapq.heappush(priority_queue, #B
➥(start_point.cost, next(tie), start_point))
while priority_queue:
_, _, next_point =
➥heapq.heappop(priority_queue) #C
if is_in_visited_points(next_point, visited_points):
continue #D
visited_points.append(next_point)
if maze_game.get_current_point_value(next_point) #E
➥== mp.MazePuzzle.GOAL:
return next_point
for neighbor in maze_game.get_neighbors(next_point):
neighbor.set_parent(next_point) #F
neighbor.cost =
➥determine_cost(next_point, neighbor, goal_point) #G
heapq.heappush(priority_queue,
➥(neighbor.cost, next(tie), neighbor)) #H
return "No path to the goal found"
Inspect a Python implementation using a heap, tie-breaker, push, pop, visited tracking, parent links, and neighbor costs. section 3.4
def determine_cost(origin, target, goal_point):
g_cost = mp.get_path_length(target) #A
move_cost = mp.get_move_cost(origin, target) #B
h_cost = abs(target.x - goal_point.x)
➥+ abs(target.y - goal_point.y) #C
return g_cost + move_cost + h_cost
Trace how path length, movement cost, and heuristic distance combine into the priority used for each node. section 3.4
