プロローグ

ロシアの文豪ドストエフスキーの著作「死の家の記録」にはこんな話がある。

シベリアに流刑された男は、半日かけて穴を掘り、半日かけてその穴を埋めるという強制労働をひたすらやらされた。朝、自分で掘った穴を、午後、自分で埋めている。そんなふうになったら、誰だって生きる意味が見出せなくなる。何の意味もない単純作業を延々とやらされると、やがて人は精神に異常をきたし発狂する。

何の価値もない、むだな労働を延々と強制させられる。まるでカイジの地下施設。

これはえげつない...。人間なら長くは持たないだろう…。

そうだ。Pythonにやらせればいいじゃないか！

↑ 犠牲になるPythonくん（一応へび🐍のつもり。カエルではない）

そして以下のgifが地下労働施設で強制労働の様子だ...。

「穴を掘ってその穴を埋める」作業を延々に繰り返している。

健気にがんばっているPythonくんに心うたれる。がんばれー！

全体像

Pythonくんは優秀なので、ただまっすぐな穴を掘らせるのでは芸がない。迷路をつくらせよう。そして毎回同じ迷路では見てるほうも退屈なので、新しい迷路をつくらせ続けよう。

これから実装しなければならないことは２つだ。

• Pythonくんに毎回新しい迷路を掘らせる
• Pythonくんに迷路を埋めさせる

これを無限回、こちらの気が済むまでくり返してもらう。

1.Pythonくんに毎回新しい迷路を掘らせる

迷路生成のやり方はいくつかあるが、ここでは「穴掘り法」を使用する。

迷路の定義

以下の条件を満たすものを迷路とする。

• 到達できない閉じた空間が存在しない
• ループできる通路は存在しない

つまりこの図みたいにはしない。

追記(2020/05/13)：@otagaisama-1さんの指摘の通り、グラフで言うと、孤立点のない一つの木をつくって迷路にする。

それでは迷路をどうやってつくるかを見ていこう。

穴掘り法のアルゴリズム

イメージとしては深さ優先探索の要領でドンドン掘り進めて、進めなくなったら掘れるところまで戻ってまた再開する。

1. 迷路の幅と高さは奇数にする
2. 迷路は初めすべて「かべ」とする
3. 始点S(x, y), x,yは奇数を決める
4. 以下を再帰的に行う
   1. 現在の座標(x, y)を「通路」にする
   2. 4方向からランダムに選ぶ。2マス先が「かべ」ならそこまで「通路」にし、4.1に戻る
   3. どこにも進めなくなったら戻る

深さ優先探索の実装には

• スタックを使う
• 再帰関数を使う

がある。ここでは読みやすさのために再帰関数でやった。

穴掘り法の実装

穴掘り法を実行するmake_maze()。説明のため疑似コードっぽく書いている。

def make_maze(self, y, x):
    # 2マス先まで掘りすすめる
    dx = [(1, 2), (-1, -2), (0, 0), (0, 0)]  # x方向
    dy = [(0, 0), (0, 0), (1, 2), (-1, -2)]  # y方向

    # 4方向いずれに進むかランダムに優先順位をつける
    array = list(range(4))
    random.shuffle(array)

    for i in array:
        # ２マス先の座標(nx, ny)
        nx = x + dx[i][1]
        ny = y + dy[i][1]

        # 迷路の外に出ていたらダメ
        if not(0 <= ny < self.HEIGHT) or not(0 <= nx < self.WIDTH):
            continue

        # ２マス先がすでに通路になっている場合、掘るとループになってしまうのでダメ
        if self.maze[ny][nx] == "通路":  
            continue

        # 通路を掘る
        for j in range(2):
            ax = x + dx[i][j]
            ay = y + dy[i][j]
            if self.maze[ay][ax] == "カベ":
                self.maze[ay][ax] = "通路"

        # 掘った先で再帰的に呼び出す
        self.make_maze(ny, nx)  

make_maze()を呼び出して、迷路を作成するgenerate_maze()。（命名が雑..）

def generateMaze(self):
    # 最初はすべてカベ
    self.maze = [["カベ"]*self.WIDTH for _ in range(self.HEIGHT)]

    # ランダムなスタート地点から迷路を作る
    sx, sy = self.get_random_start()
    self.maze[sy][sx] = "通路"
    # 穴掘り法を実行
    self.make_maze(sy, sx)
    # プレイヤーをスタートに配置
    self.maze[sy][sx] = "プレイヤー"

これでPythonくんが良い感じに迷路を掘ってくれるようになった。

2.Pythonくんに迷路を埋めさせる

埋めさせるアルゴリズム

特に思いつかなかったので、穴を掘った順番と逆順に埋めてもらうことにした。

実装

穴掘り法をするときに掘った順番をlog_of_digに保持しておく。

def make_maze(self, y, x):
    # 省略

    for i in array:
        # 省略

        # 通路を掘る
        for j in range(2):
            ax = x + dx[i][j]
            ay = y + dy[i][j]
            if self.maze[ay][ax] == "カベ":
                self.maze[ay][ax] = "通路"
                self.log_of_dig.append((ax, ay))

        # 掘った先で再帰的に呼び出す
        self.make_maze(ny, nx)  

これを逆順にたどるだけ。

self.log_of_visit = self.log_of_dig[::-1]

これでよし。

強制労働プログラムの完成

GitHubにコードをあげた。dannyso16/Maze

ここまでで「穴を掘って埋める」順番は求められているので、あとはよしなに画面に描画してあげるだけだ。ゲームエンジンPyxelでつくった。

めんどくさい部分はMapクラスに切り分けたりしたので、気になる人はGitHubを見てほしい。

最後に

健気に労働するPythonくんを見ながら飲むコーヒーはおいしいですね（最悪）

もし借金を背負って地下施設行きが決まりそうになったら、Pythonくんにやってもらいましょう！！

おまけ

「穴掘り法」をまじめに使うと下みたいな迷路ゲームができる。

ゴールはスタートから一番遠いところに設定してみた。ミニマップがあるとそれっぽくて良い感じ。

参考

迷路生成(穴掘り法)

穴掘り法を使って迷路を作ろう(Qiita)

dannyso16/Maze：書いたプログラム