在构建自动布线工具之前我会告诉自己的13件事

美男子玩编程

“ 非常棒的分享，强烈推荐！想尝试做自动布线工具的小伙伴都来学习下。本文来自 tscircuit 的主要作者 SEVE，详细总结了耗费约一年时间尝试打造全球最快自动布线工具的重要经验。 ”

vzwycoc04cu64060630032.png

我在为 tscircuit（一款用TypeScript编写的开源电子CAD内核）开发自动布线工具上耗费了约一年时间。如果我能回到一年前，以下是我会告诉自己的13件事：

kf21k5soqsx64060630132.png

一个键盘项目自动布线的中间阶段
1. 像熟悉自己的手掌一样掌握 A* 算法
如果我能当一天国王，我会把 A* 算法改名为"基础算法"。这确实是任何类型搜索中最具适应性和重要性的算法之一。它简直是为各种启发式搜索（不局限于二维网格！）打造的最佳基础框架。
这里展示的是二维网格中 A*算法与"广度优先搜索"算法的动画对比：
A* 算法探索节点的方式要快速直观得多。这两种算法的主要区别在于，广度优先搜索会探索所有相邻节点，而 A* 会优先探索距离目标更近的节点。由于它考虑了图结构外的度量标准（与目标的距离），因此属于启发式搜索。
您的代码中很可能已经在使用广度优先搜索或深度优先搜索。递归算法本质上就是深度优先搜索。任何不排序候选节点/相邻节点就直接遍历的循环结构都属于广度优先搜索。在99%的情况下，您都可以将其转换为 A* 算法并获得显著的性能提升！
在我的自动布线器中，最让我自豪的设计之一是通过运行多层 A* 算法来发现特定场景的最优超参数。我们的做法本质上是将每个自动布线器作为候选方案运行，然后通过 A* 算法确定哪些自动布线器最值得我们投入大量时间优化！
看到顶部那些数字了吗？每个数字都代表不同的超参数配置。如果不加区分地运行每个自动布线器将造成巨大的时间浪费——当某个自动布线器开始胜出（即以较低成本成功布线）时，就应为它分配更多迭代次数！这种元A*(meta-A*) 算法将常规的路径距离惩罚成本函数，与迭代次数惩罚成本函数进行了智能结合。2. 实现语言无关紧要我颇具争议地使用 JavaScript 开发自动布线器。这是人们最先质疑的点，但实际并非如想象中那般不合理。优化算法时，您本质上需要提升两个维度：

降低必要迭代次数（提升算法智能度）

提升单次迭代速度
[/ol]人们往往过度聚焦于第二点。当您采用低效实现方案时（例如将所有元素转为网格进行重叠检测），无论使用何种编程语言，执行效率都会令您大失所望！

用最优化的汇编编写的笨算法，远不及JavaScript实现的智能算法！
算法 > 语言！

95%的优化精力都应聚焦于减少迭代次数。这才是编程语言无关紧要的根本原因：能让您最快构建出最智能、最具缓存效率算法的语言，就是最佳实现路径！
3. 空间哈希索引 > 树状数据结构
在多维空间优化领域，四叉树（QuadTree）可谓无人不知。这种神奇的数据结构能将二维/三维空间中邻近物体搜索的复杂度从O(N)降为O(log(N))。
但四叉树及所有通用树状数据结构都存在致命缺陷：它们的效率极其低下。树状结构本质上无法实现启发式数据表征。

每当您选择树状结构时，实际上是用复杂度更高的O(log(N))算法替代了复杂度接近O(1)的哈希算法

为何 JavaScript 始终优先采用哈希集合与哈希映射？因为它们拥有绝对性能优势。空间哈希索引（Spatial Hash Index）的核心理念与哈希映射（HashMap）相同，不同之处在于：我们不再对物体本身进行哈希，而是对其空间坐标进行哈希处理，将其存储于特定单元（或"空间邻近物体的集合容器"）

red4pl30k3u64060630232.png

让我们看看如何用空间哈希索引替换 QuadTree，代码量只需 20%：

o20sevymbyu64060630332.png

