用六边形网格改进PCB自动布线器

PCB自动布线器的可靠性一直不算理想，但相比其他需要海量训练数据的计算机辅助设计方向，它仍然是一个有决心的程序员可以尝试实现的项目。James Bowman给出的建议有些反直觉：采用六边形网格，而不是常见的方形网格。

Bowman在自研的CuFlow PCB布局程序中实现了自动布线器。它的思路比较直接：把电路板表示成由单元组成的网格，再用Lee算法寻找连通单元之间的最短路径。程序最初使用方形网格，但改用六边形网格后获得了几个优势。

为什么是六边形

六边形网格中，每个单元有六个距离相等的邻居。方形网格若只计算上下左右，邻居只有四个；若把对角线也算进去，虽然有八个邻居，但对角线距离与正交距离不同。六边形的六个方向距离一致，因此能更均匀地扩展路径，也让布线更密集。

另一个原因是几何逼近：六边形比正方形更接近圆形。在相同的最小间距规则下，六边形单元可以做得更小，于是自动布线器能在同样的板面空间里容纳更多走线。

适用边界

此前也有其他自制自动布线器项目，但更常见的做法是让PCB设计软件调用外部布线工具。若涉及高速PCB布线，自动布线器的实现难度会显著上升，因为此时需要处理的不只是连通性，还包括信号完整性等约束。

对于想自己动手写布线器的人来说，六边形网格提供了一个值得尝试的改进方向：它不改变Lee算法的基本框架，却可能让路径搜索和空间利用更高效。