Python的迷宮路線調查

Question

我工作的一個塔防遊戲在Python中，用戶的塔樓可以修改的敵人必須採取的路徑。爲了計算路徑，我認爲Lee算法的實現可能是最好的和最簡單的，特別是如果網格變大。我試圖鬆散地基於我的算法。

我的代碼，但是，不能正常工作。我不明白爲什麼。

def getRoute(self): 
    self.routes = [[(0,0)]] 

    def _getRoutes(): 
    new_routes = [] 
    for route in self.routes: 
     for i in [(1,0),(-1,0),(0,1),(0,-1)]: 
     new_loc = [x + y for x,y in zip(route[-1],i)] 
     for index in new_loc: 
      if index < 0: 
      print('< 0') 
      continue ## if the index causes a skip across the side of the array, ignore 
     try: 
      if self.level.map[new_loc[0]][new_loc[1]].travellable: ## if the tile is able to be travelled on by enemies 
      route.append(new_loc) ## add the tile to the 'r' array 
      new_routes.append(route) ## add the new route to the new_routes array 
     except IndexError: ## if the tile is off the map, ignore 
      print('index error') 
    self.routes = new_routes 

    def _checkRoutesValidity(): 
    for route in self.routes: 
     if self.level.map[route[-1][0]][route[-1][1]].access == 5: 
     return route 
     break 
    else: 
     return None 

    while not _checkRoutesValidity(): 
    _getRoutes() 

    self.route = _checkRoutesValidity() 
    for i,j in self.route: 
    self.level.map[i][j].overlay_col = [0,1,0,1] 

路線是，應該包含所有可能路徑的敵人可以利用，並最終與正確路線的變量。目前，該算法應該以最快的綠色陰影路線。 Level是一個level對象，level.map是一個Grid對象的二維數組，每個對象都是一個單獨的單元格。如果cell.access爲5，則意味着它是敵人的出口點。

所有這一切實際發生的，是它創建的元組讀取一個令人難以置信的長列表（0,1）和（1,0）。沒有負數是不斷產生的，沒有什麼以外的1或0

可有人請點我在正確的方向要麼建立一個適當的李算法或修復我當前的代碼？

Answer 1

據我所知，你從來沒有檢查您是否已經訪問了一個正方形。此外，您使用x和y來計算不是x,y座標的值，並檢查索引的一端並捕獲另一端的異常。這非常複雜。我的建議是實現實際的算法：

def gen_lee(start, size, travelable): 
    neighbor_offsets = [(0, 1), (1, 0), (0, -1), (-1, 0)] 
    score = 0 
    path_map = [[None for _ in xrange(size)] for _ in xrange(size)] 
    node_list = [start] 
    path_map[start[0]][start[1]] = 0 
    for node in node_list: 
     score = path_map[node[0]][node[1]] 
     for neighbor_offset in neighbor_offsets: 
      neighbor_x = node[0] + neighbor_offset[0] 
      neighbor_y = node[1] + neighbor_offset[1] 
      if neighbor_x < 0 or \ 
       neighbor_y < 0 or \ 
       neighbor_x >= size or \ 
       neighbor_y >= size: 
       continue # Skip out of map neighbors 
      if not travelable[neighbor_x][neighbor_y]: 
       continue # Skip untravelable neighbors 
      if path_map[neighbor_x][neighbor_y] is None: 
       node_list.append((neighbor_x, neighbor_y)) 
       path_map[neighbor_x][neighbor_y] = score + 1 
    return path_map 

有了這個，我們可以生成航線電網：

path_map = gen_lee((1, 1), 5, [[1]* 5] * 5) 

由於沒有障礙物，我們得到：

for row in path_map: 
    print row 

[2, 1, 2, 3, 4] 
[1, 0, 1, 2, 3] 
[2, 1, 2, 3, 4] 
[3, 2, 3, 4, 5] 
[4, 3, 4, 5, 6] 

隨着障礙物：

travelable = [[1, 1, 1, 0, 1], 
       [1, 1, 1, 0, 1], 
       [1, 1, 1, 0, 1], 
       [1, 1, 1, 0, 1], 
       [1, 1, 1, 1, 1]] 

path_map = gen_lee((1, 1), 5, travelable) 

我們得到：

[2, 1, 2, None, 10] 
[1, 0, 1, None, 9] 
[2, 1, 2, None, 8] 
[3, 2, 3, None, 7] 
[4, 3, 4, 5, 6] 

然後，你開始的目標和工作方式回來，發現鄰居的比分1比目前更低。這將產生最佳路徑。 （注意，可能有不止一個滿足這個要求：你可以選擇其中的任何一個並找到等價路徑）

如果在查找路徑步驟期間的任何時刻，找不到一個較低的鄰居而你還沒有達到目標），那麼路徑被阻止。