该基础数据结构存在多种针对不同对象类型的变体，但其核心原理高度相似。我们本质上是通过空间哈希创建"容器"，并将所有位于该哈希对应单元格内的对象填充其中。
空间哈希未能广受推崇的主因在于：需审慎选择单元格尺寸：这正是其作为启发式算法的关键所在。若单元格尺寸校准失当，您将承担高昂的固定检索成本。但实践中，选取合理的单元格尺寸并非难事。
4. 高效空间分区+缓存机制的重要性是算法性能的1000倍
诸如 iPhone 内部电路板这般精密的设计，通常包含 10,000 至 20,000 条走线，即便使用全球顶尖的 EDA 工具也需要团队耗费数月完成布线。优化如此复杂的任务看似令人生畏，但事实是整个行业都在忽视一个简单真理：所有已完成布线的方案都存在历史复用可能。
游戏开发者会为导航网格"预烘焙"数GB数据。大型语言模型将整个互联网压缩为可检索的权重参数。新一代自动布线器将采用空间分区策略，并调用海量预解决方案的缓存库。当99%的布线问题已存在预解决方案时，算法本身的执行速度将变得无关紧要。
当前大多数算法并未聚焦于缓存可复用性与空间分区的有效性，但未来自动布线器的核心组件必定是以空间分区方式缓存各阶段输入输出的解决方案。
更关键的是，存储介质成本下降速度远超算力提升速度。为自动布线器配置 1GB 缓存实现 50% 提速，在当今技术环境下完全是可行方案。

jcrspudjjfy64060630433.jpg

最终，高速缓存将获胜。可缓存算法比快速算法更重要！
5. 如果问题不能可视化，你可能永远无法解决
若要将一个技术信条制成海报，我必选择"问题可视化优先"。仅凭数值分析永远无法有效调试复杂系统。
我们为每个微小子算法都构建了专属可视化视图。开发流程往往始于可视化工具的创建。无数次实践证明，这种方法能将调试与问题解决效率提升10倍。下图展示了我们在"路径简化阶段"（自动布线器近终局阶段）中，用于45度路径探索的子算法可视化方案：
6. JavaScript 性能剖析工具（Profiling）堪称神器——速速用起来！
JavaScript 性能剖析工具令人惊叹，您能直观查看每行代码消耗的毫秒级执行时长。无需引入任何性能框架，直接在浏览器运行代码后调出性能面板即可。工具还内置火焰图分析、内存使用分析等强大功能，助您精准定位性能瓶颈。

oas5ljtx41c64060630533.png

用于调试 @tscircuit/core 中性能的火焰图分析示例

osb1ogu1zjr64060630633.jpg

您可以在 Chrome 浏览器的性能工具中轻松查看每行代码所花费的时间！
7. 彻底弃用递归函数
递归函数存在多重致命缺陷：
? 同步执行特性（无法中断执行实现动画效果）
? 本质属于深度优先搜索（DFS）架构，难以改造为 A* 算法
? 迭代过程难以追踪与分析
? 可变状态(Mutability)操作在递归中极不自然，却对性能优化至关重要
以下是将典型递归函数重构为非递归实现的示例代码：

rltygphfqfr64060630733.jpg

基于迭代的实现方案性能显著提升，关键在于其维护了已访问节点集合(visitedNodes)并在节点探索前执行预检。虽然递归函数理论上也可实现类似机制，但必须通过传递可变状态对象等非自然编码方式达成。因此在编写高性能代码时，强烈建议彻底规避递归函数。
8. 像蒙特卡洛算法实属权宜之计——切勿滥用

sbknijj1fm564060630833.png

蒙特卡洛算法通过随机采样逼近解决方案，其本质缺陷在于：
? 催生非确定性算法，大幅增加调试难度
? 相较启发式策略，永远无法达成最优解
该算法仅在两种场景下具有临时价值：当解决方案路径未知但评估函数已定义时，可辅助建立基础认知框架。但一旦构建出近似成本函数，请立即转向更智能的算法（如模拟退火等随机优化技术亦需规避）。如果算法容易陷入局部最优陷阱，应通过超参数调优或复合成本函数设计破局：人眼可辨识的局部最优现象，均可转化为成本函数约束条件。
行业实践视角佐证：可曾见过PCB工程师在电路板上随机布线？绝无可能。该领域根本不存在随机技术的生存空间。启发式策略的优化空间永无止境。
9. 确保中间算法稳健可靠
当前我们的自动布线器采用13阶段处理管线架构，包含约20个可监测迭代次数的子算法模块。这些模块分别承担空间分区判定、边界路径简化等独立布线区域的专项优化任务。
通过叠加展示各阶段算法的输入输出可视化视图，能有效建立问题解决的全局认知框架。实践中，我们常发现下游阶段（特别是"高密度布线阶段"）的优化瓶颈，实则可通过提升前置阶段的输出质量实现突破性进展。

