X the Unknown Becoming an “X'' in an equation.

认识迷宫

之前的某篇post上，我提起过我学习过了如何生成迷宫。乘今晚终于把迷宫游戏重新写了一次，来总结一下吧。

至于重新写的目的，皆因想顺便练习巩固一下学习过的设计模式的使用，不过我如今写的这个迷宫还是比较微型的，用到的不多。

来个截图先：

迷宫游戏的截图

原理

话说我第一次接触如何生成一个迷宫应该是在初中的时候，因为我记得那个时候我才在我住的地方可以买到电脑报的报摊。看守报摊的是一对老夫妻了，不知道他们现在过得可好？

回到主题。我已经记得不清楚了，好像那时候上面的方法是有一个专门的数组，然后0代表通路1代表是墙的，接下来的就真的不知道了，因为那个时候我还看不懂。完全把迷宫写在一个数组里面应该算不上生成的方法吧，只是表示的方法，因为生成迷宫的是人脑不是电脑。

勉强算得上是方法的，应该是依靠填充0和1的随机数到一个二维的数组，0代表通路1代表墙，然后再图形化出来。不过这样的算法其实很囧，生成出来的能不能叫迷宫……我不知道了。

我不懂定义什么叫迷宫，不过我玩过的迷宫，一般都是只有一条路的，从起点到终点只有唯一一条路径，当然这不是绝对的，不过这种迷宫有一个附带的好处就是，你在迷宫走过的正确路径，可以构成唯一的一幅图画。我想这样的迷宫大家应该都玩过很多的啦。

其实可以让条件更严格：迷宫中任意一点都有且只有一条通往另一点的路径。

考虑一下这样的迷宫其实是什么？任意两点之间都有通路，而且通路唯一，也就是不会构成回路——没错，那就是树。

迷宫可以用树的结构表示这一点其实可以用来解释右手规则（或者左手规则）：这所谓的规则其实只是人工地遍历树罢了，迷宫的入口是树的根，出口是树结构中的某一个结点，所以是绝对可以从入口找到出口的。

所以怎样构建迷宫其实就是怎样去构建一棵树。那么有什么方法呢？

最直接的方法就是数据结构书经常有代码例子的直接生成啦，不过我感觉这个方法其实……跟人工生成没太大区别，你觉得呢？

间接生成树的方法就是从一个图中得出，比如说遍历，或者是最小生成树。图是现成的，一个3x3的迷宫完全可以看成是一个由9个顶点构成、每两个相邻的顶点之间就存在边的无向图。然后喜欢深度遍历还是Prim算法还是其他的就是你的选择了。

知道了以上的基本原理，生成一个迷宫就不是难事了。下面的没有什么原理上的东西了，只是我实现的具体细节。

实现

以下我只是选择我觉得主要的挑选部分代码写写。更详细的代码可以在这里下载。

首先要考虑的是如何表示。根据原理，可以将迷宫考虑成由行x列个小房间构成，排列成一个矩形（不考虑三角形啊五边形等等异形状迷宫）。于是，对应的图的表示也可以简单一点，直接用一个二维数组表示。数组中的每一个元素，都包含了四边的情况：对应到生成树中，若与在这一边邻接的房间之间有通路的，则这一边是通路，否则就是一面墙。于是，可以设计一个Room类：

class Room {
public:
  Wall* walls[4];
  /* other operations */
};

Wall类代表了一面墙。也可以用其他类型定义walls这个数组，只要能区分出是不是一面墙——bool型也是可以的。至于我的实现中有个Wall类是因为……这是在设计初期的产物，后期发现了，但懒得改了。所以在我的实现中，Wall类只是简单地定义为了一个空的类：

class Wall {
};

为了实践Iterator模式我专门为二维数组写了一个Array2D类，然后再为这个类写了两个Concrete Iterator：按行的Array2DRowIterator和按列的Array2DColIterator。这样做的原因仅仅只是作为Iterator模式的实践应用，没有其他特别意义^o^。

为了储存RowxCol的一个迷宫，需要RowxCol大小的数组，每个数组中包含一个Room的实例。试想一个100x100的迷宫，那么就需要10000个Room的对象，然而这些Room对象很多都是类似的——只有4个面，最多只有16种不同的情况。没错，这里我将Room类设计成了Flyweight。这样设计的结果是，Room的实例只需要16个，而 100x100的迷宫，需要的是10000个指向这16个实例的指针。指针的大小是4bytes，Room类的大小是起码16bytes，算算空间能节省了多少？

