表示迷宫的数据结构
我正在编写一个动态迷宫游戏，每次迷宫的结构都会改变（有些门会关闭，有些门会打开。类似于HP4中的Triwazard）。谁能建议我哪种数据结构最适合代表这个？
I'm writing a game of Dynamic maze in which after each time the structure of maze will change (Some doors will be closed and some doors will open. Something like Triwazard in HP4). Can anyone suggest me which data structure will be best suited to represent this?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
迷宫是一个矩形网格吗？还有别的事吗？
它还取决于地图的多少部分包含有用信息（通道或物体）。
如果它是一个矩形网格并且大多数网格方块将包含一些东西，那么一个好的数据结构是一个 2D 数组（数组的数组），数组的每个元素代表 1 行，内部数组的每个元素代表该行中的 1 个单元格，这是一个包含与该单元格相关的数据的对象（可以移动到哪些相邻单元格，该单元格包含什么，上面是否有字符）。
然而，如果迷宫不是矩形，或者如果大迷宫中的大多数单元实际上不包含任何有用的内容（例如，是无法通过的块），则良好的数据结构是图。
图的每个顶点都是一个可通过的单元格。边代表可以在其之间移动的单元对（如果某些门是单向的，则可以将其设为有向图）。每个顶点/单元都是一个包含该单元信息的对象（例如，它在要绘制的物理迷宫中的位置等）。
数组数组结构的好处是它非常容易绘制，并且处理起来相当简单（任何移动都只是索引的入/减）。添加/删除墙壁就像更改 2 个相邻单元格的数组元素中的数据一样简单。
图结构的好处是，如果迷宫通道非常稀疏（例如，只有 1/100 的区域是通道），那么它占用的空间要少得多；它是唯一可以表示随机（例如非矩形网格）几何形状的结构，并且处理相当简单。
添加/删除墙很容易，因为它只是向图表添加一条边。
Will the maze be a rectangular grid? Something else?
It also depends on how much of the map will contain useful information (passes or objects).
If it's a rectangular grid and most grid squares will contain SOMETHING, a good data structure is a 2D array (array of arrays), with each element of the array representing 1 row, each element of the inner arrays representing 1 cell in that row, which is an object containing data pertaining to that cell (which neighbor cells can be moved to, what does the cell contain, is there a character on it).
However, if the maze is not a rectangle, OR if a majority of the cells in a large maze don't actually contain any useful into (e.g. are un-passable blocks), a good data structure is a graph.
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.
The graph structure benefit is that it takes up a lot less space if the maze passes are very sparse (e.g. only 1/100th of the field is passes); it's the only structure which can represent random (e.g. non-rectangular-grid) geometry, and the processing is fairly straightforward.
Adding/removing walls is easy as it's just adding an edge to a graph.