LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@Prosamo

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

Posted at

はじめに

　PyxelでRPGなどのダンジョンを制作する際、エディタを使えば簡単に作成できます。しかし、大きなマップをたくさん用意するような場合には、流石に手書きでは厳しいですよね？そこで、手書きほどのクオリティではないにしても、「それっぽく見える」をめざしてランダム生成するコードを書きました。

アルゴリズム

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

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

DFSとは

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

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

コードの解説

　先ほどあてはめたものを箇条書きにすると以下の通りです、また、DFSの手順とは関係ありませんが、最後にゴールを設定する手順を加えています。ただし、ゴールは一番遠い行き止まりとします。

  • スタート地点を決定
  • ランダムな方向へ進む
  • 行き止まりに当たったら戻る
  • 戻った先で残りの方向を見て、どこへも進めなければ、さらに一つ戻る
  • スタート地点まで戻ってきたら終了
  • ゴール地点を設定

一つずつ実装していきます

スタート地点を決定

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

START_POSITIONSは座標のリストで、自由に指定してください。筆者はマップの四隅にしています。
dfsの引数は、現在のx座標、y座標、探索済みのマップの集合、現在の深さ、ゴールの座標、ゴールの深さとなっています。

ランダムな方向へ進む

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します。

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

#最も遠い行き止まりをゴールに設定
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し続けて戻ってきてくれます。

ゴール地点を設定

最終的に受け取ったゴール地点の座標をみて、真ん中あたりにボスのアイコンを設置します。

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

ダンジョン生成部分の全体像

以上の手順をすべてまとめて、最終的に以下のようになります。

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)

その他の部分について

先ほどのコード内で呼び出していた関数の内部も紹介します。

マップ情報の初期化

いったん全てのマスを床にしてから、各グリッドの外周を壁にします。

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

プログラム全体

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

コードを見る 
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)

最後に

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

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?