脚本之家，脚本语言编程技术及教程分享平台！
分类导航

Python|VBS|Ruby|Lua|perl|VBA|Golang|PowerShell|Erlang|autoit|Dos|bat|

服务器之家 - 脚本之家 - Python - Python实现随机生成迷宫并自动寻路

Python实现随机生成迷宫并自动寻路

2021-11-30 10:15WA的一声哭出来 pnq Python

最近在学习Python，正好今天在学习随机数，本文实现了Python实现随机生成迷宫并自动寻路，感兴趣的可以了解一下

python深搜版：

核心在于带随机的深搜（见代码第23到27行，其实也可以用22行代替这几行代码，你可以试着把第24行的数字4改大或者改小，即调整随机程度）

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
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：

Python实现随机生成迷宫并自动寻路

Python实现随机生成迷宫并自动寻路

8181：

Python实现随机生成迷宫并自动寻路

Python实现随机生成迷宫并自动寻路

坐标系有翻转，控制台中的左上角对应图片中的左下角

其中bmpeditor不是官方库代码地址，（文件名为bmpeditor.py，和这以上代码放同一个路径下即可）

python 广搜版

在队列的基础上把队列中的元素顺序打乱（第24行）

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
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)

效果：

Python实现随机生成迷宫并自动寻路

Python实现随机生成迷宫并自动寻路

相比深度优先的，这种迷宫会更加“直”一些

lua版：

大体上是深搜，加了一定的随机性使得搜索过程中有一定概率暂时放弃当前路径。见表stop_points，（第7行、第74行及其后面的repeat循环）

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
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：

Python实现随机生成迷宫并自动寻路

8989

Python实现随机生成迷宫并自动寻路

到此这篇关于python实现随机生成迷宫并自动寻路的文章就介绍到这了,更多相关python生成迷宫并自动寻路内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家！

原文链接：https://blog.csdn.net/qq_44103902/article/details/113667106

  • Python
  • 迷宫
  • 自动寻路

    • 延伸 · 阅读

    精彩推荐
    最近更新
    编辑推荐
    阅读排行
    热门标签
    2048 　 6006 　 contextlib 　 SLOTS 　 MELIAE 　 FEEDPARSER 　 暂存 　 持久性管理 　 pickle模块 　 THREADING 　 reduce 　 nignx 　 装饰器 　 函数式编程 　 兔子毒药 　 监控文件 　 流量监控 　 Web框架 　 办公工具 　 PIL库 　 高斯模糊 　 wxPython 　 import 　 自定义模块 　 Python开发 　 元类 　 metaclass 　 魔术方法 　 DNSPod 　 动态解析域名 　
    © 2019-2023 脚本之家 | 服务器之家(www.zzvips.com)旗下站点 版权所有关于我们联系我们版权申明网站地图