# Random Maze Pathfinder

I just finished a huge project of mine; a maze pathfinder. At the start, the maze that the program is traversing is randomly generated, with a 25% change to place a wall (#) at that position in the maze. The program uses the distance between every direction it can make at its current position, and takes the direction that puts the program closest to end. I'm looking for any feedback, as this is my first maze pathfinder. The real meat of the code is in the find_next_open_space function, which calculates the distance, makes the comparisons, and decides which direction to go.

Copy paste this code into a file, run it, and watch!

"""
Code written by: Linny
Github: https://github.com/Linnydude3347

This program demonstrates a pathfinding algorithm

"""

from os import system, name
import time
import random
import math

def calculate_distance(x1, y1, x2, y2):
return math.sqrt((x2 - x1)**2 + (y2 - y1)**2)

def print_grid(grid):
"""

Pretty prints the passed grid

Code from StackOverflow user "georg"
https://stackoverflow.com/a/13214945/8968906

"""
string = [[str(e) for e in row] for row in grid]
lens = [max(map(len, col)) for col in zip(*string)]
fmt = ' '.join('{{:{}}}'.format(x) for x in lens)
table = [fmt.format(*row) for row in string]
print('\n'.join(table))

def generate_maze(start_x, start_y, end_x, end_y):
"""
Generates a random maze
"""
maze = [["#"] * 40]
for _ in range(38):
row = [" "] * 40
row = "#"
row[-1] = "#"
maze.append(row)
maze.append(["#"] * 40)

maze[start_x][start_y] = "S"
maze[end_x][end_y] = "E"

for i, _ in enumerate(maze):
for j, _ in enumerate(maze[i]):
if maze[i][j] not in "#SE":
maze[i][j] = "#" if random.randint(1, 100) > 75 else " "
return maze

def clear_o(grid):
"""
Clears all "^v><" in the grid
"""
reset_grid = grid
for i, _ in enumerate(reset_grid):
for j, _ in enumerate(reset_grid[i]):
if reset_grid[i][j] in "^v><":
reset_grid[i][j] = " "
return reset_grid

def get_nsew_spaces(x, y):
"""
Returns a 2D array of the current spaces that are NSEW of passed (x, y)
No need to check bounds because outer layer will always be X
"""
north = [x - 1, y]
south = [x + 1, y]
east = [x, y + 1]
west = [x, y - 1]
return [north, south, east, west]

def find_next_open_space(x, y):
"""
Find the next available space, edits GRID to account for visitation,
and returns the x and y values of the new space
"""

spaces = get_nsew_spaces(x, y)

#Calculate boolean variables that determine if they can go a certain position
can_go_north = GRID[spaces][spaces] not in "^v<>#oS"
can_go_south = GRID[spaces][spaces] not in "^v<>#oS"
can_go_east = GRID[spaces][spaces] not in "^v<>#oS"
can_go_west = GRID[spaces][spaces] not in "^v<>#oS"

#Determine boolean determining what character to print when moving
go_up = "^" if GRID[x][y] != "S" else "S"
go_down = "v" if GRID[x][y] != "S" else "S"
go_right = ">" if GRID[x][y] != "S" else "S"
go_left = "<" if GRID[x][y] != "S" else "S"

#Get current positions of new spaces
north_position = spaces
south_position = spaces
east_position = spaces
west_position = spaces

#Calculate distance from position to E
distance_to_end_after_north = calculate_distance(north_position, north_position, 1, 1)
distance_to_end_after_south = calculate_distance(south_position, south_position, 1, 1)
distance_to_end_after_east = calculate_distance(east_position, east_position, 1, 1)
distance_to_end_after_west = calculate_distance(west_position, west_position, 1, 1)

all_distances = []
if can_go_north:
all_distances.append(distance_to_end_after_north)
if can_go_south:
all_distances.append(distance_to_end_after_south)
if can_go_east:
all_distances.append(distance_to_end_after_east)
if can_go_west:
all_distances.append(distance_to_end_after_west)

#If going north is best option and can go north:
if can_go_north and distance_to_end_after_north == min(all_distances):
GRID[x][y] = go_up
return spaces, spaces

#If going south is best option and can go south
if can_go_south and distance_to_end_after_south == min(all_distances):
GRID[x][y] = go_down
return spaces, spaces

#If going east is best option and can go east
if can_go_east and distance_to_end_after_east == min(all_distances):
GRID[x][y] = go_right
return spaces, spaces

#If going west is best option and can go west
if can_go_west and distance_to_end_after_west == min(all_distances):
GRID[x][y] = go_left
return spaces, spaces

#Now, just check if it can

if can_go_north:
if can_go_east:
GRID[x][y] = go_right
return spaces, spaces
if can_go_west:
GRID[x][y] = go_left
return spaces, spaces
GRID[x][y] = go_up
return spaces, spaces

if can_go_south:
if can_go_east:
GRID[x][y] = go_right
return spaces, spaces
if can_go_west:
GRID[x][y] = go_left
return spaces, spaces
GRID[x][y] = go_down
return spaces, spaces

if can_go_east:
if can_go_north:
GRID[x][y] = go_up
return spaces, spaces
if can_go_south:
GRID[x][y] = go_down
return spaces, spaces
GRID[x][y] = go_right
return spaces, spaces

if can_go_west:
if can_go_north:
GRID[x][y] = go_up
return spaces, spaces
if can_go_south:
GRID[x][y] = go_down
return spaces, spaces
GRID[x][y] = go_left
return spaces, spaces

return -1, -1

def find(start_x, start_y):
"""
This is the main algorithm function, nagivating
GRID from the start node at (start_x, start_y)
"""

attempts = 1
current_x = start_x
current_y = start_y
current_marker = GRID[current_x][current_y]

while current_marker != "E":
last_spot_x = current_x
last_spot_y = current_y
current_x, current_y = find_next_open_space(current_x, current_y)

#Restart search
if current_x == -1 and current_y == -1:
attempts += 1
clear_o(GRID)
GRID[last_spot_x][last_spot_y] = "#"
current_x, current_y = start_x, start_y

current_marker = GRID[current_x][current_y]

system("cls") if name == 'nt' else system("clear")
print_grid(GRID)
time.sleep(0.05)
print(f"E found in {attempts} attempts!")

if __name__ == '__main__':

GRID = generate_maze(35, 32, 2, 2)

START = time.time()
find(35, 32)
END = time.time()
print("Time to solve: %.2f seconds!" % (END - START))

• This is neither here nor there, but... as you gain more experience programming, you'll be significantly redefining what counts as a huge project :) Sep 5 '19 at 3:50

## Type hints

Presumably all of the argument to calculate_distance, as well as the return value, are float. You should indicate so with PEP484 type hints.

## List literal unpacking

    row = [" "] * 40
row = "#"
row[-1] = "#"


can be

row = ['#', *[' ']*38, '#']


## Magic numbers

Assign 40 to something like GRID_SIZE. Rather than 38, write GRID_SIZE - 2.

## Don't abuse enumerate

for i, _ in enumerate(maze):


You don't actually use the value here, so instead, do something like

for i in range(len(maze)):


can_go_north = GRID[spaces][spaces] not in "^v<>#oS"
can_go_south = GRID[spaces][spaces] not in "^v<>#oS"
can_go_east = GRID[spaces][spaces] not in "^v<>#oS"
can_go_west = GRID[spaces][spaces] not in "^v<>#oS"


becomes

possible_directions = [
GRID[space][space] not in "^v<>#oS"
for space in spaces]
]


and so on for the other chunks of code that are repeated four times with small variations.

## Clear

First of all, this:

system("cls") if name == 'nt' else system("clear")


probably belongs in a utility method. Also, name is ambiguous enough that it probably shouldn't be stripped of its module namespace; i.e. just import os; os.name instead.