I'm working on a roguelike, and I think my A* algorithm is insufficient. My general algorithm for building the dungeon is:
- Place rooms
- Figure out which rooms should connect by a relative neighborhood graph
- 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))