I'll implement the A* pathfinding algorithm for you. Here's a complete solution: ```python import heapq from typing import List, Tuple, Optional class AStarPathfinder: def __init__(self, grid: List[List[int]]): """ Initialize the pathfinder with a grid. Args: grid: 2D list where 0 = walkable, 1 = obstacle """ self.grid = grid self.rows = len(grid) self.cols = len(grid[0]) if grid else 0 def manhattan_distance(self, pos1: Tuple[int, int], pos2: Tuple[int, int]) -> int: """Calculate Manhattan distance between two positions.""" return abs(pos1[0] - pos2[0]) + abs(pos1[1] - pos2[1]) def get_neighbors(self, pos: Tuple[int, int]) -> List[Tuple[int, int]]: """Get valid neighboring positions (up, down, left, right).""" row, col = pos neighbors = [] # Define the four directions: up, down, left, right directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] for dr, dc in directions: new_row, new_col = row + dr, col + dc # Check if the new position is within bounds and walkable if (0 <= new_row < self.rows and 0 <= new_col < self.cols and self.grid[new_row][new_col] == 0): neighbors.append((new_row, new_col)) return neighbors def reconstruct_path(self, came_from: dict, current: Tuple[int, int]) -> List[Tuple[int, int]]: """Reconstruct the path from start to end using the came_from dictionary.""" path = [] while current in came_from: path.append(current) current = came_from[current] path.append(current) # Add the start position path.reverse() return path def find_path(self, start: Tuple[int, int], end: Tuple[int, int]) -> List[Tuple[int, int]]: """ Find the shortest path from start to end using A* algorithm. Args: start: Starting position as (row, col) end: Ending position as (row, col) Returns: List of (row, col) tuples representing the path, or empty list if no path exists """ # Validate input positions if (not (0 <= start[0] < self.rows and 0 <= start[1] < self.cols) or not (0 <= end[0] < self.rows and 0 <= end[1] < self.cols) or self.grid[start[0]][start[1]] == 1 or self.grid[end[0]][end[1]] == 1): return [] # If start and end are the same if start == end: return [start] # Priority queue: (f_score, position) open_set = [(0, start)] # Set of positions already evaluated closed_set = set() # For each position, which position it can most efficiently be reached from came_from = {} # Cost from start to each position g_score = {start: 0} # Estimated total cost from start to end through each position f_score = {start: self.manhattan_distance(start, end)} while open_set: # Get the position with the lowest f_score current_f, current = heapq.heappop(open_set) # If we've reached the end, reconstruct and return the path if current == end: return self.reconstruct_path(came_from, current) # Add current position to closed set closed_set.add(current) # Check all neighbors for neighbor in self.get_neighbors(current): if neighbor in closed_set: continue # Calculate tentative g_score tentative_g_score = g_score[current] + 1 # If this is a new position or we found a better path if neighbor not in g_score or tentative_g_score < g_score[neighbor]: # Update the best path to this neighbor came_from[neighbor] = current g_score[neighbor] = tentative_g_score f_score[neighbor] = tentative_g_score + self.manhattan_distance(neighbor, end) # Add to open set if not already there if not any(pos == neighbor for _, pos in open_set): heapq.heappush(open_set, (f_score[neighbor], neighbor)) # No path found return [] # Convenience function for easy usage def find_path(grid: List[List[int]], start: Tuple[int, int], end: Tuple[int, int]) -> List[Tuple[int, int]]: """ Find the shortest path using A* algorithm. Args: grid: 2D list where 0 = walkable, 1 = obstacle start: Starting position as (row, col) end: Ending position as (row, col) Returns: List of (row, col) tuples representing the path, or empty list if no path exists """ pathfinder = AStarPathfinder(grid) return pathfinder.find_path(start, end) # Example usage and test cases if __name__ == "__main__": # Test case 1: Simple path grid1 = [ [0, 0, 0, 0, 0], [0, 1, 1, 0, 0], [0, 0, 0, 0, 0], [0, 1, 1, 1, 0], [0, 0, 0, 0, 0] ] path1 = find_path(grid1, (0, 0), (4, 4)) print("Test 1 - Simple path:") print(f"Path: {path1}") print(f"Path length: {len(path1)}") print() # Test case 2: No path (completely blocked) grid2 = [ [0, 0, 0], [1, 1, 1], [0, 0, 0] ] path2 = find_path(grid2, (0, 1), (2, 1)) print("Test 2 - No path:") print(f"Path: {path2}") print() # Test case 3: Path around obstacles grid3 = [ [0, 0, 0, 0, 0], [0, 1, 1, 1, 0], [0, 1, 0, 1, 0], [0, 1, 0, 1, 0], [0, 0, 0, 0, 0] ] path3 = find_path(grid3, (0, 2), (4, 2)) print("Test 3 - Path around obstacles:") print(f"Path: {path3}") print(f"Path length: {len(path3)}") # Visualize the path def visualize_path(grid, path): """Visualize the grid with the path marked.""" if not path: print("No path to visualize") return # Create a copy of the grid for visualization vis_grid = [row[:] for row in grid] # Mark the path for i, (row, col) in enumerate(path): if i == 0: vis_grid[row][col] = 'S' # Start elif i == len(path) - 1: vis_grid[row][col] = 'E' # End else: vis_grid[row][col] = '*' # Path # Print the grid for row in vis_grid: print(' '.join(str(cell) for cell in row)) print() print("Visualization (S=Start, E=End, *=Path, 1=Obstacle, 0=Empty):") visualize_path(grid3, path3) ``` This implementation includes: ## Key Features: 1. **AStarPathfinder Class**: Encapsulates the A* algorithm logic 2. **Manhattan Distance Heuristic**: Used as required for grid-based pathfinding 3. **Grid Validation**: Checks for valid positions and obstacles 4. **Efficient Path Reconstruction**: Uses a `came_from` dictionary to rebuild the optimal path 5. **Priority Queue**: Uses Python's `heapq` for efficient node selection ## Algorithm Components: - **Open Set**: Priority queue of nodes to be evaluated - **Closed Set**: Set of already evaluated nodes - **G-Score**: Actual cost from start to each node - **F-Score**: Estimated total cost (G-Score + Heuristic) - **Came From**: Dictionary to reconstruct the final path ## Usage: ```python # Simple usage grid = [[0, 0, 1], [0, 0, 0], [1, 0, 0]] path = find_path(grid, (0, 0), (2, 2)) print(path) # [(0, 0), (0, 1), (1, 1), (1, 2), (2, 2)] ``` The algorithm handles edge cases like invalid positions, blocked start/end points, and situations where no path exists, returning an empty list when appropriate.

A* Pathfinding on Grid (Python)

anthropic/claude-sonnet-4

Traces

No span selected