pythonを用いた迷路自動生成 part.1【プログラムあり】

迷路を自動生成することは可能なのでしょうか?

このような疑問にお答えします。

迷路を自動生成することは、プログラミングで解決できます。
pythonを用いて、迷路を自動生成することを行います。

迷路の自動生成の手法として、ここでは、穴掘り法による方法を採用したいと思います。

穴掘り法は、以下の手順で迷路を生成します。

開始位置を指定する。
開始位置から上下左右の4方向に対して2ずつ位置を進め通路を作成する。
上下左右の全方向に対して、進行不可となった場合、前回の位置に戻り、再び2.を実行する。
※ 進行不可・・・迷路の設定サイズの範囲を超える。すでに進行済み。

ソースコードは、以下になります。

# coding: utf-8

import pygame
import random
import numpy as np
from pygame.locals import *
import sys
from time import sleep

sys.setrecursionlimit(10**6)

maze_width, maze_height = 21, 21
random_seed = 4
start_pos = (1, 1)
direction = [(0, -2), (0, 2), (-2, 0), (2, 0)]

maze_array = np.ones((maze_height, maze_width))

maze_array[start_pos] = 0 # 初期位置設定


def fn_print_maze(maze_array):
	for dy_list in maze_array:
		for item in dy_list:
			if item == 0:
				print("　", end="")
			elif item == 1:
				print("■", end="")
			elif item == 2:
				print("◎", end="")
				
			else:
				pass
		print("")
		

def fn_create_maze(updX, updY):
	rnd_array = list(range(random_seed))
	random.shuffle(rnd_array)
	
	for index in rnd_array:
		if updY + direction[index][1] < 1 or updY + direction[index][1] > maze_height-1:
			continue
		elif updX + direction[index][0] < 1 or updX + direction[index][0] > maze_width-1:
			continue
		elif maze_array[updY+direction[index][1]][updX+direction[index][0]] == 0:
			continue
		else:
			pass
			
		maze_array[updY+direction[index][1]][updX+direction[index][0]] = 0
		if index == 0:
			maze_array[updY+direction[index][1]+1][updX+direction[index][0]] = 0
		elif index == 1:
			maze_array[updY+direction[index][1]-1][updX+direction[index][0]] = 0
		elif index == 2:
			maze_array[updY+direction[index][1]][updX+direction[index][0]+1] = 0
		elif index == 3:
			maze_array[updY+direction[index][1]][updX+direction[index][0]-1] = 0
		else:
			pass
		
		sleep(0.2)
		fn_print_maze(maze_array)
		fn_create_maze(updX+direction[index][0], updY+direction[index][1])


if __name__ == '__main__':
	fn_create_maze(start_pos[0], start_pos[1])
	maze_array[start_pos] = 2

	print("result")
	fn_print_maze(maze_array)

# coding: utf-8

import pygame

import random

import numpy as np

from pygame.locals import *

import sys

from time import sleep

sys.setrecursionlimit(10**6)

maze_width, maze_height = 21, 21

random_seed = 4

start_pos = (1, 1)

direction = [(0, -2), (0, 2), (-2, 0), (2, 0)]

maze_array = np.ones((maze_height, maze_width))

maze_array[start_pos] = 0 # 初期位置設定

def fn_print_maze(maze_array):

for dy_list in maze_array:

for item in dy_list:

if item == 0:

print("　", end="")

elif item == 1:

print("■", end="")

elif item == 2:

print("◎", end="")

else:

pass

print("")

def fn_create_maze(updX, updY):

rnd_array = list(range(random_seed))

random.shuffle(rnd_array)

for index in rnd_array:

if updY + direction[index][1] < 1 or updY + direction[index][1] > maze_height-1:

continue

elif updX + direction[index][0] < 1 or updX + direction[index][0] > maze_width-1:

continue

elif maze_array[updY+direction[index][1]][updX+direction[index][0]] == 0:

continue

else:

pass

maze_array[updY+direction[index][1]][updX+direction[index][0]] = 0

if index == 0:

maze_array[updY+direction[index][1]+1][updX+direction[index][0]] = 0

elif index == 1:

maze_array[updY+direction[index][1]-1][updX+direction[index][0]] = 0

elif index == 2:

maze_array[updY+direction[index][1]][updX+direction[index][0]+1] = 0

elif index == 3:

maze_array[updY+direction[index][1]][updX+direction[index][0]-1] = 0

else:

pass

sleep(0.2)

fn_print_maze(maze_array)

fn_create_maze(updX+direction[index][0], updY+direction[index][1])

if __name__ == '__main__':

fn_create_maze(start_pos[0], start_pos[1])

maze_array[start_pos] = 2

print("result")

fn_print_maze(maze_array)

迷路生成の挙動としては、以下のようになります。

いかがでしょうか。
開始位置から徐々に迷路が生成されていく様子がわかると思います。
この環境を利用することで、RPG風ゲームの作成、強化学習を使用して迷路を自動的に攻略するAIを作成できるかもしれませんね。