核心在于帶隨機(jī)的深搜（見代碼第23到27行，其實(shí)也可以用22行代替這幾行代碼，你可以試著把第24行的數(shù)字4改大或者改小，即調(diào)整隨機(jī)程度）

import osimport randomfrom queue import Queueimport numpyimport coloramafrom colorama import Fore, Back, Styleimport sys from bmpEditor import bmpcolorama.init()# numpy.random.seed(1)_xy = [0,2,0,-2,0]size = 31sys.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 and0<=next_pos[1]<size andnext_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:returnfor 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 and0<=next_pos[1]<size andnext_pos in road andnext_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 = 2cell_size = 6image = 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'%sizeimage.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'%sizeimage.save_image(file_name)os.system(file_name)

效果

3131：

8181：

坐標(biāo)系有翻轉(zhuǎn)，控制臺(tái)中的左上角對(duì)應(yīng)圖片中的左下角

其中bmpEditor不是官方庫，代碼地址（文件名為bmpEditor.py，和這以上代碼放同一個(gè)路徑下即可）

在隊(duì)列的基礎(chǔ)上把隊(duì)列中的元素順序打亂（第24行）

import osimport randomfrom queue import Queueimport numpyimport coloramafrom colorama import Fore, Back, Styleimport sys import random from bmpEditor import bmpcolorama.init()numpy.random.seed(1)_xy = [0,2,0,-2,0]size = 59sys.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 and0<=next_pos[1]<size andnext_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:returnfor 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 and0<=next_pos[1]<size andnext_pos in road andnext_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 = 1cell_size = 5image = 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'%sizeimage.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'%sizeimage.save_image(file_name)os.system(file_name)

效果：

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

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

local _xy = {0,2,0,-2,0}local size = 41local base = size+1local road = {}stop_points = {}function dfs(curr_x, curr_y)road[curr_x*base+curr_y] = trueif math.random(1,10) <= 3 thenstop_points[curr_x*base+curr_y] = truereturnend-- os.execute('cls')-- print_map()local permutation = {1,2,3,4}for i=1, 4 dolocal l = math.random(1,4)local r = math.random(1,4)permutation[l], permutation[r] = permutation[r], permutation[l]endfor i=1, 4 dolocal next_x = curr_x+_xy[permutation[i]]local next_y = curr_y+_xy[permutation[i]+1]if next_x>=1 and next_x<=size andnext_y>=1 and next_y<=size androad[next_x*base+next_y] == nil thenlocal 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] = truedfs(next_x, next_y)endendendlocal ans_geted = falselocal parent = {}function get_ans(curr_x, curr_y)-- print(curr_x, curr_y)for i=1, 4 donext_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 andnext_y >= 1 and next_y <= size androad[next_x*base+next_y] andparent[next_x*base+next_y]==nilthenparent[next_x*base+next_y] = curr_x*base+curr_yget_ans(next_x, next_y)endendendlocal ans_road = {}function print_map()for i=0, size+1 dolocal line = ''for j=0, size+1 doif ans_road [i*base+j] thenline = line..'..'elseif road[i*base+j]==true thenline = line..' 'elseline = line..'HH'endendprint(line)endendstop_points[1*base+1] = true-- create mazerepeatlocal has_point = falsefor v,_ in pairs(stop_points) dohas_point = truestop_points[v] = nildfs(math.floor(v/base), v%base)breakend-- print(has_point)until not has_pointget_ans(1,1)parent[1*base+1] = nilprint('')-- 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))-- endprint('')local x = sizelocal y = sizerepeat-- print(x,y)ans_road[x*base+y] = truelocal v = parent[x*base+y]x = math.floor(v/base)y = v%baseuntil --[[(x==1 and y== 1)]] not parent[x*base+y]ans_road[1*base+1] = trueprint_map()

效果：

4141：

8989

到此這篇關(guān)于Python實(shí)現(xiàn)隨機(jī)生成迷宮并自動(dòng)尋路的文章就介紹到這了,更多相關(guān)Python生成迷宮并自動(dòng)尋路內(nèi)容請(qǐng)搜索好吧啦網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持好吧啦網(wǎng)！