# 自动寻路小程序

**Repository Path**: webcc/aStarPathfinder

## Basic Information

- **Project Name**: 自动寻路小程序
- **Description**: a星寻路小程序
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2026-06-03
- **Last Updated**: 2026-06-03

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

<p align="center">
  <img src="迷宫.png" width="600" alt="迷宫自动寻路效果图">
</p>

<h1 align="center">A* 迷宫寻路程序</h1>

<p align="center">
  <strong>Prim 算法生成随机迷宫 · A* / BFS / Dijkstra 自动寻路 · 2D / 3D 通用寻路库</strong>
</p>

<p align="center">
  <img src="https://img.shields.io/badge/Python-3.8+-blue.svg" alt="Python">
  <img src="https://img.shields.io/badge/GUI-tkinter-green.svg" alt="tkinter">
  <img src="https://img.shields.io/badge/算法-A*-orange.svg" alt="A*">
  <img src="https://img.shields.io/badge/支持-2D_3D-purple.svg" alt="2D/3D">
</p>

---

## 功能特性

- **随机迷宫生成** — 动态 Prim 算法，支持调整尺寸
- **A\* 自动寻路** — 曼哈顿距离启发式，保证最短路径
- **多种算法** — A* / BFS / Dijkstra 可切换
- **多条路模式** — 勾选后迷宫产生环路，验证 A* 仍能找到最短路径
- **键盘控制** — 方向键手动移动角色
- **通用寻路库** — `pathfinder.py` 支持 2D / 3D，可直接迁移到任何游戏项目

## 快速开始

```bash
# 安装依赖（图片显示需要 Pillow）
pip install Pillow

# 运行
python main.py
```

## 操作说明

| 操作 | 说明 |
|:----:|------|
| ↑ ↓ ← → | 移动角色 |
| **生成新迷宫** | 随机生成迷宫 |
| **显示路径** | A* 自动寻路，绿色显示最短路径 |
| **多条路** | 迷宫产生多条路径和环路 |
| **宽/高滑块** | 调整迷宫尺寸 |

---

## 迁移到你的游戏项目

只需拷贝一个文件：

```bash
cp pathfinder.py /你的游戏项目目录/
```

### 2D 游戏寻路

```python
from pathfinder import GridMap, Pathfinder

# 1. 创建地图
grid = GridMap(10, 10)

# 2. 设置障碍
grid.set_walkable(3, 5, False)
grid.set_walkable(4, 5, False)

# 3. 寻路
path = Pathfinder.find(grid, start=(0, 0), end=(9, 9))
# 返回: [(0,0), (1,0), ..., (9,9)]  或  None(不可达)
```

### 3D 游戏寻路

```python
# 多层地图 (宽 x 高 x 层数)
grid = GridMap(10, 10, 5)

grid.set_walkable(3, 5, False, z=2)  # 第2层 (3,5) 不可通行

path = Pathfinder.find(grid, start=(0, 0, 0), end=(9, 9, 4))
```

### 切换算法

```python
# A* — 默认，启发式，速度快
path = Pathfinder.find(grid, start, end, algorithm=Pathfinder.ASTAR)

# BFS — 无权图最短路径
path = Pathfinder.find(grid, start, end, algorithm=Pathfinder.BFS)

# Dijkstra — 带权图最短路径
path = Pathfinder.find(grid, start, end, algorithm=Pathfinder.DIJKSTRA)

# 允许对角线移动
path = Pathfinder.find(grid, start, end, diagonal=True)

# 自定义代价（如地形权重）
path = Pathfinder.find(grid, start, end, cost_func=my_cost_func)
```

---

## API 参考

### GridMap

```python
GridMap(width, height)            # 2D 地图
GridMap(width, height, depth)     # 3D 地图

grid.set_walkable(x, y, bool)                 # 2D 设置
grid.set_walkable(x, y, bool, z=z)            # 3D 设置
grid.is_walkable(x, y)                        # 2D 查询
grid.is_walkable(x, y, z=z)                   # 3D 查询
grid.set_block_map_2d(block_map)              # 从 2D 数组批量导入
grid.set_block_map_3d(block_map)              # 从 3D 数组批量导入
```

### Pathfinder.find()

```python
Pathfinder.find(grid, start, end,
                algorithm=None,    # ASTAR / BFS / DIJKSTRA
                diagonal=False,    # 允许对角线
                cost_func=None)    # 自定义代价函数
```

**返回值：** 成功返回 `list[tuple]`（含起止点），失败返回 `None`

---

## 性能

| 地图大小 | A* 平均耗时 |
|:--------:|:-----------:|
| 21×15 | ~0.14ms |
| 51×41 | ~1.1ms |
| 20×20×5 (3D) | ~2ms |

---

## 项目结构

```
├── main.py            # tkinter GUI 主程序
├── maze.py            # 迷宫生成 (Prim算法) + 调用寻路库
├── pathfinder.py      # ★ 通用寻路库 — 迁移只需这一个文件
├── brick.jpg          # 墙壁纹理
├── smallHJ.png        # 玩家角色
├── out.png            # 出口标记
├── 迷宫.png            # 效果截图
├── doc/
│   └── 封装过程中set_walkable参数顺序Bug分析.md
└── README.md
```

## 致谢

基于 [Maze](https://github.com/m-iDev-0792/Maze) 项目（C++ / Qt）用 Python 重写。