npm package: @rxflow/manhattan
Description: Manhattan routing algorithm for ReactFlow - generates orthogonal paths with obstacle avoidance
Author: yanxianliang@outlook.com
Latest version: 0.0.4-alpha.8

# @rxflow/manhattan

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

## 特性

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

## 安装

```bash
npm install @rxflow/manhattan
# or
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 <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

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

### PerformanceConfig

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

### DebugConfig

```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',
    }
  }
});
```

## 工具类

### GlobalGrid

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

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

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

### ObstacleMap

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

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

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

### ErrorRecovery

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

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

## License

MIT