代码之家 › 专栏 › 技术社区 › daign

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

maze data-structures

0

daign · 技术社区 · 8 年前

实际上,我真正的问题与迷宫无关,但可以很好地描述为:

想象一下,站在一个迷宫中,迷宫的墙壁沿着笛卡尔网格对齐。墙不可见,有三种类型:

(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)上是否有墙?

所以现在的问题是,什么样的数据结构适合于改进这一点?首先,我的坐标只有一半是墙,所以可以在这里缩小。但空间可能是一个次要问题。更重要的是提取信息的时间复杂性:我如何能够轻松查找此结构中某个移动的墙类型,而不必像简单解决方案中那样遍历所有三元组?澄清:下一步行动总是从上一步行动结束时开始。

附加信息:在我真正的问题中,迷宫最多有3x3个单元,只有一个房间,里面没有任何墙,只有围墙。我还对以JSON或XML格式以可读的方式保存迷宫感兴趣,但这可能是另一个问题,因为它可能与原始问题的目的相冲突。

2 回复 | 直到 8 年前

1

2

MrDeal 8 年前

我认为对你的迷宫有用的是某种双向的多链接单元格列表,本质上是一个链接单元格的图表,你可以向各个方向移动。您的每个单元格都有四个方向的相邻单元格,并有链接。

     UP              UP
LEFT    RIGHT<->LEFT     RIGHT
    DOWN            DOWN

在这里 RIGHT 和 LEFT 是到相邻单元的链接,分别是到单元位置的链接。现在,您可以通过让一个单元对象指向另一个单元对象,同时为每个单元指定四面墙来轻松实现这一点,您可以按照自己的意愿对其进行定义。通过这种方式,您可以使用简单的方法在迷宫中添加和移除细胞,以及遍历迷宫。如何定义单元格显然是您自己的决定,但如果您想轻松导出单元格,可以为每个单元格指定坐标。本质上,这就是我如何构建一个类来为您实现这一点:

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),因为这些单元“知道”它们的邻居,因为它们是链接的。

此外,通过拥有一个对象/引用(即您当前的位置)并将其更改为您要移动到的对象,可以轻松地从外部遍历链表。例如:

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

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

2

1

Jim Mischel 8 年前

一个非常简单的表示是字节的NxM矩阵(二维数组)。每面墙由两个位表示。由于每个单元格都有四面墙,所以您可以将所有四面墙存储在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;

通过对左列使用隐式左墙,对顶行使用隐式顶墙,可以节省大约一半的空间,但代码复杂度很低。然后,一个单元格只“拥有”两堵墙:底部和右侧。如果需要单元格的左墙,则可以查询相邻单元格的右墙。如果想要单元格的顶墙,可以查询上面单元格的底墙。这允许您将每个单元格存储在四位中。因此,您的数组大小为N/2 x M。查询左侧或顶部墙的速度稍慢(大约纳秒),因为它需要更多的指令。但您需要更少的内存访问来遍历整个迷宫。