在 Excalidraw 中构建 Elbow Arrows（第 2 部分）

Source: Dev.to

之前在《构建肘形箭头》…

在第一部分，我们确定了设计目标（最短路径、最少段数、正确的箭头方向以及避免形状），但我们对算法的天真且贪婪的首次尝试在多个方面都显得不足。因此，这种方法被放弃，转而采用另一种算法。

游戏来拯救

设计目标与视频游戏中路径寻找的问题惊人地相似，而路径寻找是一个常见且研究充分的问题。这些游戏中的角色常常需要从点 A 到点 B 在游戏地图上前进，避免被障碍物阻挡，并使用最短路线。他们还需要让路径看起来像是人类会走的那样，以免破坏沉浸感。因此，我们将注意力转向 A* 搜索算法。

建立基础

要理解 A* 路径寻找，我们需要了解其背景、它所基于并改进的其他图搜索算法，以及这些算法如何帮助我们解决挑战。

• A* 的来源 – 它属于一类图搜索算法，所有这些算法的目标都是在由节点和边连接的图中找到最短路径。虽然这使它们的用途远超游戏领域，但这里我们专注于在二维网格（即画布）上的路径寻找。
• 将画布转化为图 – 如果我们把画布划分为二维网格（极端情况下，每个像素都是一个单元格），每对相邻单元格的公共边可以表示为图的边，而这些单元格本身则是图的节点。

只要我们能够在这些节点边（网格单元格）之间找到满足原始约束的路线，就可以直接绘制出拐角箭头本身！

广度优先搜索

一种能够保证在无权图中找到最短路径的简单图搜索算法是朴素的 广度优先搜索（BFS），我们将从这里开始探索。

• BFS 在每一次迭代中，从已经访问过的节点出发，访问所有直接相连且未被访问的节点（从起始单元格开始）。
• 它会一直进行，直到包含终点的单元格被访问为止。
• 在搜索过程中，我们会记录每个已访问节点是从哪个相邻节点 来到 的，从而形成一条指向起始节点的链表。
• 当到达终点时（因为路径已经是最优的，我们可以提前结束），我们会沿着这条链表 回溯，得到最短路径。

得到的路径是可能的最短路径，但它 不像 那种弯曲的箭头，因此在视觉上并不美观。不过，它是我们后续构建的坚实基础。

NOTE: If you’re interested in diving deeper into BFS, DFS, and how A* works, I recommend this article, which dives deeper into these algorithms and offers interactive visualizations. This guide will only cover the key insights needed for the final elbow‑arrow implementation.

Source: …

迪杰斯特拉算法

BFS 为我们提供了最短路径并能够避开障碍，但它仍然无法产生我们在拐角箭头中需要的正交弯折。为了让算法倾向于形成所需的形状，我们转而使用 迪杰斯特拉算法。

• 迪杰斯特拉在 加权 图的边上运行，使用权重作为访问邻居的代价。
• 想象画布拥有第三个 “深度” 维度：位于正确拐角箭头路径上的单元格是平坦的，而所有其他单元格则是陡峭的 “墙”。
• 我们的 “迷宫生成器” 可以为满足设计目标的单元格分配低代价（谷地），并为其他所有单元格分配高（或禁止）代价。

由于 Excalidraw 画布实际上是无限的，我们无法预先计算整个地形。相反，算法必须能够针对任意给定的单元格查询哪些相邻单元格的访问代价低，哪些代价高。

Source: …

距离函数

塑造地形的关键在于精心挑选的 距离函数。边权应自然地向终点单元递减，形成向下的“坡度”（负梯度），同时让错误的选择代价高昂。

• 欧氏距离 – 两点之间的直线长度。
• 曼哈顿（出租车）距离 – 更适合我们的正交箭头路径。其计算方式是将坐标的绝对差相加：

[ \text{Manhattan}(p_1, p_2) = |x_1 - x_2| + |y_1 - y_2| ]

例如，([5, 12]) 与 ([10, -3]) 之间的距离为 (|5-10| + |12-(-3)| = 5 + 15 = 20)。

