def solve(self):
self.path = []
if self.node_array and self.start_node and self.end_node:
closed_nodes = set()
opened_nodes = []
heapq.heapify(opened_nodes)
heapq.heappush(opened_nodes, (self.start_node.f, self.start_node))
# ??????????
while opened_nodes:
# ?????????f????node
f, node = heapq.heappop(opened_nodes)
# ???node???????, ??????
closed_nodes.add(node)
# ????????????? self.path (???????)
if node is self.end_node:
self.path = []
while node is not self.start_node:
self.path.append((node.x, node.y))
node = node.p
self.path.append((self.start_node.x, self.start_node.y))
self.path.reverse()
return # ???????
# ??????????
adj_nodes = self.get_adjacent_nodes(node)
for adj_node in adj_nodes:
# ????????, ??????
if adj_node.r and adj_node not in closed_nodes:
# ??????????????
if (adj_node.f, adj_node) in opened_nodes:
# ???????????????????????
if node.g < adj_node.g:
self.update_node(adj_node, node)
else:
# ?????????, ??????????
self.update_node(adj_node, node)
heapq.heappush(opened_nodes,
(adj_node.f, adj_node))
评论列表
文章目录
