【Pyxel】DFSを使ってランダムにダンジョンを生成する！

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3922095/d13ac148-6f0a-45ab-ac9b-d19ff8fc33d3.png" width=500>
 
## はじめに
　PyxelでRPGなどのダンジョンを制作する際、エディタを使えば簡単に作成できます。しかし、大きなマップをたくさん用意するような場合には、流石に手書きでは厳しいですよね？そこで、手書きほどのクオリティではないにしても、「それっぽく見える」をめざしてランダム生成するコードを書きました。

## アルゴリズム
　ダンジョンの制作において良く使われる手法には、穴掘り法や壁伸ばし法などがあります。しかし、これらは迷路といった感じで、1マスの壁と1マスの床を作れる方法です。今回「それっぽく見える」を目指すにあたって、もうちょっと立体感を出したいので、これらの方法は使えません。（改良すれば良い方法があるのかもしれないけれど）

　これらを使わずに実装する上で、以下の手法を取りました
 ①マップをグリッドに分割し、全てのグリッドを壁で囲う
 ②DFS（深さ優先探索）を用いて、グリッドを全探索する。
 ③探索時に壁を空けながら進む

## DFSとは
　先にDFSの説明です。以下の木でいえば、どんどん下へと進んでいき、それより下へ行けなくなったら、上に戻って別のルートを試すという処理をします。再帰的な処理なので、再帰関数で実装することが多いようです。


<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3922095/d7d9e915-02cc-4326-aa04-f02b633e8b4e.png" width=500>

これをダンジョンの生成に当てはめると、スタート地点からランダムな方向へ進んでいき、行き止まりに当たったら戻るという処理になります。戻った先で残りの方向を見て、どこへも進めなければ、さらに一つ戻ります。これを繰り返してスタート地点まで戻ってきたら終了です。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3922095/f605b997-2d15-44cf-8d06-723f1a55d1d7.png" width=500>

## コードの解説
　先ほどあてはめたものを箇条書きにすると以下の通りです、また、DFSの手順とは関係ありませんが、最後にゴールを設定する手順を加えています。ただし、ゴールは一番遠い行き止まりとします。
- スタート地点を決定
- ランダムな方向へ進む
- 行き止まりに当たったら戻る
- 戻った先で残りの方向を見て、どこへも進めなければ、さらに一つ戻る
- スタート地点まで戻ってきたら終了
- ゴール地点を設定

一つずつ実装していきます
#### スタート地点を決定
```python
# スタート地点をランダムに選び、DFS開始
start_x, start_y = random.choice(START_POSITIONS)
goal, _ = dfs(start_x, start_y, visited, 0, None, 0)
```
`START_POSITIONS`は座標のリストで、自由に指定してください。筆者はマップの四隅にしています。
`dfs`の引数は、現在のx座標、y座標、探索済みのマップの集合、現在の深さ、ゴールの座標、ゴールの深さとなっています。

#### ランダムな方向へ進む
```python
def dfs(cx, cy, visited, depth, goal, goal_path_length):
    #上下左右を見る順番を決定
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    random.shuffle(directions)
    visited.add((cx, cy))

    for dx, dy in directions:
        nx, ny = cx + dx, cy + dy
        if 0 <= nx < GRID_SIZE and 0 <= ny < GRID_SIZE and (nx, ny) not in visited:
            # 移動方向次第で隣の部屋とつなげる
            set_room_data(cx, cy, dx, dy)
            goal, goal_path_length = dfs(nx, ny, visited, depth + 1, goal, goal_path_length)
```
まず、このタイミングで、このマスを探索済みにします（`visited`に追加）。上下左右をランダムな順番で確認し、進める方向（マップ外でないかつ探索済みでない）があれば、その方向へ進みます。ゴール地点の設定に使うので、このときに深さを+1します。

#### 行き止まりに当たったら戻る

```python
#最も遠い行き止まりをゴールに設定
if goal_path_length <= depth:
    goal_path_length = depth
    goal = (cx, cy)
    return goal, goal_path_length
```
行き止まりに当たると、for ループをすべて回しても、移動処理が発生しないので、`dfs`の残りの処理が実行されます。つまり、forのあとにこのif文を置いておくことで、行き止まりに到達したとき、現時点のゴールより遠ければ更新という処理ができます。このとき、新しく設定したゴールを返しながら、一つ前のマスに戻ります。

#### 戻った先で残りの方向を見て、どこへも進めなければ、さらに一つ戻る
戻った先ではforループの残りが回されて、以下は同じ処理の繰り返しとなります。
残りが回されるというのは以下のような感じです。
- 1ループ目：右を見る
- 2ループ目：左に進む
---
ここから再開
- 3ループ目：下を見る
- 4ループ目：上を見る→どこへも進めないので戻る

#### スタート地点まで戻ってきたら終了
　再帰関数で実装しているので、特に条件を指定しなくても、returnし続けて戻ってきてくれます。