用4个2进制位就可以刚刚好表示完这16个独立的Room实例了。所以我设计了这样的Room构造函数：

Room::Room(int wallsig = 0xF) {
  for (int i=0; i<4; i++) {
    walls[i] = 0;
    if (wallsig & (1<<i)) {
      walls[i] = SiteFactory::Factory().CreateWall();
    }
  }
}

SiteFactory是用来构建Room和Wall的类（毫无疑问Wall也是可以做成Flyweight的）：

class SiteFactory {
 protected:
 SiteFactory();
 ~SiteFactory();
 public:
  static SiteFactory& Factory();
  Room* CreateRoom(bool, bool, bool, bool);
  Room* CreateRoom(int);
  Wall* CreateWall();
 protected:
  std::map<int, Room*> roomsPool;
  Wall* wall;
};

SiteFactory是一个Abstract Factory，同时也是一个Singleton。这里的Singleton用的并非使用GoF描述的使用指针+Lazy Initialization的方法，而是把Singleton的实例定义成静态成员函数内部的静态局部变量，需要获取的时候直接返回局部变量的引用。这样的好处是，不用去担心如何销毁Singleton的实例，实例是在栈上分配的，会在作用域结束（也就是程序结束）时自动析构。只不过……我觉得引用到局部变量在概念上始终不太完美，虽然因为这同时是静态的关系而不会带来实际问题。

在表示的层次上主要的问题就是这些，下面继续考虑一下构造的层次。

经过原理上的分析，可以知道用遍历或者是生成树的方法都可以生成迷宫的树结构。其中生成树的方法是要求权值数据了，嫌麻烦的可以都赋1，或者随机赋予。这次的迷宫中，我没有用这个原理来实现生成的算法，不过给我的感觉，带权值可以较精细的控制迷宫的结构，但算法会复杂一点点。

而我使用的是遍历的方法，为了比较结果我同时实现了深度和广度遍历，使用了Strategy模式：

class BuildingStrategy {
protected:
  BuildingStrategy();
public:
  void Build(MazeContext* context) {
    int r, c;
    unvisit = context->GetRows() * context->GetCols();
    visitedTable = new Array2D<bool> (context->GetRows(), context->GetCols());
    getARandomPosition(*context, r, c);
    extendFromThePositionUntilEnd(*context, r, c);
  }
/* other primitive or non-primitive operations and data members */
};

很明显我还会派生出两个具体的Strategy，DepthConstructStrategy和WideConstructStrategy。特别列出了Build方法是因为它是一个Template Method，这个方法体现了深度遍历和广度遍历的一般步骤：建一个已访问房间的二维数组确保不会访问已经遍历的房间visitedTable)，然后挑选一个随机的位置(getARandomPosition)，最后从这个位置开始遍历直到结束(extendFromThePositionUntilEnd)。

至于如何实现这个extendFromThePositionUntilEnd，其实就是图遍历的算法，就不用我来说了，市面上随便一本数据结构的书都比我说得详细。

当然，Strategy一般可以实现成Flyweight。我也是这样做的。

如何表示以及如何构造的问题都解决了，剩下来的是如何表现。表现的方式就五花八门了，像最初我实现迷宫游戏的时候，用的是Windows GDI；现在这个则使用了Curses；想要点3D效果，弄弄OpenGL或者Direct3D也OK。因为这个原因，我想就不说关于表现的部分了。我的详细实现，可以在代码中找到。

Well……关于迷宫大概就说到这里啦。经过自己的研究学习，发现生成一个迷宫其实是很简单的事情，最核心的代码也就20行出头，倒是为了把某些可以用的上的设计模式练习一下，整个代码的规模扩大了好多倍……另外就是按广度遍历原理生成的迷宫，不知道是不是我实现得有点问题，得出来的迷宫简单得不行啊……

在这里再放一次我实现的代码的链接。

然后接下的任务啊，我想我应该学习和修炼一下自己写的代码的质量了。

或许你还会对这些文章感兴趣：

• Abstract Factory和Factory Method的区别