What happens when I switch from Manhattan to Euclidean or Chebyshev distance?

Each heuristic changes how h(n) estimates distance to the goal, which reshapes the search frontier. Manhattan distance (horizontal plus vertical steps) is exact for 4-directional movement; Euclidean distance (straight-line hypotenuse) suits diagonal movement; Chebyshev distance (the larger of the horizontal and vertical differences) suits boards where diagonal steps cost the same as orthogonal ones. Picking a heuristic that undershoots the true distance keeps A-star optimal but can expand more nodes; overshooting speeds up the search but can produce a longer path.

Why does painting a Weight tile change the route instead of just slowing it down?

A Weight tile costs 5 to enter rather than 1, so it raises g(n) for any path that crosses it. Because A-star and Dijkstra always minimise total cost, they will happily take a longer route around a cluster of weighted cells if that route is cheaper overall. Greedy Best-First, which ignores g entirely, is the only mode that can walk straight through expensive terrain.

What does the frontier colouring actually track under the hood?

Blue cells are in the open set, discovered but not yet expanded, and are stored in a binary min-heap keyed on f, with ties broken by the lower h value. Dark blue cells are closed, meaning their neighbours have already been examined and their g score is final. Yellow marks the single node popped from the heap on the current step.

Why does Generate maze make Greedy Best-First perform so much worse?

The maze generator carves a perfect maze with exactly one route between any two cells using a randomised recursive backtracker, so there are no shortcuts for a heuristic to exploit. Greedy Best-First keeps rushing toward whichever open cell looks closest to the goal in a straight line, frequently charging down dead-end corridors, whereas A-star and Dijkstra methodically retreat and try the only other option.

Is the diagonal-move cost handled correctly?

Yes, when Allow diagonal moves is ticked, diagonal steps cost the square root of two instead of 1, matching their true Euclidean length, and the simulator blocks diagonal moves that would cut through the corner of two adjacent walls. The heuristic also switches to an octile-distance formula in this mode so it remains admissible for 8-directional movement.

首页▸算法与人工智能▸A* 寻路算法

🗺️ A* 寻路算法

观察 A* 算法在网格上通过 f(n)=g(n)+h(n) 寻找最短路径。绘制墙体,拖动起点和终点,切换启发函数,并比较 A*、Dijkstra 与贪婪搜索。

算法与人工智能3D中等60 FPS

关于 A* 寻路算法

A*(读作「A-star」)是一种最佳优先图搜索算法,它将 Dijkstra 算法保证最优的「已走代价」(g)与对剩余距离的启发式估计(h)结合起来,为每个节点计算优先级得分 f = g + h,从而找到两点间的最短路径。该算法由 Hart、Nilsson 和 Raphael 于1968年提出,如今支撑着从电子游戏角色导航、机器人运动规划到谷歌地图路线计算的方方面面。当启发函数是可采纳的——即它从不高估真实代价时,A* 保证能找到最优路径。

本模拟允许你在网格上于 A*、Dijkstra(h = 0)和贪婪最佳优先(g = 0)之间切换,你可以绘制墙体和加权地形(代价 ×5)、拖动起点和终点节点、选择启发函数(曼哈顿距离、欧几里得距离或切比雪夫距离)、开关对角移动,并逐步观察节点如何被扩展。实时统计信息显示已扩展的节点数、路径长度和总代价。

常见问题

f = g + h 是什么意思?

在 A* 中,开放集中的每个节点都以 f(n) = g(n) + h(n) 打分,其中 g(n) 是从起点到节点 n 已找到的最便宜路径的准确代价,h(n) 是从 n 到终点的启发式代价估计。算法总是扩展 f 值最低的节点,这保证了只要 h 是可采纳的,首次扩展终点时得到的路径就是最优的。

什么是可采纳启发函数?

