Manhattan routing algorithm for ReactFlow - generates orthogonal paths with obstacle avoidance
Manhattan 路由算法,用于 ReactFlow 生成正交路径,支持障碍物避让。
- A* 寻路算法 - 高效的路径搜索,支持早期终止优化
- 正交路径生成 - 生成符合 Manhattan 风格的直角路径
- 障碍物避让 - 自动绕过节点障碍物
- 四叉树优化 - 使用 QuadTree 加速空间查询
- 自适应步长 - 根据节点密度和距离自动调整网格步长
- 路径缓存 - LRU 缓存机制提升重复查询性能
- 全局网格对齐 - 确保所有路径点对齐到全局网格
- 圆角支持 - 可配置的路径转角圆角半径
- 性能监控 - 内置性能指标收集和日志
``bash`
npm install @rxflow/manhattanor
pnpm add @rxflow/manhattan
yarn add @rxflow/manhattan
`tsx
import { getManHattanPath } from '@rxflow/manhattan';
import { useReactFlow } from '@xyflow/react';
function CustomEdge({ id, sourceX, sourceY, targetX, targetY, sourcePosition, targetPosition, source, target }) {
const { getNodes } = useReactFlow();
const nodeLookup = new Map(getNodes().map(n => [n.id, n]));
const path = getManHattanPath({
sourceNodeId: source,
targetNodeId: target,
sourceX,
sourceY,
targetX,
targetY,
sourcePosition,
targetPosition,
nodeLookup,
options: {
step: 10,
borderRadius: 5,
}
});
return
}
`
生成 Manhattan 风格的 SVG 路径字符串。
#### 参数
| 参数 | 类型 | 必填 | 描述 |
|------|------|------|------|
| sourceNodeId | string | ✓ | 源节点 ID |
| targetNodeId | string | ✓ | 目标节点 ID |
| sourceX | number | ✓ | 源锚点 X 坐标 |
| sourceY | number | ✓ | 源锚点 Y 坐标 |
| targetX | number | ✓ | 目标锚点 X 坐标 |
| targetY | number | ✓ | 目标锚点 Y 坐标 |
| sourcePosition | Position | ✓ | 源锚点位置 (top/right/bottom/left) |
| targetPosition | Position | ✓ | 目标锚点位置 |
| nodeLookup | NodeLookup | ✓ | ReactFlow 节点查找 Map |
| options | ManhattanRouterOptions | - | 路由配置选项 |
#### 返回值
返回 SVG 路径字符串,可直接用于 元素。
| 选项 | 类型 | 默认值 | 描述 |
|------|------|--------|------|
| step | number | 10 | 网格步长(像素) |
| maxLoopCount | number | 2000 | 最大迭代次数 |
| precision | number | 1 | 坐标精度(小数位数) |
| borderRadius | number | 5 | 转角圆角半径 |
| extensionDistance | number | 20 | 路径延伸距离 |
| padding | number \| object | 20 | 节点边界框内边距 |
| startDirections | Direction[] | ['top', 'right', 'bottom', 'left'] | 允许的起始方向 |
| endDirections | Direction[] | ['top', 'right', 'bottom', 'left'] | 允许的结束方向 |
| excludeNodes | string[] | [] | 排除的节点 ID |
| excludeShapes | string[] | [] | 排除的节点类型 |
| adaptiveStep | AdaptiveStepConfig | - | 自适应步长配置 |
| performance | PerformanceConfig | - | 性能优化配置 |
| debug | DebugConfig | - | 调试配置 |
`typescript`
interface AdaptiveStepConfig {
enabled: boolean; // 是否启用自适应步长
minStep: number; // 最小步长 (默认: 5)
maxStep: number; // 最大步长 (默认: 50)
densityThreshold: number; // 密度阈值 (默认: 0.3)
distanceThreshold: number; // 距离阈值 (默认: 500)
}
`typescript`
interface PerformanceConfig {
enableCache: boolean; // 启用路径缓存
cacheSize: number; // 缓存大小 (默认: 100)
enableQuadTree: boolean; // 启用四叉树优化
earlyTermination: boolean; // 启用早期终止
}
`typescript`
interface DebugConfig {
enableLogging: boolean; // 启用日志
enableMetrics: boolean; // 启用性能指标
logLevel: 'error' | 'warn' | 'info' | 'debug';
}
`typescript`
const path = getManHattanPath({
// ...基本参数
options: {
excludeNodes: ['node-3', 'node-4'], // 排除特定节点
excludeShapes: ['group'], // 排除特定类型
excludeTerminals: ['source'], // 排除源/目标节点
}
});
`typescript`
const path = getManHattanPath({
// ...基本参数
options: {
performance: {
enableCache: true,
cacheSize: 200,
enableQuadTree: true,
earlyTermination: true,
},
adaptiveStep: {
enabled: true,
minStep: 5,
maxStep: 30,
}
}
});
`typescript`
const path = getManHattanPath({
// ...基本参数
options: {
debug: {
enableLogging: true,
enableMetrics: true,
logLevel: 'debug',
}
}
});
全局网格对齐工具,确保所有路径点对齐到统一网格。
`typescript
import { GlobalGrid } from '@rxflow/manhattan';
const grid = new GlobalGrid(10);
const snapped = grid.snapToGrid({ x: 15, y: 23 }); // { x: 20, y: 20 }
`
障碍物地图,用于空间查询和碰撞检测。
`typescript
import { ObstacleMap } from '@rxflow/manhattan';
const map = new ObstacleMap(options);
map.build(nodeLookup, sourceId, targetId, sourceAnchor, targetAnchor);
const accessible = map.isAccessible(point);
`
错误恢复工具,提供回退路径生成。
`typescript
import { ErrorRecovery } from '@rxflow/manhattan';
const fallback = ErrorRecovery.generateFallbackPath(start, end);
const validated = ErrorRecovery.validateAndFixConfig(config);
`
```
@rxflow/manhattan
├── getManHattanPath.ts # 主入口函数
├── geometry/ # 几何类 (Point, Rectangle)
├── obstacle/ # 障碍物处理 (ObstacleMap, QuadTree)
├── pathfinder/ # A* 寻路算法
├── options/ # 配置解析
├── svg/ # SVG 路径转换
└── utils/ # 工具函数
├── GlobalGrid.ts # 全局网格
├── AdaptiveStepCalculator.ts # 自适应步长
├── PerformanceMonitor.ts # 性能监控
├── ErrorRecovery.ts # 错误恢复
└── heuristics.ts # 启发式函数
MIT