第Python實(shí)現(xiàn)隨機(jī)生成迷宮并自動(dòng)尋路next_pos=(curr_pos[0]+_xy[i],curr_pos[1]+_xy[i+1])

if(0=next_pos[0]sizeand

0=next_pos[1]sizeand

next_posnotinroad):

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

defdfs_getans(curr_pos):

ans_road.add(curr_pos)

if(size-1,size-1)inans_road:

return

foriinrange(4):

next_pos=(curr_pos[0]+_xy[i]//2,curr_pos[1]+_xy[i+1]//2)

if(0=next_pos[0]sizeand

0=next_pos[1]sizeand

next_posinroadand

next_posnotinans_roadand

(size-1,size-1)notinans_road):

dfs_getans(next_pos)

if(size-1,size-1)notinans_road:

ans_road.remove(curr_pos)

dfs_getans((0,0))

print(len(ans_road))

foriinrange(0,size):

forjinrange(0,size):

print((Back.WHITE+'')if(i,j)inroadelse(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)

foriinrange(size+3):

forjinrange(size+3):

if(i-1,j-1)inroad:

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)

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

效果：

相比深度優(yōu)先的，這種迷宮會(huì)更加“直”一些

lua版：

大體上是深搜，加了一定的隨機(jī)性使得搜索過程中有一定概率暫時(shí)放棄當(dāng)前路徑。見表stop_points，（第7行、第74行及其后面的repeat循環(huán)）

local_xy={0,2,0,-2,0}

localsize=41

localbase=size+1

localroad={}

stop_points={}

functiondfs(curr_x,curr_y)

road[curr_x*base+curr_y]=true

ifmath.random(1,10)=3then

stop_points[curr_x*base+curr_y]=true

return

--os.execute("cls")

--print_map()

localpermutation={1,2,3,4}

fori=1,4do

locall=math.random(1,4)

localr=math.random(1,4)

permutation[l],permutation[r]=permutation[r],permutation[l]

fori=1,4do

localnext_x=curr_x+_xy[permutation[i]]

localnext_y=curr_y+_xy[permutation[i]+1]

ifnext_x=1andnext_x=sizeand

next_y=1andnext_y=sizeand

road[next_x*base+next_y]==nilthen

localmid_x=math.floor((curr_x+next_x)/2)

localmid_y=math.floor((curr_y+next_y)/2)

road[mid_x*base+mid_y]=true

dfs(next_x,next_y)

localans_geted=false

localparent={}

functionget_ans(curr_x,curr_y)

--print(curr_x,curr_y)

fori=1,4do

next_x=(curr_x+math.floor(_xy[i])/2)

next_y=(curr_y+math.floor(_xy[i+1])/2)

--print(next_x,next_y)

ifnext_x=1andnext_x=sizeand

next_y=1andnext_y=sizeand

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)

localans_road={}

functionprint_map()

fori=0,size+1do

localline=""

forj=0,size+1do

ifans_road[i*base+j]then

line=line..".."

elseifroad[i*base+j]==truethen

line=line..""

else

line=line.."HH"

print(line)

stop_points[1*base+1]=true

--createmaze

repeat

localhas_point