#### ゴール地点を設定
最終的に受け取ったゴール地点の座標をみて、真ん中あたりにボスのアイコンを設置します。
```python
# ゴール地点にボスを配置
map_data[goal[1] * ROOM_SIZE + ROOM_SIZE // 2][goal[0] * ROOM_SIZE + ROOM_SIZE // 2] = 3
```

#### ダンジョン生成部分の全体像
以上の手順をすべてまとめて、最終的に以下のようになります。
```python
def dfs(cx, cy, visited, depth, goal, goal_path_length):
        #上下左右を見る順番を決定
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        random.shuffle(directions)
        visited.add((cx, cy))

        for dx, dy in directions:
            nx, ny = cx + dx, cy + dy
            if 0 <= nx < GRID_SIZE and 0 <= ny < GRID_SIZE and (nx, ny) not in visited:
                # 移動方向次第で隣の部屋とつなげる
                set_room_data(cx, cy, dx, dy)
                goal, goal_path_length = dfs(nx, ny, visited, depth + 1, goal, goal_path_length)
                
        #最も遠い行き止まりをゴールに設定
        if goal_path_length <= depth:
            goal_path_length = depth
            goal = (cx, cy)
        return goal, goal_path_length

    # マップを初期化（床で塗りつぶした後格子状に壁を設置）
    global map_data
    reset_map()
    visited = set()

    # スタート地点をランダムに選び、DFS開始
    start_x, start_y = random.choice(START_POSITIONS)
    goal, _ = dfs(start_x, start_y, visited, 0, None, 0)

    # ゴール地点にボスを配置
    map_data[goal[1] * ROOM_SIZE + ROOM_SIZE // 2][goal[0] * ROOM_SIZE + ROOM_SIZE // 2] = 3
    return map_data, (start_x * ROOM_SIZE + ROOM_SIZE // 2, start_y * ROOM_SIZE + ROOM_SIZE // 2)

```

## その他の部分について
先ほどのコード内で呼び出していた関数の内部も紹介します。
### マップ情報の初期化
いったん全てのマスを床にしてから、各グリッドの外周を壁にします。
```python
def reset_map():
    global map_data
    map_data = [[0 for _ in range(MAP_WIDTH // CELL_SIZE)] for _ in range(MAP_HEIGHT // CELL_SIZE)]
    for y in range(len(map_data)):
        for x in range(len(map_data)):
            if y % ROOM_SIZE == 0:
                map_data[y][x] = 1
            elif y % ROOM_SIZE == 1:
                map_data[y][x] = 2
            elif y % ROOM_SIZE == 2:
                map_data[y][x] = 2
            elif y % ROOM_SIZE == ROOM_SIZE - 1:
                map_data[y][x] = 1

            if x % ROOM_SIZE == 0:
                map_data[y][x] = 1
            elif x % ROOM_SIZE == ROOM_SIZE - 1:
                map_data[y][x] = 1
```

### 移動時に壁を取り払う
グリッドの座標と、移動方向を受け取って、その方向の壁をくりぬく形で隣のグリッドとつなげます。この時の処理をカスタマイズすれば、ある程度壁の形などは変更できますが、地形を凝るのは中々厳しそうです。
```python
def set_room_data(cx, cy, dx, dy):
    x, y = cx * ROOM_SIZE, cy * ROOM_SIZE
    if abs(dx):  # 左右
        if dx == 1:    #右の時
            x = x + ROOM_SIZE
        for i in range(1, ROOM_SIZE-1):
            map_data[y + i][x] = 0
            map_data[y + i][x - 1] = 0
        map_data[y + 1][x] = 2
        map_data[y + 1][x - 1] = 2
        map_data[y + 2][x] = 2
        map_data[y + 2][x - 1] = 2

    elif abs(dy):  # 上下
        if dy == 1:  # 下の時
            y = y + ROOM_SIZE
        for i in range(1, ROOM_SIZE-1):
            map_data[y - 1][x + i] = 0
            map_data[y][x + i] = 0
            map_data[y + 1][x + i] = 0
            map_data[y + 2][x + i] = 0
```

## プログラム全体
マップ全体を確認できるように、描画と視点移動も含めて書いたので、コピペ用に置いておきます。描画するにあたって、先ほどのは二次元リストに番号を詰めていっただけなので、対応するタイルの座標を`tiles`というリストにして参照させています。この部分を変えれば簡単に見た目を変更できます。`

<details><summary>コードを見る</summary>

```python
import pyxel
import random

