How to optimize my A* algorithm

Question

I'm working on a roguelike, and I think my A* algorithm is insufficient. My general algorithm for building the dungeon is:

1. Place rooms
2. Figure out which rooms should connect by a relative neighborhood graph
3. Use A* to connect the rooms

The relative neighborhood algorithm I'm using is naive; it ends up having O(n^3) running time. The connections it generates are relatively short and straight forward; despite that, the A* pathfinding ends up taking around 3 times as long as the room placement and relative neighborhood combined.

For example, here's how it clocks when I make a 300-room dungeon

events = [("Start time", time.clock())]
dungeon = NewDungeonGenerator.Dungeon(300)
level = Level.Level.FromGrid(dungeon.map)
events.append(("Created dungeon", time.clock()))
level.connect(dungeon.connectedRooms)
events.append(("Connected paths in dungeon", time.clock()))

Output:

Start time: 0.0
Created dungeon: 1.66705377095
Connected paths in dungeon: 5.48920304303

(that's time in seconds)

This is the A* code I've written:

def FindPath(level, start, end):
    validX = range(level.width)
    validY = range(level.height)
    unvisited = [[True for i in validY] for i in validX]
    unvisited[start[0]][start[1]] = False
    paths = [{
        "cost": 0,
        "steps": [start]
    }]
    while True:
        paths.sort(key=lambda path: path["cost"] + computeOffset(path["steps"][-1], end))
        if len(paths) == 0:
            return False
        best = paths[0]
        paths = paths[1:]
        lastStep = best["steps"][-1]
        if lastStep == end:
            return best["steps"]
        for neighbor in ((0, -1), (1, 0), (0, 1), (-1, 0)):
            x = lastStep[0] + neighbor[0]
            y = lastStep[1] + neighbor[1]
            if x in validX and y in validY and unvisited[x][y]:
                unvisited[x][y] = False
                cell = level.getCell(x, y)
                if cell.immutable and not cell.passable:
                    # We don't want to dig through an immutable wall
                    continue
                cost = best["cost"] + cell.digCost
                steps = best["steps"][:]
                steps.append((x, y))
                paths.append({
                    "cost": cost,
                    "steps": steps
                })



def computeOffset(start, end):
    return abs((start[0] - end[0])) + abs((start[1] - end[1]))

I feel like there's got to be a way to optimize this... One potential cause of the slowdown is how I compute the cost of a cell. If a cell is passable, its cost is 1; otherwise, I check the cell and its neighbors against some 3x3 masks to determine what it is (wall, corner, 'earth'). You can see the code for the Cell class, and the masks, here. All the other code for this project is in available at that link as well.

EDIT: As was suggested below, I changed to a heapq for storing the paths and it's shaved about a second off the time. That's good!

def FindPath(level, start, end):
    validX = range(level.width)
    validY = range(level.height)
    unvisited = [[True for i in validY] for i in validX]
    unvisited[start[0]][start[1]] = False
    paths = []
    heapq.heappush(paths, (0, 0, [start]))
    while True:
        # paths.sort(key=lambda path: path["cost"] + computeOffset(path["steps"][-1], end))
        if len(paths) == 0:
            return False
        best = heapq.heappop(paths)
        lastStep = best[2][-1]
        if lastStep == end:
            return best[2]
        for neighbor in ((0, -1), (1, 0), (0, 1), (-1, 0)):
            x = lastStep[0] + neighbor[0]
            y = lastStep[1] + neighbor[1]
            if x in validX and y in validY and unvisited[x][y]:
                unvisited[x][y] = False
                cell = level.getCell(x, y)
                if cell.immutable and not cell.passable:
                    # We don't want to dig through an immutable wall
                    continue
                cost = best[1] + cell.digCost
                steps = best[2][:] # clone list
                steps.append((x, y))
                heapq.heappush(paths, (cost + computeOffset(steps[-1], end), cost, steps))

Answer 1

the biggest problem I see is the sort call each step which is O(n log n)

I suggest using the heapq so it will be reduced to O(log n) per insert and pop saving you a factor of n

you will need to add the steps as lists with the sort key (the path["cost"] + computeOffset(path["steps"][-1], end) as first and then the tuple so natural ordering will be used

paths = []
heapq.heappush(paths, [0,{
    "cost": 0,
    "steps": [start]
}]
while True:
    if len(paths) == 0:
        return False
    best = heappop(paths)[1]

and to insert:

heapq.heappush(heap, [cost + computeOffset(steps[-1], end),
                      {
                          "cost": cost,
                          "steps": steps
                      }])

(I have no idea if I indented this correctly...)

Answer 2

In my Hex-Grid Utilities for Board Games library I obtained almost linear-in-path-length behaviour, over a grid of about 780 x 460 cells, by using eight landmarks (the four corners and four side-midpoints of the map) and the triangle inequality as outlined in Computing Point-to-Point Shortest Paths from External Memory. (Fair warning for Python developers - there be C# code; prepare for discomfort and disorientation.)

The parallel pre-computation (by Dijkstra's ,i.e. breadth-first) of distances from each landmark to every hex takes 2-3 seconds at start-up, while the computation of the longest and most complex path on the map runs so fast I can barely measure it; under 0.05 sec. Before adapting the code to use this technique, the calculation of complex diagonal paths took up to 1.6 seconds each.

I have used some additional optimizations, such as Bi-Directional A-star, but I estimate those as only providing a factor of 3-4 times in the speedup recorded.

All code in the library referenced above is available for use under The MIT License.

Note:
It is not necessary to store the pre-computed paths from each landmark at each cell - simply the minimum path-length to each landmark. This allows an extremely accurate heuristic to be computed, so that few false-steps are ever evaluated.