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[0] = "#"
row[-1] = "#"
maze.append(row)
maze.append(["#"] * 40)
#Add start and end values
maze[start_x][start_y] = "S"
maze[end_x][end_y] = "E"
#Add random walls
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[0][0]][spaces[0][1]] not in "^v<>#oS"
can_go_south = GRID[spaces[1][0]][spaces[1][1]] not in "^v<>#oS"
can_go_east = GRID[spaces[2][0]][spaces[2][1]] not in "^v<>#oS"
can_go_west = GRID[spaces[3][0]][spaces[3][1]] 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[0]
south_position = spaces[1]
east_position = spaces[2]
west_position = spaces[3]
#Calculate distance from position to E
distance_to_end_after_north = calculate_distance(north_position[0], north_position[1], 1, 1)
distance_to_end_after_south = calculate_distance(south_position[0], south_position[1], 1, 1)
distance_to_end_after_east = calculate_distance(east_position[0], east_position[1], 1, 1)
distance_to_end_after_west = calculate_distance(west_position[0], west_position[1], 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[0][0], spaces[0][1]
#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[1][0], spaces[1][1]
#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[2][0], spaces[2][1]
#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[3][0], spaces[3][1]
#Now, just check if it can
if can_go_north:
if can_go_east:
GRID[x][y] = go_right
return spaces[2][0], spaces[2][1]
if can_go_west:
GRID[x][y] = go_left
return spaces[3][0], spaces[3][1]
GRID[x][y] = go_up
return spaces[0][0], spaces[0][1]
if can_go_south:
if can_go_east:
GRID[x][y] = go_right
return spaces[2][0], spaces[2][1]
if can_go_west:
GRID[x][y] = go_left
return spaces[3][0], spaces[3][1]
GRID[x][y] = go_down
return spaces[1][0], spaces[1][1]
if can_go_east:
if can_go_north:
GRID[x][y] = go_up
return spaces[0][0], spaces[0][1]
if can_go_south:
GRID[x][y] = go_down
return spaces[1][0], spaces[1][1]
GRID[x][y] = go_right
return spaces[2][0], spaces[2][1]
if can_go_west:
if can_go_north:
GRID[x][y] = go_up
return spaces[0][0], spaces[0][1]
if can_go_south:
GRID[x][y] = go_down
return spaces[1][0], spaces[1][1]
GRID[x][y] = go_left
return spaces[3][0], spaces[3][1]
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))
