4 ways to generate maze 四种迷宫生成方法

maze.py

from matplotlib import pyplot
from matplotlib import cm
import numpy as np
import random


def show(image,name=None):
	pyplot.imshow(image, cmap='gray', interpolation='none')
	if name==None:
		pyplot.show()
	else:
		pyplot.savefig(name,dpi=100)


def init_image(size):
	m = size[0]
	n = size[1]
	image = []
	for i in range(2 * m - 1):
		image.append([0] * (2 * n - 1))
	for i in range(m):
		for j in range(n):
			image[2 * i][2 * j] = 255
	return image


def init_walls(size):
	m = size[0]
	n = size[1]
	walls = []
	for i in range(0, 2 * m - 1):
		for j in range(0, 2 * n - 1):
			if (i + j) % 2 == 1:
				walls.append((i, j))
	return walls


def init_mark(size):
	m = size[0]
	n = size[1]
	mark = []
	for i in range(m):
		mark.append([0] * n)
	return mark


def init_parent(size):
	m = size[0]
	n = size[1]
	mark = [0] * (m * n)
	for i in range(m):
		for j in range(n):
			mark[i * n + j] = i * n + j
	return mark


def get_unmark_neighbours(p, size, mark):
	x = p[0]
	y = p[1]
	m = size[0]
	n = size[1]
	neighbours = []
	if x > 0 and mark[(x - 1)][y] == 0:
		neighbours.append((x - 1, y))
	if y > 0 and mark[x][y - 1] == 0:
		neighbours.append((x, y - 1))
	if x < m - 1 and mark[x + 1][y] == 0:
		neighbours.append((x + 1, y))
	if y < n - 1 and mark[x][y + 1] == 0:
		neighbours.append((x, y + 1))
	return neighbours


def get_neighbours(p, size):
	x = p[0]
	y = p[1]
	m = size[0]
	n = size[1]
	neighbours = []
	if x > 0:
		neighbours.append((x - 1, y))
	if y > 0:
		neighbours.append((x, y - 1))
	if x < m - 1:
		neighbours.append((x + 1, y))
	if y < n - 1:
		neighbours.append((x, y + 1))
	return neighbours


def get_random_neighbour(point, size, mark):
	neighbours = get_neighbours(point, size, mark)
	return random.choice(neighbours)


def dfs(point, size, image, mark):
	mark[point[0]][point[1]] = 1
	neighbours = get_neighbours(point, size)
	while len(neighbours) > 0:
		neighbour = random.choice(neighbours)
		neighbours.remove(neighbour)
		if mark[neighbour[0]][neighbour[1]] == 0:
			image[neighbour[0] + point[0]][neighbour[1] + point[1]] = 255
			dfs(neighbour, size, image, mark)


#  1: dfs, random road
def maze1(size):
	image = init_image(size)
	mark = init_mark(size)
	dfs((0, 0), size, image, mark)
	show(image,"dfs")


def get_unmark_neighbour_walls(p, size, mark):
	walls = []
	neighbours = get_unmark_neighbours(p, size, mark)
	for n in neighbours:
		walls.append((p[0] + n[0], p[1] + n[1]))
	return walls


def get_wall_neighbours(wall):
	if wall[0] % 2 == 0:
		return [(wall[0] // 2, wall[1] // 2), (wall[0] // 2, wall[1] // 2 + 1)]
	else:
		return [(wall[0] // 2, wall[1] // 2), (wall[0] // 2 + 1, wall[1] // 2)]


#  2: prim, random wall
def maze2(size):
	image = init_image(size)
	mark = init_mark(size)
	mark[0][0] = 1
	walls = get_unmark_neighbour_walls((0, 0), size, mark)
	while (len(walls) > 0):
		w = random.choice(walls)
		walls.remove(w)
		neighbours = get_wall_neighbours(w)
		for n in neighbours:
			if (mark[n[0]][n[1]] == 0):
				mark[n[0]][n[1]] = 1
				image[w[0]][w[1]] = 255
				walls.extend(get_unmark_neighbour_walls(n, size, mark))

	show(image,"prime")


def get_parent(p, parent):
	if (parent[p] == p):
		return p
	p = get_parent(parent[p], parent)
	parent[p] = p
	return p


# 3: union-set
def maze3(size):
	image = init_image(size)
	parent = init_parent(size)
	walls = init_walls(size)
	while (len(walls) > 0):
		w = random.choice(walls)
		walls.remove(w)
		neighbours = get_wall_neighbours(w)
		n0 = neighbours[0]
		n1 = neighbours[1]
		p0 = get_parent(n0[0] * size[1] + n0[1], parent)
		p1 = get_parent(n1[0] * size[1] + n1[1], parent)
		if (p0 != p1):
			image[w[0]][w[1]] = 255
			parent[p0] = min(p0, p1)
			parent[p1] = min(p0, p1)
	show(image,"union-set")


def put_hole(image, i_s, i_e, j_s, j_e):
	if(i_e-i_s<=0 or j_e-j_s<=0):
		return
	if i_e-i_s==1:
		for j in range(j_s+1,j_e,2):
			image[i_s][j]=255
		return
	if j_e-j_s==1:
		for i in range(i_s+1,i_e,2):
			image[i][j_s]=255
		return
	holes=[]
	i = random.randrange(i_s + 1, i_e, 2)
	j = random.randrange(j_s + 1, j_e, 2)
	assert i%2==1
	assert j%2==1
	holes.append ((i, random.randrange(j_s, j, 2)))
	holes.append((i, random.randrange(j + 1, j_e, 2)))
	holes.append((random.randrange(i_s, i, 2), j))
	holes.append ((random.randrange(i + 1, i_e, 2), j))
	keep = random.randint(0,len(holes)-1)
	for k in range(len(holes)):
		if (k == keep):
			continue
		h = holes[k]
		image[h[0]][h[1]] = 255
		assert (h[0]+h[1])%2==1
	put_hole(image, i_s, i, j_s, j)
	put_hole(image, i + 1, i_e, j_s, j)
	put_hole(image, i_s, i, j + 1, j_e)
	put_hole(image, i + 1, i_e, j + 1, j_e)

# 4: recursive
def maze4(size):
	image = init_image(size)
	put_hole(image, 0, size[0] * 2-1 , 0, size[1] * 2 -1)
	show(image,"split.png")


maze1((16, 20))
maze2((16, 20))
maze3((16, 20))
maze4((16, 20))