# 初期設定
MAP_WIDTH = 512
MAP_HEIGHT = 512
CELL_SIZE = 8
GRID_SIZE = 8
ROOM_SIZE = 8
START_POSITIONS = [(0, 0), (0, GRID_SIZE - 1), (GRID_SIZE - 1, 0), (GRID_SIZE - 1, GRID_SIZE - 1)]
map_data = [[0 for _ in range(MAP_WIDTH // CELL_SIZE)] for _ in range(MAP_HEIGHT // CELL_SIZE)]

def reset_map():
    global map_data
    map_data = [[0 for _ in range(MAP_WIDTH // CELL_SIZE)] for _ in range(MAP_HEIGHT // CELL_SIZE)]
    for y in range(len(map_data)):
        for x in range(len(map_data)):
            if y % ROOM_SIZE == 0:
                map_data[y][x] = 1
            elif y % ROOM_SIZE == 1:
                map_data[y][x] = 2
            elif y % ROOM_SIZE == 2:
                map_data[y][x] = 2
            elif y % ROOM_SIZE == ROOM_SIZE - 1:
                map_data[y][x] = 1

            if x % ROOM_SIZE == 0:
                map_data[y][x] = 1
            elif x % ROOM_SIZE == ROOM_SIZE - 1:
                map_data[y][x] = 1

def set_room_data(cx, cy, dx, dy):
    x, y = cx * ROOM_SIZE, cy * ROOM_SIZE
    if abs(dx):  # 左右
        if dx == 1:    #右の時
            x = x + ROOM_SIZE
        for i in range(1, ROOM_SIZE-1):
            map_data[y + i][x] = 0
            map_data[y + i][x - 1] = 0
        map_data[y + 1][x] = 2
        map_data[y + 1][x - 1] = 2
        map_data[y + 2][x] = 2
        map_data[y + 2][x - 1] = 2

    elif abs(dy):  # 上下
        if dy == 1:  # 下の時
            y = y + ROOM_SIZE
        for i in range(1, ROOM_SIZE-1):
            map_data[y - 1][x + i] = 0
            map_data[y][x + i] = 0
            map_data[y + 1][x + i] = 0
            map_data[y + 2][x + i] = 0

def create_map():
    def dfs(cx, cy, visited, depth, goal, goal_path_length):
        #上下左右を見る順番を決定
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        random.shuffle(directions)
        visited.add((cx, cy))

        for dx, dy in directions:
            nx, ny = cx + dx, cy + dy
            if 0 <= nx < GRID_SIZE and 0 <= ny < GRID_SIZE and (nx, ny) not in visited:
                # 移動方向次第で隣の部屋とつなげる
                set_room_data(cx, cy, dx, dy)
                goal, goal_path_length = dfs(nx, ny, visited, depth + 1, goal, goal_path_length)
                
        #最も遠い行き止まりをゴールに設定
        if goal_path_length <= depth:
            goal_path_length = depth
            goal = (cx, cy)
        return goal, goal_path_length

    # マップを初期化（床で塗りつぶした後格子状に壁を設置）
    reset_map()
    visited = set()

    # スタート地点をランダムに選び、DFS開始
    start_x, start_y = random.choice(START_POSITIONS)
    goal, _ = dfs(start_x, start_y, visited, 0, None, 0)

    # ゴール地点にボスを配置
    map_data[goal[1] * ROOM_SIZE + ROOM_SIZE // 2][goal[0] * ROOM_SIZE + ROOM_SIZE // 2] = 3
    return map_data, (start_x * ROOM_SIZE + ROOM_SIZE // 2, start_y * ROOM_SIZE + ROOM_SIZE // 2)

def render_map(map_data, tiles):
    for y in range(len(map_data)):
        for x in range(len(map_data[0])):
            tile = tiles[map_data[y][x]]
            pyxel.tilemaps[0].pset(x, y, tile)

camera_x, camera_y = 0, 0
def update():
    global camera_x, camera_y
    pyxel.camera(camera_x, camera_y)
    if pyxel.btn(pyxel.KEY_LEFT):
        camera_x -= 16
    if pyxel.btn(pyxel.KEY_RIGHT):
        camera_x += 16
    if pyxel.btn(pyxel.KEY_UP):
        camera_y -= 16
    if pyxel.btn(pyxel.KEY_DOWN):
        camera_y += 16

def draw():
    pyxel.cls(0)
    pyxel.bltm(0, 0, 0, 0, 0, MAP_WIDTH, MAP_HEIGHT)

tiles = [(6, 4),    #床
         (7, 4),    #壁（天井）
         (7, 5),    #壁（側面）
         (0, 10)    #ボスアイコン
        ]

if __name__ == "__main__":
    pyxel.init(256, 256, title="Random Map Generator")
    pyxel.load("asset.pyxres")
    map_data, pos = create_map()
    render_map(map_data, tiles)
    pyxel.run(update, draw)
```

</details>

## 最後に
　ここまで読んで下さりありがとうございました。想定としては、コピペ用のコードの設定で使うことを想定していますが、32x32とかにしても使えます。一応ランダム且つ立体感のあるダンジョンは生成できたのですが、もう少し地形っぽさとか、水たまりや岩のようなものを配置したりできればなぁと思います。改善するなら、別のアルゴリズムを採用するか、グリッド単位での描画部分を頑張るかといった感じでしょうか。