# 算法驱动的迷宫探险游戏开发

## 设计目标

***\*地图：\****

一个二维矩阵，采⽤分治法⽣成，⽆孤⽴区域，存在唯⼀通路。 

输⼊：迷宫尺⼨ 。 

输出：迷宫矩阵（可存储为JSON或CSV），包括起点Start（S）、 终点Exit（E）、墙壁（#）、通路（空格）、资源（例如⾦币G）、 陷阱Trap（T）、机关Locker（L）、BOSS（B）。

 

墙壁：不可通过，无value的节点

通路：可通过，无value的节点

金币：可通过，有value 的节点。BOSS战时的行动需要消耗金币

陷阱：可通过，但经过时会扣除玩家的金币 

机关：三位密码锁。一般分布在某条路的尽头，必须开启所有机关后，终点大门才会打开

BOSS：在必经之路上，有value(血量) , 必须打败才能继续前进

 

 

***\*玩家：\****

有三种攻击方式（初始充能为0）：

A：消耗2枚金币造成1点伤害并获得1点充能

E：消耗3枚金币造成3点伤害并获得1点充能，连续第三次使用E技能时少消耗1枚金币

Q：消耗3枚金币和3点充能，造成8点伤害



## 任务分解

### 1. 分治法生成迷宫

**需求 : ** 

输入 : 正整数 n( 100>=n>=7 ) , 生成类型选择(json或者csv)

输出 : json文件 , csv文件 , 表示地图 , 无孤立区 , 存在唯一通路

S : 起点

E : 终点

\# :墙壁

blank : 通路

G : 资源

T : 陷阱

L : 机关

B : Boss

**递归分割法生成迷宫**







### 2.  动态规划进行资源收集路径规划





### 3. 贪心算法设计实时资源拾取策略





### 4. 回溯法解迷关卡





### 5. 分支限界设计boss战