Python Maze Route-finding

Question

I'm working on a Tower Defense game in Python, where the user's towers can modify the path that the enemies must take. To calculate the path, I thought an implementation of the Lee Algorithm would probably be best and easiest, particularly if the grids get large. I tried to loosely base my algorithm on that.

My code, however, doesn't work. And I can't see why.

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 is the variable that should contain all possible routes the enemy can take, and eventually the correct route. Currently, the algorithm should shade the route in green that is fastest. Level is a level object, and level.map is a 2D array of Grid objects, each being a single cell. If the cell.access is 5, it means it is an exit point for the enemy.

All that actually happens, is it creates an incredibly long list of tuples reading (0,1) and (1,0). No negative numbers are ever generated, nothing other than a 1 or a 0.

Can someone please point me in the right direction either to create a proper Lee Algorithm or to fix my current code?

Answer 1

As far as I can tell, you never check whether you've already visited a square. Additionally, you're using x and y for values which are not x,y coords and checking for one end of the index and catching exceptions for the other. This very over complicated. My advice would be to implement the actual algorithm:

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

With this, we can generate route grids:

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

With no obstructions, we get:

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]

With obstructions:

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)

we get:

[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]

Then, you start the the goal and work your way back, finding the neighbor with a score 1 lower than your current. That will generate an optimum path. (Note, there may be more than one which satisfies this: you can pick any of them and find equivalent paths)

If, at any point during the finding the path step, you cannot find a neighbor that is one lower (and you haven't reached the goal) then the path is blocked.