Things I would have told myself before building an autorouter

I’ve spent about a year working on an autorouter for tscircuit (an open-source electronics CAD kernel written in Typescript). If I could go back a year, these are the 13 things I would tell myself: An intermediate stage of our autorouting routing a keyboard. 1. Know A* like the back of your hand, use it everywhere If I was king for a day, I would rename A* to “Fundamental Algorithm”. It is truly one of the most adaptable and important algorithms for _any kind_ of search. It is simply the best foundation for any kind of informed search (not just for 2d grids!) Here’s an animated version of A* versus “breadth first search” on a 2d grid: The way A* explores nodes is a lot faster and more intuitive. The major difference between these two algorithms is BFS explores all adjacent nodes, while A* prioritizes exploring nodes that are closer to the destination. Because it considers a metric outside the graph (the distance to the destination) it’s an informed search. You are already either ... Read full article.