DL-2; マップを自動生成する — Daydreaming in Brookline, MA

1. はじめに
2. マップ自動生成
3. 続き

1 はじめに

Rogue+Wizライクなゲームを作るプロジェクトの2回目です。プロジェクトに名前が無いと不便なので、仮称DL - Daemon Lordとしました。dl.pyで作り始めます。

今回はマップの自動生成をやります。このサイトにざっと目を通して簡単に予習しておきました。

2 マップ自動生成

まずは1フロア分のマップを作ります。以下のような流れになります。

配置する部屋データを生成する
フロアを岩で埋め尽くす
部屋をフロアに配置する
廊下で部屋同士をつなぐ
ドアを配置する

2.1 部屋データ生成

まずはRoomクラスを作ります。パラメーターとして左上の座標(x, y)と横縦のサイズ(x_size, y_size)を持ちます。後で計算をさぼるために部屋の中心座標も計算して持っておきます(center_x, center_y)。

\__repr__()をデバッグ用に用意しました。

class Room:
    def __init__(self, x, y, x_size, y_size):
        self.x = x
        self.y = y
        self.x_size = x_size
        self.y_size = y_size
        self.center_x = x + x_size//2
        self.center_y = y + y_size//2

    def __repr__(self):
        return f"Room(x/y: {self.x}/{self.y}, size: {self.x_size}/{self.y_size})"

これを生成してroomsリストにアペンドしていきます。

他にもフロアFloorクラスを定義します。ディクショナリで十分な気もします。。

class Floor:
    def __init__(self, x_size, y_size, floor, floor_data):
        self.x_size = x_size
        self.y_size = y_size
        self.floor = floor
        self.floor_data = floor_data

    def __repr__(self):
        s = self.floor_data.decode()
        return f"Floor(size: {self.x_size}x{self.y_size}, floor: {self.floor} - {s})"

次は部屋生成のprepare_rooms関数です。フロアのサイズを引数として取ります。フロアのランダムな位置に、横サイズ3-12 x 縦サイズ3-7の部屋候補を作り、既にroomsリストに登録されている部屋と重ならなければリストに追加することを繰り返します。二つの部屋の重なりを判定するユーティリティー関数rooms_intersect()を定義しています。

仮に256, 10, 4等の定数を直接指定していて見苦しいですが、後でconfig値化するつもりです。

def prepare_rooms(floor_x_size, floor_y_size):
    """
    Return a list filled with Rooms objects on a floor.
    """
    rooms = []
    for _ in range(random.randrange(256)):
        rx = 3 + random.randrange(10)
        ry = 3 + random.randrange(4)
        room = Room(random.randrange(floor_x_size-rx+1),
                    random.randrange(floor_y_size-ry+1),
                    rx, ry)
        intersect = False
        for r in rooms:
            if rooms_intersect(room, r):
                intersect = True
                break
        if not intersect:
            rooms.append(room)
    return rooms

部屋の重なり判定は、「矩形」「重なり」「判定」あたりのキーワードで検索し、紙に絵をいくつか描いて整理してからコードにしました。以下のコードは単純ですが、これだけを読んで理解するのはハードルが高いかもしれません。。。

def rooms_intersect(r1, r2):
    """
    Return True if two rooms are intersected.
    """
    return max(r1.x, r2.x) <= min(r1.x+r1.x_size, r2.x+r2.x_size) \
        and max(r1.y, r2.y) <= min(r1.y+r1.y_size, r2.y+r2.y_size)

2.2 部屋のフロアへの配置

続いて、フロアを岩で埋め尽くして初期化し、そこに部屋を配置していきます。これは一フロアを生成する関数generate_floor()の中で直接やってしまいます。今回のテーマのメイン関数です。

フロアデータfloor_dataはbytearrayで表現します。最初これをstrで作って、上書きしようとしてエラーになったのは内緒です(汗)。slice操作を高速化するためにfloor_dataのmemoryviewを作成し、それに対して以降はfloor_viewに対して操作します。

'#'の文字は岩を、'.'は歩ける床を意味しています。floor_dataをb'#'で埋めたbytearrayとし、そこに(floor_view経由で)部屋の床b'.'を上書きしています。

def generate_floor(floor_x_size, floor_y_size, floor):
    """
    Generate a dungeon floor.
    Create rooms, connect among them and place doors
    """
    rooms = prepare_rooms(floor_x_size, floor_y_size)
    floor_data = bytearray(b'#' * floor_x_size *
                           floor_y_size)  # rock only floor
    floor_view = memoryview(floor_data)
    for r in rooms:
        for y in range(r.y_size):
            start = (r.y + y)*floor_x_size + r.x
            floor_view[start:start+r.x_size] = b'.'*r.x_size
    connect_all_rooms(rooms, floor_x_size, floor_view)
    place_doors(rooms, floor_x_size, floor_y_size, floor_view)
    return Floor(floor_x_size, floor_y_size, floor, floor_data)

2.3 廊下で部屋をつなぐ

そして、部屋を廊下でつないでいきます。まずは部屋をy座標 → x座標の順でソートします。そして部屋をひとつずつリストからpopして、一番近い部屋を探し、互いの中心座標を歩ける床のタイルb'.'で結び、廊下とします。他の廊下や部屋と重なっても気にしません。全ての部屋を一筆書きの要領でつなぎます。

def connect_all_rooms(rooms, floor_x_size, floor_view):
    """
    Connect all rooms with hallways.
    Try to find and connect with the nearest room.
    """
    rooms.sort(key=lambda room: room.y+room.y_size//2)
    rooms.sort(key=lambda room: room.x+room.x_size//2)
    rs = rooms[:]
    r_src = rs.pop()
    while rs:
        idx_near = 0
        len_rs = len(rs)
        for i in range(len_rs):  # look for the nearest room
            if distsq_rooms(r_src, rs[i]) < distsq_rooms(r_src, rs[idx_near]):
                idx_near = i
        r_near = rs.pop(idx_near)
        connect_rooms(r_src, r_near, floor_x_size, floor_view)
        r_src = r_near

disqsq_rooms関数は、二つの部屋間の距離(の2乗)を求めるユーティリティー関数です。

def distsq_rooms(r1, r2):
    """
    Calculate distance between two rooms.
    Will return distance**2.
    """
    return (r1.x+r1.x_size//2 - (r2.x+r2.x_size//2))**2 \
        + (r1.y+r1.y_size//2 - (r2.y+r2.y_size//2))**2

connect_rooms()関数は、二つの部屋に廊下を作ります。二つの部屋の結び方は、横方向と縦方向のどちらを先に作るかで2パターンあります。確率50%のランダムで決めています。(cx, cy)は縦線と横線が交差する点です。

def connect_rooms(r1, r2, floor_x_size, floor_view):
    """
    Create a hallway between two rooms and connect them.
    """
    if random.randrange(1) == 0:  # 1/2
        cx = r1.center_x
        cy = r2.center_y
    else:
        cx = r2.center_x
        cy = r1.center_y
    for x, y in draw_line(r1.center_x, r1.center_y, cx, cy):
        pos = floor_x_size * y + x
        floor_view[pos:pos+1] = b'.'
    for x, y in draw_line(r2.center_x, r2.center_y, cx, cy):
        pos = floor_x_size * y + x
        floor_view[pos:pos+1] = b'.'

draw_line()は縦線あるいは横線を一本引くだけの関数です。次の座標(x, y)をyieldするジェネレーター関数なので、for文に与えています。最初、終点をyieldせずにしばらく悩んだことも内緒です(汗)。これをジェネレーター関数として実装するアイデアは、例のRogue-like tutorialからいただきました。ジェネレーターはなんか初心者ぽくなくて格好良いので好きです。

def draw_line(x1, y1, x2, y2):
    """
    Utility generator function to draw a straight line.
    Must eithr be vertical (x1==x2) or horizontal (y1==y2).
    """
    if x1 < x2:
        x1, x2 = x2, x1
    if y1 < y2:
        y1, y2 = y2, y1
    while x1 > x2 or y1 > y2:
        yield x2, y2
        if x1 > x2:
            x2 += 1
        if y1 > y2:
            y2 += 1
    yield x2, y2

2.4 ドアの設置

最後に、place_doors()関数で部屋の入り口にドアを設置します。ドアにはロック無し('+')、あり('*')の2種類を用意し、10%の確率でその部屋のドアをロック付きにします。

部屋の4隅の辺(上下左右)をチェックし、その隣が歩ける床タイル('.')等なら廊下と接続していると判断し、ドアを設置していきます。

コードの繰り返しがみっともなかったので、共通部分をplace_door()関数として切り出しました。見た目がすっきりしたと思います。最初のif文では、その座標がフロアの内側にあるかどうかを判定しています。指定座標が床('.')または(ロック無し)ドア('+')ならばドア(ロック付きかもしれない)を設置します。

def place_door(x, y, floor_x_size, floor_y_size, floor_view, dc):
    """
    Utility function to check and place a door
    """
    if 0 <= x < floor_x_size and 0 <= y < floor_y_size:
        pos = y*floor_x_size + x
        c = floor_view[pos:pos+1]
        if c == b'.' or c == b'+':
            floor_view[pos:pos+1] = dc


def place_doors(rooms, fl_xsz, fl_ysz, fl_vw):
    """
    Place locked or unlocked doors in front of rooms.
    """
    for r in rooms:
        dc = b'+'  # door character
        if random.randrange(10) == 0:  # 10%
            dc = b'*'  # locked door
        for x in range(r.x_size):  # top and bottom edges
            place_door(r.x+x, r.y-1, fl_xsz, fl_ysz, fl_vw, dc)
            place_door(r.x+x, r.y+r.y_size, fl_xsz, fl_ysz, fl_vw, dc)

        for y in range(r.y_size):  # left and right edges
            place_door(r.x-1, r.y+y, fl_xsz, fl_ysz, fl_vw, dc)
            place_door(r.x+r.x_size, r.y+y, fl_xsz, fl_ysz, fl_vw, dc)

このアルゴリズムには難点があって、部屋のすぐ隣を廊下が併走しているときに、この廊下を全てドアにしてしまいます。まあ、実害は無さそうなので放置しておきましょう。

3 続き

今回はダンジョンフロアの自動生成部分を作ってみました。思いのほか長くなってしまいました。次回はフロアをスクロール画面に表示します。

Table of Contents