下图展示了一条欧氏（绿色）直线和三条等长的曼哈顿路径（红色、蓝色和黄色）。

将曼哈顿距离用作 A* 的启发式（或作为 Dijkstra 的权重函数），会促使算法倾向于正交移动，从而得到我们期望的特征性肘形箭头。

其他启发式

在 Dijkstra 算法中对我们想要访问的每个单元查询曼哈顿距离，可以得到一个用于生成 迷宫 的度量，但它会提供多条等权路径，我们需要在这些路径中选择正交拐弯最少的那一条。

我们在 迷宫生成器 中加入了额外的项：不仅考虑相邻单元到终点的曼哈顿距离，还会在移动到该单元会产生拐弯时增加其代价。

搜索度量：

Manhattan distance + bend count

这种加权函数配合 Dijkstra 算法，在没有障碍物需要规避的情况下，就能生成正确且视觉上令人满意的肘形箭头。

排除区

为了支持形状规避，我们需要停用某些单元格。这些单元格在我们的迷宫中表现为无限高的墙壁，因此图搜索算法永远不会访问它们。只需为每个单元格添加一个标志，将形状映射到这些单元格，并禁用被形状覆盖的单元格，即可轻松实现。

然而，结合我们修改后的距离计算，算法开始在形状周围走次优路径。原因在于我们看不到整个“地图”（即网格）；这就像一种战争迷雾，我们在搜索的每一次迭代中才逐步揭开。我们本应提前规避的障碍物可能直到为时已晚才被“看到”。

引入回溯过程是一种实用的解决方案，但在计算上可能不可行。为了减少不必要的探索步骤并结合我们的启发式方法，A*算法似乎是一个最佳选择。

A*类似于 Dijkstra 算法——它考虑图边的权重——但它优先探索那些最有可能让我们更接近目标的相邻节点（或单元格），从而避免浪费计算。它还承诺提供一次性通过的解法，且内存效率高。

什么是 A*？

A* 的关键洞察在于它为每个单元（节点）平衡了两个因素：

• g(n) – 从起点到达节点的实际成本（我们的拐弯计数加上以后可能的额外启发式）。
• h(n) – 从该节点到达目标的估计成本（曼哈顿距离 + 网格排除 + 任何额外的启发式函数）。
• f(n) = g(n) + h(n) – 通过该节点的路径的总估计成本。

算法维护两组节点：

• Open set – 待评估的节点。
• Closed set – 已评估的节点。

过程

1. 将起始节点加入 Open set。
2. 循环，直到 Open set 为空：
   • 选择 f(n) 分数最低的节点。
   • 如果它是目标节点，重建路径并返回。
   • 将该节点移入 Closed set。
   • 对每个邻居节点：
     • 计算一个暂定的 g 分数。
     • 如果邻居在 Closed set 中 且 新的 g 分数更差，则跳过。
     • 如果邻居不在 Open set 中 或 新的 g 分数更好：
       • 更新邻居的分数。
       • 将当前节点设为邻居的父节点。
       • 将邻居加入 Open set。
3. 如果 Open set 变为空且未找到目标，则不存在路径。

通过始终探索 f(n) 值最低的节点，A* 能高效地找到最优路径，而无需对每一种可能进行穷举搜索——这正是我们想要的。在此阶段，实现大体上符合预期，但仍会出现一些边缘情况，使得人类期望的路线选择不同，同时性能仍然是个问题。

性能优化

虽然行为已经接近，但性能很快就成为瓶颈，尤其是每帧都需要计算多个肘形箭头路径时。目标是实现 120 Hz 的流畅渲染，并在每帧重新路由约 50 条肘形箭头，这是一项高难度但可实现的目标。

二叉堆优化

最容易实现的改进是对开放节点集合（单元格）进行优化。每次迭代在开放节点上进行线性查找并不理想。显而易见的解决办法是将开放集合存放在 二叉堆 中，从而将插入和删除的时间复杂度从 O(n) 降至 O(log n)。

非均匀网格

在像素网格上操作（每个像素对应一个节点）会导致大量不必要的 A* 迭代（通常 > 99 %）。即使使用只跨越几个像素的单元格，也会浪费大量计算，并且阻碍像素级精确的结果。

