C/C++迷宫生成与求解系统

第2题：迷宫生成与求解系统
(北工大2024数据结构算法题)
【问题描述】
迷宫游戏是一中充满了随机性的游戏，每次进入游戏地图（迷宫）后，玩家会发现迷宫、怪物、装备等元素都不一样，绝没有重复的画面出现在玩家的眼前。适用迷宫作为必要元素的游戏里有着很多精品，比如：暗黑破坏神等，还有着很多游戏名就以迷宫作延伸，如：地牢围攻等。
在有些游戏中，其每一个迷宫都是不同的，是针对玩家随机生成，因此玩家即使在经历同一剧情，面对所生成的迷宫也是不一样的，这样就给玩家新鲜感，不会出现“把迷宫背熟”的情况。
作为游戏软件的工程师，就需要一个迷宫生成系统，能够根据游戏内容设计师的需求，通过指定配置参数（包括：地图规模，随机任务，地图类型等），能够随机生成不同种类的迷宫。这里为了简化问题，我们认为迷宫有2种：
源码联系UP主 -> https://space.bilibili.com/329101171
1、普通迷宫：一个单向入口（黄色方块），一个单向出口（绿色方块），玩家从入口进入迷宫，通过一定的方式走到出口，即能够通过迷宫，进入下一个同层迷宫，或者是最终出口。蓝色方块表示一个任务迷宫入口，类似的任务迷宫在普通迷宫里面可以有多个）。图1是普通迷宫的样例。

图1：普通迷宫
2、任务迷宫：一个出入口（双向，可出、可入，起点为绿色方块），玩家从同一个出入口进入，还需从同一个入口出来，但能够通过完成迷宫中任务获取经验（也包括一些必须完成的任务，如图2中的红色五角星），每个任务包含一定的经验值，当获取的经验值达到有一定数量（可以通过任务迷宫配置）方可从出入口退出，否则即使到了出入口仍不能够出去。需要注意的是，任务迷宫里面也可以嵌套其他任务迷宫（可通过配置文件定制）。图2是任务迷宫的一个样例。

图2 任务迷宫

【基本要求】
1、通过配置文件中的配置参数来设置迷宫的特性，包括：每个迷宫（均有唯一ID标记）各层规模（M*N，M>15，N>15）、迷宫的类型、嵌套的迷宫ID，入/出口。
2、输出整个生成的迷宫，并通过图形界面展示面对的迷宫，将角色置于初始迷宫的入口处让玩家可以开始闯关。
3、当进入下一个迷宫需切换到进入的迷宫，当退出迷宫后能够回到原来进入迷宫前的位置。
4、迷宫中通道可以随机设置触发任务（红色五角星），需要完成特定的任务才能继续闯关。
【扩展要求】
1、提供自动寻路功能（触发任务则暂停，人工进行任务处理，处理后继续自动寻路），能够避免死循环情况发生。
2、提供多层的迷宫。
3、对于学有余力的同学，可以在迷宫中嵌套普通迷宫，及该迷宫出口入口均在上一层迷宫的不同地点出现，并能够支持自动寻路。
【实现提示】
各个迷宫主要采用图数据结构表示，配合其他类型的数据结构表示每个迷宫出入口和迷宫的类型，以及内部的嵌套迷宫的出入口。
每次进入的迷宫需要进行标记。
任务可以是简单的算术题，选择题等，有余力的同学可以设计更有趣的任务。

【检查计划】
第一次检查
1．问题需求分析，系统的基本功能设计
2．数据结构设计
3．程序结构原型

第二次检查
使用自带的数据，演示程序的所有功能（代码，测试数据）

第三次检查
1．文档齐全
2．根据测试数据，运行程序；演示时适当地讲解，并且回答问题
3．扩展功能的演示
根据测试数据，运行程序；演示时适当地讲解，并且回答问题；
添加功能的现场操作；