服务器之家

服务器之家 > 正文

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

时间：2021-11-30 10:15     来源/作者：WA的一声哭出来 pnq

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 迷宫 自动寻路 

相关文章

热门资讯

yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
2021年耽改剧名单 2021要播出的59部耽改剧列表
2021年耽改剧名单 2021要播出的59部耽改剧列表 2021-03-05
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
返回顶部