Алгоритм решения лабиринта зависает и продолжает работать «кругами» [закрыто] ⇐ Python

[Anonymous]

Я пытаюсь реализовать программу Python для решения лабиринтов:
Лабиринт выглядит примерно так:
│╶┘│┌┐ + ┘└┐└┐ │┌┘│╵├───┐│┌───┐│╵││┌─┘│││╷│┌─┐└┘┌┤└──┐│└─┐╷ │└ ┤┌┐└┐│╵│┌──┐┌┘└┐│╷└┘┌┐│╵││└┤┌─┐└┘┌┐┌┬╴┌┘│╶ ┬┘┌┐│┌┘└ ┐└┐└┐└┐└┐│╶┬╴└┘└┐└─┐┌┐╶┘┌┘││╶┘┌─┐╵│└┐└┤┌─┐ ┌─┘│┌─── ┐├┘│┌┤┌───┐│╷│└┤│└┐┌┘┌─┘│││╵└┐│└┘╶┬┐┌┐┌┘│├┘ ┌┐╵┌─┘└ ─┐│╶┬─┤├┘└┐└─┐└┐│┌┐┌─┘┌┘╵│╷└──┐└─┤│┌─┘└┼──┤╷││└ ┐┌┘ └┴─┬┘└┬┘│╷┌┴╴│└─┘│┌─┐│└┐└┐│└┘└┐╶┐│││└┘│┌─┘└ ──┐├┐╷└ ┘┌─┤└┐┌┘││└──┐└┘└┘┌┘│┌┘┌┘┌┘┌╴└─┘├┐└──┘│┌┬╴││ └─┘┌┐ └─┘│┌┐┌┘└┐├─┐┌┐╵│╵┌┐│└╴│╵└──┘└┼─╴└─┐│└┐┌┤│└─┐ ┌┘┌╴└ ┐╵│┌─┐┌┘└┤┌─┘│┌─┐╶─┬┘┌───┘┌┘╵└┘││╵┌┘│┌┐└┐┌┐└╴ ││└┐│ ┌┬───┘┌┐└┘│┌┐╵┌┤│╶┤╵└┴╴┌──┐│└┐│└┘┌┘└┬╴┌─┤╶┴┤ ┌┐╵││├ ┐└┴┐└┘╶┐└┐│└┘╷└┐╵┌──┘├┴╴┌─┘└┐└┐└┘│└┘╷┌┘└┘│ └┘╷├╴┌┤╵ + └┘└─┘ ╶┴┐├─┘└┘│╶┐└─┘┌┘┌┘┌┘└┐├──┐┌┘╶─┤││┌─┘┌
Очевидно, это не совсем так, я просто скопировал случайный раздел txt-файла, но вы поняли, лабиринт состоит из этих символов, начало в верхнем левом углу, а конец в правом нижнем углу< /strong>
Моя идея алгоритма
Я постараюсь кратко объяснить, как работает моя программа, чтобы вам было легче ее понять.
Программа отслеживает текущую позицию в лабиринте, на основе этой позиции определяет персонаж, на котором он сейчас стоит, и на основе этого определяет, в каком направлении она может идти дальше (функция get_directions()), некоторые недействительные направления удаляются из списка, возвращаемого функцией (направление, ведущее туда, откуда вы пришли, направления, ведущие в тупик)
Программа также отслеживает путь, который был пройден туда, где он находится в данный момент («вниз», «влево», «вверх», «вверх» и т. д.])
Затем программа пробует один из возможных путей. направлениях, он также отслеживает первое встреченное пересечение (любое место, из которого нужно идти более чем в одном направлении, исключая направление, ведущее назад) и последнее столкнулся с перекрестком, причина этого в том, что ЕСЛИ алгоритм заходит в тупик (возможных направлений движения 0), он возвращается назад по переменной path и всем символам на этом пути обратно от 0 до 1, что означает, что это направление ведет в тупик. Как только он достигнет последнего встреченного перекрестка, он возвращается к первому и снова пытается двигаться. Это (надеюсь) приведет к блокировке всех путей, ведущих в тупик, что приведет до конца.
Теперь, когда с этим покончено, вот фрагменты кода, я постараюсь сделать их как можно короче

Код: Выделить всё

# Based on the character, returns a list of possible move directions
def get_moves(maze ,pos):
c = maze[pos[0]][pos[1]][0]
if c == '─':
d = ["left", "right"]
return d
elif c == '╶':
d = ["right"]
return d
elif c == '╴':
d = ["left"]
# And the rest of the characters...

Код: Выделить всё

# Checks whether position to move to is blocked or available (position is only blocked if it leads nowhere)
def check_path(maze, pos, mv):
print(f"checking move '{mv}'...")
tmp_pos = move(mv, pos)
if opposite(mv) not in get_moves(maze, tmp_pos) or maze[tmp_pos[0]][tmp_pos[1]][1] == 1:
return False # Path is invalid or blocked
return True # Path is not blocked

Код: Выделить всё

# Returns the list of possible moves except for the last move made (To prevent going back and forth) and those moves that lead to a blocked path
def exclude_invalid(moves, last_move, maze, pos):
for m in moves: # for each 'm'ove in moves
if check_path(maze, pos, m) == False: # Check if path is valid
moves.remove(m)
if opposite(last_move) in moves:
moves.remove(opposite(last_move))
if moves == []:
return ["empty"]
return moves
else:
return moves

Код: Выделить всё

# Returns the position to the first encoutered crossroad and blocks each block until the last encoutered crossroad is passed
def backtrack(crossf, crossl, pos, path, maze):
crossl_check = False
rev_path = list(map(lambda x: opposite(x), path[::-1]))
i = 0
while pos != crossf:
print("Backtracking...")
if pos == crossl:
crossl_check = True
if crossl_check == False:
maze[pos[0]][pos[1]][1] = 1
pos = move(rev_path[i], pos)
i += 1
return maze, pos

А вот основной цикл

Код: Выделить всё

# Main loop
while pos != end: # While position is not equal to the end position
print(pos)
moves = get_moves(maze, pos)
moves = exclude_invalid(moves, last_move, maze, pos)
for m in moves:
# If the only way is to go back (this direction is a dead end)
if m == "empty":
maze, pos = backtrack(crossroad_first, crossroad_last, pos, path, maze)
last_move = ""
break
if len(moves) > 1: # Position is a crossroad
crossroad_last = pos.copy()
# If path was not blocked
if check_path(maze, pos, m) == True:
print("Moving...")
last_move = m
pos = move(m, pos)
path.append(m)
break
# If path was blocked, try the next direction
else:
continue

Проблема
Когда я запускаю код, кажется, что он работает нормально, но через некоторое время он зависает на [3, 11] ], что это за символ ┼
Код не хочет двигаться, и я понятия не имею, почему...
Есть идеи?< /p>
РЕДАКТИРОВАНИЕ:
Вот ссылка на репозиторий GitHub, содержащий файл лабиринта (tmp.txt) и весь код Python, чтобы вы могли попробовать и воспроизведите проблему самостоятельно.
https://github.com/Brews-Lee/maze-solver
Большое спасибо всем за ваше желание мне помочь!

Подробнее здесь: https://stackoverflow.com/questions/785 ... in-circles