Applied Math: Autorouting & Pathfinding

How computers draw circuit board traces without lines crossing — a deep dive into graph theory, the A* search algorithm, computational geometry, and optimization. Explained step by step like we're building it together.

The Big Picture: What Problem Are We Solving?

▼

Imagine you're designing a printed circuit board (PCB) — that green board inside every electronic device. You've placed all your components: resistors here, a microchip there, capacitors spread around. Now comes the hard part: you need to draw copper traces (tiny wires etched onto the board) connecting all the pins that should be electrically connected. And you have to do it so that no two traces ever touch (that would cause a short circuit!), every trace is as short and clean as possible, and all the traces fit in the tiny space between components.

This is the autorouting problem. A computer program called an autorouter solves it automatically using a beautiful combination of graph theory (to model connections), search algorithms, computational geometry, and multi-objective optimization. Let's build this step by step.

1. Graph Theory — Teaching the Computer What to Connect

▼

Connecting pins is one thing. Connecting them BEAUTIFULLY is another. A well-designed autorouter finds traces that a human engineer would be proud of. The secret? Modifying A*'s cost function g to include penalties — extra costs for undesirable choices. This transforms simple pathfinding into multi-objective optimization: we simultaneously minimize length, turns, proximity violations, and expensive vias. Each penalty is a soft constraint — a "please avoid this" rather than a "never do this."

A graph G has two parts: V (the set of vertices, pins) and E (the set of edges, connections). n = how many pins. m = how many wires needed.

The adjacency matrix A. A[i][j] = 1 means 'connect these two!' A[i][j] = 0 means 'leave them alone.' This is a symmetric matrix because connections go both ways.

Interactive Graph Builder

▼

Build your own graph! Drag nodes to reposition them. Click a node then another to create an edge. Watch the adjacency matrix update in real time — each 1 means a connection exists. Add new nodes in Add mode. This is exactly how the autorouter stores its circuit connections.

From Graph Theory to Circuit Board: The Geometric Twist

▼

In a pure graph theory problem, vertices are abstract — they have no position. But on a real circuit board, every pin has physical coordinates (x, y) in millimeters. And components take up physical space! An edge between two pins cannot be just a straight line — it might cut right through another component. This transforms the problem into geometric graph routing: finding physical paths through 2D space that avoid obstacles while satisfying the adjacency matrix.

This problem is NP-hard: finding the PERFECT solution takes an impossibly long time as the circuit grows. The formal study of computational difficulty belongs to computational complexity theory. That's why autorouters use heuristic optimization: clever shortcuts that find excellent solutions quickly, even if they are not mathematically perfect.

Five Key Building Blocks (Remember These!)

▼

Vertex (node): one pin, pad, or terminal. The little metal leg of a resistor you solder onto the board.
Edge: one required connection between two pins. The autorouter's job is to turn each edge into a real copper trace.
Adjacency matrix: a table of 0's and 1's. The computer's "shopping list" of connections. The matrix multiplication properties of this matrix are studied in linear algebra.
Geometric graph: a graph where vertices have real-world positions. Now edges are actual paths, not abstract lines.
Netlist: a text file listing all connections. Example: "R1.pin1 → U2.pin5" means "resistor 1, pin 1 connects to chip 2, pin 5."

Where You've Seen Graphs Before

▼

Where You've Seen Graphs Before

If you've ever used Google Maps, you've used graph theory! Intersections are vertices, roads are edges, and finding the fastest route is optimization on a weighted graph — exactly what the autorouter does. The Dijkstra algorithm (ancestor of A*) runs on millions of graph nodes every time you search for directions. Social networks (Facebook's friend graph), recommendation systems (Netflix's user-movie graph), and even DNA sequencing (de Bruijn graphs) all use the same mathematics.

2. Pathfinding — Finding the Best Route Between Two Pins

▼

Now the computer knows WHAT to connect. The next question is HOW. Between pin A and pin B, the board is full of obstacles (other components, existing traces). The autorouter needs to find a path that goes AROUND all obstacles while being as short as possible.

First, the continuous board is converted into a grid — like graph paper. Each tiny square is a "cell" that is either free (trace can go here) or blocked (component is here). This discretization is essential: it turns a smooth, infinite problem into a finite, computable one. The search algorithm then explores the grid cell by cell, using a priority queue to decide which cell to explore next.

The Two Pathfinding Giants

▼

Lee's Algorithm: The Wave That Finds Everything

Imagine dropping a pebble in a pond. The ripples spread out evenly in all directions. Lee's algorithm does exactly this on the grid. Starting from the source pin, it marks every neighboring cell with a 1. Then from all cells marked 1, it marks THEIR neighbors with a 2. Then 3, 4, 5... like a wave expanding outward. When the wave finally touches the destination cell, the number written there is exactly the shortest path length! To find the actual path, the algorithm backtracks: from the destination, jump to any neighbor with a lower number, keep going down, and you arrive at the source.

