Section 3.4 Interactive A* Pathfinding ActiveCode

Now let’s bring all these concepts together: grid representation, Manhattan distance heuristics, and tracking path costs \(g(n)\) and \(f(n)\text{.}\)

The A* Search Processing Flow repeats a two-step cycle: first, pull the node with the lowest \(f(n)\) score from the open list. If that node is the goal, the path is reconstructed and the search stops. Otherwise, the search evaluates all of that node’s 4-connected neighbors, computing \(g(\text{neighbor}) = g(\text{current}) + 1\) and \(f(\text{neighbor}) = g + h\) for each one, and the cycle repeats by pulling the next lowest-\(f(n)\) node.

Figure 3.4.1. The A* core loop selects the lowest-cost node, checks for the goal, and otherwise evaluates neighboring cells before continuing the search.

Subsection 3.4.1 Section 3.4 Interactive Exercises

Subsubsection 3.4.1.1 Exercise 3.4.1: A* Pathfinding Completion Challenge

Below is a lightweight Python implementation of A* pathfinding on a 2D matrix grid.

Task:

Complete the heuristic function to return the Manhattan distance between cell and goal.
Complete the \(f(n)\) cost score update line: f_score = tentative_g + h_score.
Run the code to trace the shortest path found around the obstacle wall!

def heuristic(node, goal):
    # TODO: Return Manhattan Distance between node (r1, c1) and goal (r2, c2)
    r1, c1 = node
    r2, c2 = goal
    return 0  # Replace this line with correct Manhattan distance formula!

def run_astar(grid, start, goal):
    num_rows = len(grid)
    num_cols = len(grid[0])

# Open list stores tuples of (f_score, cell)
    open_list = [(0, start)]
    g_score = {start: 0}
    came_from = {}

while len(open_list) > 0:
        # Sort to find cell with lowest f_score
        open_list.sort()
        current_f, current = open_list.pop(0)

if current == goal:
            # Reconstruct path
            path = []
            while current in came_from:
                path.append(current)
                current = came_from[current]
            path.append(start)
            path.reverse()
            return path

row, col = current
        for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:  # 4-connected
            r_new, c_new = row + dr, col + dc
            neighbor = (r_new, c_new)

if 0 <= r_new < num_rows and 0 <= c_new < num_cols:
                if grid[r_new][c_new] == 0:  # If cell is free
                    tentative_g = g_score[current] + 1

if neighbor not in g_score or tentative_g < g_score[neighbor]:
                        came_from[neighbor] = current
                        g_score[neighbor] = tentative_g

h_score = heuristic(neighbor, goal)

# TODO: Compute total f_score
                        f_score = tentative_g + h_score

open_list.append((f_score, neighbor))

return None  # Path not found

# Grid layout: 0 = Free, 1 = Obstacle Wall
# Start at top-left (0, 0), Goal at bottom-right (4, 4)
grid_map = [
    [0, 0, 0, 0, 0],
    [0, 1, 1, 1, 0],
    [0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0]
]

start_pos = (0, 0)
goal_pos = (4, 4)

path = run_astar(grid_map, start_pos, goal_pos)
print("Path found by A*:", path)

You have attempted of activities on this page.

Prev Top Next