在具有三种墙的简单迷宫中走动的数据结构

Question

其实我真正的问题与迷宫没有太大关系，但可以这样描述：

想象一下，站在一个迷宫中，迷宫的墙壁沿笛卡尔网格对齐。墙是不可见的，一共有三种：

(N)没有墙，可以通过
(S) 实心墙，你运行抵着它就被挡住了。
(F) 致命的墙，运行撞到它就死了。

每次移动都是从一个单元格到相邻单元格，我想确定每次移动都发生了什么。

简单的解决方案：我像这样为我的网格使用坐标：

  1 2 3 4 5 6 7
1 +---+---+---+
2 |   |   |   |
3 +---+---+---+

我只保存坚固致命的墙壁，不保存角落。与墙的类型一起构成三倍：

(1,2,S), (1,4,S), (1,6,F), (2,1,S) ...

每次移动我都会计算墙的位置并在我的三元组中查找它。 (2,2) 到 (2,4) -> 位置 (2,3) 上有墙吗？

所以现在的问题是什么样的数据结构适合改进这个？首先，我的坐标只有一半可以是墙，所以可以在这里减少。但是 space 可能是一个小问题。更重要的是提取信息的时间复杂度：我如何才能轻松地查找此结构中的墙类型以进行特定移动，而无需像简单解决方案中那样遍历所有三元组？澄清一下：下一个动作总是从上一个动作的结尾开始。

附加信息：在我的实际问题中，迷宫最大为 3x3 个单元格，而且只有一个房间，房间内没有任何墙壁，只有围墙。我也有兴趣以 JSON 或 XML 格式以可读的方式保存迷宫，但这可能是一个不同的问题，因为它可能与原始问题的目的冲突。

Answer 1

我认为对你的迷宫有用的是某种 bi-directional multi-linked 你的单元格列表，本质上是一个链接单元格的图表，你可以在其中移动所有方向。每个你的单元格将在四个方向上有相邻的单元格，它有链接。

     UP              UP
LEFT    RIGHT<->LEFT     RIGHT
    DOWN            DOWN

这里，RIGHT和LEFT是到相邻小区的链接，分别是到小区的位置。现在，您可以通过让一个单元格对象指向另一个单元格对象并同时为每个单元格提供四面墙来轻松实现这一点，您可以将其定义为您想要的样子。这种方式允许您在迷宫中添加和删除单元格，以及使用简单的方法遍历迷宫。你如何定义你的细胞，显然是你自己的决定，但如果你想轻松地导出它们，你可以给它们每个坐标。从本质上讲，这就是我将如何构建一个 class 来为您完成此操作：

Cell
    Cell left, right, up, down //links to neighbors (can also be pointers)
    Wall leftWall, rightWall, upWall, downWall //the walls of the cell
    Coordinate coordinate //if needed

访问单元格的方法如下所示：

//go left
if leftWall is passable
    go to left //e.g. return left cell
else if leftWall is deadly
    end //or so
else
    do stuff

如果您希望坐标轻松导出单元格，您可以在创建时分配它们，具体取决于您添加它们的位置，例如假设一个单元格位于 (0,1) 并且您在右侧创建一个单元格使用一种方法 addRight 您可以将新单元格的坐标自动设置为 (0,2)，因为这些单元格是它们邻居的 "aware"，因为它们是链接的。

此外，从外部遍历一个链表也很容易，只需要一个 object/reference，这是你当前的位置，然后将其更改为你要移动到的位置。例如：

Cell currentCell = some cell
currentCell = currentCell.goLeft //checks if there is a wall to the left

如果没有墙，'currentCell' 现在将保留对起始单元格左侧单元格的引用。

Answer 2

一个非常简单的表示是一个 NxM 字节矩阵（two-dimensional 数组）。每面墙由两位表示。由于每个单元格有四面墙，因此您只需 8 位即可存储所有四面墙。

将您的墙类型定义为：

wallTypeNone = 0;
wallTypeSolid = 1;
wallTypeFatal = 2;
wallTypeInvalid = 3;  // should never see this

现在，将左墙映射到两个低位，将顶墙映射到位 2 和 3，依此类推。

leftWallType = wallType & 0x03;
topWallType = (wallType >> 2) & 0x03;
rightWallType = (wallType >> 4) & 0x03;
bottomWallType = (wallType >> 6) & 0x03;

通过为左列使用隐式左墙，为顶行使用隐式顶墙，您可以节省大约一半 space，但代码会稍微复杂一些。一个单元格然后 "owns" 只有两个墙：底部和右侧。如果你想要一个单元格的左墙，那么你查询相邻单元格的右墙。如果你想要一个单元格的顶壁，你查询上面单元格的底壁。这使您可以仅用四位存储每个单元格。所以你的数组大小为 N/2 x M。查询左墙或顶墙的速度稍慢（纳秒级），因为它需要更多的指令。但是你需要更少的内存访问来遍历整个迷宫。

在具有三种墙的简单迷宫中走动的数据结构

Data structure for walking around in a simple maze with three types of walls

maze

data-structures