Поиск лабиринта без информации о плитках в Python

Question

Я работаю над лабиринтом, который генерируется с использованием модуля черепахи в Python.Мне разрешено взаимодействовать с лабиринтом, используя 5 действий через агента.Этими действиями ( методы ) являются {Вперед, назад, вправо, влево, IsSuccess}, где 4 - это движения, и одно - проверить, достиг ли я финишной линии лабиринта.

Некоторыеинформация, которая необходима для понимания объема.
1: У меня есть доступ к текущей позиции Агента, где он стоит (x, y)
2: Агент всегда, например, в одном и том же направленииесли ему дают команду идти направо, он повернет на 90 градусов в соответствующем направлении и переместит набор пикселей вперед, а затем повернет на -90 градусов, чтобы снова повернуть в том же направлении.
3: Если он сталкивается со стеной в лабиринте при использовании одного из методов движения, движение будет отменено, и False возвращается.Если ход действителен, он остается в новой позиции и возвращается True .
4: Нет необходимости возвращаться назад, чтобы получить путь к финишу.
5: Лабиринт построен по кругу, при этом игрок начинает ближе к середине, и цель состоит в том, чтобы выбраться из кругового лабиринта.Параметр, который проверяет, выиграл ли игрок в игре, - это то, как далеко игрок находится от центра.Например, игрок может начать с кругового значения 50, а перемещение между внутренним и внешним кругами дает +25 или -25 к этому значению.Хотя цель состоит в том, чтобы достичь определенного значения, скажем, 125.

Теперь я начал с некоторых простых алгоритмов рекурсивного поиска, но независимо от того, как я его настраивал, я застреваю после навигации по x шагу в лабиринте.Это то, что я имею до сих пор:

def escape():
    if isSuccess():
        return True

   position = (math.floor(agent.pos()[0]),math.floor(agent.pos()[1])) #Gets current agent position

   if position in visistedPositions:
       print("Already visited here")
       return False
   visistedPositions.append(position) #Adds agents position to visited list

   if(Right(agent)):
       print("Moved right")
       escape()
   else:
       print("Could not move Right")
   if(Backward(agent)):
       print("Moved Back")
       escape()
   else:
       print("Could not move Back")
   if(Left(agent)):
       print("Moved Left")
       escape()
   else:
       print("Could not move Left")
   if(Forward(agent)):
       print("Moved Forward")
       escape()
   else:
       print("Could not move Forward")
   return False

Какие-либо предложения о том, как я могу выполнить эту задачу, имея только данные действия в моем распоряжении?Я исследовал и исследовал различные алгоритмы, такие как BFS, DFS и A *, но я не понимаю, как я мог бы приспособить любой из них к этой проблеме.Любые предложения приветствуются.

РЕДАКТИРОВАТЬ: Чтобы прояснить, как движется агент, я публикую фрагмент из методов Right() и Backward().

def Right(agent):
global circle_level
if circle_level < SUCCESS_LEVEL:
    #turtle.home()
    p1 = Point(agent.pos()[0], agent.pos()[1])
    agent.circle(circle_level,-22.5)
    p2 = Point(agent.pos()[0], agent.pos()[1])
    if isBlocked(Line(p1,p2)):
        print('blocked')
        agent.circle(circle_level,22.5)
        return False
return True

def Backward(agent):
global circle_level
if circle_level > 50 and circle_level < SUCCESS_LEVEL:
    circle_level -= 20
    p1 = Point(agent.pos()[0], agent.pos()[1])
    agent.right(90)
    agent.backward(20)
    agent.right(-90)
    p2 = Point(agent.pos()[0], agent.pos()[1])
    if isBlocked(Line(p1,p2)):
        print('blocked')
        circle_level += 20
        agent.right(90)
        agent.forward(20)
        agent.right(-90)
        return False
return True

Answer 1

Хотя это кажется странным приведением в качестве рекурсивной функции, я буду подыгрывать.Основная проблема, которую я вижу, заключается в том, что вы вызываете escape() рекурсивно, но игнорируете его возвращаемое значение.Как вы узнаете, что преуспели в рекурсии?

Ниже приведена моя работа с вашим кодом для решения этой проблемы:

def escape():
    if isSuccess():
        return True

    position = (math.floor(agent.xcor()), math.floor(agent.ycor()))  # Get current agent position

    if position in visitedPositions:
        print("Already visited here")
        return False

    visitedPositions.append(position)  # Add agent's position to visited list

    if Right(agent):
        print("Moved right")
        return escape()

    print("Could not move Right")

    if Backward(agent):
        print("Moved Back")
        return escape()

    print("Could not move Back")

    if Left(agent):
        print("Moved Left")
        return escape()

    print("Could not move Left")

    if Forward(agent):
        print("Moved Forward")
        return escape()

    print("Could not move Forward")

    return False

Возможно, будет эффективнее, если вы сделаете visitedPositions [правописание изменено] set вместо list.