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


猜你喜欢
- 时间序列预测时间序列是按照时间顺序排列的数据集合,在很多应用中都非常常见。时间序列分析是对这些数据进行分析和预测的过程。时间序列预测是该分析
- 1.简介本文将介绍首先为什么需要主动关闭goroutine,并介绍如何在Go语言中关闭goroutine的常见套路,包括传递终止信号和协程内
- 前言若电脑之前已经安装过vue-cli了,但是版本过低,比方说当前vue-cli的版本为2.9.6,然后我想升级到vue-cli的最新版本4
- 对称二叉树的含义非常容易理解,左右子树关于根节点对称,具体来讲,对于一颗对称二叉树的每一颗子树,以穿过根节点的直线为对称轴,左边子树的左节点
- 在IE中,在使用checkbox或radio时,你会发现有时不能通过CheckBoxObject.checked = true或CheckB
- 引言昨天把系分的项目又加了一点逻辑判断,比如已经下单的菜品不能减少,不能重复下单,应该先下单再支付等…弄完购物车的逻辑之后,发现一直没有管备
- 一、使用安装pip install mitmproxymitmproxy 是具有控制台界面的交互式,支持SSL的拦截代理mitmdump是m
- 前言首先,我们开发的项目会有多个版本.其次,我们的项目版本会随着更新越来越多,我们不可能因出了新版本就不维护旧版本了.那么,我们就需要对版本
- instanceof 运算符 和 is_a() 方法都是判断:某对象是否属于该类 或 该类是此对象的父类(用于确定一个 PHP 变量是否属于
- 简介Blade 是 Laravel 所提供的一个简单且强大的模板引擎。相较于其它知名的 PHP 模板引擎,Blade 并不会限制你必须得在视
- 前言最近发现了一个可以把照片美化的项目,自己玩了玩,挺有意思的,分享一下。Github地址:DPED项目地址下面来看看项目怎么玩?先放一些项
- 先解释一下这篇Blog延期的原因,本来已经准备好了全部内容,但是当我重新回顾实例三的时候,发现自己还是存在认知不足的地方,于是为了准确表述,
- 很早很早的时候,computer这个东西习惯于被称之为计算机,因为它的主要功能是完成一些科学计算的东西,我记得自己鼓捣它的时候,就是计算,根
- 关于current()函数: 每个数组中都有一个内部的指针指向它“当前的”单元,初始指向插入到数组中的第一个单元。用current()获取。
- 在批评Python的讨论中,常常说起Python多线程是多么的难用。还有人对 global interpreter lock(也被亲切的称为
- 一、效果展示1、俄罗斯方块这个应该是玩起来最最简单的了…2、扫雷运气好,点了四下都没踩雷哈哈…3、五子棋我是菜鸡,玩不赢电脑人…
- 1、enumerate返回针对序列类型的可迭代对象的枚举对象。2、eval取出字符串中的内容。将str中有效的表达式返回计算结果。3、exe
- 程序中常常需要复制一个对象, 按思路应该是这样的a = [1, 2, 3]b = a# [1, 2, 3]print b 已经复制好了,但是
- 本篇文章主要介绍了Python基于mysql实现学生管理系统,分享给大家,具体如下:import pymysqlimport redef i
- 1、使用函数模型API,新建一个model,将输入和输出定义为原来的model的输入和想要的那一层的输出,然后重新进行predict.#co