迷路を作るアルゴリズムを実装する

暇だったので迷路を作るアルゴリズムを実装してみた。

アルゴリズムの概要

以下のような表を用意して、隣り合う2つのマスを選択する。(例えば2と8のマス)

壁を壊して、小さいほうの値で更新する。

同様に3と4のマスを選択すると以下のようになる。

さらに2と3のマスを選択する。

この操作をすべてのマスが0になるまで繰り返す。

実装

適当な実装は以下。

import random
import numpy as np
from itertools import product

news = ['n', 'e', 'w', 's']
SPACE = '　'
WALL = '■'
START = 'Ｓ'
GOAL = 'Ｇ'


def print_maze(maze):
    """
    迷路を出力
    """
    with open('maze.txt', 'w') as f:
        for row in maze:
            f.write(''.join(row) + '\n')


# 迷路のサイズを指定
m, n = 30, 50

memo = np.array([i for i in range(n * m)])
memo = memo.reshape(m, n)

# 迷路を初期化
maze = [[SPACE for _ in range(2 * n + 1)] for _ in range(2 * m + 1)]
maze[1][1] = START
maze[2 * m - 1][2 * n - 1] = GOAL
for i, j in product(range(2 * m + 1), range(2 * n + 1)):
    if i % 2 == 0 or j % 2 == 0:
        maze[i][j] = WALL

while (memo != 0).any():
    x1 = random.choice(range(m))
    y1 = random.choice(range(n))
    direction = random.choice(news)

    if direction == 'e':
        x2, y2 = x1, y1 + 1
    elif direction == 'w':
        x2, y2 = x1, y1 - 1
    elif direction == 'n':
        x2, y2 = x1 - 1, y1
    elif direction == 's':
        x2, y2 = x1 + 1, y1

    # 範囲外の場合はcontinue
    if (x2 < 0) or (x2 >= m) or (y2 < 0) or (y2 >= n):
        continue

    if memo[x1, y1] != memo[x2, y2]:
        tmp_min = min(memo[x1, y1], memo[x2, y2])
        tmp_max = max(memo[x1, y1], memo[x2, y2])

        # メモの更新
        memo[memo == tmp_max] = tmp_min

        # 壁を壊す
        maze[x1 + x2 + 1][y1 + y2 + 1] = SPACE

print_maze(maze)