Python实现随机生成迷宫并自动寻路

python深搜版： 核心在于带随机的深搜（见代码第23到27行，其实也可以用22行代替这几行代码，你可以试着把第24行的数字4改大或者改小，即调整随机程度）

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)

def dfs(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
www.cppcns.com		next_pos not in roa编程客栈d ):

dfs(next_pos)

dfs((0,0))

q = Queue()
q.put((0,0))
def dfs_getans(curr_pos):
# print(curr_pos)
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

dfs_getans(next_pos)
if (size-1, size-1) not in ans_road:

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):
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)

# 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：

Python 广搜版

```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))
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
q.append(next_pos)

def dfs_getans(curr_pos):
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
dfs_getans(next_pos)
if (size-1, size-1) not in ans_road:

dfs_getans((0,0))

for i in range(0, size):
for j in range(0, size):
printsAndjZdVAu((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):
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)

# 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版：

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

stop_points = {}
function dfs(curr_x, curr_y)
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

local mid_x = math.floor((curr_x+next_x)/2)
local mid_y = math.floor((curr_y+next_y)/2)
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
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

function print_map()
for i=0, size+1 do
local line = ""
for j=0, size+1 do
line = line..".."
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)
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]

print_map()

```

4141：

8989