Routing

Import these from @grafloria/engine.

On their own pages

• PathSimplifier: PathSimplifier provides algorithms for simplifying paths
• 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
Copy
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
Copy
function serveSolver(port: {
  onmessage: ((ev: { data: SolverRequest }) => void) | null;
  postMessage(msg: SolverResponse): void;
}): void

Classes

AStarRouter

A* Pathfinding Router

ts
Copy
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
Copy
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
Copy
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
Copy
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
Copy
const liveRerouting = new LiveReroutingEngine(routingEngine, diagram);
liveRerouting.enable();

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

ManhattanRouter

ts
Copy
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
Copy
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
Copy
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
Copy
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
Copy
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
Copy
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
Copy
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
Copy
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
Copy
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
Copy
interface AStarOptions

Properties

DijkstraOptions

Configuration options for Dijkstra router

ts
Copy
interface DijkstraOptions

Properties

IRouter

Interface for routing algorithms

ts
Copy
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

Obstacle in the routing space (usually a node)

ts
Copy
interface Obstacle extends GeometryRectangle

Properties

ObstacleMapOptions

ts
Copy
interface ObstacleMapOptions

Properties

RoutedPath

A complete routed path

ts
Copy
interface RoutedPath

Properties

RoutePoint

A point in the routing grid/space

ts
Copy
interface RoutePoint extends Point

Properties

RouteRequest

Routing request

ts
Copy
interface RouteRequest

Properties

RouteSegment

A segment of a route path

ts
Copy
interface RouteSegment

Properties

SolverEdge

ts
Copy
interface SolverEdge

Properties

SolverOptions

ts
Copy
interface SolverOptions

Properties

SolverPort

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

ts
Copy
interface SolverPort

Properties

Members

• postMessage(msg: SolverRequest): void

SolverRequestIncremental

ts
Copy
interface SolverRequestIncremental

Properties

SolverRequestSolve

ts
Copy
interface SolverRequestSolve

Properties

SolverResponse

ts
Copy
interface SolverResponse

Properties

SolverStats

ts
Copy
interface SolverStats

Properties

VisibilityGraphOptions

Configuration options for Visibility Graph router

ts
Copy
interface VisibilityGraphOptions

Properties

Types

CostFunction

Cost function for path evaluation

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

HeuristicFunction

Heuristic function for pathfinding

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

PortDirection

Port direction for routing algorithms that need to respect port orientation

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

RoutingAlgorithm

Routing algorithm type

ts
Copy
type RoutingAlgorithm =
  | 'straight'
  | 'orthogonal'
  | 'manhattan'      // Wave 5 Card 3: grid router with JointJS+-parity knobs
  | 'elk'
  | 'a-star'
  | 'dijkstra'
  | 'visibility-graph'
  | 'custom';

SolverRequest

ts
Copy
type SolverRequest = SolverRequestSolve | SolverRequestIncremental;

Enums

AStarHeuristic

Heuristic functions for A* algorithm

ts
Copy
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