@rxflow/manhattan

Manhattan 路由算法，用于 ReactFlow 生成正交路径，支持障碍物避让。

特性

• A 寻路算法* - 高效的路径搜索，支持早期终止优化
• 正交路径生成 - 生成符合 Manhattan 风格的直角路径
• 障碍物避让 - 自动绕过节点障碍物
• 四叉树优化 - 使用 QuadTree 加速空间查询
• 自适应步长 - 根据节点密度和距离自动调整网格步长
• 路径缓存 - LRU 缓存机制提升重复查询性能
• 全局网格对齐 - 确保所有路径点对齐到全局网格
• 圆角支持 - 可配置的路径转角圆角半径
• 性能监控 - 内置性能指标收集和日志

安装

npm install @rxflow/manhattan
# or
pnpm add @rxflow/manhattan
yarn add @rxflow/manhattan

基本使用

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 <path d={path} />;
}

API

getManHattanPath(params)

生成 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 路径字符串，可直接用于 <path d={...} /> 元素。

ManhattanRouterOptions

| 选项 | 类型 | 默认值 | 描述 | |------|------|--------|------| | 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 | - | 调试配置 |

AdaptiveStepConfig

interface AdaptiveStepConfig {
  enabled: boolean;        // 是否启用自适应步长
  minStep: number;         // 最小步长 (默认: 5)
  maxStep: number;         // 最大步长 (默认: 50)
  densityThreshold: number; // 密度阈值 (默认: 0.3)
  distanceThreshold: number; // 距离阈值 (默认: 500)
}

PerformanceConfig

interface PerformanceConfig {
  enableCache: boolean;      // 启用路径缓存
  cacheSize: number;         // 缓存大小 (默认: 100)
  enableQuadTree: boolean;   // 启用四叉树优化
  earlyTermination: boolean; // 启用早期终止
}

DebugConfig

interface DebugConfig {
  enableLogging: boolean;  // 启用日志
  enableMetrics: boolean;  // 启用性能指标
  logLevel: 'error' | 'warn' | 'info' | 'debug';
}

高级用法

自定义障碍物排除

const path = getManHattanPath({
  // ...基本参数
  options: {
    excludeNodes: ['node-3', 'node-4'],  // 排除特定节点
    excludeShapes: ['group'],             // 排除特定类型
    excludeTerminals: ['source'],         // 排除源/目标节点
  }
});

性能优化配置

const path = getManHattanPath({
  // ...基本参数
  options: {
    performance: {
      enableCache: true,
      cacheSize: 200,
      enableQuadTree: true,
      earlyTermination: true,
    },
    adaptiveStep: {
      enabled: true,
      minStep: 5,
      maxStep: 30,
    }
  }
});

调试模式

const path = getManHattanPath({
  // ...基本参数
  options: {
    debug: {
      enableLogging: true,
      enableMetrics: true,
      logLevel: 'debug',
    }
  }
});

工具类

GlobalGrid

全局网格对齐工具，确保所有路径点对齐到统一网格。

import { GlobalGrid } from '@rxflow/manhattan';

const grid = new GlobalGrid(10);
const snapped = grid.snapToGrid({ x: 15, y: 23 }); // { x: 20, y: 20 }

ObstacleMap

障碍物地图，用于空间查询和碰撞检测。

import { ObstacleMap } from '@rxflow/manhattan';

const map = new ObstacleMap(options);
map.build(nodeLookup, sourceId, targetId, sourceAnchor, targetAnchor);
const accessible = map.isAccessible(point);

ErrorRecovery

错误恢复工具，提供回退路径生成。

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      # 启发式函数

License

MIT