用于表示迷宫的数据结构

Question

15

我正在编写一个动态迷宫游戏，在每次游戏中，迷宫结构都会发生改变（有些门会关闭，有些门会打开，就像《哈利波特与火焰杯》中的Triwazard）。有人能建议我使用哪种数据结构最适合表示这个问题吗？

- Mahesh Gupta

2

- DVK

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- DVK · Accepted Answer

这个迷宫会是一个矩形的网格吗？还是其他形式的结构？

这也取决于地图中有多少信息（路径或对象）。

如果它是一个矩形网格，而且大多数的网格方块都包含SOMETHING，那么一个好的数据结构是一个二维数组（数组的数组），其中数组的每个元素代表一行，内部数组的每个元素代表该行中的一个单元格，它是一个包含与该单元格相关的数据的对象（可以移动到哪些邻居单元格，该单元格包含什么内容，上面是否有字符等）。

然而，如果迷宫不是矩形的，或者在一个大的迷宫中大多数单元格实际上并没有包含任何有用的信息（例如障碍物），那么一个好的数据结构是一个图。

图的每个顶点都是一个可通过的单元格。边表示可以在其之间移动的单元格对（如果某些门只能朝一个方向通行，则可以将其设置为定向图）。每个顶点/单元格都是一个包含该单元格信息的对象（例如，在要绘制的实际迷宫中的位置等）。

数组-数组结构的好处是非常容易绘制它，并且处理相对简单（任何移动只是一个索引的增量/减量）。添加/删除墙壁就像改变2个相邻单元格的数组元素中的数据一样容易。

图结构的好处是如果迷宫路径非常稀疏（例如，只有1/100的区域可以通过），则占用的空间要少得多；它是唯一能表示随机（例如非矩形网格）几何形状的结构，而且处理相对简单。添加/删除墙壁很容易，只需将边添加到图中即可。