Python實現(xiàn)隨機生成迷宮并自動尋路
更新時間：2021年06月12日 10:34:37 作者：WA的一聲哭出來 pnq
最近在學習Python，正好今天在學習隨機數(shù)，本文實現(xiàn)了Python實現(xiàn)隨機生成迷宮并自動尋路，感興趣的可以了解一下
Python深搜版：
核心在于帶隨機的深搜（見代碼第23到27行，其實也可以用22行代替這幾行代碼，你可以試著把第24行的數(shù)字4改大或者改小，即調(diào)整隨機程度）
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：
坐標系有翻轉(zhuǎn)，控制臺中的左上角對應(yīng)圖片中的左下角
其中bmpEditor不是官方庫，代碼地址（文件名為bmpEditor.py，和這以上代碼放同一個路徑下即可）
Python 廣搜版
在隊列的基礎(chǔ)上把隊列中的元素順序打亂（第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)
效果：
相比深度優(yōu)先的，這種迷宮會更加“直”一些
lua版：
大體上是深搜，加了一定的隨機性使得搜索過程中有一定概率暫時放棄當前路徑。見表stop_points，（第7行、第74行及其后面的repeat循環(huán)）
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
到此這篇關(guān)于Python實現(xiàn)隨機生成迷宮并自動尋路的文章就介紹到這了,更多相關(guān)Python生成迷宮并自動尋路內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
Python網(wǎng)絡(luò)爬蟲神器PyQuery的基本使用教程
這篇文章主要給大家介紹了關(guān)于Python網(wǎng)絡(luò)爬蟲神器PyQuery的基本使用教程，文中通過示例代碼介紹的非常詳細，對大家學習使用PyQuery具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧。2018-02-02
這篇文章主要介紹了python3 刪除所有自定義變量的操作，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2021-04-04
Python實現(xiàn)查找最小的k個數(shù)示例【兩種解法】
這篇文章主要介紹了Python實現(xiàn)查找最小的k個數(shù),結(jié)合實例形式對比分析了Python常見的兩種列表排序、查找相關(guān)操作技巧,需要的朋友可以參考下2019-01-01
這篇文章主要介紹了pytorch如何獲得模型的計算量和參數(shù)量操作，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-05-05
PyTorch詳解經(jīng)典網(wǎng)絡(luò)種含并行連結(jié)的網(wǎng)絡(luò)GoogLeNet實現(xiàn)流程
今天小編就為大家分享一篇Pytorch實現(xiàn)GoogLeNet的方法，GoogLeNet提出了一個名為“Inception”的深度卷積神經(jīng)網(wǎng)結(jié)構(gòu)，其目標是將分類、識別ILSVRC14數(shù)據(jù)集的技術(shù)水平提高一個層次。這一結(jié)構(gòu)的主要特征是對網(wǎng)絡(luò)內(nèi)部計算資源的利用進行了優(yōu)化2022-05-05
python格式化字符串的實戰(zhàn)教程(使用占位符、format方法)
我們經(jīng)常會用到%-formatting和str.format()來格式化,下面這篇文章主要給大家介紹了關(guān)于python格式化字符串的相關(guān)資料,文中通過實例代碼介紹的非常詳細,需要的朋友可以參考下2022-08-08
這篇文章主要介紹了將matplotlib繪圖嵌入pyqt的方法示例，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-01-01
量化交易,作為現(xiàn)代金融市場中的一種先進交易方式,通過運用數(shù)學模型、統(tǒng)計方法和計算機算法來指導交易決策,旨在提高交易效率和決策的準確性,本文將詳細介紹如何使用Python進行量化交易,包括策略開發(fā)、數(shù)據(jù)處理、回測、風險管理和實盤交易等關(guān)鍵步驟2024-09-09
這篇文章主要為大家詳細介紹了python機器學習實現(xiàn)決策樹，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-11-11
這篇文章介紹了Python中的re正則表達式模塊，文中通過示例代碼介紹的非常詳細。對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2022-05-05