from random import randint
class Node:
def __init__(self, worth = None,
next_element = None):
self.val = worth
self.subsequent = next_element
class stack:
def __init__(self):
self.head = None
self.size = 0
def insert(self, information):
self.head = Node(information, self.head)
self.size += 1
def pop(self):
if self.size == 0:
return None
else:
returned = self.head.val
self.head = self.head.subsequent
self.size -= 1
return returned
def not_empty(self):
return bool(self.size)
def high(self):
return self.head.val
def random_maze_generator(r, c, P0, Pf):
ROWS, COLS = r, c
maze = record(record(0 for _ in vary(COLS))
for _ in vary(ROWS))
seen = record(record(False for _ in vary(COLS))
for _ in vary(ROWS))
earlier = record(record((-1, -1)
for _ in vary(COLS)) for _ in vary(ROWS))
S = stack()
S.insert(P0)
whereas S.not_empty():
x, y = S.pop()
seen[x][y] = True
if (x + 1 < ROWS) and maze[x + 1][y] == 1
and earlier[x][y] != (x + 1, y):
proceed
if (0 < x) and maze[x-1][y] == 1
and earlier[x][y] != (x-1, y):
proceed
if (y + 1 < COLS) and maze[x][y + 1] == 1
and earlier[x][y] != (x, y + 1):
proceed
if (y > 0) and maze[x][y-1] == 1
and earlier[x][y] != (x, y-1):
proceed
maze[x][y] = 1
to_stack = []
if (x + 1 < ROWS) and seen[x + 1][y] == False:
seen[x + 1][y] = True
to_stack.append((x + 1, y))
earlier[x + 1][y] = (x, y)
if (0 < x) and seen[x-1][y] == False:
seen[x-1][y] = True
to_stack.append((x-1, y))
earlier[x-1][y] = (x, y)
if (y + 1 < COLS) and seen[x][y + 1] == False:
seen[x][y + 1] = True
to_stack.append((x, y + 1))
earlier[x][y + 1] = (x, y)
if (y > 0) and seen[x][y-1] == False:
seen[x][y-1] = True
to_stack.append((x, y-1))
earlier[x][y-1] = (x, y)
pf_flag = False
whereas len(to_stack):
neighbour = to_stack.pop(randint(0, len(to_stack)-1))
if neighbour == Pf:
pf_flag = True
else:
S.insert(neighbour)
if pf_flag:
S.insert(Pf)
x0, y0 = P0
xf, yf = Pf
maze[x0][y0] = 2
maze[xf][yf] = 3
return maze
if __name__ == "__main__":
N = 5
M = 5
P0 = (0, 0)
P1 = (4, 4)
maze = random_maze_generator(N, M, P0, P1)
for line in maze:
print(line)
