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

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：

坐標系有翻轉，控制臺中的左上角對應圖片中的左下角

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

在隊列的基礎上把隊列中的元素順序打亂（第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)

效果：

相比深度優先的，這種迷宮會更加“直”一些

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

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

到此這篇關于Python實現隨機生成迷宮并自動尋路的文章就介紹到這了,更多相關Python生成迷宮并自動尋路內容請搜索好吧啦網以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持好吧啦網！