# mapf-visualizer

**Repository Path**: futurelei/mapf-visualizer

## Basic Information

- **Project Name**: mapf-visualizer
- **Description**: 用纯js和html技术实现的MAPF多智能体路径规划器仿真工具，用于我自己的多智能体算法验证，如CBS规划器等。
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2026-06-20
- **Last Updated**: 2026-06-22

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# MAPF 多智能体路径规划可视化系统

多智能体路径规划 (MAPF) 可视化系统，支持 **CBS** / **PIBT** / **LaCAM\*** 三种规划器切换，矩形车身碰撞检测，自适应仓库布局。

## 📋 项目结构

```
mapf-visualizer/
├── index.html              # 主页面 — 可视化控制面板
├── README.md
├── css/
│   └── style.css
└── js/
    ├── robot.js            # 机器人实体 (矩形车身/朝向/体型)
    ├── astar-st.js         # 时空A* 单智能体路径规划器
    ├── cbs-planner.js      # CBS 多智能体路径规划器
    ├── pibt-planner.js     # PIBT 优先级继承回溯规划器
    ├── lacam-planner.js    # LaCAM* 多智能体路径规划器
    ├── simulator.js        # 仿真管理器
    └── visualizer.js       # Canvas 可视化引擎
```

## 🎯 规划器

| 规划器 | 算法 | 特点 | 适用场景 |
|--------|------|------|----------|
| **CBS** | Conflict-Based Search + 时空A* | 代价最优, 精确路径 | ≤15台, 有货架 |
| **PIBT** | Priority Inheritance with Backtracking | O(N) 线性时间, 极快 | 10~100+台, 开柜或宽通道 |
| **LaCAM*** | Lazy Constraints Addition Method | 多轮搜索 + 懒约束 | 10~50台, 含约束场景 |

右侧面板下拉菜单可切换规划器。

## 🔧 架构

- **图结构**: 空闲格构建邻居图, 支持 4/8 方向或自定义连接
- **距离表**: BFS 预计算每个目标到全图的实际最短步数 (绕过障碍物)
- **矩形车身**: 每个机器人随机 bodyWidth × bodyLength, 旋转中心随机
- **后处理修复**: 中心点规划完成后用等待插入修复车身碰撞

## 📐 算法参考

- **CBS** — [Conflict-Based Search for MAPF](https://www.aaai.org/ocs/index.php/AAAI/AAAI12/paper/viewFile/5062/5239) (Sharon et al., 2012) — [参考实现](https://gitee.com/zhr530629/Warehouse-Logistics-Dispatch)
- **PIBT** — [Priority Inheritance with Backtracking](https://www.ijcai.org/proceedings/2019/0542) (Okumura et al., 2019) — [参考实现](https://gitee.com/futurelei/pibt2)
- **LaCAM*** — [LaCAM: Search-Based Algorithm for Quick MAPF](https://ojs.aaai.org/index.php/AAAI/article/view/25523) (Okumura, 2023) — [参考实现 (LLLG)](https://gitee.com/futurelei/lllg)
- **时空A\*** — Spatio-Temporal A* for non-holonomic robots

## 🚀 快速开始

直接在浏览器打开 `index.html`。

1. **添加机器人** — 点击「添加」或点击网格空白处
2. **分配目标** — 点击「随机目标」或选中机器人后点击目标格
3. **选择规划器** — CBS (标准) / PIBT (快速) / LaCAM* (新)
4. **执行规划** — 点击「执行规划」
5. **播放动画** — ▶ ⏩ ⏪ ⏹

### 键盘快捷键

| 按键 | 功能 |
|------|------|
| `Space` | 播放 / 暂停 |
| `→` `←` | 步进 |
| `R` | 重置 |
| `P` | 执行规划 |

## ⚙️ 配置

- **网格尺寸**: 5~500 × 5~500
- **最大时间步**: 50~2000
- **播放速度**: 50ms~2000ms 可调
- **障碍模式**: 点「障碍」按钮后点击网格放置/移除障碍