Skip to content

Instantly share code, notes, and snippets.

@joelchrono12
Created November 9, 2022 04:00
Show Gist options
  • Save joelchrono12/1347db84f67530fde98eac77e3c94e53 to your computer and use it in GitHub Desktop.
Save joelchrono12/1347db84f67530fde98eac77e3c94e53 to your computer and use it in GitHub Desktop.
A simple wall following algorithm that can solve arrays of 1s and 0s
#!/usr/bin/python3
# import random
import time
import os
def get_initial_position(array):
last_row = array[len(array)-1]
last_row_index = array.index(last_row)
for item in last_row:
if item == 1:
current_x_position=last_row.index(item)
print(current_x_position,last_row_index)
return current_x_position, len(array)-1
def get_exit(array):
print("Getting exit")
for item in array[0]:
if item == 1:
index = array[0].index(item)
return index, 0
# Check to see if we are safe to move West(left) by making sure we are in the
# bounds of the maze and not a wall
def checkXWest():
if (current_x-1<0 or maze[current_y][current_x-1] == 0): return False
else: print("West is available"); return True
# Check to see if we are safe to move East(right) by making sure we are in the
# bounds of the maze and not a wall
def checkXEast():
if (current_x+1 >= columns or maze[current_y][current_x+1] == 0): return False
else: print("East is available"); return True
# Check to see if we are safe to move North(up) by making sure we are in the
# bounds of the maze and not a wall
def checkYNorth():
if (current_y-1 < 0 or maze[current_y-1][current_x] == 0): return False
else: print("North is available"); return True
# Check to see if we are safe to move South(down) by making sure we are in
# the bounds of the maze and not a wall
def checkYSouth():
if (current_y+1 >= rows or maze[current_y+1][current_x] == 0): return False
else: print("South is available"); return True
def check_exit():
# print("Checking exit")
if (current_x == exit_x and current_y == exit_y): return 1
else: return 0
def print_maze(maze):
for x in maze:
for y in x:
if y == 1: y = "."
elif y == 0: y = "~"
else: y = "X"
print(y, end=" ")
print()
# print(row)
# Example maze
maze = [
[0,0,0,1,0,0,0,0,0,0,0],
[0,0,0,1,0,0,0,1,0,0,0],
[0,0,0,1,0,0,0,1,0,0,0],
[0,0,0,1,1,1,1,1,1,1,0],
[0,0,0,0,0,0,0,1,0,0,0],
[0,1,1,1,1,1,1,1,0,0,0],
[0,1,0,0,0,0,0,0,0,0,0],
[0,1,0,0,0,0,0,1,0,0,0],
[0,1,1,1,1,1,1,1,1,0,0],
[0,0,0,0,1,0,0,1,0,0,0],
[0,0,0,0,1,0,0,0,0,0,0],
]
print_maze(maze)
start = input("Input any key to solve the maze")
entry_x, entry_y= get_initial_position(maze)
exit_x, exit_y = get_exit(maze)
current_x, current_y = entry_x, entry_y
previous_x, previous_y = entry_x, entry_y+1
orientationX = current_x - previous_x
orientationY = current_y - previous_y
maze[current_y][current_x] = 8
columns = len(maze[0])
rows = len(maze)
print("Columns: ",columns)
print("Rows: ",rows)
print("Entrance is at: ", current_x, current_y)
print( "Exit is at: ",exit_x,exit_y )
# De esta manera, estamos viendo hacia el norte
finish = 0
while finish == 0:
time.sleep(.2)
os.system("clear")
#If orientationX is 1, we stepped left. Else, right
orientationX = current_x - previous_x
#If orientationX is 1, we stepped up. Else, down
orientationY = current_y - previous_y
print("Your orientation is: ",orientationX, orientationY)
print("Your position is: ",current_x, current_y)
if (orientationY == -1 and orientationX == 0):
direction = "north"
elif (orientationY == 1 and orientationX == 0):
direction = "south"
elif (orientationX == 1 and orientationY == 0):
direction = "east"
elif (orientationX == -1 and orientationY == 0):
direction = "west"
else:
print("Something with direction is wrong")
print("Your direction is: ", direction)
previous_x = current_x
previous_y = current_y
if direction == "north":
if checkXEast(): # If we can go right, we step right
current_x += 1
# If we can't go right, we go up
elif checkYNorth():
# Decrementing our Y coordinate means we step up
current_y-=1
#If not up either, we try to go left
elif checkXWest():
# Decrementing our X coordinate mimics going left
current_x-=1
# If we can't go any of the other directions, we must step down*/
elif checkYSouth():
# incrementing our Y coordinate mimics heading down
current_y += 1
maze[current_y][current_x]=8;
elif direction == "south":
if checkXWest():
current_x-=1
elif checkYSouth():
current_y += 1
elif checkXEast():
current_x += 1
elif checkYNorth():
current_y-=1
maze[current_y][current_x]=8;
elif direction == "east":
if checkYSouth():
current_y += 1
elif checkXEast():
current_x += 1
elif checkYNorth():
current_y-=1
elif checkXWest():
current_x-=1
maze[current_y][current_x]=8;
elif direction == "west":
if checkYNorth():
current_y-=1
elif checkXWest():
current_x-=1
elif checkYSouth():
current_y += 1
elif checkXEast():
current_x += 1
maze[current_y][current_x]=8;
finish = check_exit()
print_maze(maze)
print("\nITS DONE!")
print_maze(maze)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment