Python 은 랜 덤 으로 미 로 를 생 성하 고 자동 으로 길 을 찾 습 니 다.

Python 심층 검색 판:
핵심 은 랜 덤 으로 검색 하 는 것 이다.

import os
import random
from queue import Queue
import numpy
import colorama
from colorama import Fore, Back, Style
import sys   

from bmpEditor import bmp

colorama.init()


# numpy.random.seed(1)
_xy = [0,2,0,-2,0]
size = 31
sys.setrecursionlimit(100000000)

road = set()
def dfs(curr_pos):
	road.add(curr_pos)
	# for i in numpy.random.permutation(4):
	p = [0,1,2,3]
	for i in range(4):
		l = random.randint(0,3)
		r = random.randint(0,3)
		p[l], p[r] = p[r], p[l]
	for i in p:
		next_pos = (curr_pos[0] + _xy[i], curr_pos[1] + _xy[i+1])
		if (0<=next_pos[0]<size and
			0<=next_pos[1]<size and
			next_pos not in road ):
			
			road.add(((curr_pos[0] + next_pos[0])/2, (curr_pos[1] + next_pos[1])/2))
			dfs(next_pos)

dfs((0,0))

q = Queue()
q.put((0,0))
ans_road = set()
def dfs_getans(curr_pos):
	# print(curr_pos)
	ans_road.add(curr_pos)
	if (size-1, size-1) in ans_road:
		return
	for i in range(4):
		next_pos = (curr_pos[0] + _xy[i]//2, curr_pos[1] + _xy[i+1]//2)
		if (0<=next_pos[0]<size and
			0<=next_pos[1]<size and
			next_pos in road and
			next_pos not in ans_road and
			(size-1, size-1) not in ans_road):
			
			dfs_getans(next_pos)
	if (size-1, size-1) not in ans_road:
		ans_road.remove(curr_pos)

dfs_getans((0,0))

for i in range(size):
	for j in range(size):
		print((Back.WHITE + ' ') if (i,j) in road else (Back.BLACK + ' '), end=' ')
	print()


wall_width = 2
cell_size = 6
image = bmp((size+3)*cell_size-wall_width, (size+3)*cell_size-wall_width, 0x000000)
for i in range(size+3):
	for j in range(size+3):
		if (i-1, j-1) in road:
			image.paint_rect(i*cell_size, j*cell_size, cell_size*2-wall_width, cell_size*2-wall_width, 0xffffff)

file_name = "%dmaze.bmp"%size
image.save_image(file_name)
os.system(file_name)

for p in ans_road:
	# image.paint_rect(p[0]+1, p[1]+1)
	image.paint_rect((
		p[0]+1)*cell_size + (cell_size - wall_width)//2,
		(p[1]+1)*cell_size + (cell_size - wall_width)//2,
		cell_size, cell_size,
		0xff0000
	)

file_name = "%dans.bmp"%size
image.save_image(file_name)
os.system(file_name)

효과.
3131：


8181：


좌 표 는 뒤 집 히 고 콘 솔 의 왼쪽 상단 은 그림 의 왼쪽 아래 에 대응 합 니 다.
그 중에서 bmpEditor 는 공식 라 이브 러 리 가 아 닙 니 다코드 주소(파일 이름 은 bmpEditor.py 입 니 다.이 코드 와 같은 경 로 를 두 면 됩 니 다)
파 이 썬
대기 열 을 바탕 으로 대기 열 에 있 는 요소 순 서 를 흐 트 러 뜨 립 니 다(24 줄)

import os
import random
from queue import Queue
import numpy
import colorama
from colorama import Fore, Back, Style
import sys   
import random   

from bmpEditor import bmp
colorama.init()


numpy.random.seed(1)
_xy = [0,2,0,-2,0]
size = 59
sys.setrecursionlimit(size*size//4+size)

q = []
q.append((0,0))
road = set()
road.add((0,0))
while len(q) != 0:
	random.shuffle(q)
	curr_pos = q.pop()
	# print(curr_pos)
	for i in range(4):
		next_pos = (curr_pos[0] + _xy[i], curr_pos[1] + _xy[i+1])
		if (	0<=next_pos[0]<size and
				0<=next_pos[1]<size and
				next_pos not in road ):
			road.add( ((curr_pos[0] + next_pos[0])//2, (curr_pos[1] + next_pos[1])//2) )
			q.append(next_pos)
			road.add(next_pos)

ans_road = set()
def dfs_getans(curr_pos):
	ans_road.add(curr_pos)
	if (size-1, size-1) in ans_road:
		return
	for i in range(4):
		next_pos = (curr_pos[0] + _xy[i]//2, curr_pos[1] + _xy[i+1]//2)
		if (	0<=next_pos[0]<size and
				0<=next_pos[1]<size and
				next_pos in road and
				next_pos not in ans_road and
				(size-1, size-1) not in ans_road):
			dfs_getans(next_pos)
	if (size-1, size-1) not in ans_road:
		ans_road.remove(curr_pos)

dfs_getans((0,0))
print(len(ans_road))

for i in range(0, size):
	for j in range(0, size):
		print((Back.WHITE + ' ') if (i,j) in road else (Back.BLACK + ' '), end=' ')
	print()
wall_width = 1
cell_size = 5
image = bmp((size+3)*cell_size-wall_width, (size+3)*cell_size-wall_width, 0x000000)
for i in range(size+3):
	for j in range(size+3):
		if (i-1, j-1) in road:
			image.paint_rect(i*cell_size, j*cell_size, cell_size*2-wall_width, cell_size*2-wall_width, 0xffffff)

file_name = "%dmaze.bmp"%size
image.save_image(file_name)
os.system(file_name)

for p in ans_road:
	# image.paint_rect(p[0]+1, p[1]+1)
	image.paint_rect((
		p[0]+1)*cell_size + (cell_size - wall_width)//2,
		(p[1]+1)*cell_size + (cell_size - wall_width)//2,
		cell_size, cell_size,
		0xff0000
	)

file_name = "%dans.bmp"%size
image.save_image(file_name)
os.system(file_name)

효과:


깊이 가 우선 인 것 보다 이런 미 로 는 더욱'직'할 것 이다.
lua 버 전:
대체로 깊 은 검색 이 고 임 의 성 을 더 해 검색 과정 에서 현재 경 로 를 잠시 포기 할 확률 이 있 습 니 다.시계 보기 stoppoints,(7 줄,74 줄 및 그 뒤의 repeat 순환)

local _xy = {0,2,0,-2,0}
local size = 41
local base = size+1
local road = {}

stop_points = {}
function dfs(curr_x, curr_y)
	road[curr_x*base+curr_y] = true
	if math.random(1,10) <= 3 then
		stop_points[curr_x*base+curr_y] = true
		return
	end
	-- os.execute("cls")
	-- print_map()
	local permutation = {1,2,3,4}
	for i=1, 4 do
		local l = math.random(1,4)
		local r = math.random(1,4)
		permutation[l], permutation[r] = permutation[r], permutation[l]
	end

	for i=1, 4 do
		local next_x = curr_x+_xy[permutation[i]]
		local next_y = curr_y+_xy[permutation[i]+1]
		if  next_x>=1 and next_x<=size and
			next_y>=1 and next_y<=size and
			road[next_x*base+next_y] == nil then

			local mid_x = math.floor((curr_x+next_x)/2)
			local mid_y = math.floor((curr_y+next_y)/2)
			road[mid_x*base+mid_y] = true
			dfs(next_x, next_y)
		end
	end
end

local ans_geted = false
local parent = {}
function get_ans(curr_x, curr_y)
	-- print(curr_x, curr_y)
	for i=1, 4 do
		next_x =  (curr_x + math.floor(_xy[i])/2 )
		next_y =  (curr_y + math.floor(_xy[i+1])/2 )
		-- print(next_x, next_y)
		if  next_x >= 1 and next_x <= size and
			next_y >= 1 and next_y <= size and
			road[next_x*base+next_y] and
			parent[next_x*base+next_y]==nil
		then
			parent[next_x*base+next_y] = curr_x*base+curr_y
			get_ans(next_x, next_y)
		end
	end

end

local ans_road = {}
function print_map()
	for i=0, size+1 do
		local line = ""
		for j=0, size+1 do
			if ans_road [i*base+j] then
				line = line..".."
			elseif road[i*base+j]==true then
				line = line.."  "
			else
				line = line.."HH"
			end
		end
		print(line)
	end
end

stop_points[1*base+1] = true

-- create maze
repeat
	local has_point = false
	for v,_ in pairs(stop_points) do
		has_point = true
		stop_points[v] = nil
		dfs(math.floor(v/base), v%base)
		break
	end
	-- print(has_point)
until not has_point


get_ans(1,1)
parent[1*base+1] = nil
print("")
-- for k,v in pairs(parent) do
-- 	print(string.format("[%d,%d]->[%d,%d]", math.floor(k/base), k%base, math.floor(v/base), v%base))
-- end
print("")
local x = size
local y = size
repeat
	-- print(x,y)
	ans_road[x*base+y] = true
	local v = parent[x*base+y]
	x = math.floor(v/base)
	y = v%base
until --[[(x==1 and y== 1)]] not parent[x*base+y]
ans_road[1*base+1] = true

print_map()

효과:
4141：

8989

파 이 썬 이 랜 덤 으로 미 로 를 만 들 고 자동 으로 길 을 찾 는 것 에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 파 이 썬 이 미 로 를 만 들 고 자동 으로 길 을 찾 는 내용 은 예전 의 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 많은 응원 부탁드립니다!