stateSearchProgram.py

import time

def move_right(current_coodinate):
    temp_state = { "x":current_coodinate['x'],"y": current_coodinate['y']}
    y_position = temp_state['y'] + 1
    temp_state['y'] = y_position
    return temp_state

def move_left(current_coodinate):
    temp_state = { "x":current_coodinate['x'],"y": current_coodinate['y']}
    y_position = temp_state['y'] - 1
    temp_state['y'] = y_position
    return temp_state

def move_up(current_coodinate):
    temp_state = { "x":current_coodinate['x'],"y": current_coodinate['y']} 
    x_position = temp_state['x'] - 1
    temp_state['x'] = x_position
    return temp_state

def move_down(current_coodinate):
    temp_state = { "x":current_coodinate['x'],"y": current_coodinate['y']} 
    x_position = temp_state['x'] + 1
    temp_state['x'] = x_position
    return temp_state

#for now hard code bonds since its a 4x4 matrix maze checks if the state is out of bound or not 
def checkBonds(current_coordinates):
    if(0 <= current_coordinates['x'] <= 9) and (0 <= current_coordinates['y'] <= 9):
        return True
    
    return False

#checks if the state is a wall or not 
def checkWallState(current_coordinates, maze):
    x = current_coordinates['x']
    y = current_coordinates['y']
    if(maze[x][y] == '#'):
        return True
    
    return False

def checkVistedState(stack_path, current_coordinates):
    if current_coordinates in stack_path:
        return True
    
    return False
 
def checkExistState(current_coordinates, maze):
    x = current_coordinates['x']
    y = current_coordinates['y']
    if(maze[x][y] == 'E'):
        return True
    
    return False

def peek(stack):
    return stack[-1]

def runMaze(maze,stack_path):
    for position in stack_path:
        current_position = position
        for row in range(10):
            for col in range(10):
                if row == current_position['x'] and col == current_position['y']:
                    print("'S' ",end="")
                else:
                    print(f"'{maze[row][col]}' ",end="")
            print()
            time.sleep(0.1)
        print()
        print()
        

maze = [
    ['#', '#', '#', '#', '#', '#', '#', '#', '#', '#'],
    ['S', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#'],
    ['#', '#', '#', '#', ' ', '#', '#', '#', ' ', '#'],
    ['#', ' ', ' ', ' ', ' ', ' ', '#', ' ', ' ', '#'],
    ['#', ' ', '#', '#', ' ', '#', '#', ' ', '#', '#'],
    ['#', ' ', ' ', '#', ' ', ' ', '#', ' ', ' ', '#'],
    ['#', '#', ' ', '#', ' ', '#', '#', '#', ' ', '#'],
    ['#', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', '#'],
    ['#', ' ', '#', '#', ' ', '#', ' ', '#', ' ', '#'],
    ['#', '#', '#', '#', '#', '#', 'E', '#', '#', '#']
]

#start co ordinates
currentCo_ordinates = {"x":1, "y":0}

#this is to store final path from start to exit
stack_path = []

#add current postion
stack_path.append(currentCo_ordinates)

#this is to store current state posible paths
stack_possible_transactions = []

#explore direct stack
explore_state = []

#mutliple route
multi_route = False


#for keeping how deep you went 
root_count = []

#counting current branch
count_path = 0


#for now im working with a fixed maze as practice to create a more generic approach to finding a way out of 
#any maze using state search technique 
while True:
    
    #check if we are in exist state
    if(checkExistState(currentCo_ordinates,maze)):
        if currentCo_ordinates not in stack_path:
            stack_path.append(currentCo_ordinates)
        break
    
    #check which direction can you move 
    # bound are x should be 0 < x < 10 and 0 < y < 10 (bounds are hard coded for now)
        
    #check the move if its valid and add it to possible_path stack
    #its should be within maze bound and should not be a wall and it should not be a state thats been visited 
    
    #checking up direction
    moveUpCheck = move_up(currentCo_ordinates)
    if checkBonds(moveUpCheck) and not checkWallState(moveUpCheck,maze) and not checkVistedState(stack_path,moveUpCheck):
        stack_possible_transactions.append(moveUpCheck)
   
    #checking down direction
    moveDownCheck = move_down(currentCo_ordinates)
    if checkBonds(moveDownCheck) and not checkWallState(moveDownCheck,maze) and not checkVistedState(stack_path,moveDownCheck):
        stack_possible_transactions.append(moveDownCheck)
    
    #checking left direction
    moveLeftCheck = move_left(currentCo_ordinates)
    if checkBonds(moveLeftCheck) and not checkWallState(moveLeftCheck,maze) and not checkVistedState(stack_path,moveLeftCheck):
        stack_possible_transactions.append(moveLeftCheck)
    
    #checking right  direction
    moveRightCheck = move_right(currentCo_ordinates)
    if checkBonds(moveRightCheck) and not checkWallState(moveRightCheck,maze) and not checkVistedState(stack_path,moveRightCheck):
        stack_possible_transactions.append(moveRightCheck)
        
    
    if(len(stack_possible_transactions) == 0):
        for i in range(count_path):
            if(len(stack_path) !=0):
                stack_path.pop()
        
        #set counth path to prevouse count
        if len(root_count) != 0:
            count_path += root_count.pop()-1
            
        currentCo_ordinates = explore_state.pop()
        stack_path.append(currentCo_ordinates)
        continue
    
    if(len(stack_possible_transactions) == 1):
        if(multi_route):
            count_path += 1
            
        currentCo_ordinates = stack_possible_transactions.pop()
        stack_path.append(currentCo_ordinates)
        continue
    
    if(len(stack_possible_transactions) >= 2):
        multi_route = True
        
        #add to root count and reset the count to 0 for the new branch 
        if count_path != 0:
            root_count.append(count_path)
            count_path = 1
        
        currentCo_ordinates = stack_possible_transactions.pop()
        stack_path.append(currentCo_ordinates)
        explore_state.append(stack_possible_transactions.pop())
        continue
        
print("exist path: ",stack_path)
#run maze 
runMaze(maze, stack_path)