解决方案是绘制 非均匀网格，仅在可能出现拐弯的地方放置节点。美观的肘形箭头总是在以下位置转折：

• 形状的拐角，
• 起点和终点的方向，
• 需要规避的形状之间的中点（可加可选的间距）。

由于算法在图的节点上运行，我们并不需要使用统一大小的网格。A* 和曼哈顿距离计算唯一的要求是相邻单元格具有连续的笛卡尔坐标。

Adaptive Grid (preview)

本文继续探讨如何根据当前形状的布局动态生成并调整非均匀网格，但此摘录在此结束。

图片来源：Wikipedia（via dev.to）

Source:

使用曼哈顿距离的 A* 实现美观且高效的拐角箭头

美观启发式

虽然基本的 A* 实现已经比 BFS 方法产生了更好的结果，但仍然存在一些情况——除了弯曲次数过多之外——会生成不自然的路径。通过仔细构建额外的启发式，我们能够解决这些问题。然而，对 A* 度量的修改会影响所有边缘情况，因此测试和微调都是手动进行的，最终得到下面的方案。

1. 防止向后访问

当没有其他可行路线时，箭头段禁止向后移动（即与之前的段重叠）。这不仅可以防止出现尖峰式路径（直接反向的段），几乎还能完全避免需要 U 形箭头配置的路线。

• 工作原理
  • 记录访问的方向。
  • 向后查看一步、向前查看一步，以检测问题配置。
  • 将此与非常特定的网格选择相结合，防止在边缘情况下触发该问题。

注意： 之所以可行，是因为最多只能有 两个 闭合的轴对齐边界框（即形状）需要规避。若障碍物更多，问题会再次出现。

2. 考虑段长

即使曼哈顿距离是驱动 A* 寻路的主要度量，仍然更倾向于使用更长的直线段（欧氏距离）而不是多个短段。在某些极端情况下，非均匀网格会误以为生成的路径是最短的，但投射到像素网格后会产生不应出现的短步模式——尤其是当相连的形状相距较远时。

3. 形状侧面感知

在决定绕障碍物左侧还是右侧时，算法会考虑：

• 障碍物各侧的长度。
• 起点和终点的方向相对位置（参见本系列第 1 部分的“方向”）。
• 箭头与形状边界框侧面的平行或正交关系。

4. 短箭头处理

针对起点和终点极其接近的情况，使用特殊逻辑防止过度蜿蜒和环路。在一个几乎重叠的相连形状场景中，采用硬编码的简化直线路径，因为通用算法永远不会产生期望的路径。

5. 重叠管理

实现中会显式检测形状是否覆盖起点和/或终点。当相连的形状或点重叠时，会有选择地为一个形状或两个形状关闭规避，从而确保即使排除区会阻断路径，也仍然能够得到有效路线。

其他方案

使用曼哈顿距离的 A* 并不是获得正交（拐角）箭头的唯一方法。以下是一些曾被考虑但最终未采用的研究论文：

• Gladisch, V., Weigandt, H., Schumann, C., & Tominski, C.
  Orthogonal Edge Routing for the EditLens – arXiv:1612.05064

• Wybrow, M., Marriott, K., & Stuckey, P. J.
  Orthogonal Connector Routing – Springer PDF

结论

最初只是一个简单的功能请求——“添加弯折箭头”，却演变成一个复杂的路径寻找挑战。通过结合：

• 经典算法（A*），
• 领域特定的优化（非均匀网格、仅需规避两种形状等），以及
• 精心调校的启发式（美观权重），

Excalidraw 的弯折箭头显著加快了绘图速度，并消除了手绘、手动管理箭头的需求。

这些改进还使其他强大功能成为可能，例如 键盘快捷键流程图创建（观看演示），进一步赋能有严肃绘图需求的 Excalidraw 用户。

接下来： 加入我，观看本系列关于弯折箭头的 第三篇也是最后一篇，我将向你展示如何通过控制和修正箭头段落，使得对高级用户而言难以预测的路径成为可能！