Lee's algorithm ALWAYS finds the shortest path if one exists. But it explores EVERYTHING in all directions, like filling the entire pond before finding the exit. For a big PCB with millions of grid cells, this uses way too much memory and time. It was revolutionary in 1961 but is rarely used alone today.

A* (A-Star): The Smart Explorer That Knows Where It's Going

A* (pronounced "A-star") is the algorithm that made autorouting practical. Instead of expanding equally in all directions like Lee, A* has a sense of direction. It maintains a priority queue of candidate cells to explore. Each cell gets a score: f = g + h. The cell with the lowest f score gets explored next. Because h (the heuristic) estimates how far the destination is, A* naturally expands TOWARD the destination rather than away from it. This simple idea — adding a directional hint — makes A* explore dramatically fewer cells than Lee. On a typical PCB, A* might explore 5-10% as many cells as Lee's algorithm.

A* guarantees the shortest path if the heuristic is admissible (never overestimates the true distance). The Manhattan distance is the perfect heuristic for PCB routing because traces can only move horizontally and vertically (90-degree angles). It's the same "city block" distance you'd walk in Manhattan: you can't cut diagonally through buildings, only go along streets.

The magic formula of A*. f = total estimated cost of going through this cell. g = how far we've already traveled (known for sure). h = how far we think we still have to go (an educated guess).

Manhattan distance. Count the horizontal steps plus vertical steps — that's the shortest possible path in a grid with no obstacles. Since traces can only move at 90-degree angles, this is the perfect guess.

Manhattan Distance Visualizer

▼

Drag the blue source and red target points across the grid. The grid path shows the Manhattan (taxicab) distance — moving only horizontally and vertically at 90-degree angles. The dashed line shows Euclidean (straight-line) distance for comparison. Autorouters use Manhattan because PCB traces can only route at right angles.

How A* Works — A Step-by-Step Walkthrough

▼

Let's follow A* through a simple board, like a character in a video game trying to reach treasure while avoiding walls. We maintain two collections: an open set (candidate cells, ordered by f-score using a priority queue) and a closed set (cells already fully investigated).

