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]

Routes 是一个变量，它应该包含敌人可能采取的所有可能路线，最终是正确的路线。目前，该算法应该用最快的绿色遮蔽路线。 Level 是一个级别对象，level.map 是一个 Grid 对象的二维数组，每个对象都是一个单元格。如果 cell.access 是 5，则表示它是敌人的出口。

实际发生的一切，是它创建了一个非常长的元组列表，读取 (0,1) 和 (1,0)。从来没有生成负数，除了 1 或 0 之外什么都没有。

有人可以为我指出正确的方向来创建正确的 Lee 算法或修复我当前的代码吗？

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 的邻居。这将生成最佳路径。（注意，可能有不止一个满足这个：你可以选择其中任何一个并找到等效路径）

如果在寻找路径步骤的任何时候，您找不到比您低一个的邻居（并且您还没有达到目标），那么路径就会被阻塞。

Python迷宫寻路

Python Maze Route-finding

python

maze

python-2.7