AlgorithmsReact NativeMobile

How do you connect point A to point B?

Electrical Panel app: how we adapted Dijkstra’s algorithm to route electrical connections around obstacles while minimizing direction changes.

Real-time routing while dragging a component

When I started thinking about how to connect two electrical nodes on the Electrical Panel canvas, the obvious answer was "just draw a straight line". But real panels don’t work that way: cables go around breakers, contactors and rails. I needed a cable that could find its own path.

The problem: a cable that thinks

The canvas can have dozens of active components, each with its own exclusion area. The cable has to leave the node in a vertical direction (based on the pin orientation), go around every obstacle, and reach the destination node from the correct direction. On top of that, cables in a real panel are orthogonal: no diagonals, no free curves. That turns the problem into a grid graph with variable costs.

Dijkstra over a dynamic grid

The solution was to build a graph from the vertices and edges formed by the coordinates of every obstacle currently on the canvas. Each electrical component contributes four lines to the "map": its four sides expanded by a clearance margin. The intersection points of those lines become graph nodes, and two nodes are connected if the segment between them is horizontal or vertical and doesn’t cross any obstacle.

typescript
// utils/routing.ts
export const BEND_PENALTY = 50; // extra cost for changing direction
export const STUB = 30;          // initial segment perpendicular to the node

function buildGraph(s1: Pt, s2: Pt, obstacles: Rect[]): GMap {
  // 1. Collect every relevant X and Y coordinate
  const xs: number[] = [];
  const ys: number[] = [];
  for (const r of obstacles) {
    xs.push(r.x, r.x + r.w);
    ys.push(r.y, r.y + r.h);
  }
  xs.push(s1.x, s2.x);
  ys.push(s1.y, s2.y);

  // 2. Add an outer margin so the cable can "exit" the canvas
  const uniqueX = [...new Set(xs)].sort((a, b) => a - b);
  const uniqueY = [...new Set(ys)].sort((a, b) => a - b);
  uniqueX.push(Math.min(...uniqueX) - GRID_MARGIN, Math.max(...uniqueX) + GRID_MARGIN);
  uniqueY.push(Math.min(...uniqueY) - GRID_MARGIN, Math.max(...uniqueY) + GRID_MARGIN);

  // 3. Only add nodes that don't fall inside an obstacle
  const g: GMap = new Map();
  for (const x of uniqueX) {
    for (const y of uniqueY) {
      const pt = { x, y };
      if (!obstacles.some(r => segHitsRect(pt, pt, r))) {
        gAdd(g, pt);
      }
    }
  }

  // 4. Connect nodes with horizontal/vertical edges free of obstacles
  const pts = Array.from(g.values()).map(n => n.data);
  for (const p1 of pts) {
    for (const p2 of pts) {
      if (p1 === p2) continue;
      if ((p1.y === p2.y || p1.x === p2.x)
          && !obstacles.some(r => segHitsRect(p1, p2, r))) {
        const dist = Math.hypot(p2.x - p1.x, p2.y - p1.y);
        gConnect(g, p1, p2, dist);
      }
    }
  }
  return g;
}

The trick: penalizing direction changes

Standard Dijkstra minimizes total distance. But on an electrical panel, a cable with lots of bends is undesirable both visually and in real life. I added an extra cost every time the partial optimal path changes direction (from horizontal to vertical or vice versa). With that, the algorithm prefers "clean" paths with few turns, even if they’re a few pixels longer.

typescript
// The relaxation function compares the direction of the previous
// segment with the one being evaluated. If they differ, it adds BEND_PENALTY.
function gRelax(g: GMap, target: GNode, w: number, src: GNode): void {
  const prevDir = gInferDir(g, src);   // 'h' | 'v' | null
  const curDir  = gDir(src, target);   // 'h' | 'v' | null
  const penalty = prevDir && curDir && prevDir !== curDir
    ? BEND_PENALTY
    : 0;

  const totalCost = src.distance + w + penalty;
  if (totalCost < target.distance) {
    target.distance = totalCost;
    target.shortestPath = [...src.shortestPath, src.key];
  }
}

From the graph to a Skia path

Once Dijkstra returns the list of waypoints, I run them through a function that generates a SkPath with rounded corners using quadTo. That gives the visual look of well-finished cables without needing extra libraries. The resulting path is passed as a Reanimated SharedValue so it recalculates on the UI thread while the user drags a component, without blocking the JS thread.

  • —The graph is rebuilt on every drag from the canvas’s current obstacles.
  • —Components currently being dragged are temporarily excluded so they don’t block their own cable.
  • —For Bézier-mode connections, the algorithm is replaced by a simpler, faster cubic Bézier.
  • —Freehand connections (drawn with a finger) are smoothed with Ramer-Douglas-Peucker + Chaikin before saving.

The result is a system that feels "magical" to the user: you tap two nodes and the cable finds its own way through every component on the panel. That kind of detail is what separates a professional tool from a plain diagram editor.

← Back to blog