数据结构代表迷宫 [英] Data Structure to Represent a Maze

问题描述

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

解决方案

迷宫是否为矩形网格？还有另外一些吗？

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

如果它是一个矩形网格，并且大多数网格正方形将包含SOMETHING，一个很好的数据结构是一个2D数组（数组），数组的每一个元素代表1行，内部数组的每个元素表示1个单元格行，它是一个包含与该单元格相关的数据的对象（可以移动相邻单元格，单元格包含哪些元素，它上面有一个字符）。

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

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

数组结构的好处是它很容易绘制它，并且相当直接的处理（任何动作只是在一个索引的/ de-crement）。添加/删除墙壁与在两个相邻单元的数组元素中更改数据一样简单。

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

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?

解决方案

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.

这篇关于数据结构代表迷宫的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！