地下施設での強制労働をPythonにやらせる

# プロローグ

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

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

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

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

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

![image-20200509212352284.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/305855/3f80a250-e461-998e-2ee2-1ece50677cfe.png)
↑  犠牲になるPythonくん（一応へび🐍のつもり。カエルではない）
<br>

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

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

![python_dig_and_fill.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/305855/f10bddfa-a9d2-1bfd-d3c3-1e63f9a6095d.gif)

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



# 全体像

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

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

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

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

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

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

## 迷路の定義

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

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

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

![maze_description.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/305855/5490e1fa-0d35-c6d8-8381-c7f9bb9546e0.png)

追記(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()`。説明のため疑似コードっぽく書いている。

```python
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)  
```

<br>

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

```python
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くんが良い感じに迷路を掘ってくれるようになった。

![掘る.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/305855/d1b0a4af-fe37-82df-1ae6-6b21eb702e3f.gif)



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

## 埋めさせるアルゴリズム

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



## 実装

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

```python
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)  
```

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

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

![埋める.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/305855/92078ae9-738b-7b2f-ff11-6b539b61acba.gif)

これでよし。


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

GitHubにコードをあげた。[dannyso16/Maze](https://github.com/dannyso16/Maze)

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

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


# 最後に

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

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


# おまけ

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

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

![demo_play.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/305855/48ca4dfd-98d8-06fd-931b-4bf3d3f0eafe.gif)


# 参考

[迷路生成(穴掘り法)](https://algoful.com/Archive/Algorithm/MazeDig)

[穴掘り法を使って迷路を作ろう(Qiita)](https://qiita.com/naru_1017/items/e4d017433372a313aeb3)

[dannyso16/Maze](https://github.com/dannyso16/Maze)：書いたプログラム