TypeScript中如何定义支持流程图节点连线正交路由的优先级队列算法类型

做流程图或者白板类产品时，连线的自动布线是个绕不开的功能。用户从节点A拖一条线到节点B，系统要生成一段不穿节点的正交折线路径，这就需要正交路由算法。而在实现这类算法时，优先级队列几乎是必用的数据结构。TypeScript环境下，如果类型定义不够严谨，路由逻辑很容易出现隐匿的bug，比如方向类型写错、拐点成本计算遗漏等。本文围绕如何在TypeScript中定义一套支持正交路由的优先级队列类型体系展开，给出可以直接落地的代码。

一、先理清正交路由的类型模型

正交路由是指路径只允许水平走和垂直走，每一步都是90度的转角。主流做法是把画布离散成网格，在网格上跑A星或者跳点搜索。所以在写优先级队列之前，得先把几个基础类型定下来：网格坐标、移动方向、路由节点以及锚点。

坐标用{x: number, y: number}表示，方向是一个四值联合类型。这里强烈建议用字面量联合而不是枚举，因为字面量联合在泛型推导和可辨识联合场景下表现更好，配合switch还能获得完备性检查。方向类型定义如下：

// 网格坐标
export interface GridPoint {
  x: number;
  y: number;
}

// 四个移动方向，用字面量联合类型约束
export type Direction = "up" | "down" | "left" | "right";

// 方向到坐标增量的映射，类型安全地绑定方向与位移
export const DIR_VECTORS: Readonly<Record<Direction, GridPoint>> = {
  up: { x: 0, y: -1 },
  down: { x: 0, y: 1 },
  left: { x: -1, y: 0 },
  right: { x: 1, y: 0 },
};

// 流程图上的业务节点，路由时视为障碍物
export interface FlowNode {
  id: string;
  x: number;
  y: number;
  width: number;
  height: number;
}

接下来是搜索状态。正交路由和普通网格寻路最大的区别在于：拐弯本身是有成本的。真实产品里连线拐点太多会非常难看，所以评估一个状态时，除了g值和h值，还要记录进入该格子的方向，用于判断下一步是否转弯。这就是搜索状态必须包含方向的原因。

// 路由搜索中的一个状态：格子坐标 + 进入该格子的方向
export interface SearchState {
  point: GridPoint;
  fromDirection: Direction;
}

// 带成本的状态，g 为已花费成本，h 为启发估计
export interface CostedState extends SearchState {
  g: number;
  h: number;
}

// 计算f值：总优先级
export function fOf(state: CostedState): number {
  return state.g + state.h;
}

二、泛型优先级队列的类型定义

优先级队列可以基于二叉小顶堆实现。定义成泛型类PriorityQueue<T>，通过第二个泛型参数或构造参数传入比较器，这样队列本身不关心业务上是路由状态还是别的什么。关键点在于比较器的签名要用(a: T, b: T) => number，返回负数表示a优先级更高，这与Array.prototype.sort保持一致，学习成本低。

export type Comparator<T> = (a: T, b: T) => number;

export class PriorityQueue<T> {
  private heap: T[] = [];

  constructor(private compare: Comparator<T>) {}

  get size(): number {
    return this.heap.length;
  }

  push(item: T): void {
    this.heap.push(item);
    this.siftUp(this.heap.length - 1);
  }

  pop(): T | undefined {
    if (this.heap.length === 0) return undefined;
    const top = this.heap[0];
    const last = this.heap.pop()!;
    if (this.heap.length > 0) {
      this.heap[0] = last;
      this.siftDown(0);
    }
    return top;
  }

  private siftUp(i: number): void {
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (this.compare(this.heap[i], this.heap[parent]) < 0) {
        [this.heap[i], this.heap[parent]] = [this.heap[parent], this.heap[i]];
        i = parent;
      } else break;
    }
  }

  private siftDown(i: number): void {
    const n = this.heap.length;
    while (true) {
      let smallest = i;
      const l = 2 * i + 1;
      const r = 2 * i + 2;
      if (l < n && this.compare(this.heap[l], this.heap[smallest]) < 0) smallest = l;
      if (r < n && this.compare(this.heap[r], this.heap[smallest]) < 0) smallest = r;
      if (smallest === i) break;
      [this.heap[i], this.heap[smallest]] = [this.heap[smallest], this.heap[i]];
      i = smallest;
    }
  }
}

有了这个泛型队列，路由状态的比较器就能单独定义。注意这里不能只比较f值——f值相同时，h值更小的状态通常更接近终点，先出队能让搜索更快收敛，这是A星实现里一个经典的小优化。比较器代码如下：

