# Routing

Import these from `@grafloria/engine`.

## On their own pages

- [`PathSimplifier`](https://atloria.dev/p/grafloria-h7YM7amryF/developer/grafloria-engine-routing-pathsimplifier): PathSimplifier provides algorithms for simplifying paths
- [`RoutingOptions`](https://atloria.dev/p/grafloria-h7YM7amryF/developer/grafloria-engine-routing-routingoptions): Routing options

## Functions

### `mergeObstacles`

Merge two obstacle sources into one array, collapsing entries that are the
SAME obstacle described twice.

This exists because `RoutingEngine.route()` unions its global ObstacleMap with
the request's obstacles, and the renderer's request repeats what the engine
already registered — so a 5,000-node diagram was handing the router a
9,998-entry obstacle array, and every one of those entries was scanned on
every collision test. Deduplication is keyed on id AND geometry, so two
entries that genuinely disagree about where an obstacle is are both kept:
the effective blocked region is unchanged.

```ts
function mergeObstacles(
  a: readonly Obstacle[],
  b: readonly Obstacle[]
): Obstacle[]
```

### `serveSolver`

Serve solver requests on a port. This IS the worker's message loop — call it
inside the worker script with `self`, or in a test with a fake port.

```ts
function serveSolver(port: {
  onmessage: ((ev: { data: SolverRequest }) => void) | null;
  postMessage(msg: SolverResponse): void;
}): void
```

## Classes

### `AStarRouter`

A* Pathfinding Router

```ts
class AStarRouter
```

**Methods**

- `constructor(obstacleMap: ObstacleMap, options: AStarOptions = {})`
- `getName(): string` — Get algorithm name
- `route(start: Point, end: Point): Point[]` — Find path from start to end using A* algorithm

### `DijkstraRouter`

Dijkstra's Shortest Path Router
Guarantees shortest path but may be slower than A* for long distances

```ts
class DijkstraRouter
```

**Methods**

- `constructor(obstacleMap: ObstacleMap, options: DijkstraOptions = {})`
- `getName(): string` — Get algorithm name
- `route(start: Point, end: Point): Point[]` — Find shortest path from start to end using Dijkstra's algorithm

### `GlobalRouteSolver`

```ts
class GlobalRouteSolver
```

**Methods**

- `constructor(options: SolverOptions = {})`
- `get stats(): Readonly<SolverStats>`
- `solve(edges: SolverEdge[], obstacles: Obstacle[]): Map<string, Point[]>` — Full solve. Deterministic: edges route in id order, every pass.
- `solveIncremental( changed: Array<{ edge: SolverEdge; removed?: boolean }>, obstacles?: Obstacle[] ): Map<string, Point[]>` — Re-solve after a change: `changed` edges re-route (removed ones pass with
`removed: true`), and so does every edge whose current route touches a cell
a changed edge occupied before or after. Everything else is served as-is.

### `LiveReroutingEngine`

LiveReroutingEngine automatically updates link paths when nodes move or resize.

Features:
- Throttled rerouting for performance (60fps by default)
- Batches multiple node movements
- Can be enabled/disabled
- Configurable throttle time

```ts
class LiveReroutingEngine
```

**Methods**

- `constructor(routingEngine: RoutingEngine, diagram: DiagramModel)`
- `enable(): void` — Enable live rerouting
- `disable(): void` — Disable live rerouting
- `setThrottle(ms: number): void` — Set throttle time in milliseconds
- `rerouteAll(): void` — Manually trigger reroute of all links in the diagram
Useful for manual refresh or after bulk operations
- `destroy(): void` — Clean up event listeners

**Example**

```typescript
const liveRerouting = new LiveReroutingEngine(routingEngine, diagram);
liveRerouting.enable();

// Links will automatically update when nodes move
node.setPosition({ x: 100, y: 100 });
```

### `ManhattanRouter`

```ts
class ManhattanRouter implements IRouter
```

**Methods**

- `getName(): string` — Get algorithm name
- `route(request: RouteRequest): RoutedPath | null` — Calculate a route from start to end
Can be synchronous or asynchronous (for algorithms like ELK.js)

### `ObstacleIndex`

```ts
class ObstacleIndex
```

**Methods**

- `constructor(obstacles: readonly Obstacle[], cellSize: number = DEFAULT_CELL_SIZE)`
- `get size(): number` — How many obstacles were indexed.
- `collides(px: number, py: number, margin: number): boolean` — Does the point, expanded by `margin`, touch any obstacle?

Byte-for-byte the predicate `OrthogonalRouter.collidesWithObstacles` used to
evaluate against the whole array — inclusive bounds and all.
- `queryBox(minX: number, minY: number, maxX: number, maxY: number): Obstacle[]` — Every obstacle whose rect could overlap the axis-aligned box — the candidate
set for a segment test. Conservative (a superset); the caller runs the exact
geometry test on what comes back.
- `all(): Obstacle[]` — Every indexed obstacle (deduplicated). Escape hatch for degenerate queries.

### `ObstacleMap`

ObstacleMap manages spatial indexing of obstacles for efficient queries
Uses a simple grid-based spatial index for O(1) lookups

```ts
class ObstacleMap
```

**Methods**

- `size(): number` — Get number of obstacles in the map
- `add(obstacle: Obstacle): void` — Add an obstacle to the map
- `remove(id: string): boolean` — Remove an obstacle from the map
- `get(id: string): Obstacle | undefined` — Get an obstacle by ID
- `update(obstacle: Obstacle): void` — Update an obstacle (remove and re-add to update spatial index)
- `clear(): void` — Clear all obstacles
- `queryRegion(region: Rectangle): Obstacle[]` — Query obstacles in a rectangular region
- `queryNearPoint(point: Point, radius: number): Obstacle[]` — Query obstacles near a point within a given radius
- `queryLine(start: Point, end: Point): Obstacle[]` — Query obstacles along a line segment
- `getObstacles(): Obstacle[]` — Get all obstacles as an array
- `isPointInside(point: Point, respectMargin = false): boolean` — Check if a point is inside any obstacle
- `doesLineIntersect(start: Point, end: Point, margin = 0): boolean` — Check if a line segment intersects any obstacle

### `ObstacleMapBuilder`

ObstacleMapBuilder creates ObstacleMap from DiagramModel
Uses global bounds to account for transforms and hierarchy

```ts
class ObstacleMapBuilder
```

**Methods**

- `static fromDiagram(diagram: DiagramModel, options: ObstacleMapOptions = {}): ObstacleMap` (static) — Build obstacle map from all nodes in diagram
- `static fromDiagramExcluding( diagram: DiagramModel, excludeIds: string[], options: ObstacleMapOptions = {} ): ObstacleMap` (static) — Build obstacle map excluding specific nodes
Useful for routing where source/target nodes should not be obstacles

### `OrthogonalRouter`

OrthogonalRouter creates paths with only 90-degree angles
Supports obstacle avoidance using A* on a grid

```ts
class OrthogonalRouter implements IRouter
```

**Methods**

- `getName(): string` — Get algorithm name
- `route(request: RouteRequest): RoutedPath | null` — Calculate a route from start to end
Can be synchronous or asynchronous (for algorithms like ELK.js)
- `static deriveExitSide(from: Point, toward: Point): 'left' | 'right' | 'top' | 'bottom'` (static) — The exit side a FLOATING anchor should use, derived from where the
other endpoint is — dominant axis first, ties break horizontal (matching
the midline fallback's own axis choice, so the derived route agrees with
what the undirected route would have preferred).

### `RoutingEngine`

RoutingEngine coordinates routing operations and manages obstacles

```ts
class RoutingEngine
```

**Methods**

- `constructor()`
- `registerRouter(name: string, router: IRouter): void` — Register a custom router
- `unregisterRouter(name: string): boolean` — Unregister a router
- `getAvailableAlgorithms(): string[]` — Get list of available routing algorithms
- `setDefaultAlgorithm(algorithm: RoutingAlgorithm): void` — Set default routing algorithm
- `getDefaultAlgorithm(): RoutingAlgorithm` — Get default algorithm
- `addObstacle(obstacle: Obstacle): void` — Add a global obstacle
- `removeObstacle(id: string): boolean` — Remove a global obstacle
- `updateObstacle(obstacle: Obstacle): void` — Update an existing obstacle's position/size
More efficient than remove + add
- `getObstacles(): Obstacle[]` — All registered obstacles — the map's own array accessor, passed through.
- `getObstacleCount(): number`
- `clearObstacles(): void` — Clear all global obstacles
- `clearCache(): void` — Clear route cache
- `route(request: RouteRequest): RoutedPath | null` — Route from start to end (synchronous version)
Throws error if algorithm is async (like ELK)
Use routeAsync() for async routers
- `async routeAsync(request: RouteRequest): Promise<RoutedPath | null>` — Route from start to end (async version)
Supports both sync and async routers like ELK.js
- `getStats(): { obstacleCount: number; routerCount: number; cacheSize: number; }` — Get routing engine statistics

### `SolverHost`

The caller-side host. Pass a real Worker (or anything satisfying SolverPort)
to run remote; pass nothing to run inline on the same thread — identical
behaviour, no protocol drift, because BOTH paths speak through serveSolver.

```ts
class SolverHost
```

**Methods**

- `constructor(port?: SolverPort)`
- `solve( edges: SolverEdge[], obstacles: Obstacle[], options?: SolverOptions ): Promise<{ routes: Map<string, Point[]>; stats: SolverStats }>`
- `solveIncremental( changed: Array<{ edge: SolverEdge; removed?: boolean }>, obstacles?: Obstacle[] ): Promise<{ routes: Map<string, Point[]>; stats: SolverStats }>`

### `StraightRouter`

StraightRouter creates a direct straight line from start to end

```ts
class StraightRouter implements IRouter
```

**Methods**

- `getName(): string` — Get algorithm name
- `route(request: RouteRequest): RoutedPath | null` — Calculate a route from start to end
Can be synchronous or asynchronous (for algorithms like ELK.js)

### `VisibilityGraphRouter`

Visibility Graph Router
Optimal for environments with few obstacles and open spaces
Creates graph of obstacle corners and finds shortest geometric path

```ts
class VisibilityGraphRouter
```

**Methods**

- `constructor(obstacleMap: ObstacleMap, options: VisibilityGraphOptions = {})`
- `getName(): string` — Get algorithm name
- `route(start: Point, end: Point): Point[]` — Find shortest geometric path using visibility graph

## Interfaces

### `AStarOptions`

Configuration options for A* router

```ts
interface AStarOptions
```

**Properties**

| Name | Type | Default | Description |
| --- | --- | --- | --- |
| `heuristic?` | `AStarHeuristic` |  | Heuristic function to use (default: MANHATTAN) |
| `allowDiagonal?` | `boolean` |  | Allow diagonal movement (default: true) |
| `gridSize?` | `number` |  | Grid size for discretization (default: 5) |
| `smoothing?` | `boolean` |  | Enable path smoothing (default: true) |
| `obstacleMargin?` | `number` |  | Margin around obstacles (default: 5) |
| `maxIterations?` | `number` |  | Maximum iterations before giving up (default: 10000) |

### `DijkstraOptions`

Configuration options for Dijkstra router

```ts
interface DijkstraOptions
```

**Properties**

| Name | Type | Default | Description |
| --- | --- | --- | --- |
| `allowDiagonal?` | `boolean` |  | Allow diagonal movement (default: true) |
| `gridSize?` | `number` |  | Grid size for discretization (default: 5) |
| `smoothing?` | `boolean` |  | Enable path smoothing (default: true) |
| `obstacleMargin?` | `number` |  | Margin around obstacles (default: 5) |
| `maxIterations?` | `number` |  | Maximum iterations before giving up (default: 10000) |

### `IRouter`

Interface for routing algorithms

```ts
interface IRouter
```

**Members**

- `route(request: RouteRequest): RoutedPath | null | Promise<RoutedPath | null>` — Calculate a route from start to end
Can be synchronous or asynchronous (for algorithms like ELK.js)
- `getName(): string` — Get algorithm name

### `Obstacle`

Also has every member of `Rectangle`, listed on its own entry.

Obstacle in the routing space (usually a node)

```ts
interface Obstacle extends GeometryRectangle
```

**Properties**

| Name | Type | Default | Description |
| --- | --- | --- | --- |
| `id` | `string` |  | Unique identifier |
| `margin?` | `number` |  | Optional padding/margin around obstacle |
| `kind?` | `'node' \| 'group'` |  | Containment. Obstacles are no longer a flat set — a group obstacle knows it is one, and a node obstacle can carry its containing group, so routers can treat "inside the same container" and "collapsed group = one solid block" as first-class facts. |
| `parentId?` | `string` |  | The containing group's id, when the obstacle lives inside one. |

### `ObstacleMapOptions`

```ts
interface ObstacleMapOptions
```

**Properties**

| Name | Type | Default | Description |
| --- | --- | --- | --- |
| `margin?` | `number` |  | Margin to add around each obstacle |

### `RoutedPath`

A complete routed path

```ts
interface RoutedPath
```

**Properties**

| Name | Type | Default | Description |
| --- | --- | --- | --- |
| `points` | `RoutePoint[]` |  | Ordered points forming the path |
| `totalLength` | `number` |  | Total path length |
| `bendCount` | `number` |  | Number of bends/turns in the path |
| `cost?` | `number` |  | Optional cost of the path |
| `segments?` | `RouteSegment[]` |  | Route segments |

### `RoutePoint`

Also has every member of `Point`, listed on its own entry.

A point in the routing grid/space

```ts
interface RoutePoint extends Point
```

**Properties**

| Name | Type | Default | Description |
| --- | --- | --- | --- |
| `cost?` | `number` |  | Optional cost associated with this point |

### `RouteRequest`

Routing request

```ts
interface RouteRequest
```

**Properties**

| Name | Type | Default | Description |
| --- | --- | --- | --- |
| `start` | `Point` |  | Start point |
| `end` | `Point` |  | End point |
| `obstacles?` | `Obstacle[]` |  | Obstacles to avoid |
| `options?` | `RoutingOptions` |  | Routing options |
| `sourceDirection?` | `PortDirection` |  | Direction the source port points (for orthogonal routing) |
| `targetDirection?` | `PortDirection` |  | Direction the target port points (for orthogonal routing) |
| `obstacleIndex?` | `ObstacleIndex` |  | A prebuilt spatial index over EXACTLY `obstacles`. |

### `RouteSegment`

A segment of a route path

```ts
interface RouteSegment
```

**Properties**

| Name | Type | Default | Description |
| --- | --- | --- | --- |
| `start` | `RoutePoint` |  |  |
| `end` | `RoutePoint` |  |  |
| `length` | `number` |  | Length of the segment |
| `angle` | `number` |  | Angle in degrees |

### `SolverEdge`

```ts
interface SolverEdge
```

**Properties**

| Name | Type | Default | Description |
| --- | --- | --- | --- |
| `id` | `string` |  |  |
| `start` | `Point` |  |  |
| `end` | `Point` |  |  |
| `sourceDirection?` | `Side` |  |  |
| `targetDirection?` | `Side` |  |  |
| `jetty?` | `number` |  | per-edge jetty override; defaults to the solver's gridSize |

### `SolverOptions`

```ts
interface SolverOptions
```

**Properties**

| Name | Type | Default | Description |
| --- | --- | --- | --- |
| `gridSize?` | `number` |  |  |
| `obstacleMargin?` | `number` |  |  |
| `congestionPenalty?` | `number` |  | cost added per step through a cell occupied by K other edges: K × this |
| `crossingPenalty?` | `number` |  | cost added per step through a cell that another edge crosses PERPENDICULAR to this step |
| `passes?` | `number` |  | refinement passes over the whole edge set |
| `maxIterations?` | `number` |  | per-edge search budget (ManhattanRouter maxIterations) |
| `bendCost?` | `number` |  |  |

### `SolverPort`

The message port surface the host needs — a real Worker satisfies it.

```ts
interface SolverPort
```

**Properties**

| Name | Type | Default | Description |
| --- | --- | --- | --- |
| `onmessage` | `((ev: { data: SolverResponse }) => void) \| null` |  |  |

**Members**

- `postMessage(msg: SolverRequest): void`

### `SolverRequestIncremental`

```ts
interface SolverRequestIncremental
```

**Properties**

| Name | Type | Default | Description |
| --- | --- | --- | --- |
| `seq` | `number` |  |  |
| `kind` | `'incremental'` |  |  |
| `changed` | `Array<{ edge: SolverEdge; removed?: boolean }>` |  |  |
| `obstacles?` | `Obstacle[]` |  |  |

### `SolverRequestSolve`

```ts
interface SolverRequestSolve
```

**Properties**

| Name | Type | Default | Description |
| --- | --- | --- | --- |
| `seq` | `number` |  |  |
| `kind` | `'solve'` |  |  |
| `edges` | `SolverEdge[]` |  |  |
| `obstacles` | `Obstacle[]` |  |  |
| `options?` | `SolverOptions` |  |  |

### `SolverResponse`

```ts
interface SolverResponse
```

**Properties**

| Name | Type | Default | Description |
| --- | --- | --- | --- |
| `seq` | `number` |  |  |
| `routes` | `Array<[string, Point[]]>` |  |  |
| `stats` | `SolverStats` |  |  |

### `SolverStats`

```ts
interface SolverStats
```

**Properties**

| Name | Type | Default | Description |
| --- | --- | --- | --- |
| `edgesRouted` | `number` |  | edges routed in the last solve/solveIncremental call |
| `edgesReused` | `number` |  | edges served untouched from the previous solution |

### `VisibilityGraphOptions`

Configuration options for Visibility Graph router

```ts
interface VisibilityGraphOptions
```

**Properties**

| Name | Type | Default | Description |
| --- | --- | --- | --- |
| `obstacleMargin?` | `number` |  | Margin around obstacles (default: 1) - corners placed outside obstacle bounds |

## Types

### `CostFunction`

Cost function for path evaluation

```ts
type CostFunction = (path: RoutedPath) => number;
```

### `HeuristicFunction`

Heuristic function for pathfinding

```ts
type HeuristicFunction = (a: Point, b: Point) => number;
```

### `PortDirection`

Also has every member of `String`, listed on its own entry.

Port direction for routing algorithms that need to respect port orientation

```ts
type PortDirection = 'left' | 'right' | 'top' | 'bottom';
```

### `RoutingAlgorithm`

Also has every member of `String`, listed on its own entry.

Routing algorithm type

```ts
type RoutingAlgorithm =
  | 'straight'
  | 'orthogonal'
  | 'manhattan'
  | 'elk'
  | 'a-star'
  | 'dijkstra'
  | 'visibility-graph'
  | 'custom';
```

### `SolverRequest`

Also has every member of `SolverRequestSolve`, listed on its own entry.

```ts
type SolverRequest = SolverRequestSolve | SolverRequestIncremental;
```

## Enums

### `AStarHeuristic`

Heuristic functions for A* algorithm

```ts
enum AStarHeuristic
```

**Members**

- `MANHATTAN = 'manhattan'` — Manhattan distance (L1 norm) - best for grid-based movement
- `EUCLIDEAN = 'euclidean'` — Euclidean distance (L2 norm) - best for free movement
- `DIAGONAL = 'diagonal'` — Diagonal distance (Chebyshev/L∞ norm) - best for 8-directional movement