Despite the recent leaps forward in other forms of computer-driven design, the reliability of PCB autorouters remains questionable; on the positive side, though, the lack of massive training data makes them plausible for a determined programmer to implement. For anyone contemplating this undertaking, [James Bowman] recommends a slightly unusual choice: use a hexagonal layout grid.
[James] built his own autorouter in his CuFlow PCB layout program. It takes a fairly straightforward approach: it represents the board as a grid of cells, and uses Lee’s algorithm to find the shortest routes between connected cells. The program initially used a square grid, but a hexagonal grid had a few advantages: in particular, each cell has six equidistant neighbors, rather than four (or eight, if you accept diagonal neighbors at a different distance), which allows denser routing. Because a hexagon more closely approximates a circle than a square, the same minimum-distance rules allow smaller cells, allowing the autorouter to pack more traces into the same space.
While we have previously seen a self-built autorouter, it’s much more common to interface with an external tool. If you start to get into high-speed PCB routing, though, building an autorouter becomes much harder.
Routers are cool but layout is the majority of the battle. If your layout is well and proper, routing takes barely any time. Otherwise routing becomes painful and you have to take every trace through a could of layers, zig-zagging through. At that point it’s worth starting anew though, and improve the layout
That said, are there tools that can do layout?
I would love an autorouter that can also optimise the position of some components.
https://github.com/DingoOz/TraceMaker does exactly this
That’s cute and all but ODB will be screwed depending on what’s reading it that can barely handle pads on a 45
The six equally spaced neighbours are what make this click for me. A square grid always feels like it has to cheat a little once diagonal routes are allowed, because those moves aren’t the same distance. Using hexagons seems like a surprisingly elegant way to get denser routing without making the underlying algorithm much more complicated.
I would love to see. A straight forward autorouter for high speed memory like DDR. it seems sort of paradoxical but that routing task has the most constrained layout requirements while also being the most repetitive AND the most time consuming.
Throw in some scripted monte carlo hyperlynx analysis to close the loop and it would be awesome
And why not an octogon?
Octagons don’t give you gapless packing.
Octagons can’t fill a plane the same way a hexagon, square, or triangle can.
Because Hexagons are clearly the bestagons!
Nice work. On his example on the blog he writes “The autorouter has joined them […] spanning the minimum number of cells.” But if the right pad went down-left instead o down-right, wouldn’t he have used one cell less?