Python迷宮解決 - 使用什麼架構？

Question

我是相當新的python，並試圖建立一個迷宮求解器。我已經構建了一種可以導航單個路線並打印路線（N/E/S/W）的算法，但我想將其移至多個路線。我應該使用什麼樣的架構來處理多條路線？

我正在考慮使用類和子類來模擬不同的路由，以便子類繼承它們的「存根」，但現在我想知道這是否會使它過度複雜化。我看過關於遞歸的文章，但不知道從哪裏開始。

有沒有人有任何建議？我的代碼是低於單一途徑，如果有人有興趣：

# ============================================================================= 
# MAZE 
# ============================================================================= 
# Edit this grid to change the maze. Codes are: 

# 0 = Walkable 
# 1 = Wall 
# 2 = Start 
# 3 = Finish 

maze = [[1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1], 
     [1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1], 
     [1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1], 
     [1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1], 
     [1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1], 
     [1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1], 
     [1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1], 
     [1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1], 
     [1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1], 
     [1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 
     [1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 
     [1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 
     [1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]] 


# ============================================================================= 
# CLASSES AND METHODS 
# ============================================================================= 


# Class which will hold all the routes 
class Route(): 
    used = [] 

    def __init__(self): 
     self.directions = [] 
     self.tracks = [] 
     self.status = 'Pending' 


# Class which stores position of 'marker' and 'start' in maze 
class Pos(): 
    def __init__(self, x, y): 
     self.x = x 
     self.y = y 
     self.coords = [] # Coordinates updated UPDATE_POS method 
     self.N = [] 
     self.E = [] 
     self.S = [] 
     self.W = [] 

     self.update_pos(x, y) 

    # When called, it updates values manually 
    def update_pos(self, x, y): 
     self.coords = [x, y] # Coordinates updated from x and y 
     self.N = [x, y-1, 'N']  # Directions define adjacents 
     self.E = [x+1, y, 'E'] 
     self.S = [x, y+1, 'S'] 
     self.W = [x-1, y, 'W'] 

    # Find start of maze and set position 
    def find_start(self, maze): 

     for row in maze: 
      if 2 not in row: 
       continue 
      if 2 in row: 
       self.y = maze.index(row) 
       self.x = maze[maze.index(row)].index(2) 
       self.update_pos(self.x, self.y) 

    # Check if the index is within the maze 
    def valid_space(self, maze, index):  # index in the form [x,y] 
     size = len(maze) 

     if index[0] < size and index[1] < size: 
      return True 
     else: 
      return False 

    # Looks for walkable spaces and moves the position to that space 
    def look_around(self, maze): 

     directions = [self.N, self.E, self.S, self.W] 

     for direction in directions: 
      # Eliminate invalid moves, used or outside maze 
      if self.valid_space(maze, direction): 
       if direction[0:2] in Route.used: 
        continue 
       # Look for walkable space 
       if maze[direction[1]][direction[0]] == 0: 
        self.x = direction[0] 
        self.y = direction[1] 
        self.update_pos(self.x, self.y) 
        route1.directions.append(direction[2]) 
        Route.used.append(self.coords) 
        break 
       # Look for finish 
       if maze[direction[1]][direction[0]] == 3: 
        self.x = direction[0] 
        self.y = direction[1] 
        self.update_pos(self.x, self.y) 
        route1.directions.append(direction[2]) 
        Route.used.append(self.coords) 
        route1.status = 'Finished' 
      else: 
       continue 


# ============================================================================= 
# MAIN 
# ============================================================================= 


# Initialise position and route 
position = Pos(0, 0) 
start_pos = Pos(0, 0) 
route1 = Route() 


# Change position to start of maze and print 
start_pos.find_start(maze) 
position.find_start(maze) # Set position to start 

print('Solving...') 
while route1.status != 'Finished': 
    position.look_around(maze) 

print('''The directions to the finish are: ''') 
print(route1.directions) 

Answer 1

你真的不需要的數據結構比在迷宮跟蹤路徑列表更復雜。您可能需要使用列表列表來跟蹤您找到的路徑。

在開發解決方案時，請考慮如何跟蹤已經存在的位置。