Step 1: Put the source cell in the open set with g=0, h=Manhattan distance to target, f=g+h.
Step 2: Pull out the open-set cell with the lowest f. If it's the target — DONE! Trace backward to reconstruct the path.
Step 3: Move this cell to the closed set. For each free neighbor: compute tentative g (current cell's g + 1), compute h (Manhattan to target), compute f = g + h. If this g is better than any previous g for this neighbor, update its scores, set its "came from" pointer to the current cell, and add it to the open set.
Step 4: Go back to Step 2. If the open set empties before reaching the target — no path exists.

The magic is in the heuristic h. Because h "points" toward the target, cells closer to the target get lower f-scores and are explored first. The frontier naturally expands toward the goal rather than in all directions like Lee's algorithm.

The golden rules for h. Admissibility: our guess must never be bigger than the real distance (no cheating!). Consistency: our guess must satisfy the triangle inequality (going through a neighbor can't be shorter than going direct). If both hold, A* finds the true shortest path.

3. Computational Geometry — So the Traces Don't Crash Into Things

▼

Finding a path on a grid is step one. But a real autorouter needs to understand where the empty space is and whether two lines cross. This is computational geometry — the math of shapes, positions, and spatial relationships. Imagine walking through a dark room full of furniture. You need to know: where are the wide-open spaces? Where are the narrow gaps? Will I bump into something? The autorouter faces the same questions. Three geometric tools, all rooted in advanced graph theory, give it spatial awareness.

Three Geometric Superpowers for Autorouting

▼

Voronoi Diagrams — Finding the Center of Every Gap

Given a set of obstacles (components on the PCB), the Voronoi diagram divides the board into regions. Every point in a region is closer to ONE particular obstacle than to any other. The really interesting part is the boundaries between regions. Points on these boundaries are exactly halfway between two obstacles — smack in the center of the available space! By routing traces along these boundaries, the autorouter automatically stays as far as possible from every component. This is like walking down the exact center of a hallway rather than brushing against the walls. It ensures maximum clearance, which is critical for high-voltage circuits and high-speed signals where noise can jump between traces that are too close.

Delaunay Triangulation — The Shortcut Network

The Delaunay triangulation is the mathematical dual of the Voronoi diagram. Instead of boundaries between regions, it draws lines connecting the centers of adjacent obstacles. The result is a network of triangles covering the board. Delaunay triangulation has a magical property: it maximizes the minimum angle of all triangles. This means no long, skinny, degenerate triangles — every triangle is as "nice" as possible. In autorouting, this triangle network serves as a highway system. Instead of searching every grid cell (millions!), the autorouter first builds the Delaunay network (thousands of edges), then runs A* on THIS reduced graph. The result: paths that are geometrically clean and found much faster.

Collision Detection — The Algebra of "Do These Lines Cross?"

Before accepting a new trace, the autorouter must verify it doesn't cross any existing trace. The mathematical test uses the 2D cross product — a tiny formula that answers one question: is point C to the left or right of the directed line from A to B? To check if two line segments intersect, compute four cross products. If the signs reveal that each segment has the other's endpoints on opposite sides, the segments cross. This test runs in constant time (O of 1) per pair of segments. For thousands of existing traces, spatial indexing data structures like R-trees reduce the checks from "compare against everything" to "compare against the few nearby segments."

The 2D cross product. Positive means C is to the LEFT of the arrow from A to B. Negative means RIGHT. Zero means C is right on the infinite line through A and B.

2D Cross Product Visualizer

▼

Drag points A, B, and C to see the cross product in action. Blue arrow = vector AB. Cyan arrow = vector AC. The yellow arc shows the angle between them. Positive = C is to the LEFT of AB. Negative = RIGHT. Zero = colinear. This single number decides intersection in autorouting.

Two line segments AB and CD cross if and only if BOTH pairs of cross products have opposite signs. This is the complete intersection test. Four cross products, two comparisons.

Segment Intersection Tester

▼

Drag the endpoints of the blue and cyan segments. The cross products are computed live for all four combinations. When the product of cross(AB,C)×cross(AB,D) is negative AND cross(CD,A)×cross(CD,B) is negative, the segments intersect! This is the exact math used to prevent trace collisions.

4. Penalty Functions — Teaching the Autorouter Good Taste

▼

Connecting pins is one thing. Connecting them BEAUTIFULLY is another. A well-designed autorouter doesn't just find any path — it finds a path that a human engineer would be proud of. How? By modifying the cost function g inside A* to include penalties — extra costs added for undesirable choices. This transforms the problem from simple pathfinding into multi-objective optimization: we're simultaneously trying to minimize length, minimize turns, maximize clearance, and minimize expensive manufacturing features called vias.

The real cost function. Every penalty P is a function that inspects the proposed move to cell n and adds extra cost if the move creates an undesirable situation. g accumulates the sum of all costs from start to current cell.

The Autorouter's Penalty Catalog (or: How to Teach a Computer Good Etiquette)

▼

Base cost = 1 per cell: just moving one step. This is the minimum. Without penalties, all paths of the same length look equally good to the algorithm.
Turn penalty = +10: applied when the trace changes direction. Straight lines are preferred! Turns create impedance discontinuities in high-frequency signals and look messy. The +10 penalty makes A* prefer one long straight segment over a zigzag pattern.
Proximity penalty = +50: applied when the trace passes within 2 cells of an unrelated component or another trace. This enforces clearance — the minimum safe distance between conductors. At high voltages, traces that are too close will spark (arcing). At high frequencies, they'll interfere (crosstalk).
Via penalty = +100: a via is a tiny drilled hole that connects a trace on the top layer to the bottom layer. Vias are expensive (they add manufacturing steps), unreliable (they can crack), and electrically problematic (they add inductance). The authorouter treats them as a last resort. Think of changing PCB layers like changing floors in a building — you really only do it when you have to.
Crossing penalty = infinity: two traces on the same layer must NEVER touch. This is not a preference — it's a hard rule. If A* tries to move into an occupied cell, the cost is so astronomically high that the algorithm simply avoids it.

The autorouter's global scorecard. L = total trace length. Alpha, beta, gamma are adjustable weights the PCB designer tunes. Crank up alpha for cleaner-looking boards. Crank up gamma for extra-safe high-voltage boards.

5. The Full Autorouting Pipeline — Six Stages From Netlist to Finished Board

▼

Now let's put everything together. A real industrial autorouter (like the ones in KiCad, Altium, or Eagle) follows a systematic pipeline of six stages. This is the same workflow whether you're designing a simple Arduino shield or a 16-layer server motherboard.

The Six-Stage Pipeline: From Schematic to Routed Board

▼

Stage 1 — Build the graph: read the netlist file, create the adjacency matrix. Now the computer has its complete "to-do list" of connections. Power and ground nets get special treatment — they'll become large copper planes (polygons) rather than thin traces because they carry high current.
Stage 2 — Sort connections by priority: route the critical signals first. Clock signals and high-speed differential pairs (like USB) go before slow signals. Short connections go before long ones (if you route the long one first, it might block the short one's ideal path). Power traces get wider widths. This ordering strategy is a heuristic — not optimal, but practically very effective.
Stage 3 — Discretize the board into a grid: overlay a grid where each cell equals the minimum trace width plus clearance. A typical cell might be 0.15mm x 0.15mm. A 100mm x 100mm board creates about 444,000 cells — that is the search space. This numerical discretization is the same technique used in weather simulation and fluid dynamics.
Stage 4 — Mark obstacles: every cell that contains part of a component, an existing trace, a mounting hole, or a keep-out zone is marked BLOCKED. The autorouter also blocks cells within the clearance distance of each obstacle (the "halo" around each component). This leaves only the truly free cells as candidates for routing.
Stage 5 — Run A* for each connection: one by one, in priority order, execute A* between each pair of pins that need connecting. After finding a path, mark its cells as BLOCKED so future traces don't cross it. If a trace can't find a path, the autorouter may do rip-up and retry: undo some previously routed traces and try again in a different order.
Stage 6 — Post-process and beautify: smooth out jagged corners (convert 90-degree stair-steps into 45-degree chamfers or arcs). Widen traces that carry high current. Add teardrops at pad connections for mechanical strength. Run a Design Rule Check (DRC) to verify everything meets specifications. Generate the final Gerber files for manufacturing.

Worked Example: A* on a Tiny Board

▼

Worked Example: A* on a Tiny Board

Imagine a tiny 5 by 5 grid. Our source pin S is at the top-left corner (row 0, column 0). Our target pin T is near the bottom-right (row 3, column 3). There are two obstacles: a capacitor at (row 2, column 1) and another at (row 1, column 2). The autorouter can only move up, down, left, or right — one cell per step. Using Manhattan distance for the h-guess.

Step 1: S enters the open bag. Its g is 0 (we haven't moved yet). Its h is 6 (Manhattan distance from (0,0) to (3,3) is 3 horizontal + 3 vertical). Its f is 0+6 = 6.

Step 2: S is the only thing in the open bag, so we pull it out and close it. Its neighbors are (1,0) going right and (0,1) going down. Both are free. Both get g=1 (one step from S), h=5 (5 steps to T), f=6. They enter the open bag.

Step 3: Both have f=6, so we pick either. Say (1,0). Close it. Its right neighbor (2,0) gets g=2, h=4, f=6. Its down neighbor (1,1) gets g=2, h=4, f=6.

Step 4-7: The frontier marches rightward along row 0, then downward, always keeping f=6. The obstacles at (2,1) and (1,2) are blocked, so A* routes around them — specifically, it goes all the way to the right edge (col 3) then straight down.

Step 8: From (3,2), the down neighbor is (3,3) — that's T! g=6, h=0 (we're here!), f=6. T enters the closed bag. We trace backward: (3,3) came from (3,2), which came from (3,1), from (3,0), from (2,0), from (1,0), from (0,0).

Result: Path = (0,0) → (1,0) → (2,0) → (3,0) → (3,1) → (3,2) → (3,3). Length = 6 steps. Only 8 cells were ever investigated. A* went straight to the goal instead of wandering all over the board — the heuristic guided it along the border, avoiding the obstacles perfectly.

From Theory to Practice: Real Autorouters in the Wild

▼

From Theory to Practice: Real Autorouters in the Wild

Every PCB design tool has an autorouter. KiCad's is open source (you can read its code). Altium's handles industrial 16-layer boards. Eagle's targets 2-layer hobbyist designs. All implement A* with penalties, plus advanced features: differential pair routing (two traces must stay exactly parallel for USB/HDMI), length matching (bus signals must arrive simultaneously — a timing optimization problem), and multi-layer rip-up and retry. The math is always A* at the core; only the cost function grows richer. And yes — the interactive demo below runs the EXACT same A* algorithm that professional autorouters use.

Interactive A* Pathfinding Demo — Try It Yourself!

▼

Click the grid to set Start (green S), Target (red T), and obstacles (gray walls). Then watch A* explore! Cyan = frontier (open set). Blue = explored (closed set). Gold = final path. Each cell shows its f(n) = g(n) + h(n) score. Try Random Maze for a challenge!

StartTargetOpen (frontier)Closed (visited)Path (f(n)=g(n)+h(n) in cells)Obstacle

Funci\u00f3n de Costo

f(n) = g(n) + h(n)

g = camino recorrido | h = Manhattan al destino

Explorando... paso 0

Interactive Circuit Autorouter — Route Your Own PCB!

▼

Click pads to select them and create connections. Place obstacles to simulate components. Then run Animate to watch Lee's algorithm (BFS wavefront) find the shortest path, or Route All to instantly route every connection — the same algorithm used by professional PCB design tools.

PadSelectedFrontier (A* open set)Target cell (h=0)Blocked