wozek-projekt/bfs.py

from typing import List
from num_map import num_matrix

MAX_ROWS = 15
MAX_COLS = 25


class State:
    """
    Directions
    UP: 0
    RIGHT: 1
    DOWN: 2
    LEFT: 3
    """
    def __init__(self, row, column, direction):
        self.direction = direction
        self.row = row
        self.column = column

    def rotate_left(self):
        return (self.direction - 1) % 4

    def rotate_right(self):
        return (self.direction + 1) % 4


class Node:
    def __init__(self, state: "State", parent=None, action=None):
        self.state = state
        self.parent = parent
        self.action = action


def is_valid_move(num_map, target_row, target_column):
    if 0 <= target_row < MAX_ROWS and 0 < target_column < MAX_COLS:
        return True
    return False


def get_successor(state: "State", num_matrix):
    successors = list()
    direction = state.direction
    row = state.row
    col = state.column

    rotate_left = State(row=state.row, column=state.column, direction=state.rotate_left())
    rotate_right = State(row=state.row, column=state.column, direction=state.rotate_right())

    successors.append(('rotate_left', rotate_left))
    successors.append(('rotate_right', rotate_right))

    if direction == 0:
        if is_valid_move(num_map=num_matrix, target_row=row-1, target_column=col):
            forward = State(row=row-1, column=col, direction=direction)
            successors.append(('go', forward))
    elif direction == 1:
        if is_valid_move(num_map=num_matrix, target_row=row, target_column=col+1):
            forward = State(row=row, column=col+1, direction=direction)
            successors.append(('go', forward))
    elif direction == 2:
        if is_valid_move(num_map=num_matrix, target_row=row+1, target_column=col):
            forward = State(row=row+1, column=col, direction=direction)
            successors.append(('go', forward))
    elif direction == 3:
        if is_valid_move(num_map=num_matrix, target_row=row, target_column=col-1):
            forward = State(row=row, column=col-1, direction=direction)
            successors.append(('go', forward))

    return successors


def graphsearch(initial_state: State, mp=num_matrix, goal_list=(6, 1), fringe: List[Node] = None, explored: List[Node] = None):
    if fringe is None:
        fringe = list()
    if explored is None:
        explored = list()
    explored_states = set()
    fringe_states = set()

    fringe.append(Node(initial_state))
    fringe_states.add((initial_state.row, initial_state.column, initial_state.direction))

    while True:
        if not any(fringe):
            return []

        element = fringe.pop(0)
        fringe_states.remove((element.state.row, element.state.column, element.state.direction))

        if is_reached(goal_list, element.state):
            actions_sequence = [element.action]
            parent = element.parent

            while parent is not None:
                if parent.action is not None:
                    actions_sequence.append(parent.action)
                parent = parent.parent

            actions_sequence.reverse()
            return actions_sequence

        explored.append(element)
        explored_states.add((element.state.row, element.state.column, element.state.direction))

        for successor in get_successor(element.state, num_matrix=mp):
            successor_state = (successor[1].row, successor[1].column, successor[1].direction)

            if successor_state not in fringe_states and successor_state not in explored_states:
                new_node = Node(state=successor[1],
                                parent=element,
                                action=successor[0])
                fringe.append(new_node)
                fringe_states.add((new_node.state.row, new_node.state.column, new_node.state.direction))


def is_reached(goal_list, state: State):
    comp = (state.row, state.column)
    if comp == goal_list:
        return True
    return False


if __name__ == "__main__":
    initial_state = State(row=7, column=1, direction=1)
    print(graphsearch(initial_state=initial_state))