```import random

SIZE = 19
CELL_SIZE = 100 / SIZE
MATRIX_SIZE = SIZE * SIZE

def mset(matrix, point, value):
matrix[SIZE * point[0] + point[1]] = value

def mget(matrix, point):
return matrix[SIZE * point[0] + point[1]]

def wall_neighbors(cell):
x = cell[0]
y = cell[1]
n = []
if x > 2:
n.append((x - 1, y))
if y > 2:
n.append((x, y - 1))
if x < SIZE - 3:
n.append((x + 1, y))
if y < SIZE - 3:
n.append((x, y + 1))
return n

def cell_neighbors(wall):
x = wall[0]
y = wall[1]
n = []
if x % 2 == 0:
if x > 0:
n.append((x - 1, y))
if x < SIZE - 1:
n.append((x + 1, y))
else:
if y > 0:
n.append((x, y - 1))
if y < SIZE - 1:
n.append((x, y + 1))
return n

def generate_maze():
maze = [(i % SIZE) % 2 == 0 or (i * SIZE) % 2 == 1 for i in range(MATRIX_SIZE)]
walls = set()
visited = set()
point = (1, 1)
walls.update(wall_neighbors(point))
while len(walls) > 0:
wall = random.sample(walls, 1)[0]
walls.remove(wall)
count = 0
for n in cell_neighbors(wall):
if n in visited:
count += 1
else:
unvisited = n
if count == 1:
mset(maze, wall, False)
walls.update(wall_neighbors(unvisited))
return maze

def draw_map(maze):
for x in range(SIZE):
for y in range(SIZE):
color = 'black' if mget(maze, (x, y)) else 'white'
Rectangle(width=CELL_SIZE,height=CELL_SIZE,x=(x+.5)*CELL_SIZE,y=(y+.5)*CELL_SIZE,color=color)

def maze_neighbors(maze, point):
x = point[0]
y = point[1]
n = []
if x > 1 and not mget(maze, (x - 1, y)):
n.append((x - 1, y))
if y > 1 and not mget(maze, (x, y - 1)):
n.append((x, y - 1))
if x < SIZE - 2 and not mget(maze, (x + 1, y)):
n.append((x + 1, y))
if y < SIZE - 2 and not mget(maze, (x, y + 1)):
n.append((x, y + 1))
return n

def find_distances(maze, player, target):
distances = [MATRIX_SIZE for _ in range(MATRIX_SIZE)]
visited = set()
todo = [target]
todo_index = 0
mset(distances, target, 0)
found = False
point = todo[todo_index]
todo_index += 1
if point == player:
found = True
else:
value = mget(distances, point)
for n in maze_neighbors(maze, point):
if n not in visited:
mset(distances, n, value + 1)
todo.append(n)
return distances

def find_next(maze, distances, point):
best = MATRIX_SIZE
top = None
for n in maze_neighbors(maze, point):
distance = mget(distances, n)
if distance < best:
best = distance
top = n

center = (SIZE // 2, SIZE // 2)
targets = [(SIZE - 2, 1), (SIZE - 2, SIZE - 2), (1, SIZE - 2), (1, 1), center]
for _ in range(5):
x = random.randint(1, SIZE // 2) * 2 - 1
y = random.randint(1, SIZE // 2) * 2 - 1
targets.append((x, y))
random.shuffle(targets)

target = targets[0]
player = targets[-1]
maze = generate_maze()
draw_map(maze)

player_circle = Circle(width=CELL_SIZE,height=CELL_SIZE,x=(player[0]+.5)*CELL_SIZE,y=(player[1]+.5)*CELL_SIZE,color='red')
target_circle = Circle(width=CELL_SIZE,height=CELL_SIZE,x=(target[0]+.5)*CELL_SIZE,y=(target[1]+.5)*CELL_SIZE,color='blue')

for target in targets:
distances = find_distances(maze, player, target)

with animation(duration = 0.001):
target_circle.x = (target[0]+.5)*CELL_SIZE
target_circle.y = (target[1]+.5)*CELL_SIZE

while player != target:
with animation(duration = 0.25):
player = find_next(maze, distances, player)
player_circle.x = (player[0]+.5)*CELL_SIZE
player_circle.y = (player[1]+.5)*CELL_SIZE```

# Maze Solver

by Scepheo

Created 1 year, 8 months ago.