请帮我写一篇简单完整的A星算法,带有中文注释
时间: 2023-12-26 19:06:58 浏览: 18
好的,以下是一个简单的A星算法实现,带有中文注释:
```python
# 定义节点类
class Node:
def __init__(self, x, y):
self.x = x # 节点横坐标
self.y = y # 节点纵坐标
self.g = 0 # 起点到该节点的实际距离(g值)
self.h = 0 # 该节点到终点的估算距离(h值)
self.f = 0 # f值等于g值加上h值
self.parent = None # 父节点
# 定义A星算法函数
def A_star(start, end, obstacles):
open_list = [] # 存放待考察节点的列表
closed_list = [] # 存放已考察节点的列表
open_list.append(start) # 将起点放入待考察列表
while open_list:
current_node = open_list[0] # 取出f值最小的节点
for node in open_list:
if node.f < current_node.f:
current_node = node
open_list.remove(current_node) # 将该节点从待考察列表中删除
closed_list.append(current_node) # 将该节点放入已考察列表中
if current_node == end: # 到达终点
path = []
while current_node:
path.append((current_node.x, current_node.y))
current_node = current_node.parent
return path[::-1] # 返回路径(倒序)
neighbors = [] # 存放相邻节点的列表
for i, j in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
x, y = current_node.x + i, current_node.y + j
if 0 <= x < len(obstacles) and 0 <= y < len(obstacles[0]) and not obstacles[x][y]:
neighbors.append(Node(x, y))
for neighbor in neighbors:
if neighbor in closed_list:
continue
g = current_node.g + 1 # 从起点到该相邻节点的实际距离为当前节点的g值加1
if neighbor not in open_list:
neighbor.h = ((neighbor.x - end.x) ** 2 + (neighbor.y - end.y) ** 2) ** 0.5 # 估算该节点到终点的距离
open_list.append(neighbor) # 将该节点放入待考察列表中
elif g >= neighbor.g:
continue # 如果当前节点的g值不比已存在的节点的g值更小,则忽略该节点
neighbor.g = g
neighbor.f = neighbor.g + neighbor.h # 更新该节点的f值
neighbor.parent = current_node # 更新该节点的父节点
return None # 没有找到路径,返回None
```
调用该函数时,需要传入起点、终点和障碍物的二维列表,如下所示:
```python
start = Node(0, 0)
end = Node(4, 4)
obstacles = [[0, 0, 0, 0, 0],
[0, 1, 0, 1, 0],
[0, 0, 0, 0, 0],
[0, 1, 0, 1, 0],
[0, 0, 0, 0, 0]]
path = A_star(start, end, obstacles)
print(path) # [(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)]
```
在上面的例子中,障碍物用数字1表示,其他位置用数字0表示。返回的路径是一个由元组组成的列表,每个元组表示一个节点的坐标。