A* 算法的搭配指南
这篇文章是介绍 A* 算法的搭配指南，我在其中解释了的工作原理。在此页面上，我将展示如何广为实现度优先搜索、Dijkstra 算法、贪婪最佳优先搜索和 A*。我尽量保持这里的代码简单。
图搜索是一系列相关算法。算法有很多变体，在实现上也有很多变体。将此页面上的代码视为起点，而不是适用于所有情况的算法的最终版本。
1 Python 实现#
我解释了下面的大部分代码。您可以在implementation.py 中找到一些额外的位。它们使用Python 3，因此如果您使用 Python 2，则需要删除类型注释、更改super()调用并更改print函数以使用 Python 2。
1.1. 广度优先搜索#
让我们在 Python 中实现广度优先搜索。主要文章展示了搜索算法的 Python 代码，但我们还需要定义它所处理的图。这些是我将使用的抽象：
图形
可以告诉我
neighbors每个图形位置的数据结构（请参阅本教程）。甲加权曲线图还给出了一个cost沿边缘移动。地点
一个简单的值（整数、字符串、元组等），用于标记图中的位置。这些不一定是地图上的位置。根据要解决的问题，它们可能包括其他信息，例如方向、燃料、车道或库存。
搜索
一种算法，它采用图、起始图位置和可选的目标图位置，并计算一些或所有图位置的一些有用信息（已到达、父指针、距离）。
队列
搜索算法使用的一种数据结构，用于决定处理图形位置的顺序。
在主要文章中，我专注于搜索。在这个页面上，我将填写其余的细节以制作完整的工作程序。让我们从图表开始。图形是什么样的？它是一个位置类型以及一个具有获取相邻位置的方法的类：
Location = TypeVar( 'Location' ) class Graph (Protocol): def neighbor ( self , id : Location) -> List[Location]: pass
Graph是搜索算法需要的界面。这是一个实现：
class SimpleGraph : def __init__ ( self ): self .edges: Dict[Location, List[Location]] = {}
def 邻居( self , id : Location) -> List[Location]: 返回 self .edges[ id ]
是的，这就是我们所需要的！你可能会问，Node 对象在哪里？答案是：我很少使用节点对象。我发现使用整数、字符串或元组作为Location类型，然后使用使用位置作为索引的数组或哈希表（dicts）更简单。
请注意，边是有向的：我们可以有从 A 到 B 的边，而没有从 B 到 A 的边。在游戏地图中，大多数边是双向的，但有时会有单向门或跳下悬崖表示为有向边缘。让我们从具有双向和单向链接的示例地图开始：
将地图转换为图形的一部分是选择要标记的位置。在这里，我决定将每个水平平台标记为一个位置。我们可以用一个图形来表示这个例子，其中Location类型是字母 A、B、C、D、E 或 F。
对于每个位置，我都需要一个它指向哪些位置的列表：
example_graph = SimpleGraph()示例图。边缘= { 'A' : [ 'B' ], 'B' : [ 'C' ], 'C' : [ 'B' , 'D' , 'F' ], 'D' : [ 'C' , 'E' ], 'E' : [ 'F' ], 'F' : [],}
在我们可以将它与搜索算法一起使用之前，我们需要创建一个队列：
进口藏品class Queue : def __init__ ( self ): self .elements = collections.deque()
def empty ( self ) -> bool : return not self .elements
def put ( self , x: T): self .elements.append(x)
def get ( self ) -> T: return self .elements.popleft()
这个队列类是内置类的包装器collections.deque。随意deque直接在您自己的代码中使用。
让我们用这个队列和主要文章中的广度优先搜索算法代码来尝试示例图：
从实现导入*def width_first_search ( graph : Graph, start: Location): #打印出我们找到的东西
前沿=队列（）
frontier.put（开始）
到达：Dict[Location, bool ] = {} 到达[start] = True
而 不是frontier.empty（）： 当前：位置= frontier.get（） 打印（“参观％的”％电流） 为 下一个 在graph.neighbors（当前）： 如果 接下来 没有 在 达到：
frontier.put(下一个)
到达 [下一个] =真打印（'可从A：'）广度第一搜索（example_graph，'A'）打印（'从E可达：'）广度第一搜索（example_graph，'E'）
从 A 可达： 访问 A 访问 B 访问 C 访问 D 访问 F 访问 E从 E 可达： 访问 E 访问 F
网格也可以表示为图形。我现在将定义一个名为的新图SquareGrid，它GridLocation是一个元组 (x: int, y: int)。在这张地图中，图中的位置（“状态”）与游戏地图上的位置相同，但在许多问题中，图位置与地图位置不同。我将在neighbors函数中计算它们，而不是显式存储边缘。在许多问题中，最好显式存储它们。
GridLocation = 元组[ int , int ]class SquareGrid : def __init__ ( self , width: int , height: int ): self .width = width self。高度= 高度 自我。墙壁：列表[GridLocation] = []
def in_bounds ( self , id : GridLocation) -> bool :
(x, y) = id
返回0 <= x < self .width和0 <= y < self .height
高清 尚可（自我，ID：GridLocation） - > BOOL： 返回 ID 不是 在 自我.walls
def 邻居( self , id : GridLocation) ->迭代器[GridLocation]:
(x, y) = id
neighbor = [(x+1, y), (x-1, y), (x, y-1), (x, y+1)] # EWNS
#参见“丑陋的路径”部分解释：
if (x + y) % 2 == 0: databases.reverse () # SNWE
results = filter ( self .in_bounds, neighbor) results = filter ( self .passable, results) return results
让我们用主要文章中的第一个网格来尝试一下：
from implementation import * g = SquareGrid(30, 15)G。wall = DIAGRAM1_WALLS #长列表, [(21, 0), (21, 2), ...]draw_grid(g)
. . . . . . . . . . . . . . . . . . . . . ######。. . . . . . . . . . . . . . . . . . . . . . . . . . . ######。. . . . . . . . . . . . . . . . . . . . . . . . . . . ######。. . . . . . . . . ######。. . . . . . . . . . . . . . . ######。. . . . . . . . . ######。. . . . . . . ######。. . . . . ######。. . . . . . . . . ######。. . . . . . . ######。. . . . . ###############。. . . . . . ######。. . . . . . . ######。. . . . . ###############。. . . . . . ######。. . . . . . . ######。. . . . . . . . . . . . . . . . . ######。. . . . . . . ######。. . . . . . . . . . . . . . . . . ######。. . . . . . . ######。. . . . . . . . . . . . . . . . . ######。. . . . . . . ######。. . . . . . . . . . . . . . . . . ######。. . . . . . . ######。. . . . . . . . . . . . . . . . . . . . . . . . . . . ######。. . . . . . . . . . . . . . . . . . . . . . . . . . . ######。. . . . . . . . . . . . . . . . . . . . . . . . . . . ######。. . . . . . . . . . . . . .
为了重建路径，我们需要存储我们来自哪里的位置，因此我将reached(True/False)重命名为came_from(location)：
从实现导入*高清 breadth_first_search（图：图中，启动：位置）：
前沿=队列（）
frontier.put（开始）
come_from : Dict[Location, Optional[Location]] = {} came_from [start] = None
而 不是frontier.empty（）： 当前：位置= frontier.get（） 对于 下一个 在graph.neighbors（电流）： 如果 下一个 不 在 came_from：
frontier.put(下一个)
come_from[下一个] = 当前
返回来自g = SquareGrid(30, 15)G。墙壁= DIAGRAM1_WALLS开始= (8, 7)父母= 广度_第一_搜索（g，开始）draw_grid(g, point_to=parents, start=start)
→→→↓↓↓↓↓↓↓↓↓↓↓↓↓←←←←←######↓↓↓↓↓↓↓→→→→↓↓↓↓↓↓↓↓↓↓↓←←←←←←######→↓↓↓↓↓↓→→→→→↓↓↓↓↓↓↓↓↓←←←←←←←######→→↓↓↓↓↓→→↑######↓↓↓↓↓↓↓↓←←←←←←←←######→→→↓↓↓↓→↑↑######↓↓↓↓↓↓↓←######↑←←←←←######→→→↓↓↓↓↑↑↑######→↓↓↓↓↓←←######↑↑←←←←###############↓↓↓←↑↑↑######→→↓↓↓←←←######↑↑↑←←←###############↓↓←←↓↓↓######→→→ 一种 ←←←←######↑↑↑↑←←←←←←←←←←←↓↓↓######→→↑↑↑←←←######↑↑↑↑↑←←←←←←←←←←↓↓↓######→↑↑↑↑↑←←######↑↑↑↑↑↑←←←←←←←←←→↓↓######↑↑↑↑↑↑↑←######↑↑↑↑↑↑↑←←←←←←←←→→↓######↑↑↑↑↑↑↑↑######↑↑↑↑↑↑↑↑←←←←←←←→→→→→↑↑↑↑↑↑↑↑######↑↑↑↑↑↑↑↑↑←←←←←←→→→→↑↑↑↑↑↑↑↑↑######↑↑↑↑↑↑↑↑↑↑←←←←←→→→↑↑↑↑↑↑↑↑↑↑######↑↑↑↑↑↑↑↑↑↑↑←←←←
一些实现使用内部存储，创建一个 Node 对象来保存came_from每个图形节点的其他值。我选择使用外部存储，创建一个哈希表来存储came_from所有图形节点。如果您知道您的地图位置具有整数索引，则另一种选择是使用数组来存储came_from.
1.2. 提前退出#
按照主要文章中的代码，我们需要在主循环中添加一个if语句。此测试对于广度优先搜索或 Dijkstra 算法是可选的，并且实际上是贪婪最佳优先搜索和 A* 所必需的：
从实现导入*def width_first_search（图：图，开始：位置，目标：位置）：
前沿=队列（）
frontier.put（开始）
come_from : Dict[Location, Optional[Location]] = {} came_from [start] = None
虽然 不是frontier.empty()： current : Location = frontier.get()
如果当前 ==目标： 中断
对于 接下来 在graph.neighbors（当前）： 如果 下一 没有 在came_from：
frontier.put(下一个)
come_from[下一个] = 当前
返回来自G = SquareGrid(30, 15)G。墙壁= DIAGRAM1_WALLS开始= (8, 7)目标= (17, 2)父母= 广度_优先搜索(g, 开始, 目标)draw_grid(g, point_to=parents, start=start,goal=goal)
. →→↓↓↓↓↓↓↓↓↓↓↓↓↓←. . . . ######。. . . . . . →→→→↓↓↓↓↓↓↓↓↓↓↓←←←. . . ######。. . . . . . →→→→→↓↓↓↓↓↓↓↓↓←←←Z。. . ######。. . . . . . →→↑######↓↓↓↓↓↓↓↓←←←←←←. . ######。. . . . . . . ↑↑######↓↓↓↓↓↓↓←######↑←←. . . ######。. . . . . . . .↑######→↓↓↓↓↓←←######↑↑. . . . ###############。. . . . . . ######→→↓↓↓←←←######↑. . . . . ###############。. . . . . . ######→→→ 一种 ←←←←######。. . . . . . . . . . . . . . . . . ######→→↑↑↑←←←######。. . . . . . . . . . . . . . . .↓######→↑↑↑↑↑←←######。. . . . . . . . . . . . . . . ↓↓######↑↑↑↑↑↑↑←######。. . . . . . . . . . . . . . →→↓######↑↑↑↑↑↑↑↑######。. . . . . . . . . . . . . . →→→→→↑↑↑↑↑↑↑↑######。. . . . . . . . . . . . . . →→→→↑↑↑↑↑↑↑↑↑######。. . . . . . . . . . . . . . . →→↑↑↑↑↑↑↑↑↑↑######。. . . . . . . . . . . . . .
您可以看到算法在找到目标时停止Z。
1.3. Dijkstra 算法#
这就是增加图搜索复杂性的原因，因为我们将以比“先进先出”更好的顺序开始处理位置。我们需要改变什么？
该图需要知道移动成本。
该队列需要以不同的顺序返回节点。
该搜索需要保持从图中这些费用的跟踪，并给他们的队列。
1.3.1. 带权重的图表
常规图告诉我neighbors每个节点的 。甲加权曲线图还告诉我沿着每个边缘移动的成本。我将添加一个cost(from_node, to_node)函数，告诉我们从 location 移动from_node到它的邻居的成本to_node。这是界面：
class WeightedGraph (Graph): def cost ( self , from_id: Location, to_id: Location) -> float : pass
让我们使用网格实现接口，该网格使用网格位置并将权重存储在字典中：
class GridWithWeights (SquareGrid): def __init__ ( self , width : int , height: int ): super ().__init__(width, height) self .weights: Dict[GridLocation, float ] = {}
def cost ( self , from_node: GridLocation, to_node: GridLocation) -> float : return self .weights.get(to_node, 1)
在这张森林地图中，我选择使运动仅依赖于to_node，但还有其他类型的运动同时使用这两个节点。另一种实现是在neighbors函数返回的值中包含移动成本。
1.3.2. 有优先权的队列
优先级队列为每个项目关联一个称为“优先级”的数字。返回项目时，它会选择编号最小的项目。
插入
将项目添加到队列
消除
删除编号最小的项目
重新确定优先级
（可选）将现有项目的优先级更改为较低的数字
这是一个使用二进制堆的相当快的优先级队列，但不支持重新确定优先级。为了获得正确的排序，我们将使用元组 (priority, item)。当插入一个已经在队列中的元素时，我们会有一个重复的；我将在优化部分解释为什么这没问题。
导入堆class PriorityQueue : def __init__ ( self ): self .elements: List[Tuple[ float , T]] = []
def empty ( self ) -> bool : return not self .elements
def put ( self , item: T, 优先级: float ):
heapq.heappush( self .elements, (priority, item))
def get ( self ) -> T: return heapq.heappop( self .elements)[1]
1.3.3. 搜索
这里有一个关于实现的棘手点：一旦我们添加了移动成本，就有可能再次访问一个位置，并使用更好的cost_so_far. 这意味着该线路if next not in came_from将不起作用。相反，必须检查自上次到达以来成本是否下降。（在文章的原始版本中，我没有检查这个，但我的代码仍然有效；我写了一些关于那个错误的笔记。）
这张森林地图来自主页。
def dijkstra_search (图：加权，开始：位置，目标：位置）：
前沿 = PriorityQueue()
frontier.put（开始，0）
come_from : Dict[Location, Optional[Location]] = {} cost_so_far : Dict[Location, float ] = {} came_from [start] = None
cost_so_far [start] = 0
而 不是frontier.empty(): current : Location = frontier.get()
如果当前 ==目标： 中断
对于 接下来 在graph.neighbors（电流）：
new_cost = cost_so_far [当前] + graph.cost（电流，下一个） ，如果 下一个 不 在cost_so_far或new_cost < cost_so_far [下一个]：
cost_so_far[ next ] = new_cost 优先级= new_cost
frontier.put( next , priority) come_from [ next ] = current
return come_from, cost_so_far
最后，在搜索之后，我需要构建路径：
DEF reconstruct_path（came_from：字典[地点，地点]
开始：位置，目标：位置）->列表[位置]：
当前：位置 = 目标
路径: List[Location] = [] 而current != start :
path.append（当前）
当前 = come_from[当前]
path.append(start) #可选
path.reverse() #可选
返回路径
尽管路径最好被认为是一系列边，但将它们存储为一系列节点很方便。要构建路径，请从末端开始并沿着came_from指向前一个节点的地图进行操作。当我们到达开始时，我们就完成了。它是向后路径，因此如果您需要将其向前存储，请reverse()在末尾调用reconstruct_path。有时，将其向后存储实际上更方便。有时将起始节点也存储在列表中很有用。
让我们试试看：
from implementation import * start，goal = (1, 4), (8, 3) come_from , cost_so_far = dijkstra_search(diagram4, start,goal)draw_grid（diagram4，point_to=came_from，start=start，goal=goal）打印()draw_grid(diagram4, path=reconstruct_path(came_from, start=start,goal=goal))
↓↓←←←←←←←←↓↓←←←↑↑←←←↓↓←←←←↑↑←←↓↓←←←←←↑ Z 。 → 一种 ←←←←. . . . ↑↑←←←←. . . . ↑↑←←←←←. . . ↑##########↑←↓↓. . ↑##########↓↓↓←← . ↑←←←←←←←← . . @@@@@@@。. . . @。. . . @@。. . @。. . . . @@。 . @。. . . . . @。 . @。. . . . . . . . . . . . . . . . . . . . . . . . . . . . ##########。. . . . . . ##########。. . . . . . . . . . . . . . .
第一个输出显示向量场；第二个显示路径。
为什么这条路要走上又走？请记住，这是主页上的森林示例，其中地图中间有一个大森林，移动速度很慢。最短路径绕过森林，而不是穿过森林。
该行if next not in cost_so_far or new_cost < cost_so_far[next]可以简化为，if new_cost < cost_so_far.get(next, Infinity)但我不想get()在主要文章中解释 Python ，所以我保持原样。另一种方法是使用collections.defaultdict默认为无穷大。
收集距离而不是方向为我们提供了一个距离场，这对某些应用程序很有用：
from implementation import * start , goal = (1, 4), (8, 3) came_from , cost_so_far = dijkstra_search(diagram4, start,goal)draw_grid(diagram4, number=cost_so_far, start=start,goal=goal)
5 4 5 6 7 8 9 10 11 12 4 3 4 5 10 13 10 11 12 13 3 2 3 4 9 14 15 12 13 14 2 1 2 3 8 13 18 17 ž。 1阿1 6 11 16。. . . 2 1 2 7 12 17 . . . . 3 2 3 4 9 14 19 . . . 4 ######### 14 19 18 15 . . 5 ######### 15 16 13 14 15 . 6 7 8 9 10 11 12 13 14 .
我们可以通过使简化逻辑cost_so_far一collections.defaultdict使用默认设置为math.inf。这条线if next not in cost_so_far or new_cost < cost_so_far[next]变成if new_cost < cost_so_far[next]因为cost_so_far当 时将返回无穷大next not in cost_so_far，然后新的成本将始终小于无穷大。
1.4. A* 搜索#
A* 几乎与 Dijkstra 算法完全一样，只是我们添加了一个启发式算法。请注意，该算法的代码并非特定于 grids。有关网格的知识在图类 ( GridWithWeights)、位置和heuristic函数中。替换这三个，您就可以将 A* 算法代码与任何其他图形结构一起使用。
def 启发式(a: GridLocation, b: GridLocation) -> float :
(x1, y1) = a
(x2, y2) = b
返回 abs (x1 - x2) + abs (y1 - y2)def a_star_search（图：WeightedGraph，开始：位置，目标：位置）：
前沿 = PriorityQueue()
frontier.put（开始，0）
come_from : Dict[Location, Optional[Location]] = {} cost_so_far : Dict[Location, float ] = {} came_from [start] = None
cost_so_far [start] = 0
而 不是frontier.empty(): current : Location = frontier.get()
如果当前 ==目标： 中断
对于 下一个 在graph.neighbors（电流）：
new_cost = cost_so_far [当前] + graph.cost（电流，下一个） ，如果 下一个 不 在cost_so_far或new_cost < cost_so_far [下一个]：
cost_so_far[下一个] = new_cost 优先级= new_cost + 启发式（下一个，目标）
frontier.put( next , priority) come_from [ next ] = current
return come_from, cost_so_far
让我们试试看：
from implementation import * start , goal = (1, 4), (8, 3) come_from , cost_so_far = a_star_search(diagram4, start,goal)draw_grid（diagram4，point_to=came_from，start=start，goal=goal）打印()draw_grid(diagram4, path=reconstruct_path(came_from, start=start,goal=goal))
↓↓↓↓←←←←←←↓↓↓↓←↑↑←←←↓↓↓↓←←↑↑←←→↓←←←← . ↑Z。 → 一种 ←←←. . . . . ↑↑↑←←. . . . . ↑↑↑←←. . . . . ↑#########。. . . . . . #########。. . . . . . . . . . . . . . . . . . @@@@@。. . . . . @。. @@。. . . . @。. . @@。 . @@@。. . . @。 . @。. . . . . . . . . . . . . . . . . . . . . . . . . . . . #########。. . . . . . #########。. . . . . . . . . . . . . . .
这是它计算的距离：
from implementation import * start , goal = (1, 4), (8, 3) come_from , cost_so_far = a_star_search(diagram4, start,goal)draw_grid(diagram4, number=cost_so_far, start=start,goal=goal)
5 4 5 6 7 8 9 10 11 12 4 3 4 5 10 13 10 11 12 13 3 2 3 4 9 14 15 12 13 14 2 1 2 3 8 13 . 17 ž。 1阿1 6 11。. . . . 2 1 2 7 12 。. . . . 3 2 3 4 9 . . . . . 4 #########。. . . . . . #########。. . . . . . . . . . . . . . .
就是这样！我们已经实现了图形、网格、广度优先搜索、Dijkstra 算法和 A*。
1.4.1. 更直的路径
如果您在自己的项目中实现此代码，您可能会发现某些路径并不像您希望的那样“直”。这是正常的。当使用网格，网格尤其是其中每一步都具有相同的运行成本，你最终的联系：许多路径具有完全相同的成本。A* 最终选择了许多短路径中的一个，而且通常对您来说看起来并不好。我在后面的部分列出了一些解决方案。
2 C++ 实现#
注意：部分示例代码需要包含redblobgames/pathfinding/a-star/implementation.cpp才能运行。我在这段代码中使用C++14，因此如果您使用旧版本的 C++ 标准，则需要更改其中的一些内容。
此处的代码适用于本教程，不是生产质量的；最后有一个部分，其中包含有关使其变得更好的提示。
2.1. 广度优先搜索#
让我们用 C++ 实现广度优先搜索。这些是我们需要的组件：
图形
可以告诉我
neighbors每个图形位置的数据结构（请参阅本教程）。一个加权图也可以告诉我cost沿着边缘移动。地点
一个简单的值（整数、字符串、元组等），用于标记图中的位置。这些不一定是地图上的位置。根据要解决的问题，它们可能包括其他信息，例如方向、燃料、车道或库存。
搜索
一种算法，它采用图、起始图位置和可选的目标图位置，并计算一些或所有图位置的一些有用信息（已到达、父指针、距离）。
队列
搜索算法使用的一种数据结构，用于决定处理图形位置的顺序。
在主要文章中，我专注于搜索。在这个页面上，我将填写其余的细节以制作完整的工作程序。让我们从位置图开始char：
struct SimpleGraph {
std :: unordered_map < char , std :: vector < char > > edges ;
std :: vector < char >邻居（char id）{
返回边[id]； } } ;
请注意，边是有向的：我们可以有从 A 到 B 的边，而没有从 B 到 A 的边。在游戏地图中，大多数边是双向的，但有时会有单向门或跳下悬崖表示为有向边缘。让我们从具有双向和单向链接的示例地图开始：
将地图转换为图形的一部分是选择要标记的位置。在这里，我决定将每个水平平台标记为一个位置。我们可以用一个图形来表示这个例子，其中Location类型是字母 A、B、C、D、E 或 F。
SimpleGraph example_graph {{
{ 'A' , { 'B' }} , { 'B' , { 'C' }} , { 'C' , { 'B' , 'D' , 'F' }} , { ' D' , { 'C' , 'E' }} , { 'E' , { 'F' }} , { 'F' , {}} , }} ;
C++ 标准库已经包含一个队列类。我们现在有一个图 ( SimpleGraph)、位置 ( char) 和一个队列 ( std::queue)。现在我们可以尝试广度优先搜索：
#include "redblobgames/pathfinding/a-star/implementation.cpp"void width_first_search ( SimpleGraph graph , char start ) {
std :: queue < char > frontier ;
前沿推（开始）；
std :: unordered_set < char >到达；
到达。插入（开始）；
while ( ! frontier.empty()) {
char current = frontier.front();
边境.pop();
std ::cout << " 访问 " << 当前 << '\n' ; for ( char next : graph.neighbors(current)) {
if (reached.find(next) ==reached.end()) {
前沿推（下一个）；
到达.插入（下一个）；
}
}
} }int main () {
std ::cout << "可从 A:\n" ;
广度第一搜索（example_graph，'A'）； std ::cout << "可从 E:\n" ;
广度第一搜索（example_graph，'E'）；}
从 A 可达： 访问 A 访问 B 访问 C 访问 D 访问 F 访问 E从 E 可达： 访问 E 访问 F
网格也可以表示为图形。我现在将定义一个名为的新图SquareGrid，其位置结构具有两个整数。在这张地图中，图中的位置（“状态”）与游戏地图上的位置相同，但在许多问题中，图位置与地图位置不同。我将在neighbors函数中计算它们，而不是显式存储边缘。在许多问题中，最好显式存储它们。
struct GridLocation {
int x , y ;} ;namespace std { /*实现哈希函数，以便我们可以将 GridLocation 放入 unordered_set */模板<> struct hash < GridLocation > {
std :: size_t operator () ( const GridLocation & id ) const noexcept {
return std ::hash< int >()(id.x ^ (id.y << 4)); } } ;}结构 SquareGrid {
静态 的std ::阵列< GridLocation，4> DIRS ;
整数 宽度，高度； std :: unordered_set < GridLocation > walls；
SquareGrid ( int width_ , int height_ )
：宽度（宽度_），高度（高度_）{}
bool in_bounds ( GridLocation id ) const {
return 0 <= id.x && id.x < 宽度
&& 0 <= id.y && id.y < 高度；
}
bool的 通行（GridLocation ID）const的 {
返回walls.find（ID）== walls.end（）; }
std :: vector < GridLocation >邻居（GridLocation id）const {
std :: vector < GridLocation >结果；
for ( GridLocation dir : DIRS ) {
GridLocation next { id.x + dir.x, id.y + dir.y } ; if (in_bounds(next) && passable(next)) {
结果.push_back（下一个）；
}
}
if ((id.x + id.y) % 2 == 0) {
//参见“丑陋路径”部分的解释：
std ::reverse(results.begin(), results.end()); }
返回结果； } } ;STD ::阵列< GridLocation，4> SquareGrid :: DIRS = {
/ *东，西，北，南* /
GridLocation { 1,0 }，GridLocation { -1,0 }，
GridLocation { 0, -1 } , GridLocation { 0, 1 } } ;
在帮助文件中，implementation.cpp我定义了一个函数来制作网格：
#include "redblobgames/pathfinding/a-star/implementation.cpp"int main () {
SquareGrid grid = make_diagram1();
绘制网格（网格）；}
. . . . . . . . . . . . . . . . . . . . . ######。. . . . . . . . . . . . . . . . . . . . . . . . . . . ######。. . . . . . . . . . . . . . . . . . . . . . . . . . . ######。. . . . . . . . . ######。. . . . . . . . . . . . . . . ######。. . . . . . . . . ######。. . . . . . . ######。. . . . . ######。. . . . . . . . . ######。. . . . . . . ######。. . . . . ###############。. . . . . . ######。. . . . . . . ######。. . . . . ###############。. . . . . . ######。. . . . . . . ######。. . . . . . . . . . . . . . . . . ######。. . . . . . . ######。. . . . . . . . . . . . . . . . . ######。. . . . . . . ######。. . . . . . . . . . . . . . . . . ######。. . . . . . . ######。. . . . . . . . . . . . . . . . . ######。. . . . . . . ######。. . . . . . . . . . . . . . . . . . . . . . . . . . . ######。. . . . . . . . . . . . . . . . . . . . . . . . . . . ######。. . . . . . . . . . . . . . . . . . . . . . . . . . . ######。. . . . . . . . . . . . . .
让我们再次尝试广度优先搜索，跟踪came_from：
#include "redblobgames/pathfinding/a-star/implementation.cpp"模板< typename Location , typename Graph > std :: unordered_map < Location , Location > breadth_first_search ( Graph graph , Location start ) {
std :: queue < Location > frontier ;
前沿推（开始）；
std :: unordered_map < Location , Location > came_from；
come_from[开始] = 开始；
while ( ! frontier.empty()) {
Location current = frontier.front();
边境.pop();
for (下一个位置 ：graph.neighbors(current)) { if (came_from.find(next) == come_from.end()) {
前沿推（下一个）；
come_from[下一个] = 当前；
}
}
}
return come_from;}int main () {
SquareGrid grid = make_diagram1(); GridLocation start { 7, 8 } ; 自动 父母= 广度_第一_搜索（网格，开始）；
draw_grid(grid, nullptr , &parents, nullptr , &start);}
→→→↓↓↓↓↓↓↓↓↓↓↓↓↓←←←←←######↓↓↓↓↓↓↓→→→→↓↓↓↓↓↓↓↓↓↓↓←←←←←←######→↓↓↓↓↓↓→→→→→↓↓↓↓↓↓↓↓↓←←←←←←←######→→↓↓↓↓↓→→↑######↓↓↓↓↓↓↓↓←←←←←←←←######→→→↓↓↓↓→↑↑######↓↓↓↓↓↓↓←######↑←←←←←######→→→↓↓↓↓↑↑↑######↓↓↓↓↓↓←←######↑↑←←←←###############↓↓↓←↓↓↓######↓↓↓↓↓←←←######↑↑↑←←←###############↓↓←←↓↓↓######→↓↓↓←←←←######↑↑↑↑←←←←←←←←←←←↓↓↓######→→ 一种 ←←←←←######↑↑↑↑↑←←←←←←←←←←↓↓↓######→↑↑↑←←←←######↑↑↑↑↑↑←←←←←←←←←→↓↓######↑↑↑↑↑←←←######↑↑↑↑↑↑↑←←←←←←←←→→↓######↑↑↑↑↑↑←←######↑↑↑↑↑↑↑↑←←←←←←←→→→→→↑↑↑↑↑↑↑←######↑↑↑↑↑↑↑↑↑←←←←←←→→→→↑↑↑↑↑↑↑↑↑######↑↑↑↑↑↑↑↑↑↑←←←←←→→→↑↑↑↑↑↑↑↑↑↑######↑↑↑↑↑↑↑↑↑↑↑←←←←
一些实现使用内部存储，创建一个 Node 对象来保存came_from每个图形节点的其他值。相反，我选择使用外部存储，创建一个std::unordered_map存储came_from所有图形节点的单一存储。如果您知道您的地图位置具有整数索引，另一种选择是使用一维或二维数组/向量来存储came_from和其他值。
2.2. 提前退出#
默认情况下，广度优先搜索和 Dijkstra 算法将探索整个地图。如果我们正在寻找单个路径，我们可以在if (current == goal)找到路径后立即添加以退出循环。
#include "redblobgames/pathfinding/a-star/implementation.cpp"template < typename Location , typename Graph > std :: unordered_map < Location , Location > breadth_first_search ( Graph graph , Location start , Location goal ) {
std :: queue < Location > frontier ;
前沿推（开始）；
std :: unordered_map < Location , Location > came_from；
come_from[开始] = 开始；
while ( ! frontier.empty()) {
Location current = frontier.front();
边境.pop();
如果（当前 == 目标）{
中断； }
for (下一个位置 ：graph.neighbors(current)) { if (came_from.find(next) == come_from.end()) {
前沿推（下一个）；
come_from[下一个] = 当前；
}
}
}
return come_from;}int main () {
GridLocation start { 8, 7 } ,目标{ 17, 2 } ; SquareGrid grid = make_diagram1(); auto come_from = 广度第一搜索（网格，开始，目标）；
draw_grid(grid, nullptr , &came_from, nullptr , &start, &goal);}
. →→↓↓↓↓↓↓↓↓↓↓↓↓↓←. . . . ######。. . . . . . →→→→↓↓↓↓↓↓↓↓↓↓↓←←←. . . ######。. . . . . . →→→→→↓↓↓↓↓↓↓↓↓←←←Z。. . ######。. . . . . . →→↑######↓↓↓↓↓↓↓↓←←←←←←. . ######。. . . . . . . ↑↑######↓↓↓↓↓↓↓←######↑←←. . . ######。. . . . . . . .↑######→↓↓↓↓↓←←######↑↑. . . . ###############。. . . . . . ######→→↓↓↓←←←######↑. . . . . ###############。. . . . . . ######→→→ 一种 ←←←←######。. . . . . . . . . . . . . . . . . ######→→↑↑↑←←←######。. . . . . . . . . . . . . . . .↓######→↑↑↑↑↑←←######。. . . . . . . . . . . . . . . ↓↓######↑↑↑↑↑↑↑←######。. . . . . . . . . . . . . . →→↓######↑↑↑↑↑↑↑↑######。. . . . . . . . . . . . . . →→→→→↑↑↑↑↑↑↑↑######。. . . . . . . . . . . . . . →→→→↑↑↑↑↑↑↑↑↑######。. . . . . . . . . . . . . . . →→↑↑↑↑↑↑↑↑↑↑######。. . . . . . . . . . . . . .
在输出中我们可以看到算法没有探索整个地图，而是提前停止。
2.3. Dijkstra 算法#
这就是增加图搜索复杂性的原因，因为我们将以比“先进先出”更好的顺序开始处理位置。我们需要改变什么？
该图需要知道移动成本。
该队列需要以不同的顺序返回节点。
该搜索需要保持从图中这些费用的跟踪，并给他们的队列。
2.3.1. 带权重的图表
常规图告诉我neighbors每个节点的 。甲加权曲线图还告诉我沿着每个边缘移动的成本。我将添加一个cost(from_node, to_node)函数，告诉我们从 location 移动from_node到它的邻居的成本to_node。在这张森林地图中，我选择使运动仅依赖于to_node，但还有其他类型的运动同时使用这两个节点。另一种实现是将其合并到neighbors函数中。这是一个包含森林图块列表的网格，其移动成本为 5：
struct GridWithWeights : SquareGrid {
std :: unordered_set <GridLocation>森林； GridWithWeights ( int w , int h ): SquareGrid (w, h) {}
double cost ( GridLocation from_node , GridLocation to_node ) const {
return forests.find(to_node) != Forests.end()? 5：1； } } ;
2.3.2. 有优先权的队列
我们需要一个优先队列。C++ 提供了一个priority_queue使用二进制堆但不使用重新排序操作的类。我将使用一对（优先级，项目）作为队列元素来获得正确的排序。默认情况下，C++ 优先级队列首先返回最大元素，使用std::less比较器；我们想要最小元素，所以我将使用std::greater比较器。
模板< typename T , typename priority_t > struct PriorityQueue {
typedef std :: pair < priority_t , T > PQElement ; STD :: priority_queue < PQElement，性病::矢量< PQElement >， STD ::更大< PQElement >>元件;
内联 bool empty () const {
return elements.empty(); }
内联 无效 放置（T 项，priority_t 优先级）{
element.emplace（优先级，项目）；
}
T get () {
T best_item = elements.top().second;
元素.pop();
返回best_item; } } ;
在此示例代码中，我包装了 C++std::priority_queue类，但我认为直接使用该类而不使用包装器是合理的。
2.3.3. 搜索
请参阅主页上的森林地图。
template < typename Location , typename Graph > void dijkstra_search
( Graph graph , Location start , Location goal , std :: unordered_map < Location , Location >& came_from , std :: unordered_map < Location , double >& cost_so_far ) {
PriorityQueue < Location , double>前沿；
Frontier.put(start, 0);
come_from[开始] = 开始；
cost_so_far[开始] = 0;
while ( ! frontier.empty()) {
Location current = frontier.get();
如果（当前 == 目标）{
中断； }
for ( Location next : graph.neighbors(current)) {
double new_cost = cost_so_far[current] + graph.cost(current, next); if (cost_so_far.find(next) == cost_so_far.end()
|| new_cost < cost_so_far[next]) {
cost_so_far[next] = new_cost;
come_from[下一个] = 当前；
Frontier.put(next, new_cost);
}
}
} }
该类型的cost变量都应该匹配在图中使用的类型。如果使用，int则可以int用于优先级队列中的成本变量和优先级；如果你使用，double那么你应该double用于这些。在这段代码中，我使用了double但我可以使用int它并且它会起作用。但是，如果您的图边成本是双精度的，或者您的启发式方法使用双精度，那么您需要在此处使用双精度。
最后，在搜索之后，我需要构建路径：
模板< typename Location > std :: vector < Location > reconstruct_path（ 位置 开始，位置 目标， std :: unordered_map < Location，Location > came_from ）{
std :: vector < Location > path ; 当前位置 =目标； 而（当前！=开始）{
path.push_back（当前）；
当前 = come_from[当前];
}
path.push_back(start); //可选
std ::reverse(path.begin(), path.end()); 返回路径；}
尽管路径最好被认为是一系列边，但将它们存储为一系列节点很方便。要构建路径，请从末端开始并沿着came_from指向前一个节点的地图进行操作。当我们到达开始时，我们就完成了。它是向后路径，因此如果您需要将其向前存储，请reverse()在末尾调用reconstruct_path。有时，将其向后存储实际上更方便。有时将起始节点也存储在列表中很有用。
让我们试试看：
#include "redblobgames/pathfinding/a-star/implementation.cpp" 主界面 () {
GridWithWeights grid = make_diagram4(); GridLocation 开始{ 1, 4 } ,目标{ 8, 3 } ; std :: unordered_map < GridLocation , GridLocation > come_from； std :: unordered_map < GridLocation , double > cost_so_far；
dijkstra_search（网格，开始，目标，came_from，cost_so_far）；
draw_grid(grid, nullptr , &came_from, nullptr , &start, &goal); std ::cout << '\n' ; std :: vector < GridLocation > path =reconstruct_path(start,goal,came_from);
draw_grid(grid, nullptr , nullptr , &path, &start, &goal); std ::cout << '\n' ;
draw_grid(grid, &cost_so_far, nullptr , nullptr , &start, &goal);}
↓↓←←←←←←←←↓↓←←←↑↑←←←↓↓←←←←↑↑←←↓↓←←←←←↑ Z 。 → 一种 ←←←←. . . . ↑↑←←←←. . . . ↑↑←←←←←. . . ↑##########↑←↓↓. . ↑##########↓↓↓←← . ↑←←←←←←←← . . @@@@@@@。. . . @。. . . @@。. . @。. . . . @@。 . @。. . . . . Z。 . 一个。. . . . . . . . . . . . . . . . . . . . . . . . . . . . #########。. . . . . . #########。. . . . . . . . . . . . . . . 5 4 5 6 7 8 9 10 11 12 4 3 4 5 10 13 10 11 12 13 3 2 3 4 9 14 15 12 13 14 2 1 2 3 8 13 18 17 ž。 1阿1 6 11 16。. . . 2 1 2 7 12 17 . . . . 3 2 3 4 9 14 19 . . . 4 ######### 14 19 18 15 . . 5 ######### 15 16 13 14 15 . 6 7 8 9 10 11 12 13 14 .
为什么这条路要走上又走？请记住，这是主页上的森林示例，其中地图中间有一个大森林，移动速度很慢。最短路径绕过森林，而不是穿过森林。
结果并不总是与 Python 版本相同，因为我使用的是 C++ 和 Python 中的内置优先级队列。这些可能会以不同的方式对等值节点进行排序。如果使用 grids ，您会遇到这种情况。有许多同样短的路径，探路者会找到其中之一，不一定是你眼中最好的。
2.4. A* 搜索#
A* 几乎与 Dijkstra 算法完全一样，只是我们添加了一个启发式算法。请注意，该算法的代码并非特定于 grids。有关网格的知识在图类 ( GridWithWeights)、位置 ( Locationstruct ) 和heuristic函数中。替换这三个，您就可以将 A* 算法代码与任何其他图形结构一起使用。
内联 双 启发式( GridLocation a , GridLocation b ) {
return std ::abs(ax - bx) + std ::abs(ay - by);}template < typename Location , typename Graph > void a_star_search
( Graph graph , Location start , Location goal , std :: unordered_map < Location , Location >& came_from , std :: unordered_map < Location , double >& cost_so_far ) {
PriorityQueue < Location , double>前沿；
Frontier.put(start, 0);
come_from[开始] = 开始；
cost_so_far[开始] = 0;
while ( ! frontier.empty()) {
Location current = frontier.get();
如果（当前 == 目标）{
中断； }
for ( Location next : graph.neighbors(current)) {
double new_cost = cost_so_far[current] + graph.cost(current, next); if (cost_so_far.find(next) == cost_so_far.end()
|| new_cost < cost_so_far[next]) {
cost_so_far[next] = new_cost;
双 优先级= new_cost + 启发式（下一个，目标）；
frontier.put（下一个，优先级）；
come_from[下一个] = 当前；
}
}
} }
priority包括优先级队列中使用的类型在内的值的类型应该足够大，以包括图成本 ( cost_t) 和启发式值。例如，如果图成本是整数并且启发式返回双精度值，那么您需要优先级队列接受双精度值。在此示例代码中，我double用于所有三个（成本、启发式和优先级），但我可以使用，int因为我的成本和启发式是整数值。
小注：写frontier.put(start, heuristic(start, goal))比frontier.put(start, 0)但在这里没有区别更正确，因为起始节点的优先级无关紧要。它是优先级队列中的唯一节点，并且在将其他任何内容放入其中之前被选中和删除。
让我们试试看：
#include "redblobgames/pathfinding/a-star/implementation.cpp"int main () {
GridWithWeights grid = make_diagram4(); GridLocation 开始{ 1, 4 } ,目标{ 8, 3 } ; std :: unordered_map < GridLocation , GridLocation > come_from； std :: unordered_map < GridLocation , double > cost_so_far；
a_star_search（网格，开始，目标，came_from，cost_so_far）；
draw_grid(grid, nullptr , &came_from, nullptr , &start, &goal); std ::cout << '\n' ; std :: vector < GridLocation > path =reconstruct_path(start,goal,came_from);
draw_grid(grid, nullptr , nullptr , &path, &start, &goal); std ::cout << '\n' ;
draw_grid(grid, &cost_so_far, nullptr , nullptr , &start, &goal);}
↓↓↓↓←←←←←←↓↓↓↓←↑↑←←←↓↓↓↓←←↑↑←←→↓←←←← . ↑Z。 → 一种 ←←←. . . . . ↑↑↑←←. . . . . ↑↑↑←←. . . . . ↑#########。. . . . . . #########。. . . . . . . . . . . . . . . . . . @@@@@。. . . . . @。. @@。. . . . @。. . @@。 . @@@。. . . Z。 . 一个。. . . . . . . . . . . . . . . . . . . . . . . . . . . . #########。. . . . . . #########。. . . . . . . . . . . . . . . 5 4 5 6 7 8 9 10 11 12 4 3 4 5 10 13 10 11 12 13 3 2 3 4 9 14 15 12 13 14 2 1 2 3 8 13 . 17 ž。 1阿1 6 11。. . . . 2 1 2 7 12 。. . . . 3 2 3 4 9 . . . . . 4 #########。. . . . . . #########。. . . . . . . . . . . . . . .
就是这样！我们已经实现了图形、网格、广度优先搜索、Dijkstra 算法和 A*。
2.4.1. 更直的路径
如果您在自己的项目中实现此代码，您可能会发现某些路径并不像您希望的那样“直”。这是正常的。当使用网格，网格尤其是其中每一步都具有相同的运行成本，你最终的联系：许多路径具有完全相同的成本。A* 最终选择了许多短路径中的一个，而且通常对您来说看起来并不好。我在后面的部分列出了一些解决方案。
2.5. 生产代码#
我上面显示的 C++ 代码经过简化，以便更容易地遵循算法和数据结构。在实践中，您希望以不同的方式做很多事情：
内联小函数
该
Location参数应该是Graph成本可能是整数或双倍，并且应该是
Graph如果 id 是密集整数，则使用
array而不是unordered_set，并在退出时重置这些值而不是在进入时初始化通过引用而不是通过值传递更大的数据结构
在输出参数中返回更大的数据结构而不是返回它们，或者使用移动构造函数（例如，从
neighbors函数返回的向量）启发式可以变化并且应该是 A* 函数的模板参数，以便它可以被内联
以下是 A* 代码在其中一些（但不是全部）更改后的外观可能有所不同：
template < typename Graph > void a_star_search
( Graph graph , typename Graph :: Location start , typename Graph :: Location goal , std :: function < typename Graph ::cost_t( typename Graph :: Location a , typename Graph :: Location b ) >启发式， 标准:: unordered_map < typename Graph :: Location , typename Graph :: Location >& came_from , std :: unordered_map < typename Graph :: Location , typename Graph :: cost_t >& cost_so_far ) {
typedef typename Graph :: Location Location ; typedef typename Graph :: cost_t 成本_t ; PriorityQueue < Location , cost_t > frontier ; std :: vector <位置>邻居；
Frontier.put(start, cost_t(0));
come_from[开始] = 开始；
cost_so_far[开始] = cost_t(0);
while ( ! frontier.empty()) {
typename Location current = frontier.get();
如果（当前 == 目标）{
中断； }
graph.get_neighbors（当前，邻居）；
for (下一个位置 ：邻居) { cost_t new_cost = cost_so_far[current] + graph.cost(current, next); if (cost_so_far.find(next) == cost_so_far.end()
|| new_cost < cost_so_far[next]) {
cost_so_far[next] = new_cost;
cost_t 优先级= new_cost + 启发式（下一个，目标）；
frontier.put（下一个，优先级）；
come_from[下一个] = 当前；
}
}
} }
我希望这个页面上的代码是关于算法和数据结构的，而不是关于 C++ 优化的，所以我试图展示简单的代码而不是快速或抽象的代码。
3 C# 实现#
这些是我的第一个 C# 程序，因此它们可能不符合习惯或风格。这些示例不如 Python 和 C++ 部分完整，但我希望它们会有所帮助。
这是一个简单的图表和广度优先搜索：
使用 系统；使用 系统。收藏品。通用;公共 类 图<位置>{
// NameValueCollection 在这里是一个合理的选择，如果
//你总是使用字符串位置类型
public Dictionary < Location , Location []> edge
= new Dictionary < Location , Location []>();
公共 位置[]邻居（位置 ID）
{
返回边[id];
}};类 广度优先搜索{
静态 无效 搜索（图形<字符串>图形，字符串 开始）
{
var frontier = new Queue < string >();
边境。入队（开始）；
var 达到=新 HashSet <字符串>();
到达。添加（开始）；
while (frontier.Count > 0)
{
var current = 前沿。出队();
安慰。WriteLine ( "访问 {0}" ,当前); foreach ( var next in graph. Neighbors ( current ))
{
如果（！达到。包含（下一个））{
边境。入队（下一个）；
到达。添加（下一个）；
}
}
}
}
静态 无效 主（）
{
图形<字符串> g =新 图形<字符串>();
g.edges =新 字典<字符串，字符串[]>
{
{ "A" ,新[] { "B" } },
{ "B" , new [] { "A" , "C" , "D" } },
{ "C" ,新[] { "A" } },
{ "D" ,新[] { "E" , "A" } },
{ "E" ,新[] { "B" } }
};
搜索( g , "A" );
}}
这是一个表示带有加权边的网格的图（主页上的森林和墙壁示例）：
使用 系统；使用 系统。收藏品。通用;// A* 只需要一个 WeightedGraph 和一个位置类型 L，并且*不必* //必须是一个网格。但是，在示例代码中，我使用了网格。公共 接口 WeightedGraph < L >{
双倍 成本（位置 a，位置 b）； IEnumerable <位置>邻居（位置 id）；}公共 结构 位置{
//实施说明：我正在使用默认的 Equals，但它
//可能很慢。您可能希望
在实际项目中同时覆盖 Equals 和// GetHashCode。
public readonly int x , y ; 公共 位置（int x，int y）
{
这.x = x; 这.y = y;
}}公共 类 SquareGrid : WeightedGraph < Location >{
//实施说明：为了方便起见，我将字段
设为公开，//但在实际项目中，您可能希望遵循标准
//样式并将它们设为私有。
public static readonly Location [] DIRS = new []
{
新 位置(1, 0), 新 位置(0, -1), 新 位置(-1, 0), 新 位置(0, 1)
};
公共 整数 宽度，高度； public HashSet < Location > wall = new HashSet < Location >(); public HashSet < Location > forests = new HashSet < Location >();
public SquareGrid ( int width , int height )
{
这个.width = 宽度； 这个.height = 高度；
}
public bool InBounds（位置 ID）
{
返回0 <= id.x && id.x < 宽度
&& 0 <= id.y && id.y < 高度；
}
public bool Passable ( Location id )
{
回来 ！墙壁。包含(id);
}
公共 双倍 费用（位置 a，位置 b）
{
回归森林。包含(b) ? 5：1；
}
public IEnumerable < Location > Neighbors ( Location id )
{
foreach ( var dir in DIRS) { Location next = new Location (id.x + dir.x, id.y + dir.y); if ( InBounds (next) && Passable (next)) { yield return next;
}
}
}}公共 类 PriorityQueue < T >{
//我在这个例子中使用了一个未排序的数组，但理想情况下这个
//将是一个二元堆。有添加一个二进制的悬而未决的问题
//堆标准C＃库：https://github.com/dotnet/corefx/issues/574
//
//在此之前，找到一个二元堆类：
// * HTTPS： //github.com/BlueRaja/High-Speed-Priority-Queue-for-C-Sharp
// * http://visualstudiomagazine.com/articles/2012/11/01/priority-queues-with-c.aspx
/ / * http://xfleury.github.io/graphsearch.html
// * http://stackoverflow.com/questions/102398/priority-queue-in-net
private List < Tuple < T , double >> elements = new List < Tuple < T , double >>();
公共 整数 计数
{
得到{返回元素。计数; }
}
public void Enqueue（T 项，双 优先级）
{
元素。添加（元组。创建（项目，优先级））；
}
公共 T 出队()
{
int 最佳索引= 0;
for ( int i = 0; i < elements.Count; i++) { if (elements[i].Item2 < elements[bestIndex].Item2) {
最佳指数 = i;
}
}
T bestItem = elements[bestIndex].Item1;
元素。RemoveAt ( bestIndex ); 返回最佳项目；
}}/*关于类型的注意事项：在主要文章中，在 Python 代码中我只是* 使用数字来表示成本、启发式和优先级。在 C++ 代码中* 我为此使用了 typedef，因为您可能需要 int 或 double 或* 其他类型。在这个 C# 代码中，我使用 double 来表示成本、启发式、* 和优先级。如果你知道你的值总是整数，你可以使用 int，如果你知道* 值总是很小，你可以使用更小的数字。*/公开 课 AStarSearch{
public Dictionary < Location , Location > comeFrom
= new Dictionary < Location , Location >(); public Dictionary < Location , double > costSoFar
= new Dictionary < Location , double >();
//注意：A* 的通用版本将抽象 Location 和
//也启发式
静态 public double Heuristic ( Location a , Location b )
{
返回数学。Abs (ax - bx) + 数学。Abs (ay - by);
}
公共 AStarSearch ( WeightedGraph < Location > graph , Location start , Location goal )
{
var frontier = new PriorityQueue < Location >();
边境。入队（开始，0）；
comeFrom[开始] = 开始；
costSoFar[开始] = 0;
while (frontier.Count > 0)
{
var current = 前沿。出队();
如果（当前。等于（目标））
{
打破;
}
foreach ( var next in graph. Neighbors ( current ))
{
double newCost = costSoFar[当前]
+ 图表。成本（当前，下一个）； 如果（！ costSoFar。的containsKey（未来）
|| newCost < costSoFar[next])
{
costSoFar[next] = newCost;
双 优先级= newCost + Heuristic ( next , goal );
边境。入队（下一个，优先级）；
comeFrom[下一个] = 当前；
}
}
}
}}公开 课 测试{
static void DrawGrid ( SquareGrid grid , AStarSearch astar ) { //打印出cameFrom 数组
for ( var y = 0; y < 10; y++)
{
for ( var x = 0; x < 10; x++)
{
位置 id =新 位置( x , y ); 位置 ptr = id; 如果（！ astar.cameFrom。TryGetValue（ID，出 PTR））
{
ptr = id;
}
if (grid.walls. Contains ( id )) { Console. 写（“##”）；} else if (ptr.x == x+1) { 控制台。写（“\u2192”）；} else if (ptr.x == x-1) { 控制台。写( "\u2190 " ); } else if (ptr.y == y+1) { 控制台。写（“\u2193”）；} else if (ptr.y == y-1) { 控制台。写（“\u2191”）；} 其他{ 安慰。写（“*”）；}
}
安慰。写线();
}
}
静态 无效 主（）
{
//从主要文章制作“图表 4”
var grid = new SquareGrid (10, 10); for ( var x = 1; x < 4; x++)
{
for ( var y = 7; y < 9; y++)
{
网格墙。添加（新 位置（x，y））；
}
}
grid.forests =新的 HashSet <位置>
{
new Location (3, 4), new Location (3, 5), new Location (4, 1), new Location (4, 2), new Location (4, 3), new Location (4, 4), new Location (4, 5), new Location (4, 6), new Location (4, 7), new Location (4, 8), new Location (5, 1), new Location (5, 2), new Location (5) , 3),new Location (5, 4), new Location (5, 5), new Location (5, 6), new Location (5, 7), new Location (5, 8), new Location (6, 2), new Location (6, 3), new Location (6, 4), new Location (6, 5), new Location (6, 6), new Location (6, 7), new Location (7, 3), new Location(7, 4), 新 位置(7, 5)
};
//运行 A*
var astar = new AStarSearch ( grid , new Location (1, 4), new Location (8, 5));
DrawGrid ( grid , astar );
}}
我很少使用 C#，但是我的 Python 和 C++ 示例的代码结构是相同的，您可以在 C# 中使用相同的结构。
4 算法变化#
我页面上的 Dijkstra 算法和 A* 版本与您在算法或 AI 教科书中看到的略有不同。
Dijkstra's Algorithm 的纯版本以所有节点开始优先队列，并且没有提前退出。它在队列中使用“减少键”操作。理论上没问题。但在实践中……
通过仅使用起始节点启动优先级，我们可以将其保持在较小的范围内，从而使其速度更快并使用更少的内存。
使用提前退出，我们几乎不需要将所有节点都插入队列中，我们可以在找到路径后立即返回。
通过在开始时不将所有节点放入队列，大多数时候我们可以使用廉价的插入操作而不是更昂贵的减少键操作。
通过在开始时不将所有节点放入队列，我们可以处理甚至不知道所有节点或节点数量无限的情况。
此变体有时称为“统一成本搜索”。请参阅维基百科以查看伪代码，或阅读Felner 的论文[PDF] 以查看这些更改的理由。
我的版本与您可能在其他地方找到的版本之间还有三个不同之处。这些适用于 Dijkstra 算法和 A*：
我消除了对处于边界中的节点的检查，成本更高。通过不检查，我最终会在边界中得到重复的元素。该算法仍然有效。它将不必要地重新访问某些位置（但很少，根据我的经验，只要启发式是可接受的）。代码更简单，它允许我使用更简单、更快的优先级队列，该队列不支持减少键操作。论文“Priority Queues and Dijkstra's Algorithm”表明这种方法在实践中更快。
我没有同时存储“闭集”和“开集”，而是将开集称为
frontier，并且我有一个reached标志来告诉我它是否在这两个集合中的任何一个中。我仍然有两组，但将两者合并可以reached简化代码。我使用哈希表而不是节点对象数组。这消除了许多其他实现所具有的相当昂贵的初始化步骤。对于大型游戏地图，这些数组的初始化通常比 A* 的其余部分慢。
如果您对保持性能的简化有更多建议，请告诉我！
5 优化#
对于我在这里展示的代码，我一直专注于简单性和通用性而不是性能。首先让它工作，然后让它快速。我在实际项目中使用的许多优化都是特定于项目的，因此这里不提供最佳代码，而是为您自己的项目提供一些想法：
5.1. 图形#
您可以进行的最大优化是探索更少的节点。我的 #1 建议是，如果您使用网格地图，请考虑使用非网格寻路图。这并不总是可行的，但值得一看。
如果您的图形具有简单的结构（例如网格），请在函数中计算邻居。如果它是一个更复杂的结构（非网格，或有很多墙的网格，如迷宫），请将邻居存储在数据结构中。
您还可以通过重用邻居数组来节省一些复制。不是每次都返回一个新的，而是在搜索代码中分配一次并将其传递给图的邻居方法。
5.2. 队列#
广度优先搜索使用一个简单的队列，而不是其他算法所需的优先级队列。队列比优先级队列更简单、更快。作为交换，其他算法通常探索更少的节点。在大多数游戏地图中，探索更少的节点值得其他算法的放缓。尽管有些地图您不会节省太多，但使用广度优先搜索可能会更好。
对于队列，使用双端队列而不是数组。双端队列允许在任一端快速插入和删除，而数组仅在一端快速。在 Python 中，请参阅collections.deque；在 C++ 中，请参阅deque容器。
然而，事实证明广度优先搜索甚至不需要队列！队列只包含具有 distance 的d节点和具有 distance 的节点d+1。我们可以将队列分成两个，一个 ford和一个 for d+1：
从实现导入*高清 breadth_first_search（图：图中，启动：位置）：
当前前沿 = []
下一个前沿= []
currentfrontier.append(start)
到达：Dict[Location, bool ] = {} 到达[start] = True
而 currentfrontier： 对于当前在currentfrontier： 对于 接下来 的graph.neighbors（当前）： 如果 接下来 没有 在达到：
nextfrontier.append(下一个)
到达 [下一个] =真
＃优化：交换和清晰
currentfrontier，nextfrontier = nextfrontier，currentfrontier
nextfrontier.clear()打印（'可从A：'）广度第一搜索（example_graph，'A'）打印（'从E可达：'）广度第一搜索（example_graph，'E'）
这使用两个数组而不是队列，当您没有不同的边权重时，广度优先搜索的运行速度比 Dijkstra 算法快。在我的 Javascript 项目中，它每秒运行超过 1,000,000 个节点。
5.3. 优先队列#
对于优先级队列，使用二进制堆而不是数组或排序数组。二元堆允许快速插入和删除，而数组在一个或另一个上都很快，但不能同时在这两个上。在 Python 中，请参阅heapq；在 C++ 中，请参阅priority_queue容器。
在 Python 中，我上面介绍的 Queue 和 PriorityQueue 类非常简单，您可以考虑将这些方法内联到搜索算法中。我不知道这对你有没有帮助；我需要测量它。C++ 版本将被内联。
在 Dijkstra 算法中，请注意优先级队列的优先级存储了两次，一次在优先级队列中，一次在 中cost_so_far，因此您可以编写一个从其他地方获取优先级的优先级队列。我不确定这是否值得。
Chen、Chowdhury、Ramachandran、Lan Roche、Tong的论文“Priority Queues and Dijkstra's Algorithm”建议通过不重新确定优先级来优化 Dijkstra 算法的结构，它还建议查看配对堆和其他数据结构。
如果您正在考虑使用除二元堆以外的其他东西，请首先测量边界的大小以及重新确定优先级的频率。分析代码并查看优先级队列是否是瓶颈。
我的直觉是分桶是有前途的。就像当键是整数时桶排序和基数排序可以作为快速排序的有用替代方案一样，我们有一个更好的 Dijkstra 算法和 A* 情况。Dijkstra 算法中的优先级非常狭窄。如果队列中最低的元素具有优先级f，则最高的元素具有优先级f+e，其中e是最大边权重。在森林示例中，我的边权重为 1 和 5。这意味着队列中的所有优先级都将介于f和之间f+5。由于它们都是整数，因此只有六个不同的优先级. 我们可以使用六个桶，而根本不排序任何东西！A* 产生了更广泛的优先级，但它仍然值得一看。还有更高级的分桶方法可以处理更广泛的情况。
5.4. 搜索#
启发式增加了复杂性和 CPU 时间。但目标是探索更少的节点。在某些地图（例如迷宫）中，启发式可能不会添加太多信息，最好使用没有启发式指南的更简单的算法。
有些人使用不可接受（高估）的启发式方法来加速 A* 搜索。这似乎是合理的。不过，我还没有仔细研究它的含义。我相信（但不确定）一些已经到达的元素可能需要再次访问，即使它们已经被带出边界。
一些实现总是将一个新节点插入到开放集中，即使它已经存在。您可以避免检查节点是否已经在开放集中的潜在昂贵步骤。这将使您的开放集更大/更慢，并且您最终也会评估比必要更多的节点。如果开放集测试很昂贵，它可能仍然值得。但是，在我提供的代码中，我使测试成本低廉，并且不使用这种方法。
一些实现不测试新节点是否比开放集中的现有节点更好。这避免了潜在的昂贵检查。但是，它也可能导致错误。对于某些类型的地图，跳过此测试将找不到最短路径。在我提供的代码中，我检查了这个 ( new_cost < cost_so_far)。这个测试很便宜，因为我查起来很便宜cost_so_far。
5.5. 整数位置#
如果您的图形使用整数作为位置，可以考虑使用一个简单的数组，而不是一个哈希表cost_so_far，reached，came_from，等。由于reached是布尔值数组，你可以使用一个位向量。初始化reached所有IDS位向量，但离开cost_so_far和came_from初始化。然后只在第一次访问时初始化。
向量< uint16_t >达到（1+maximum_node_id/16）；…
size_t 索引 = node_id/16;
uint16_t 位掩码= 1u << (node_id & 0xf); if ( ! (达到[索引] & 位掩码)
|| new_cost < cost_so_far[next]) {
到达[索引] |= 位掩码；
…
}
如果一次只运行一次搜索，则可以静态分配这些数组，然后从一次调用到下一次调用重复使用这些数组。然后保留已分配给位向量的所有索引的数组，然后在退出时重置这些索引。例如：
静态 向量< uint16_t >达到(1 + maximum_node_id/16)；静态 向量< size_t > indices_to_clear；…
size_t 索引 = node_id/16;
uint16_t 位掩码= 1u << (node_id & 0xf); if ( ! (达到[索引] & 位掩码)
|| new_cost < cost_so_far[next]) {
if ( ! reached[index]) {
indexs_to_clear.push_back(index);
}
到达[索引] |= 位掩码；
…
}…for ( size_t 索引：indices_to_clear) {
到达[索引] = 0;}indexs_to_clear.clear();
（警告：我没有使用或测试过这段代码）
6 故障排除#
6.1. TODO没有路径#
有时只是没有从开始到目标的路径。这些图搜索算法将搜索和搜索，直到它们用完要探索的节点。最后，frontier将是空的，这意味着没有找到路径。
6.2. 错误的路径#
如果您没有得到最短路径，请尝试测试：
你的优先队列工作正常吗？尝试停止搜索并使所有元素出列。他们都应该井井有条。
你的启发式是否高估了真实距离？在
priority一个新的节点应该不会比其父的优先级低，除非你是高估的距离（你可以做到这一点，但你不会得到的最短路径了）。尝试将启发式设置为 0。如果 0 启发式修复了路径，则您的启发式方法可能是错误的。如果 0 启发式没有帮助，那么您的图搜索算法代码可能存在错误。在静态类型语言中，成本、启发式和优先级值需要具有兼容的类型。此页面上的示例代码适用于整数或浮点类型，但并非所有图形和启发式都仅限于整数值。由于重点是成本和启发式的总和，优先级将需要浮点如果任何成本或启发式的浮点运算。
启发式和成本需要具有相同的“单位”。尝试在没有墙的地图上测试 A*。如果启发式和移动成本匹配，则整个路径上的优先级应该相同。如果不是，那么您的启发式和成本可能不匹配。当没有障碍物且移动成本一致时，在每一步，启发式应该减少与 cost_so_far 增加相同的量。
6.3. 丑陋的道路#
当人们在网格上运行寻路时，我遇到的最常见问题是为什么我的路径看起来不直？在具有统一移动成本的网格上，可以有多个相同长度的最短路径。例如，在 4 向移动网格中，向南 2 和向东 2 移动可以是以下任何一种：SSEE、SESE、SEES、ESSE、ESES、EESS。寻路算法将选择一个，它可能不是您喜欢的那个。该路径短，但它并没有看起来不错。我们可以做些什么来支持好看的路径，比如SESE或ESES？
使用“拉线”算法拉直路径：如果最终路径有点 P、Q、R、S，并且从 P 到 S 有一条直线，那么沿着这条直线而不是访问 Q 和 R。
不要使用网格：只告诉 A* 你可能转弯的地方，而不是每个网格方块；在这里阅读更多。奖励：切换到非网格通常会使 A* 更快。
修改 A* 算法以支持“任意角度”路径：Theta*、Block A*、Field A* 或 AnyA。请参阅Uras 和 Koenig的论文An Empirical Comparison of Any-Angle Path-Planning Algorithms from Uras & Koenig。
通过调整队列中节点的顺序，当与更好看的路径有联系时，微调路径。对于 4 向运动，我在下面描述了两个技巧。对于 8 向运动，请确保您的邻居函数在数组中比对角线方向（NW、SE、SW、NE）更早地返回基本方向（N、E、S、W）。
hacks 不如其他三种方法好用，但它们很容易实现，所以我将在这里描述它们：
6.3.1. 棋盘邻居顺序#
广度优先搜索对其探索图块邻居的顺序很敏感。我们通常以固定的顺序通过邻居。由于广度优先搜索使用先进先出队列，它将选择到节点的第一条路径。
如果向南 2 和向东 2 移动，有很多方法可以到达那里：SSEE, SESE, SEES, ESSE, ESES, EESS。如果在邻居列表中东在南之前，那么它总是在向南探索之前向东探索，并最终选择EESS。如果南在东之前，那么它总是先探索南，最后选择SSEE。我们可以在这个更大的例子中看到这个问题，其中的顺序是东、北、西、南：
从实现导入*test_with_custom_order([(+1, 0), (0, -1), (-1, 0), (0, +1)])
→→→→→→→→↓↓↓↓↓↓↓↓↓↓↓↓↓######。. . . . . . →→→→→→→→↓↓↓↓↓↓↓↓↓↓↓↓↓######。. .↓. . . →→→→→→→→↓↓↓↓↓↓↓↓↓↓↓↓↓######。.→↓ Z ↓ . ↑↑↑######→→→↓↓↓↓@ @ @ @ @ @ @ ######。→→↓ @ ↓↓↑↑↑######→→→↓↓↓↓@ ######↑↑↑↑↑@ ######→→→↓ @ ↓↓↑↑↑######→→→↓↓↓↓@ ######↑↑↑↑↑@ ###############↓ @ ↓↓↑↑↑######→→→↓↓↓↓@ ######↑↑↑↑↑@ ###############↓ @ ↓↓↑↑↑######→→→一个@@@@ ######↑↑↑↑↑ @@@@@@@@@ ←←→→↓######↑↑↑↑↑↑↑↑######↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑→→↓######↑↑↑↑↑↑↑↑######↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑→→↓######↑↑↑↑↑↑↑↑######↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑→→↓######↑↑↑↑↑↑↑↑######↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑→→→→→↑↑↑↑↑↑↑↑######↑↑↑↑↑↑↑↑↑↑↑↑↑↑ . ↑↑↑↑↑↑↑↑↑↑↑↑↑######↑↑↑↑↑↑↑↑↑↑↑↑. . . ↑↑↑↑↑↑↑↑↑↑↑↑↑######↑↑↑↑↑↑↑↑↑↑↑. . . .
在考虑北或南之前，它尽可能向东移动。
如果北在东之前进入列表怎么办？这是输出顺序为南、西、北、东：
从实现导入*test_with_custom_order([(0, +1), (-1, 0), (0, -1), (+1, 0)])
↓↓↓↓↓↓↓↓↓←←←←←←←←←←←←######。. .↓. . . ↓↓↓↓↓↓↓↓↓←←←←←←←←←←←←######。.↓↓←. . →→→→→↓↓↓↓←←←←←←←←←←←←######。↓↓@ ž。. →→↑######↓↓↓ @@@@@@@@@ ←←←←←######↓↓↓ @ ←← . →→↑######↓↓↓ @ ←←←←###### @←←←←←######→→→ @ ←←←→→↑######↓↓↓ @ ←←←←###### @←←←←←############### @←←←→→↑######↓↓↓ @ ←←←←###### @←←←←←############### @←←←↓↓↓######→→→ 一种 ←←←←###### @ @ @ @ @ @ @ @ @ @←←←↓↓↓######→→→↑←←←←######↑←←←←←←←←←←←←←←↓↓↓######→→→↑←←←←######↑←←←←←←←←←←←←←←↓↓↓######→→→↑←←←←######↑←←←←←←←←←←←←←←↓↓↓######→→→↑←←←←######↑←←←←←←←←←←←←←←→→→→→→→→↑←←←←######↑←←←←←←←←←←←←← . →→→→→→→→↑←←←←######↑←←←←←←←←←←←←. . →→→→→→→→↑←←←←######↑←←←←←←←←←←←. . .
让我们试试南、东、西、北：
从实现导入*test_with_custom_order([(0, +1), (+1, 0), (-1, 0), (0, -1)])
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓######。. . . . . . ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓######。. .↓. . . →→→→→↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓######。.↓↓ Z ↓ . →→↑######↓↓↓↓↓↓↓ @@@@@ ←←←←←######。↓↓↓ @ ↓↓→→↑######↓↓↓↓↓↓↓@ ###### @←←←←←######→→→↓ @ ↓↓→→↑######↓↓↓↓↓↓↓@ ###### @←←←←←###############↓ @ ↓↓→→↑######↓↓↓↓↓↓↓@ ###### @←←←←←###############↓ @ ↓↓↓↓↓######→→→一个@@@@ ###### @ @ @ @ @ @ @ @ @ @ @ @←←↓↓↓######→→→↑←←←←######↑←←←←←←←←←←←←←←↓↓↓######→→→↑←←←←######↑←←←←←←←←←←←←←←↓↓↓######→→→↑←←←←######↑←←←←←←←←←←←←←←↓↓↓######→→→↑←←←←######↑←←←←←←←←←←←←←←→→→→→→→→↑←←←←######↑←←←←←←←←←←←←← . →→→→→→→→↑←←←←######↑←←←←←←←←←←←←. . →→→→→→→→↑←←←←######↑←←←←←←←←←←←. . .
没有帮助。任何固定的邻居顺序都会导致路径的水平和垂直部分很长。
这是广度优先搜索的技巧：在图形类中，使邻居列表依赖于(x + y) % 2：
0 时：返回南、北、西、东邻居
when 1：返回东、西、北、南邻居
结果是在垂直和水平步骤之间交替的路径：
从实现导入*test_with_custom_order(无)
→→→↓↓↓↓↓↓↓↓↓↓↓↓↓←←←←←######。. . . . . . →→→→↓↓↓↓↓↓↓↓↓↓↓←←←←←←######。. .↓. . . →→→→→↓↓↓↓↓↓↓↓↓←←←←←←←######。.↓↓ Z ↓ . →→↑######↓↓↓↓↓↓↓ @@@@@ ←←←←←######。→→↓ @ ↓↓→↑↑######↓↓↓↓↓↓@@ ###### @@←←←←######→→→↓ @ ↓↓↑↑↑######→↓↓↓↓ @@ ←######↑ @@ ←←←###############↓ @ ↓←↑↑↑######→→↓↓ @@ ←←######↑↑ @@ ←←###############↓ @ ←←↓↓↓######→→→一个@←←←######↑↑↑ @@@@@@@@@@@@ ←←↓↓↓######→→↑↑↑←←←######↑↑↑↑↑←←←←←←←←←←↓↓↓######→↑↑↑↑↑←←######↑↑↑↑↑↑←←←←←←←←←→↓↓######↑↑↑↑↑↑↑←######↑↑↑↑↑↑↑←←←←←←←←→→↓######↑↑↑↑↑↑↑↑######↑↑↑↑↑↑↑↑←←←←←←←→→→→→↑↑↑↑↑↑↑↑######↑↑↑↑↑↑↑↑↑←←←←← . →→→→↑↑↑↑↑↑↑↑↑######↑↑↑↑↑↑↑↑↑↑←←←. . →→→↑↑↑↑↑↑↑↑↑↑######↑↑↑↑↑↑↑↑↑↑↑←. . .
这是代码：
类 SquareGrid：
…
def 邻居( self , id : GridLocation) ->迭代器[GridLocation]:
(x, y) = id
邻居= [(x+1, y), (x-1, y), (x, y-1), (x, y+1)] # EWNS
if (x + y) % 2 == 0: neighbor.reverse() #改为SNWE
results = filter ( self .in_bounds, neighbor) results = filter ( self .passable, results) 返回结果
这是一个快速的技巧，但它与 4 向移动一起工作，使广度优先搜索路径看起来更好。我在这些教程页面上使用了这个技巧。（注意：我为这些教程页面想出了这个 hack；如果你看到了很好的参考，请将它发送给我。）
6.3.2. 棋盘运动成本#
上面的方向顺序技巧适用于广度优先搜索，但它适用于 A* 吗？我们试试看：
从实现导入*g = GridWithWeights(30, 15)G。wall = DIAGRAM1_WALLS start , goal = (8, 7), (27, 2) come_from , cost_so_far = a_star_search(g, start,goal)draw_grid（g，point_to=came_from，path=reconstruct_path（came_from，开始，目标），开始=开始，目标=目标）
. . . . .↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓######。. . . . . . . . . .↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓######。. .↓. . . . . .→→→→→↓←←←←←←←←←←←←######。.→@ ž。. . . . ######→→→@ @ @ @ @ @ @ @ @ @ @ ######。.→ @ ←. . . . . ######→→→ @ ←←←←######↑↑↑↑↑@ ######。.→ @ ←. . . . . ######→→→ @ ←←←←######↑↑↑↑↑@ ############### @←. . . . . ######→→→ @ ←←←←######↑↑↑↑↑@ ############### @←. . . . . ######→→→ 一种 ←←←←######↑↑↑↑↑ @@@@@@@@ ←. . . . . ######↑↑↑↑↑↑↑↑######↑↑↑↑↑↑↑↑↑↑↑↑. . . . . . ######↑↑↑↑↑↑↑↑######。. . . . . . . . . . . . . . . . . ######。↑↑↑↑↑↑↑######。. . . . . . . . . . . . . . . . . ######。.↑↑↑↑↑↑######。. . . . . . . . . . . . . . . . . . . . . .↑↑↑↑↑######。. . . . . . . . . . . . . . . . . . . . . . . . . . . ######。. . . . . . . . . . . . . . . . . . . . . . . . . . . ######。. . . . . . . . . . . . . .
不，它没有。它更改了队列的插入顺序，但 Dijkstra 算法和 A* 使用遵循优先级顺序的优先级队列而不是插入顺序。Dijkstra 算法中的优先级使用移动成本；A* 中的优先级同时使用移动成本和启发式。我们需要修改移动成本或启发式以更改优先级顺序。
这是A* 和 Dijkstra 算法的技巧：在图形类中，使移动成本取决于(x + y) % 2：
0 时：使水平移动稍微更昂贵
当 1：使垂直移动稍微更昂贵
从实现导入*g = GridWithAdjustedWeights(30, 15)G。wall = DIAGRAM1_WALLS start , goal = (8, 7), (27, 2) come_from , cost_so_far = a_star_search(g, start,goal)draw_grid（g，point_to=came_from，path=reconstruct_path（came_from，开始，目标），开始=开始，目标=目标）
. . . . .↓↓↓↓↓↓↓↓↓↓↓←↓←↓←######。. . . . . . . . . .↓↓↓↓↓↓↓↓↓↓↓←↓←↓←↓######。. . . . . . . . .→→↓→↓↓↓↓↓↓↓←←←←←←←######。. .↓Z。. . . . ######→↓↓↓↓↓↓ @@@@@@@ ←←←######。.→↓ @ ← . . . . ######↓→↓↓↓↓@@ ######↑← @@ ↑←######。.→↓ @ ← . . . . ######→↓→↓↓ @@ ←######↑↑← @@ ↑###############↓ @ ← . . . . ######→→↓↓ @@ ←←######↑↑↑←@@ ###############↓ @ ← . . . . ######→→→一个@←←←######↑↑↑↑← @@@@@@@@@ ← . . . . ######→→↑↑↑←↑←######↑↑↑↑↑↑↑↑↑↑↑↑↑. . . . . ######→↑↑↑↑↑←↑######。. . . . . . . . . . . . . . . . . ######。↑↑↑↑↑↑←######。. . . . . . . . . . . . . . . . . ######。.↑↑↑↑↑↑######。. . . . . . . . . . . . . . . . . . . . . .↑↑↑↑↑######。. . . . . . . . . . . . . . . . . . . . . . . . . . . ######。. . . . . . . . . . . . . . . . . . . . . . . . . . . ######。. . . . . . . . . . . . . .
这适用于 4 向运动。
这是代码：
class GridWithAdjustedWeights (GridWithWeights): def cost ( self , from_node, to_node): prev_cost = super ().cost(from_node, to_node) nudge = 0
(x1, y1) = from_node
(x2, y2) = to_node
if (x1 + y1) % 2 == 0 and x2 != x1 : nudge = 1 if (x1 + y1) % 2 == 1 and y2 != y1 : nudge = 1 return prev_cost + 0.001 * nudge
这是一个快速的技巧，但它与 4 向运动一起工作，使 Dijkstra 算法和 A* 路径看起来更好。（注意：我为这些教程页面想出了这个 hack；如果你在其他地方看到过这个想法，请给我一个参考，以便我可以将它添加到页面中。）
6.3.3. 8向运动#
以上两个技巧适用于 4 向运动。如果你有 8 向运动怎么办？如果所有 8 个方向具有相同的移动成本，我们最终可以得到一条看起来不应该采用对角线的路径：
从实现导入*test_with_custom_order([(-1, -1), (-1, +1), (+1, -1), (+1, +1), (+1, 0), (0, -1), ( -1, 0), (0, +1)])
↓→↓↓↓↓↓↓↓↓↓↓↓↓↓↓←↓←↓←######。. . . . . . →↑→↓↓↓↓↓↓↓↓↓↓↓ @ ←↑←↑←↑######↓↓↓↓↓↓↓↑→↑→↓↓↓↓↓↓↓↓↓ @ ← @ ←↑←↑←######↓↓↓↓ Z ↓↓→↑↑######↓↓↓↓↓↓↓ @ ←↑← @ ←↑←↑######→↓↓↓ @ ↓↓↑↑↑######↓↓↓↓↓↓ @ ←######↑← @ ←↑←######↑→↓ @ ↓↓↓↑↑↑######→↓↓↓↓ @ ←↑######↑↑← @ ←↑###############↓ @ ↓←↑↑↑######↑→↓↓ @ ←↑←######↑↑↑← @ ←############### @↓←↑↑↑↑######→↑→ 一种 ←↑←↑######↑↑↑↑← @ ← @ ← @@ ↓←↑←↓↓↓######↑→↑↑↑←↑←######↑↑↑↑↑← @ ← @ ←↑←↑←↑↓↓↓######→↑↑↑↑↑←↑######↑↑↑↑↑↑←↑←↑←↑←↑←↓↓↓######↑↑↑↑↑↑↑←######↑↑↑↑↑↑↑←↑←↑←↑←↑→↓↓######↑↑↑↑↑↑↑↑######↑↑↑↑↑↑↑↑←↑←↑←↑←↑→↓→↑↑↑↑↑↑↑↑↑######↑↑↑↑↑↑↑↑↑←↑←↑←↑→↑→↑↑↑↑↑↑↑↑↑↑######↑↑↑↑↑↑↑↑↑↑←↑←↑←↑→↑↑↑↑↑↑↑↑↑↑↑######↑↑↑↑↑↑↑↑↑↑↑←↑←↑
4 路打破平局的技巧可以扩展到这里工作：
广度优先搜索：确保基数邻居（N、S、E、W）在对角邻居（NE、NW、SE、SW）之前。
Dijkstra 算法，A*：向对角线运动添加微小的运动惩罚 (0.001)。
使用这些技巧之一后，路径将如下所示：
从实现导入*test_with_custom_order([(+1, 0), (0, -1), (-1, 0), (0, +1), (-1, -1), (-1, +1), (+1 , -1), (+1, +1)])
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓######。. . . . . . ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓######。↓↓↓↓. . →→→→↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓######↓↓↓↓ Z ↓↓↑↑↑######↓↓↓↓↓↓↓↓ @@@@@@ ←←←######↓↓↓ @ ↓↓↓↑↑↑######↓↓↓↓↓↓↓@ ######↑↑↑ @ ↑↑######→→↓ @ ↓↓↓↑↑↑######↓↓↓↓↓↓ @ ↓######↑↑↑↑ @ ↑############### @↓↓↓↑↑↑######↓↓↓↓↓ @ ↓↓######↑↑↑↑↑@ ############### @↓↓↓↑↑↑######→→→一个@←←←######↑↑↑↑↑↑ @@@@@@ ←←←←↓↓↓######↑↑↑↑↑↑↑↑######↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↓↓↓######↑↑↑↑↑↑↑↑######↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↓↓↓######↑↑↑↑↑↑↑↑######↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↓↓↓######↑↑↑↑↑↑↑↑######↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑→→→→↑↑↑↑↑↑↑↑↑######↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑######↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑######↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑
这些技巧很容易实现，并为网格提供了合理的路径。但是，要获得更好的路径，请尝试丑陋路径部分中列出的方法。
7 词汇#
算法教科书经常使用带有单字母变量名称的数学符号。在这些页面上，我尝试使用更具描述性的变量名称。函件：
cost有时写成w或d或l或长度cost_so_far通常写为g或d或距离heuristic通常写成h在 A* 中，
priority通常写为f，其中f = g + hcame_from有时写成π或 parent 或 previous 或 prevfrontier通常称为开放或边缘诸如
current和 之类的next位置称为状态或节点，并用字母u , v书写
OPEN、CLOSED 和reached 集是状态集。在我的代码中，它们没有自己的数据结构，而是作为其他数据结构的一部分包含在内：
的元素的
frontier是OPEN组和所述优先级的frontier是相关联的优先级值。该键的的
came_from地图是达到设定和值的的came_from地图是父指针。另外，如果你想保留的成本，该键的的cost_so_far地图是达到设定和值的的cost_so_far地图是成本。到达集合是 OPEN 和 CLOSED 的并集。
即使它们没有存储在单独的数据结构中，我们也可以对 OPEN、CLOSED 和已到达集合进行推理。
8 更多阅读#
Aleksander Nowak在https://github.com/vyrwu/a-star-redblob上编写了此代码的Go 版本