如果启发函数 h 从不高估到达终点的真实代价——形式上对所有 n 都有 h(n) ≤ h*(n),则称它是可采纳的。曼哈顿距离(水平和垂直步数之和)在四连通网格上是可采纳的;欧几里得距离在任意网格上都是可采纳的。不可采纳的启发函数可以让 A* 更快,但可能返回次优路径。

A* 与 Dijkstra 算法有何不同?

Dijkstra 算法令 h = 0,因此它按照从起点出发的准确代价顺序扩展节点,像涟漪一样向四面八方均匀扩散。A* 则加入启发函数引导搜索朝向终点,通常扩展的节点要少得多。在没有障碍物的开放网格上,使用曼哈顿距离的 A* 相比 Dijkstra 可将节点扩展数减少50%–90%。

为什么贪婪最佳优先搜索更快但不是最优的?

贪婪最佳优先令 g = 0,只用 h 对节点排序,总是急于冲向看起来离终点最近的节点。这在开阔环境中非常快,但它忽略了实际路径代价,因此可能被引诱穿过昂贵地形或绕过障碍物,走上更长的路线。最坏情况下,它找到的路径可能比最优路径差得多。

什么时候该用曼哈顿距离、欧几里得距离还是切比雪夫距离?

当移动仅限于4个方向(上下左右)时使用曼哈顿距离,因为它准确计算出最少步数。当允许对角移动且对角代价等于 √2 时,欧几里得距离更合适。当所有8个方向代价相同时(许多策略游戏中常见),切比雪夫距离(|Δx|、|Δy| 中的较大者)是正确的选择。

什么是加权格子,它如何影响寻路?

加权格子代表更难穿越的地形——泥地、浅水或崎岖道路。在本模拟中,进入一个加权格子的代价是5而不是1,因此 A* 通常会绕开若干加权格子,而不是直接穿过它们。Dijkstra 和 A* 都能正确处理权重;贪婪最佳优先则忽略代价,可能直接穿过昂贵地形。

A* 的时间复杂度是多少?

最坏情况下,A* 的时间和空间复杂度为 O(b^d),其中 b 是分支因子,d 是最优解的深度。使用一致性启发函数(满足三角不等式)时,每个节点最多被扩展一次,在有 V 个顶点的有限图上给出 O(V log V) 的复杂度——与使用二叉堆的 Dijkstra 算法渐进复杂度相同。

迷宫生成如何影响搜索?

迷宫生成器使用随机化算法在网格中开凿通道,生成一个「完美迷宫」,保证任意两个格子间恰好有一条路径。迷宫对搜索算法要求特别高,因为狭窄的走廊消除了 A* 的启发式优势——由于只有一条有效路径,所有算法都必须探索大致相同的节点。

网格上的颜色分别代表什么?

绿色标记起点,红色标记终点。蓝色格子构成当前的前沿(开放集),深蓝色标记已访问(封闭)的节点,黄色高亮正在被扩展的节点。加权格子显示为棕色。一旦找到路径,会从起点到终点以青柠绿描出,你可以在统计面板中读取确切的代价。

A* 能用于三维或非网格图吗?

可以——只要边的代价非负,并且你能提供一个可采纳的启发函数,A* 就可用于任意图。实际应用包括三维机械臂运动规划(位形空间图)、网络路由(以延迟为代价)以及自然语言解析(类似维特比的格架)。这里的网格只是该通用算法最直观的可视化表现形式。

「已扩展节点数」这个计数器有什么意义?

已扩展节点数统计算法从前沿中取出并处理其邻居的次数——这是衡量 A* 效率的主要指标。数值越低说明启发函数引导得越好。在一个30×30的网格(900个格子)上,好的启发函数往往能在扩展少于100个节点的情况下找到最优路径,而 Dijkstra 可能要扩展每一个可达的格子。

关于本模拟

