不知道如何修复 A* 寻路算法
Dont know how to fix A* pathfinding algorithm
我正在尝试 A* outline from GeeksforGeeks。我遵循了灰色框中的大部分步骤，直到我在 dii 和 diii 上遇到了障碍。这是寻路部分：
def pathfind(grid):
sx, sy = 0, 0
# find start point and end point cood
for y in range(len(grid)):
for x in range(len(grid[y])):
if grid[y][x] == "S":
sx = x
sy = y
elif grid[y][x] == "E":
ex = x
ey = y
opensq = []
closedsq = []
successor = []
#add starting point to closed
opensq.append([sx, sy, gcost(sx, sy, sx, sy), hcost(sx, sy, ex, ey)])
grid[sy][sx] = "O"
while opensq:
# find the node with lowest fcost
q = opensq[0]
if len(opensq) == 1:
pass
else:
for sq in range(len(opensq)):
if sq == len(opensq) - 1:
pass
else:
if q[2] + q[3] < opensq[sq + 1][2] + opensq[sq + 1][3]:
pass
elif q[2] + q[3] == opensq[sq + 1][2] + opensq[sq + 1][3]:
# if f is same, check hcost
if q[3] < opensq[sq + 1][3]:
pass
elif q[3] == opensq[sq + 1][3]:
pass
else:
q = opensq[sq + 1]
else:
q = opensq[sq + 1]
opensq.pop(opensq.index(q))
# pick successors to q
successors = []
successors.append([q[0] + 1, q[1], gcost(q[0] + 1, q[1], sx, sy), hcost(q[0] + 1, q[1], ex, ey)])
successors.append([q[0] - 1, q[1], gcost(q[0] - 1, q[1], sx, sy), hcost(q[0] - 1, q[1], ex, ey)])
successors.append([q[0], q[1] + 1, gcost(q[0], q[1] + 1, sx, sy), hcost(q[0], q[1] + 1, ex, ey)])
successors.append([q[0], q[1] - 1, gcost(q[0], q[1] - 1, sx, sy), hcost(q[0], q[1] - 1, ex, ey)])
for s in successors:
# if successor is the goal, stop search
if s[0] == ex and s[1] == ey:
pass
# if a node with the same position as
# successor is in the OPEN list which has a
# lower f than successor, skip this successor
for sq in opensq:
if sq[2] + sq[3] < s[2] + s[3]:
successors.pop(successors.index(s))
# if a node with the same position as
# successor is in the CLOSED list which has
# a lower f than successor, skip this successor
# otherwise, add the node to the open list
for sq in closedsq:
if sq[2] + sq[3] < s[2] + s[3]:
successors.pop(successors.index(s))
for s in successors:
opensq.append(s)
grid[s[1]][s[0]] = "O"
closedsq.append(q)
grid[q[1]][q[0]] = "C"
sx 和 sy 是起点，ex ey 是终点。我使用字母来确定节点是打开还是关闭或者开始还是结束，以及它们的第一个字母。当我 运行 时弹出此错误：
Traceback (most recent call last):
File "D:/Bruh/Desktop/Codes and Scripts/AI/A_Pathfinding/Code.py", line 287, in <module>
main()
File "D:/Bruh/Desktop/Codes and Scripts/AI/A_Pathfinding/Code.py", line 274, in main
pathfind(grid)
File "D:/Bruh/Desktop/Codes and Scripts/AI/A_Pathfinding/Code.py", line 98, in pathfind
successors.pop(successors.index(s))
ValueError: [5, 12, 3, 14] is not in list
这是整个脚本，我使用 pygame 进行可视化，但只关注寻路方法，它目前有点工作，但 1. 由于某种原因，每次循环后封闭节点再次变为开放节点，并且2.如果我跳过后继者，当它面对墙壁时，它会陷入循环。
https://pastebin.com/yZfcPkq8
编辑：终于完成了代码！我会把它放在那里，唯一的问题是..我不知道如何显示路径..
https://pastebin.com/EYSxFzpe
错误发生在以下部分：
for s in successors:
if s[0] == ex and s[1] == ey:
pass
for sq in opensq:
if sq[2] + sq[3] < s[2] + s[3]:
successors.pop(successors.index(s)) # line 1
for sq in closedsq:
if sq[2] + sq[3] < s[2] + s[3]:
successors.pop(successors.index(s)) # line 2
在“第 1 行”和“第 2 行”上，successors.index(s) 可以在 s 已经在 for 循环的前一个循环中弹出之后调用。然后，出现错误。
而且，更重要的是，您的代码没有正确执行 A* search algorithm。当您对代码发表评论时，您应该只检查“与后继位置相同的节点”。您可以尝试使用以下代码代替上述部分来解决问题。
# Iterate over a copy of the list,
# since we are popping elements in the original list.
for s in list(successors):
if s[0] == ex and s[1] == ey:
pass
for sq in opensq + closedsq:
if sq[0] == s[0] and sq[1] == s[1] and sq[2] + sq[3] <= s[2] + s[3]:
successors.pop(successors.index(s))
break
而且，上面的代码还是不够简洁。您可以看到 sq[3] == s[3] 始终保持上面的 if 语句，因为它们是 hcost 相同的位置。因此，您可以将 sq[2] 与 s[2] 进行比较，即 gcost。 （换句话说，因为 sq[3] == s[3] 成立，你可以在上面的 if 语句中做 sq[2] <= s[2] 而不是 sq[2] + sq[3] <= s[2] + s[3]。）我认为 A* 搜索算法在灰色框 on GeeksforGeeks 不是那么整洁。
gcost 是“沿着生成的路径从起点移动到网格上给定方格的移动成本。”所以你应该修正你的代码：
移除gcost功能
修复用于
的行gcost
opensq.append([sx, sy, 0, hcost(sx, sy, ex, ey)])
successors.append([q[0] + 1, q[1], q[2] + 1, hcost(q[0] + 1, q[1], ex, ey)])
successors.append([q[0] - 1, q[1], q[2] + 1, hcost(q[0] - 1, q[1], ex, ey)])
successors.append([q[0], q[1] + 1, q[2] + 1, hcost(q[0], q[1] + 1, ex, ey)])
successors.append([q[0], q[1] - 1, q[2] + 1, hcost(q[0], q[1] - 1, ex, ey)])
通过上述修复，您的代码似乎可以正常工作。但我认为你仍然可以改进你的代码。我们可以改进的一件事是将节点和节点的 gcost 分开。现在，您代码中的 opensq 将节点坐标和 gcost 一起保存，如果计算出的 gcost 不同，则可以多次将节点添加到 opensq。
您还可以参考您已经参考过的A* pseudocode on Wikipedia. I think it is more neat and clean than on GeeksForGeeks。
closed列表可以参考pseudocode on Wikipedia:
后面的“Remark”
Remark: In this pseudocode, if a node is reached by one path, removed from openSet, and subsequently reached by a cheaper path, it will be added to openSet again. This is essential to guarantee that the path returned is optimal if the heuristic function is admissible but not consistent. If the heuristic is consistent, when a node is removed from openSet the path to it is guaranteed to be optimal so the test ‘tentative_gScore < gScore[neighbor]’ will always fail if the node is reached again.
已关闭列表on GeeksForGeeks is really closed only if the heuristic function is consistent。
我正在尝试 A* outline from GeeksforGeeks。我遵循了灰色框中的大部分步骤，直到我在 dii 和 diii 上遇到了障碍。这是寻路部分：
def pathfind(grid):
sx, sy = 0, 0
# find start point and end point cood
for y in range(len(grid)):
for x in range(len(grid[y])):
if grid[y][x] == "S":
sx = x
sy = y
elif grid[y][x] == "E":
ex = x
ey = y
opensq = []
closedsq = []
successor = []
#add starting point to closed
opensq.append([sx, sy, gcost(sx, sy, sx, sy), hcost(sx, sy, ex, ey)])
grid[sy][sx] = "O"
while opensq:
# find the node with lowest fcost
q = opensq[0]
if len(opensq) == 1:
pass
else:
for sq in range(len(opensq)):
if sq == len(opensq) - 1:
pass
else:
if q[2] + q[3] < opensq[sq + 1][2] + opensq[sq + 1][3]:
pass
elif q[2] + q[3] == opensq[sq + 1][2] + opensq[sq + 1][3]:
# if f is same, check hcost
if q[3] < opensq[sq + 1][3]:
pass
elif q[3] == opensq[sq + 1][3]:
pass
else:
q = opensq[sq + 1]
else:
q = opensq[sq + 1]
opensq.pop(opensq.index(q))
# pick successors to q
successors = []
successors.append([q[0] + 1, q[1], gcost(q[0] + 1, q[1], sx, sy), hcost(q[0] + 1, q[1], ex, ey)])
successors.append([q[0] - 1, q[1], gcost(q[0] - 1, q[1], sx, sy), hcost(q[0] - 1, q[1], ex, ey)])
successors.append([q[0], q[1] + 1, gcost(q[0], q[1] + 1, sx, sy), hcost(q[0], q[1] + 1, ex, ey)])
successors.append([q[0], q[1] - 1, gcost(q[0], q[1] - 1, sx, sy), hcost(q[0], q[1] - 1, ex, ey)])
for s in successors:
# if successor is the goal, stop search
if s[0] == ex and s[1] == ey:
pass
# if a node with the same position as
# successor is in the OPEN list which has a
# lower f than successor, skip this successor
for sq in opensq:
if sq[2] + sq[3] < s[2] + s[3]:
successors.pop(successors.index(s))
# if a node with the same position as
# successor is in the CLOSED list which has
# a lower f than successor, skip this successor
# otherwise, add the node to the open list
for sq in closedsq:
if sq[2] + sq[3] < s[2] + s[3]:
successors.pop(successors.index(s))
for s in successors:
opensq.append(s)
grid[s[1]][s[0]] = "O"
closedsq.append(q)
grid[q[1]][q[0]] = "C"
sx 和 sy 是起点，ex ey 是终点。我使用字母来确定节点是打开还是关闭或者开始还是结束，以及它们的第一个字母。当我 运行 时弹出此错误：
Traceback (most recent call last):
File "D:/Bruh/Desktop/Codes and Scripts/AI/A_Pathfinding/Code.py", line 287, in <module>
main()
File "D:/Bruh/Desktop/Codes and Scripts/AI/A_Pathfinding/Code.py", line 274, in main
pathfind(grid)
File "D:/Bruh/Desktop/Codes and Scripts/AI/A_Pathfinding/Code.py", line 98, in pathfind
successors.pop(successors.index(s))
ValueError: [5, 12, 3, 14] is not in list
这是整个脚本，我使用 pygame 进行可视化，但只关注寻路方法，它目前有点工作，但 1. 由于某种原因，每次循环后封闭节点再次变为开放节点，并且2.如果我跳过后继者，当它面对墙壁时，它会陷入循环。 https://pastebin.com/yZfcPkq8
编辑：终于完成了代码！我会把它放在那里，唯一的问题是..我不知道如何显示路径.. https://pastebin.com/EYSxFzpe
错误发生在以下部分：
for s in successors:
if s[0] == ex and s[1] == ey:
pass
for sq in opensq:
if sq[2] + sq[3] < s[2] + s[3]:
successors.pop(successors.index(s)) # line 1
for sq in closedsq:
if sq[2] + sq[3] < s[2] + s[3]:
successors.pop(successors.index(s)) # line 2
在“第 1 行”和“第 2 行”上，successors.index(s) 可以在 s 已经在 for 循环的前一个循环中弹出之后调用。然后，出现错误。
而且，更重要的是，您的代码没有正确执行 A* search algorithm。当您对代码发表评论时，您应该只检查“与后继位置相同的节点”。您可以尝试使用以下代码代替上述部分来解决问题。
# Iterate over a copy of the list,
# since we are popping elements in the original list.
for s in list(successors):
if s[0] == ex and s[1] == ey:
pass
for sq in opensq + closedsq:
if sq[0] == s[0] and sq[1] == s[1] and sq[2] + sq[3] <= s[2] + s[3]:
successors.pop(successors.index(s))
break
而且，上面的代码还是不够简洁。您可以看到 sq[3] == s[3] 始终保持上面的 if 语句，因为它们是 hcost 相同的位置。因此，您可以将 sq[2] 与 s[2] 进行比较，即 gcost。 （换句话说，因为 sq[3] == s[3] 成立，你可以在上面的 if 语句中做 sq[2] <= s[2] 而不是 sq[2] + sq[3] <= s[2] + s[3]。）我认为 A* 搜索算法在灰色框 on GeeksforGeeks 不是那么整洁。
gcost 是“沿着生成的路径从起点移动到网格上给定方格的移动成本。”所以你应该修正你的代码：
移除
gcost功能修复用于
的行gcost
opensq.append([sx, sy, 0, hcost(sx, sy, ex, ey)])
successors.append([q[0] + 1, q[1], q[2] + 1, hcost(q[0] + 1, q[1], ex, ey)])
successors.append([q[0] - 1, q[1], q[2] + 1, hcost(q[0] - 1, q[1], ex, ey)])
successors.append([q[0], q[1] + 1, q[2] + 1, hcost(q[0], q[1] + 1, ex, ey)])
successors.append([q[0], q[1] - 1, q[2] + 1, hcost(q[0], q[1] - 1, ex, ey)])
通过上述修复，您的代码似乎可以正常工作。但我认为你仍然可以改进你的代码。我们可以改进的一件事是将节点和节点的 gcost 分开。现在，您代码中的 opensq 将节点坐标和 gcost 一起保存，如果计算出的 gcost 不同，则可以多次将节点添加到 opensq。
您还可以参考您已经参考过的A* pseudocode on Wikipedia. I think it is more neat and clean than on GeeksForGeeks。
closed列表可以参考pseudocode on Wikipedia:
后面的“Remark”Remark: In this pseudocode, if a node is reached by one path, removed from openSet, and subsequently reached by a cheaper path, it will be added to openSet again. This is essential to guarantee that the path returned is optimal if the heuristic function is admissible but not consistent. If the heuristic is consistent, when a node is removed from openSet the path to it is guaranteed to be optimal so the test ‘tentative_gScore < gScore[neighbor]’ will always fail if the node is reached again.
已关闭列表on GeeksForGeeks is really closed only if the heuristic function is consistent。