Python实现随机生成迷宫并自动寻路
作者:WA的一声哭出来 pnq 发布时间:2023-11-18 11:12:41
标签:Python,迷宫,自动寻路
Python深搜版:
核心在于带随机的深搜(见代码第23到27行,其实也可以用22行代替这几行代码,你可以试着把第24行的数字4改大或者改小,即调整随机程度)
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:
坐标系有翻转,控制台中的左上角对应图片中的左下角
其中bmpEditor不是官方库,代码地址(文件名为bmpEditor.py,和这以上代码放同一个路径下即可)
Python 广搜版
在队列的基础上把队列中的元素顺序打乱(第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)
效果:
相比深度优先的,这种迷宫会更加“直”一些
lua版:
大体上是深搜,加了一定的随机性使得搜索过程中有一定概率暂时放弃当前路径。见表stop_points,(第7行、第74行及其后面的repeat循环)
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
来源:https://blog.csdn.net/qq_44103902/article/details/113667106
0
投稿
猜你喜欢
- 如下:counter.htm<a href=counter.asp?save=123&url=http://127.0.0
- 前言本博客默认读者对神经网络与Tensorflow有一定了解,对其中的一些术语不再做具体解释。并且本博客主要以图片数据为例进行介绍,如有错误
- 一、subprocess以及常用的封装函数运行python的时候,我们都是在创建并运行一个进程。像Linux进程那样,一个进程可以fork一
- Python 字符串格式化使用 "字符 %格式1 %格式2 字符"%(变量1,变量2),%格式表示接受变量的类型。简单的
- 在一些微服务或web服务中我们难免需要日志功能,用来记录一些用户的登录记录,操作记录,以及一些程序的崩溃定位,执行访问定位等等;Python
- 本文实例为大家分享了python代码实现猜拳小游戏的具体代码,供大家参考,具体内容如下游戏实现具体功能原有的用户登录的信息均能保存在txt文
- 本文的爬虫教程分为四部: 1.从哪爬 where &nbs
- 一、数据的概括性度量1、统计学概括:统计学是应用数学的一个分支,主要通过利用概率论建立数学模型,收集所观察系统的数据,进行量化的分析、总结,
- 1 使用Flask处理表单什么是表单(Form)? 表单是搜集用户数据信息的各种表单元素的集合区域。它的作用是实现用户和服务器的数据交互。通
- 进行已经矢量化后的字符串数据,可以使用pandas的Series数据对象的map方法。这样,对于未经矢量化的数据也可以先进行数据的矢量化转换
- 置信椭圆原理及椭圆图形绘制置信椭圆长短轴计算def confidence_oval(self,factor, ppf_rate): &nbs
- 深度遍历:原则:从上到下,从左到右逻辑(本质用递归):1)、找根节点2)、找根节点的左边3)、找根节点的右边class Node(objec
- sys模块sys模块是与python解释器交互的一个接口sys.argv 命令行参数List,第一个元素是程序本身路径sys.
- 前言你是否曾经想将某张照片中的人物抠出来,然后拼接到其他图片上去,从而可以即使你在天涯海角,我也可以到此一游?专业点的人使用 PhotoSh
- 函数最重要的目的是方便我们重复使用相同的一段程序。将一些操作隶属于一个函数,以后你想实现相同的操作的时候,只用调用函数名就可以,而不需要重复
- 前言异常值是指样本中的个别值,也称为离群点,其数值明显偏离其余的观测值。常用检测方法3σ原则和箱型图。其中,3σ原则只适用服从正态分布的数据
- HAVE_VFORK 是一个宏定义,用于表示当前 Python 解释器是否支持 vfork() 系统调用。vfork() 是一个类似于 fo
- 天天敲代码的朋友,有没有想过代码也可以变得很酷炫又浪漫?今天就教大家用Python模拟出绽放的烟花,工作之余也可以随时让程序为自己放一场烟花
- 数据库中提取长长的文章,总是有碍网页的排版布局。所以,想固定地提取一部分字符,然后后面有……替代。相关推荐:当标题不能显示完整的时候 1、原
- 本文实例为大家分享了Python实现滑雪小游戏的具体代码,供大家参考,具体内容如下源码分享:import sysimport cfgimpo