用C++写出伪LISP代码（三）

发表于 | 分类于 ，
字数统计: 1,662 字

迷。

老规矩

1
#include "mylist.h"

作业要求

设计一个迷宫游戏，给定迷宫的入口；如果存在出口，程序能够显示行走的路径，并最终到达出口，并输出“成功走出迷宫”；如果不存在出口，程序也能够显示行走的过程，并最终回退到入口，并输出“回退到入口”；

最终成果

实现思路

要是以为这个作业的难度在于走迷宫，那就大错特错了。走迷宫不要太简单，像我这样完全没接触过OI、ACM的普通学生，一般都能想到用所谓的广度优先算法解决。
实际上，这个问题困难的地方在于生成迷宫，如何生成一个有且仅有一条通路的、视觉效果还不赖的迷宫，是做这个作业最终要解决的问题。

走迷宫

既然走迷宫是很容易解决的问题，我们就先挑这个软柿子捏捏。

按意愿编程法

《SICP》提出过这么一种编程思路 —— 按意愿编程。意思是，先别管你写的程序能不能跑，假装代码中的所有函数都能正常工作，尽管实际上还没实现。这个办法能让人从细节的纠缠中脱离，从大局出发，每次专注于某个功能的实现。
当初我用Scheme来写走迷宫就采用了这样的办法，所以非常快地解决了问题。

主要函数

是该有这么一个find_way函数，功能是这样的：查看走出迷宫没有，如果没有，那就走下一步，再查看走出迷宫没有，如果没有，那就走下一步，……，直至走出迷宫。
find_shortest_way函数就是按意愿编程法的产物，因为我还没实现它，只是期望它能够帮我查找ways的所有路线中是否存在某条路线走出了迷宫。若找到了这条路线，find_way就圆满完成了任务，返回这条最短路线。
接下来的for循环，是由于我的Map函数不够完善而临时采用的遍历操作。它利用假想的next_steps函数，让ways中的每条路线都走出下一步，然后把这些“下一步”存储在poor_new_ways中。叫poor的原因是，我假想的next_steps函数直接产生上下左右四个新位置，还需要下一步的过滤操作。
过滤操作利用is_forwardable，就可以筛选出真正可以走的下一步。
最后再递归进行如上操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Way find_way(MyWayList ways) {
  auto shortest_way{find_shortest_way(ways)};
  if (!(shortest_way == EmptyCorList)) {
    return shortest_way;
  }
  else {
    auto poor_new_ways{EmptyWayList};
    for( auto old_ways = ways
        ; old_ways != EmptyWayList
        ; poor_new_ways = Append(next_steps(old_ways->head()), poor_new_ways)
        , old_ways = old_ways->tail()) {}
    return find_way(Filter([this](Way way) { return is_forwardable(way->head()); },
                    poor_new_ways));    
  }
}

下面再去实现上面所需要的子函数。

下一步

生成某条路线的所有可能的下一步。first、second分别代表坐标x、y。C函数用于构造坐标。

1
2
3
4
5
6
7
8
9
10
MyWayList next_steps(Way way) {
  auto last_pstion{way->head()};
  auto d{Cons(C(last_pstion->first + 1, last_pstion->second), way)};
  auto u{Cons(C(last_pstion->first - 1, last_pstion->second), way)};
  auto l{Cons(C(last_pstion->first, last_pstion->second - 1), way)};
  auto r{Cons(C(last_pstion->first, last_pstion->second + 1), way)};
  return toList({ d, u, l, r });
}

可达与否

下一步不可达的情况是：走出了边界范围、撞了墙、走了别的路线走过的位置。
需要特别提出的是：走了别的路线走过的位置。感觉这是一种挺精巧的想法：既然你慢了一步，不是第一条走这个位置的路线，你就已经失去了成为最短路线的可能，淘汰吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool is_forwardable(CorP step) {
  auto not_out_of_bound = [=]() -> bool {
    auto x_{step->first};
    auto y_{step->second};
    return (x_ < xbound) && (y_ < ybound) && (x_ >= 0) && (y_ >= 0);
  };
  auto not_wall = [=]() -> bool {
    return step != wall; // 伪代码，取决于具体实现
  };
  auto not_been = [=]() -> bool {
    return step != been; // 伪代码，取决于具体实现
  };
  return not_out_of_bound() && not_wall() && not_been();
}

到达终点与否

1
2
3
4
5
6
7
8
9
10
Way find_shortest_way(MyWayList ways) {
  auto is_reached = [=](Way way) -> bool {
    auto step = way->head();
    return (step->first == destination->first &&
      step->second == destination->second);
  };
  auto reachs{Filter(is_reached, ways)};
  return (reachs == EmptyWayList) ? EmptyCorList : reachs->head();
}

到此，走迷宫的代码已经完成。马上迎来重头戏：生成迷宫。

生成迷宫

思路

首先看到这样一个有望成为迷宫的胚子：

我们需要做的是，把某些墙推倒，解放每个格子(cell)。离散数学中的最小生成树算法就派上了用场。
把每个格子都当成一个结点，让所有格子连成一棵树。树的每两个结点，都必定只有一条最短路径可达。这样恰好就是一个迷宫。
既然是最小生成树，那么每个结点的权重是多少？这里假设每个格子的东南西北四个方向邻接的格子权重相同，与其他格子的距离无限大。并采用随机挑选的办法来处理权重相同的结点。

Prim 算法

Prim算法是比较简单的最小生成树算法。我把这种思路整理成了如下的伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
未连通::Set <- All
已连通::Set <- []
待连通::Set <- []
a <- 未连通.RandomGet()
已连通.Add(a)
未连通.Remove(a)
b[] <- Filter(a.Around, 未连通)
待连通.Add(b[])
未连通.Remove(b[])
while (not 待连通.EMPTY)
{
    c <- 待连通.RandomGet()
    d[] <- Filter(c.Around, 已连通)
    e <- d[].RandomGet()
    Connect(c, e)
    待连通.Remove(c)
    已连通.Add(c)
    
    f[] <- Filter(c.Around, 未连通)
    待连通.Add(f[])
    未连通.Remove(f[])
}

首先明确，任何已连通的格子周围的格子都是待连通的格子。于是算法可以总结成：最开始先随机找到一个格子，加入已连通的集合。再从待连通集合里随机挑选一个格子，推倒它与已连通集合中随机挑选出的它周围的格子之间的墙。重复前过程直至待连通集合再无格子。
参考链接: http://weblog.jamisbuck.org/2011/1/10/maze-generation-prim-s-algorithm

观察我的C++代码，基本与上述的伪代码一一对应：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
CorSet un;
for (int y = 0; y < height; y++) {
  for (int x = 0; x < width; x++) {
    un.insert( Cor(x, y) );
  }
}
CorSet ed;
CorSet ing;
Cor a = *(std::next(un.begin(), rand_int(0, un.size())));
ed.insert(a);
un.erase(a);
auto b{filterAround(a, un)};
for ( const auto& x : *b ) { 
  ing.insert(x);
  un.erase(x);
}
while (!ing.empty()) {
  Cor c = *(std::next(ing.begin(), rand_int(0, ing.size())));
  auto d =  filterAround(c, ed);
  Cor e = d->at(rand_int(0, d->size()));
  pullDown(c, e);
  ing.erase(c);
  ed.insert(c);
  auto f{filterAround(c, un)};
  for ( const auto& x : *f ) { 
    ing.insert(x);
    un.erase(x);
  }
}

最后就会得到一个长这样的迷宫：

寒假作业终于告一段落，要开始写周末作业了……
完整代码：https://github.com/zhongzc/C-/blob/master/maze.cpp