Как реализовать метод рекурсивно в Python

Question

Я пытаюсь реализовать этот метод рекурсивно. Однако через несколько секунд я получаю сообщения об ошибках в индексе «Can not pop from empty stack». Как я могу это исправить? По сути, точка всего кода (который я не включил) заключается в создании лабиринта и руководстве робота через него.

пустых (неисследованные) клетки
EMPTY = 0

клеток с препятствием
OBSTACLE = 1

клетка, которая находится на пути
ON_PATH = 2

клеток, которые были изучены, но не на путь
EXPLORED = 3

клеток робот в
ROBOT = 4

def solve(self, location): 

    eventType, done = None, False 
    self.maze[location[0]][location[1]] = ROBOT 
    if self.mode == GRAPHICAL_FULL: 
     self.display_init() 
     self.draw_maze() 
    elif self.mode == GRAPHICAL_LIMITED: 
     self.display_init() 
     self.update_maze() 
    while eventType != QUIT and not done: 
     if self.mode == GRAPHICAL_FULL or self.mode == GRAPHICAL_LIMITED: 
      for event in pygame.event.get(): 
       eventType = event.type 
     new_location = self.find_next_step() 
     if new_location is None: 
      # Mark the current location as a dead end 
      self.maze[location[0]][location[1]] = EXPLORED 
      # pop the next cell off the path stack (go back one space) 
      location = self.path.pop() 
      self.maze[location[0]][location[1]] = ROBOT 
      self.solve(location) 
     else: 
      self.maze[location[0]][location[1]] = ON_PATH 
      self.path.push(location) 
      location = new_location 
      self.solve(location) 
     if self.mode == GRAPHICAL_FULL or self.mode == GRAPHICAL_LIMITED: 
      self.clock.tick(self.framerate) 
      self.update_maze() 
      self.screen.blit(self.background, (0,0)) 
      pygame.display.flip() 
     if (self.maze[0][0] == EXPLORED or 
      location == (self.dimension['x']-1, self.dimension['y']-1)): 
      self.path.push(location) 
      done = True 
    return self.path 


def find_next_step(self): 
    # Search for a place to go 
    for direction in SEARCH_ORDER: 
     new_location = (self.location[0] + direction['x'], 
         self.location[1] + direction['y']) 
     if (0 <= new_location[0] < self.dimension['x'] and 
      0 <= new_location[1] < self.dimension['y'] and 
      self.maze[new_location[0]][new_location[1]] == EMPTY): 
      self.maze[new_location[0]][new_location[1]] = ROBOT 
      return new_location 
    return None 

Answer 1

В поп вызывается, только если NEW_LOCATION его нет, self.find_next_step() не вернулся ни один. Без кода для find_next_step() его трудно быть уверенным, но я предполагаю, что робот прошел все пути, вернулся в начале (с пустым путём) и, следовательно, сбой .pop().

В любом случае, я бы предположил, что ошибка действительно встречается в возвращаемом значении из find_next_step().

Это не совсем ответ, но у меня нет респ комментировать все же, надеюсь, что это помогает;)

Update:

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

Однако оказалось, что find_next_step вернет None, если пустых значений direction в SEARCH_ORDER. (хотя я не знаю, как выглядит направление. SEARCH_ORDER предположительно является константой? (Не большой пользователь python)).

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

Answer 2

Недостаточно приложения, чтобы это было окончательным, но я думаю, что ваша проблема находится в конце шаблона. Когда вы переходите в конечное местоположение, вы снова вызываете решение(). В этом цикле вы получите new_location значение «Нет» и начнете двигаться назад, пока не дойдете до первого места, и получите ошибку, потому что вы не можете поместить больше мест с вашего пути. Ваш чек, чтобы разбить цикл рекурсии, не вызывается до тех пор, пока все не раскрутится.

Перемещайте чек на «сделано» в чем-то вроде этого ...

location = new_location 
if not done: 
    self.solve(location)