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比目前更低。这将产生最佳路径。 （注意，可能有不止一个满足这个要求：你可以选择其中的任何一个并找到等价路径）

如果在查找路径步骤期间的任何时刻，找不到一个较低的邻居而你还没有达到目标），那么路径被阻止。