Как добраться до конечной точки лабиринта?

Question

В моем коде в методе read_file Я читаю файл и возвращаю 2d массив, содержащий строки лабиринта. Например. [[1 0 0 0 0 1 0 0], [0 0 0 1 0 0 1 0 0]]

2 - начальная точка лабиринта, а 3 - конечная точка лабиринта.

import numpy as np

class Maze:
    @staticmethod
    def read_file(file):
        """ function that reads the file and returns the content of the file in an array """
        # dict for replacements
        replacements = {'*': 0, ' ': 1, 'A': 2, 'B': 3}
        # open and read file
        file = open(file, "r")
        lines = file.readlines()
        file.close()
        # row and col count
        rows = len(lines)
        cols = len(lines[0]) - 1
        # create array
        maze_array = np.zeros((rows, cols), dtype=int)
        # add lines to array
        for index, line in enumerate(lines):
            for i in range(0, len(line) - 1):
            # replace line content with the ones from the dictionary and add it to the array
            maze_array[index][i] = replacements.get(line[i], line[i])
        return maze_array

Теперь я хочу пройти через лабиринт и получить конечную точку, начиная с начальной. Для этого я написал метод под названием search . В этом методе я проверяю клетки лабиринта. Когда ячейка равна 3, я нашел конец лабиринта. «0» - это стена, а «1» - пустая ячейка, через которую я могу пройти. Пройдя через ячейки, я установил их на 4, чтобы пометить как посещенные. Тогда рекурсивные вызовы ниже.

     @staticmethod
    def search(x, y, array):
        """
           0: wall
           1: empty
           2: starting point
           3: ending point
           4: visited cell
        """
        if array[x][y] == 3:
            print('end at %d,%d' % (x, y))
            return True
        elif array[x][y] == 0:
            print('wall at %d,%d' % (x, y))
            return False
        elif array[x][y] == 4:
            print('visited at %d,%d' % (x, y))
            return False

        print('visiting %d,%d' % (x, y))

        array[x][y] == 4

        if ((x < len(array) - 1 and Maze.search(x + 1, y, array))
            or (y > 0 and Maze.search(x, y - 1, array))
            or (x > 0 and Maze.search(x - 1, y, array))
            or (y < len(array) - 1 and Maze.search(x, y + 1, array))):
        return True

    return False


def main():
    """ Launcher """
    # [1][1] is starting point
    array = Maze.read_file("maze-one.txt")
    Maze.search(1, 1, array)


if __name__ == "__main__":
    main()

Это не работает. Благодаря @Florian H я изменил свой код, но все равно получаю следующую ошибку:

 RecursionError: maximum recursion depth exceeded while calling a Python object

Но мне нужно пройти через весь лабиринт, чтобы получить конечную точку. Это возможно с рекурсивными вызовами или это слишком много? Есть ли другое решение, кроме использования рекурсивных вызовов?

Answer 1

Вы перезагружаете свой файл в рекурсивной функции с помощью

array = Maze.read_file('maze-one.txt')

на каждом шаге рекурсии, поэтому array[x][y] == 4 будет перезаписываться при перезагрузке каждый раз.Это означает, что ваш лабиринт всегда не посещается, а ваша рекурсия бесконечна.

отредактируйте свой комментарий

Я не говорю, что вы должны использовать глобальную переменную, но этобудет вариант.В вашем случае я бы предпочел параметр функции.

Прежде всего, вам не нужен ни параметр self в статическом методе, ни объект класса только со статическими элементами, но это другая тема имногое объяснить здесь.Вы можете прочитать о ООП самостоятельно.

Вы можете задать лабиринт в качестве параметра функции, например:

def search(x, y, array):
    ...

, чем вы вызываете его из основного метода, например:

def main():
    """ Launcher """
    # [1][1] is starting point
    Maze.search(1, 1, Maze.load_file('maze-one.txt'))

удалите строку load_file из вашей функции search и измените вызовы функций Maze.search в вашем методе поиска таким же образом.

 if ((x < len(array) - 1 and Maze.search(x + 1, y, array))...

Второе редактирование

Я на самом деле не понимаю, если часть вашей функции поиска.Но инстинктивно я бы разделил это на один, если это похоже на следующее:

if x < len(array) -1:
    if Maze.search(x + 1, y, array):
        return True

if y > 0:
    if Maze.search(x, y - 1, array):
        return True

if x > 0:
    if Maze.search(x - 1, y, array):
        return True

if y < len(array):
    Maze.search(x, y + 1, array):
        return True

return False