代表迷宫的数据结构

Question

我正在写一个充满活力的迷宫游戏，每次迷宫的结构都会改变（有些门会关闭，有些门会打开。类似于HP4中的Triwazard）。谁能建议我最适合代表哪种数据结构？

Answer 1

迷宫会是矩形网格吗？还有其他吗？

这也取决于地图中的多少包含有用的信息（通过或对象）。

如果它是矩形网格，并且大多数网格正方形将包含某些内容，则良好的数据结构是2D数组（数组数组），并且数组的每个元素代表1行，内部数组的每个元素代表该行中的1个单元格，这是一个包含与该单元有关的数据的对象（可以将邻居单元移至其中包含的内容，上面有一个字符）。

但是，如果迷宫不是矩形，或者大型迷宫中的大多数单元实际上并不包含任何有用的（例如，不可用的块），则良好的数据结构是图形。

图的每个顶点都是可通过的单元格。边缘表示可以在它们之间移动的单元对对（如果某些门仅是单向的，则可以使其成为有向图）。每个顶点/单元格是一个包含该单元格的信息的对象（例如其在物理迷宫中要绘制的位置，等等）。

阵列结构的好处是，绘制它非常容易，并且对处理相当直（任何动作都在索引的/删除中）。添加/拆卸墙与在2个相邻单元格的阵列元素中更改数据一样容易。

图结构的好处是，如果迷宫通行证非常稀疏，则占用的空间要少得多（例如，仅1/100段是通行证）；这是唯一可以代表随机（例如非矩形网格）几何形状的结构，并且处理相当简单。添加/卸下墙壁很容易，因为它只是在图表中添加边缘。