data-structures - 表示迷宫的数据结构

Question

我正在编写一个动态迷宫游戏，其中每次迷宫的结构都会改变(有些门会关闭，有些门会打开。就像 HP4 中的 Triwazard)。谁能建议我哪种数据结构最适合代表这个？

Answer 1

迷宫会是一个矩形网格吗？还有什么？

它还取决于 map 将包含多少有用信息( channel 或对象)。

如果它是一个矩形网格并且大多数网格方块将包含一些东西，一个好的数据结构是一个二维数组(数组数组)，数组的每个元素代表 1 行，内部数组的每个元素代表该行中的 1 个单元格，这是一个包含与该单元格有关的数据的对象(可以移动到哪些相邻单元格，单元格包含什么，上面是否有字符)。

但是，如果迷宫不是矩形，或者如果大迷宫中的大多数单元格实际上不包含任何有用的内容(例如，是无法通过的块)，则良好的数据结构是图。

图的每个顶点都是一个可通过的单元格。边代表您可以在其间移动的成对单元格(如果某些门是单向的，您可以将其设为有向图)。每个顶点/单元格都是一个包含该单元格信息的对象(例如，它在要绘制的物理迷宫中的位置等...)。

数组数组结构的好处是绘制它非常容易，并且处理起来相当直接(任何移动都只是索引的/递减)。添加/移除墙壁就像更改 2 个相邻单元格数组元素中的数据一样简单。

图结构的好处是，如果迷宫 channel 非常稀疏(例如，只有 1/100 的场是 channel )，它占用的空间要少得多；它是唯一可以表示随机(例如非矩形网格)几何的结构，并且处理相当简单。
添加/移除墙壁很容易，因为它只是向图形添加一条边。