lohuiuwvals64060630933.jpg

构建子算法时，开发者常倾向于将算法抽象至最简形态（例如采用以(0,0)为中心的归一化处理）。但此类坐标变换存在致命风险：可能导致早期算法阶段产生的误差效应难以快速传导至后续阶段进行观测。解决方案其实很简单：在整个算法生命周期内保持坐标系绝对一致。下图展示了我们各阶段算法的串行处理流程：我们常通过深入分析该视图，精准定位引发设计规则检查(DRC)失败的罪魁祸首所在阶段。10. 为迭代过程注入动画洞察，找出愚蠢行为
还记得降低迭代次数至关重要吗？
通过动画呈现算法迭代过程，您将直观感知算法在无关路径上的无效探索。这种帧级可视化能极大提升对迭代浪费的认知效率。该方法在调节贪心乘数时（详见第12点）尤其有效。
这段动画实景演示了一条简单走线失败的案例：算法未及时终止，反而持续向外围无意义扩张。若无动画辅助，此类异常行为将极难被察觉！
11. 交集的数学计算很快，真的需要使用网格吗？
判断走线A与走线B是否交叠存在两种技术路径：
方案一：逐段解析A/B走线几何特征，执行向量交集检测算法
方案二：构建二值化网格标注走线B位置，遍历走线A覆盖网格单元进行存在性检测

hqzhgujhcku64060631033.png

难以置信的是，多数工程师会选择方案二，即便其性能差距可达千倍！究其根源，竟是数学运算太难了??
幸而现代大语言模型使向量交集计算易如反掌。请务必采用高速向量运算方案！须知：检测单个网格单元（涉及内存访问！）的实际耗时可能超过执行点积运算完成两线段交叠判断的完整计算过程！
12. 量化各阶段空间失败概率：可解性优先原则
在解决空间分区问题时，可通过先导指标量化每个处理阶段的失败概率。以 Unravel 自动布线器为例，我们在核心管线阶段实时追踪每个容量节点（Capacity Node）的失败概率分布。各阶段算法通过重构相邻节点或优化布线路径，持续降低下游阶段的失败风险。
选择失败概率作为核心指标的优势在于：该指标可量化测量并随算法改进持续优化。通过逐阶段最小化未来失败概率，形成自适应的优化链路。
相较于堆砌过多约束条件，优先保障布线可解性更具战略价值。当获得可行解后，基于现有方案迭代优化往往比从零构建最优解更高效。
13. 贪婪乘数（Greedy Multiplier）：以最优性换取百倍 A* 性能的秘技严格来说这并非机密，或许该称为"公开的秘密"。但若您尚未掌握此技，则说明尚未发挥 A* 算法的真正威力！默认配置下，A* 算法保证提供最优解。但若您更追求极速求解而非绝对最优呢？只需对评估函数f(n)做微调，即可获得加权 A* 变体。这种贪婪型优化策略可将求解速度提升数个数量级！
标准A*：f(n) = g(n) + h(n)加权A*：f(n) = g(n) + w * h(n)
游戏开发者与自动布线工程师面临诸多共性难题，因此查阅游戏开发领域的技术论文不失为寻找解决方案的捷径！

ooztda3i3ae64060631133.jpg

原文转载自https://blog.autorouting.com/p/13-things-i-would-have-told-myself，已经过翻译及校对

注意：如果想第一时间收到 KiCad 内容推送，请点击下方的名片，按关注，再设为星标。
常用合集汇总：

和 Dr Peter 一起学 KiCad
KiCad 8 探秘合集
KiCad 使用经验分享KiCad 设计项目（Made with KiCad）常见问题与解决方法KiCad 开发笔记插件应用
发布记录