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

Question

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

Answer 1

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

它还取决于地图的多少将包含有用的信息（通行证或对象）。

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

然而，如果迷宫不是一个矩形，或者如果一个大迷宫中的大多数单元实际上不包含任何有用的内容（例如不可通过的块），那么一个好的数据结构就是一个图。

Every vertex of the graph is a cell that's passable. Edges represent the pairs of cells which you can move between (you can make it a directed graph if some doors are one-way only). Every vertex/cell is an object containing info on that cell (e.g. its location in the physical maze to be drawn, etc...).

The array-of-arrays structure benefit is that it's VERY easy to draw it, and fairly straight-forward to process (any move is just in/de-crement of an index). Adding/removing walls is as easy as changing data in 2 neighboring cells' array elements.

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