// 路由专用比较器：f值小者优先，f相同时h小者优先
export const routeComparator: Comparator<CostedState> = (a, b) => {
  const fa = fOf(a);
  const fb = fOf(b);
  if (fa !== fb) return fa - fb;
  return a.h - b.h;
};

三、把拐点惩罚纳入成本模型

正交路由好不好看，关键看成本函数怎么设计。假设每走一格成本是1，每次转弯额外惩罚一个值（比如2），那么g值的更新逻辑就必须依赖方向是否改变。下面给出移动成本的计算函数，用Record映射方向与数值，避免裸写魔法数字：

export const ROUTE_COSTS = {
  step: 1,      // 直行一格的成本
  turnPenalty: 2 // 转弯一次的额外成本
} as const;

export function moveCost(prevDir: Direction, nextDir: Direction): number {
  return prevDir === nextDir
    ? ROUTE_COSTS.step
    : ROUTE_COSTS.step + ROUTE_COSTS.turnPenalty;
}

// 曼哈顿距离作为启发函数，保证admissible不会高估
export function heuristic(a: GridPoint, b: GridPoint): number {
  return Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
}

值得注意的是，加入拐点惩罚后启发函数仍然是安全的。曼哈顿距离只统计步数、不统计拐弯，永远不会高估真实成本，所以A星的最优性依然成立。如果希望路径更倾向于贴着节点边缘走，还可以在成本模型里叠加“距离障碍物的间距惩罚”，做法是把网格扩展成带权地图，类型上用Map<string, number>记录每个格子的额外代价，key用`${x},${y}`序列化即可。

四、主搜索流程与锚点对齐的类型收窄

主流程里用Map<string, CostedState>作为closed集合，key同样是坐标加方向的序列化字符串。这一点很重要：同一个格子从不同方向进入，其后续成本不同，是不同的搜索状态，如果只用坐标做key会丢掉转弯信息，导致路径出现多余的拐角。

const stateKey = (p: GridPoint, d: Direction) => `${p.x},${p.y},${d}`;

export function findOrthoRoute(
  start: GridPoint,
  startDir: Direction,
  goal: GridPoint,
  blocked: Set<string>
): GridPoint[] | null {
  const open = new PriorityQueue<CostedState>(routeComparator);
  const seen = new Map<string, CostedState>();
  const parent = new Map<string, string>();

  const startState: CostedState = {
    point: start,
    fromDirection: startDir,
    g: 0,
    h: heuristic(start, goal)
  };
  open.push(startState);
  seen.set(stateKey(start, startDir), startState);

  while (open.size > 0) {
    const current = open.pop()!;
    if (current.point.x === goal.x && current.point.y === goal.y) {
      return rebuildPath(parent, current);
    }
    for (const dir of Object.keys(DIR_VECTORS) as Direction[]) {
      const vec = DIR_VECTORS[dir];
      const next: GridPoint = {
        x: current.point.x + vec.x,
        y: current.point.y + vec.y
      };
      const key = stateKey(next, dir);
      if (blocked.has(`${next.x},${next.y}`) || seen.has(key)) continue;
      const g = current.g + moveCost(current.fromDirection, dir);
      const state: CostedState = { point: next, fromDirection: dir, g, h: heuristic(next, goal) };
      seen.set(key, state);
      parent.set(key, stateKey(current.point, current.fromDirection));
      open.push(state);
    }
  }
  return null;
}

最后是锚点对齐问题。流程图连线一般从源节点的右侧出发、进入目标节点的左侧，如果两个节点的y坐标没对齐，路由前要先把起终点吸附到节点边界上，并推导初始方向。可以通过一个函数把业务节点转成边界锚点，用类型收窄保证返回值方向与坐标一致：

export interface Anchor {
  point: GridPoint;
  exitDirection: Direction;
}

export function rightAnchorOf(node: FlowNode, cellSize: number): Anchor {
  return {
    point: {
      x: Math.round((node.x + node.width) / cellSize),
      y: Math.round((node.y + node.height / 2) / cellSize)
    },
    exitDirection: "right"
  };
}

整套类型体系的核心在于：用字面量联合约束方向、用可辨识状态区分同格不同向、用泛型优先级队列解耦数据结构与比较逻辑。落地时再补上路径简化（合并共线段）和与其他连线的避让权重，就能得到一个表现相当不错的正交路由实现。

TypeScript类型定义正交路由算法优先级队列修改时间：2026-09-04 10:35:27