I. Introduction to the idea
- A 2-path maze can be formed by opening a suitable piece of wall on top of an existing single-path maze.
- An open wall cannot be too close to an existing path.
- 1. perform a breadth-first search starting at the start and end points, and for each cell in the maze record the number of steps the cell takes away from the start and end points.
- 2. Split the maze into two parts by putting all cells closer to the beginning into the start set and all cells closer to the goal into the end set.
- 3. Choose any wall that separates the two areas and take it apart to create a 2-way maze.
- If you want to generate the shortest pathway you can choose the wall with the largest difference in distance between neighboring grids to split, and in general these two pathways are also farther apart.
II. Illustrations
III. Subregional presentation codes
#!/usr/bin/python3.7
# -*- coding: utf-8 -*-
import random
import pygame
#import depth_maze
import maze
#import aldous_broder_maze
() # Initialize pygame
size = width, height = 800, 600 # Set window size
screen = .set_mode(size) # Display window
# Color
diamond_color_size = 8
COLOR_RED, COLOR_BLUE, COLOR_GREEN, COLOR_YELLOW, COLOR_BLACK, COLOR_GREY, COLOR_GOLDEN, COLOR_NO_DIAMOND = list(range(
diamond_color_size))
COLOR = {
COLOR_RED: (255, 0, 0),
COLOR_BLUE: (0, 0, 255),
COLOR_GREEN: (0, 255, 0),
COLOR_YELLOW: (255, 255, 0),
COLOR_BLACK: (0, 0, 0),
COLOR_GREY: (250, 240, 230),
COLOR_GOLDEN : (255,215,0),
COLOR_NO_DIAMOND: (100, 100, 100),
}
# Lattice size
DIAMOND_LEN = 20
DIAMOND_SIZE = (DIAMOND_LEN, DIAMOND_LEN)
# Blue plaid
DIAMOND=(DIAMOND_SIZE).convert()
(COLOR[COLOR_BLUE])
# Green plaid
DIAMOND_GREEN=(DIAMOND_SIZE).convert()
DIAMOND_GREEN.fill(COLOR[COLOR_GREEN])
# Red plaid
DIAMOND_RED=(DIAMOND_SIZE).convert()
DIAMOND_RED.fill(COLOR[COLOR_RED])
# Yellow plaid
DIAMOND_YELLOW=(DIAMOND_SIZE).convert()
DIAMOND_YELLOW.fill(COLOR[COLOR_YELLOW])
# The plaid of gray #
DIAMOND_GREY=(DIAMOND_SIZE).convert()
DIAMOND_GREY.fill(COLOR[COLOR_GREY])
# Fonts
use_font = ("", 16)
use_font12 = ("", 12)
# Background
background=(size).convert()
(COLOR[COLOR_BLACK])
# Text
score_surface = use_font.render("Find the end.", True, COLOR[COLOR_BLACK], COLOR[COLOR_GREY])
# Time
clock = ()
##############################################
# Lattice access markers x,y,0, right wall x,y,1, lower wall x,y,2
##############################################
# Marker
NOWALL= # Without walls
WALL= # With walls
WALL2=maze.WALL2 # With walls
VISIT= # Visited
NOVISIT= # Never been there #
VERTICAL = # Vertical
HORIZONTAL = # Horizontal
INFINITE = # Infinity
INFINITE = # Infinity
#
def FindNext(pathList, walls, grids, rows, cols):
nextList = [] # Next
for node in pathList:
r, c = node
l = grids[r][c]
nl=l+1
# Accessible locations
if r>0 and NOWALL == walls[r][c][1] and INFINITE == grids[r-1][c]:
# move = 'u'
nr=r-1
nc=c
if (nr,nc) not in nextList:
((nr,nc))
grids[nr][nc] = l+1
if c>0 and NOWALL == walls[r][c][0] and INFINITE == grids[r][c-1]:
# move = 'l'
nr=r
nc=c-1
if (nr,nc) not in nextList:
((nr,nc))
grids[nr][nc] = l+1
if c<cols-1 and NOWALL == walls[r][c+1][0] and INFINITE == grids[r][c+1] :
# move='r'
nr=r
nc=c+1
if (nr,nc) not in nextList:
((nr,nc))
grids[nr][nc] = l+1
if r<rows-1 and NOWALL == walls[r+1][c][1] and INFINITE == grids[r+1][c] :
# move='d'
nr=r+1
nc=c
if (nr,nc) not in nextList:
((nr,nc))
grids[nr][nc] = l+1
return nextList
def draw_diamond(r,c, screen, POSX, POSY, diamod):
px,py=POSX + 1 + (c) * DIAMOND_SIZE[0], POSY + 1 + (r) * DIAMOND_SIZE[1]
# Marked visited grids
(diamod, (px, py))
return
def draw_diamond_and_str(r,c, screen, POSX, POSY, diamod, use_font, string, color, color_back):
px,py=POSX + 1 + (c) * DIAMOND_SIZE[0], POSY + 1 + (r) * DIAMOND_SIZE[1]
# Marked visited grids
(diamod, (px, py))
distance_surface = use_font.render(string, True, color, color_back)
(distance_surface, (px, py))
return
# Sample algorithm
def multipath_maze_demo(rows, cols):
#walls = maze.aldous_broder_maze(rows, cols)
#walls = maze.depth_maze(rows, cols)
#walls = maze.kruskal_maze(rows, cols)
#walls = maze.prim_maze(rows, cols)
#walls = maze.wilson_maze(rows, cols)
walls = maze.wilson_maze(rows, cols)
POSX=40
POSY=40
# Initialization not accessed
grids=[[ INFINITE for i in range(cols)]for j in range(rows)]
# Starting point
# Marking the maze
r=0
c=0
findEndPoint=False
findPath=False
# Starting point
startPoint=(r,c)
# The end point
stopPoint=(rows-1,cols-1)
#
mainList=[] # Primary path
beginList=[startPoint]
endList=[stopPoint]
grids[r][c]=0 # Marker has traveled the grid distance
grids[stopPoint[0]][stopPoint[1]]=0
# Grids not visited
notUseGrids = []
for tr in range(rows):
for tc in range(cols):
((tr,tc))
beginMap=beginList
endMap=endList
while True:
for event in ():
if == :
return
if notUseGrids:
beginNextList = [] # Next
for node in beginList:
r, c = node
l = grids[r][c]
# Accessible locations
if r>0 and NOWALL == walls[r][c][1] and INFINITE == grids[r-1][c]:
# move = 'u'
nr=r-1
nc=c
if (nr,nc) not in beginNextList:
((nr,nc))
grids[nr][nc] = l+1
if c>0 and NOWALL == walls[r][c][0] and INFINITE == grids[r][c-1]:
# move = 'l'
nr=r
nc=c-1
if (nr,nc) not in beginNextList:
((nr,nc))
grids[nr][nc] = l+1
if c<cols-1 and NOWALL == walls[r][c+1][0] and INFINITE == grids[r][c+1] :
# move='r'
nr=r
nc=c+1
if (nr,nc) not in beginNextList:
((nr,nc))
grids[nr][nc] = l+1
if r<rows-1 and NOWALL == walls[r+1][c][1] and INFINITE == grids[r+1][c] :
# move='d'
nr=r+1
nc=c
if (nr,nc) not in beginNextList:
((nr,nc))
grids[nr][nc] = l+1
# Next lap
beginList = beginNextList
beginMap = beginMap + beginNextList
# end
endNextList = [] # Next
for node in endList:
r, c = node
l = grids[r][c]
# Accessible locations
if r>0 and NOWALL == walls[r][c][1] and INFINITE == grids[r-1][c]:
# move = 'u'
nr=r-1
nc=c
if (nr,nc) not in endNextList:
((nr,nc))
grids[nr][nc] = l+1
if c>0 and NOWALL == walls[r][c][0] and INFINITE == grids[r][c-1]:
# move = 'l'
nr=r
nc=c-1
if (nr,nc) not in endNextList:
((nr,nc))
grids[nr][nc] = l+1
if c<cols-1 and NOWALL == walls[r][c+1][0] and INFINITE == grids[r][c+1] :
# move='r'
nr=r
nc=c+1
if (nr,nc) not in endNextList:
((nr,nc))
grids[nr][nc] = l+1
if r<rows-1 and NOWALL == walls[r+1][c][1] and INFINITE == grids[r+1][c] :
# move='d'
nr=r+1
nc=c
if (nr,nc) not in endNextList:
((nr,nc))
grids[nr][nc] = l+1
# Next lap
endList = endNextList
endMap = endMap + endNextList
elif findEndPoint and not findPath:
((r,c))
l = grids[r][c]
nl=l-1
# Recent
if r>0 and NOWALL == walls[r][c][1] and nl == grids[r-1][c]:
# move = 'u'
nr=r-1
nc=c
if c>0 and NOWALL == walls[r][c][0] and nl == grids[r][c-1]:
# move = 'l'
nr=r
nc=c-1
((nr,nc))
if c<cols-1 and NOWALL == walls[r][c+1][0] and nl == grids[r][c+1] :
# move='r'
nr=r
nc=c+1
if r<rows-1 and NOWALL == walls[r+1][c][1] and nl == grids[r+1][c] :
# move='d'
nr=r+1
nc=c
# Finding the starting point
if 0 == nl:
((nr,nc))
findPath = True
r,c=nr,nc
(background, (0, 0))
# Plaid
for cx in range(cols):
for ry in range(rows):
px,py=POSX + 1 + (cx) * DIAMOND_SIZE[0], POSY + 1 + (ry) * DIAMOND_SIZE[1]
# Marked visited grids
if == grids[ry][cx]:
draw_diamond(ry, cx, screen, POSX, POSY, DIAMOND)
else:
s = "{}".format(grids[ry][cx])
draw_diamond_and_str(ry, cx, screen, POSX,POSY, DIAMOND_GREY, use_font12, s, COLOR[COLOR_BLACK], COLOR[COLOR_GREY])
# Enclave
for pos in beginMap:
s = "{}".format(grids[pos[0]][pos[1]])
draw_diamond_and_str(pos[0], pos[1], screen, POSX,POSY, DIAMOND_GREEN, use_font12, s, COLOR[COLOR_BLACK], COLOR[COLOR_GREEN])
for pos in endMap:
s = "{}".format(grids[pos[0]][pos[1]])
draw_diamond_and_str(pos[0], pos[1], screen, POSX,POSY, DIAMOND_YELLOW, use_font12, s, COLOR[COLOR_BLACK], COLOR[COLOR_YELLOW])
# Circular outer ring
if beginList and not mainList:
for pos in beginList:
s = "{}".format(grids[pos[0]][pos[1]])
draw_diamond_and_str(pos[0], pos[1], screen, POSX,POSY, DIAMOND_RED, use_font12, s, COLOR[COLOR_BLACK], COLOR[COLOR_RED])
for pos in endList:
s = "{}".format(grids[pos[0]][pos[1]])
draw_diamond_and_str(pos[0], pos[1], screen, POSX,POSY, DIAMOND_RED, use_font12, s, COLOR[COLOR_BLACK], COLOR[COLOR_RED])
# Path
if mainList:
for pos in mainList:
s = "{}".format(grids[pos[0]][pos[1]])
draw_diamond_and_str(pos[0], pos[1], screen, POSX,POSY, DIAMOND_YELLOW, use_font12, s, COLOR[COLOR_BLACK], COLOR[COLOR_YELLOW])
# r,c
px,py=POSX + 1 + (c) * DIAMOND_SIZE[0], POSY + 1 + (r) * DIAMOND_SIZE[1]
(DIAMOND_GREEN, (px, py))
s = "{}".format(grids[r][c])
distance_surface = use_font12.render(s, True, COLOR[COLOR_BLACK], COLOR[COLOR_GREEN])
(distance_surface, (px, py))
# Painted facades
(screen, COLOR[COLOR_RED], (POSX + 0, POSY + 0, DIAMOND_LEN*cols+1, DIAMOND_LEN*rows+1), 2)
# Drawing walls that aren't open
for cx in range( cols):
for ry in range(rows):
px,py=POSX + 1 + (cx) * DIAMOND_SIZE[0], POSY + 1 + (ry) * DIAMOND_SIZE[1]
color = COLOR[COLOR_BLACK]
if == walls[ry][cx][0]:
(screen, color, (px, py), (px, py+DIAMOND_LEN), 2)
if == walls[ry][cx][1]:
(screen, color, (px, py), (px+DIAMOND_LEN, py), 2)
# Print text alerts
if findEndPoint:
(score_surface, (POSX+50, POSY+rows*22))
# Frame rate
(25)
()
return
# main
if __name__ == "__main__":
'''main'''
multipath_maze_demo(20, 30)
To this article on how to teach you to use Python to achieve multi-path maze is introduced to this article, more related Python to achieve multi-path maze content, please search for my previous posts or continue to browse the following related articles I hope you will support me in the future!