本模拟展示了 A* 搜索算法 在加权网格上寻找最短路径的过程。每个前沿节点都携带一个得分 f(n) = g(n) + h(n),其中 g 是从起点走过的准确距离,h 是到终点剩余距离的启发式估计;算法总是优先扩展 f 值最低的节点。将算法下拉菜单切换到Dijkstra 会将 h 归零,而贪婪最佳优先则完全舍弃 g,因此你可以逐节点地观察同一个迷宫以三种不同方式被求解。

🔬 展示内容

彩色编码的网格实时追踪搜索过程:蓝色格子处于开放前沿,深蓝色格子已被完全扩展(封闭),黄色标记当前正在处理的节点。到达终点后,获胜路径会以青柠绿描出,侧边栏报告已扩展的节点数以及总路径代价。

🎮 使用方法

从下拉菜单中选择算法和启发函数,然后使用绘制工具按钮添加墙体、代价×5的加权地形,或拖动「移动起点/移动终点」标记。「允许对角移动」在4方向和8方向移动间切换,「显示 g/h/f 值」会在每个格子上叠加原始得分,「自动运行」「单步」「生成迷宫」「清除墙体」和「重置」控制回放与棋盘布局。

💡 你知道吗?

A* 由 Peter Hart、Nils Nilsson 和 Bertram Raphael 于1968年发表,尽管已有半个多世纪的历史,但由于只要给定可采纳的启发函数,它就绝不会探索多余的节点,因此至今仍是大多数电子游戏、机器人系统和路线规划器的默认寻路选择。

常见问题

从曼哈顿距离切换到欧几里得或切比雪夫距离会发生什么?

每种启发函数都会改变 h(n) 估计到终点距离的方式,从而重塑搜索前沿。曼哈顿距离(水平加垂直步数)对4方向移动是精确的;欧几里得距离(直线斜边)适合对角移动;切比雪夫距离(水平与垂直差值中较大者)适合对角步和正交步代价相同的棋盘。选择低估真实距离的启发函数能保持 A* 最优,但可能扩展更多节点;高估则会加快搜索,但可能产生更长的路径。

为什么绘制加权格子会改变路线,而不只是让速度变慢?

加权格子的进入代价是5而非1,因此会提高任何穿过它的路径的 g(n)。由于 A* 和 Dijkstra 总是最小化总代价,如果绕开一簇加权格子的路线整体更便宜,它们会欣然选择更长的绕行路线——完全忽略 g 的贪婪最佳优先,是唯一可能直接穿过昂贵地形的模式。

前沿的颜色实际追踪的是什么底层机制?

蓝色格子处于开放集——已发现但尚未扩展——存储在以 f 为键的二叉最小堆中,若 f 相同则以较低的 h 值打破平局。深蓝色格子已封闭,意味着其邻居已被检查过,其 gScore 已确定。黄色标记当前这一步从堆中弹出的那个节点。

为什么「生成迷宫」会让贪婪最佳优先的表现差这么多?

迷宫生成器使用随机化的递归回溯算法开凿出「完美迷宫」,任意两个格子间恰好有一条路径,没有捷径可供启发函数利用。贪婪最佳优先总是冲向直线上看起来离终点最近的那个开放格子,常常一头扎进死胡同,而 A* 和 Dijkstra 则会有条不紊地退回并尝试唯一的其他选项。

对角移动的代价处理是否正确?

是的——勾选「允许对角移动」后,对角步的代价为 √2 而非1,与其真实的欧几里得长度相符,且模拟器会阻止那些会穿过两堵相邻墙体夹角的对角移动。此模式下启发函数也会切换为「八方距离」公式,以保持对8方向移动的可采纳性。

⚙ Under the hood

Watch A* find the shortest path on a grid using f = g + h. Paint walls, drag start/goal, switch heuristics, and compare A* vs Dijkstra vs Greedy to see how the heuristic changes nodes expanded.

Canvas 2DPathfindingA*Heuristic SearchDijkstra

3D · Three.js / WebGL renderer · 60 FPS target · runs fully client-side, no install