import heapq
class Node:
""""""
Represents a node in the grid for A* pathfinding.
Attributes:
x (int): The x-coordinate of the node.
y (int): The y-coordinate of the node.
parent (Node, optional): The parent node in the path. Defaults to None.
g (int): Cost from the start node to this node. Defaults to 0.
h (int): Estimated cost from this node to the end node. Defaults to 0.
""""""
def __init__(self, x, y, parent=None):
self.x = x
self.y = y
self.parent = parent
self.g = 0
self.h = 0
def __lt__(self, other):
""""""Compares nodes based on their f-score (g + h).""""""
return (self.g + self.h) < (other.g + other.h)
def a_star(grid, start, end):
""""""
Implements the A* pathfinding algorithm.
Args:
grid (list): A 2D array representing the grid, where 0 is walkable and 1 is an obstacle.
start (tuple): The starting point coordinates (x, y).
end (tuple): The end point coordinates (x, y).
Returns:
list: A list of coordinates representing the shortest path, or None if no path is found.
""""""
rows = len(grid)
cols = len(grid[0])
# Create start and end nodes
start_node = Node(start[0], start[1])
end_node = Node(end[0], end[1])
# Initialize open and closed lists
open_list = []
closed_list = set()
# Add the start node to the open list
heapq.heappush(open_list, start_node)
while open_list:
# Get the node with the lowest f-score
current_node = heapq.heappop(open_list)
# Add the current node to the closed list
closed_list.add((current_node.x, current_node.y))
# Check if we've reached the goal
if current_node.x == end_node.x and current_node.y == end_node.y:
# Reconstruct and return the path
path = []
while current_node:
path.append((current_node.x, current_node.y))
current_node = current_node.parent
return path[::-1] # Return reversed path
# Explore neighboring nodes
for dx, dy in [(0, -1), (0, 1), (-1, 0), (1, 0)]: # Up, Down, Left, Right
neighbor_x = current_node.x + dx
neighbor_y = current_node.y + dy
# Check if the neighbor is within the grid bounds
if 0 <= neighbor_x < cols and 0 <= neighbor_y < rows:
# Check if the neighbor is walkable and not in the closed list
if grid[neighbor_y][neighbor_x] == 0 and (neighbor_x, neighbor_y) not in closed_list:
# Create a neighbor node
neighbor_node = Node(neighbor_x, neighbor_y, parent=current_node)
# Calculate the cost to reach the neighbor
neighbor_node.g = current_node.g + 1
# Calculate the heuristic (Manhattan distance)
neighbor_node.h = abs(neighbor_node.x - end_node.x) + abs(neighbor_node.y - end_node.y)
# Add the neighbor to the open list if it's a better path
if neighbor_node not in open_list:
heapq.heappush(open_list, neighbor_node)
# No path found
return None
# Example usage:
grid = [
[0, 0, 0, 0, 0],
[0, 1, 0, 1, 0],
[0, 0, 0, 0, 0],
[0, 1, 1, 1, 0],
[0, 0, 0, 0, 0]
]
start = (0, 0)
end = (4, 4)
path = a_star(grid, start, end)
if path:
print(""Shortest path:"", path)
else:
print(""No path found."")
說明：
節點類別：
代表格線中的儲存格。
商店座標 (x、y)、父項節點、g (從起點開始的成本) 和 h (到終點的啟發式)。
__lt__ 可根據 f = g + h，比較優先佇列的節點 (使用 heapq)。
a_star 函式：
以 grid、start 和 end 點做為輸入。
初始化 open_list (要探索的節點) 和 closed_list (已探索的節點)。
使用 heapq 從 open_list 中有效擷取 f 分數最低的節點。
迴圈會持續執行，直到找到 end 或 open_list 為空 (沒有路徑) 為止。
探索鄰居、計算成本 (g、
h)，並更新 open_list。
到達 end 時，重建並傳回路徑。
使用範例：
建立 grid 範例，並定義 start 和 end 點。
呼叫 a_star 尋找路徑。
列印最短路徑，或指出路徑不存在。
import heapq
class Node:
def __init__(self, position, parent=None):
self.position = position
self.parent = parent
self.g = 0
self.h = 0
self.f = 0
def __lt__(self, other):
return self.f < other.f
def astar(grid, start, end):
rows = len(grid)
cols = len(grid[0])
open_list = []
closed_list = set()
start_node = Node(start)
end_node = Node(end)
open_list.append(start_node)
while open_list:
current_node = heapq.heappop(open_list)
if current_node.position == end_node.position:
path = []
while current_node:
path.append(current_node.position)
current_node = current_node.parent
return path[::-1]
closed_list.add(current_node.position)
for neighbor in get_neighbors(grid, current_node):
if neighbor.position in closed_list:
continue
if neighbor not in open_list:
neighbor.g = current_node.g + 1
neighbor.h = manhattan_distance(neighbor.position, end_node.position)
neighbor.f = neighbor.g + neighbor.h
neighbor.parent = current_node
heapq.heappush(open_list, neighbor)
else:
if neighbor.g > current_node.g + 1:
neighbor.g = current_node.g + 1
neighbor.f = neighbor.g + neighbor.h
neighbor.parent = current_node
heapq.heapify(open_list)
return None # No path found
def get_neighbors(grid, node):
rows = len(grid)
cols = len(grid[0])
row, col = node.position
neighbors = []
if row > 0 and grid[row - 1][col] == 0:
neighbors.append(Node((row - 1, col)))
if row < rows - 1 and grid[row + 1][col] == 0:
neighbors.append(Node((row + 1, col)))
if col > 0 and grid[row][col - 1] == 0:
neighbors.append(Node((row, col - 1)))
if col < cols - 1 and grid[row][col + 1] == 0:
neighbors.append(Node((row, col + 1)))
return neighbors
def manhattan_distance(a, b):
return abs(a[0] - b[0]) + abs(a[1] - b[1])
# Example usage
grid = [
[0, 0, 0, 0, 0],
[0, 1, 1, 1, 0],
[0, 0, 0, 0, 0],
[0, 1, 1, 1, 0],
[0, 0, 0, 0, 0],
]
start = (0, 0)
end = (4, 4)
path = astar(grid, start, end)
print(path)
