[SciPy-User] Efficient Dijkstra on a large grid

Chris Weisiger cweisiger@msg.ucsf....
Tue Apr 9 18:07:46 CDT 2013


I'm working on a roguelike videogame (basically a top-down dungeon
crawler), and more specifically, right now I'm working on monster
pathfinding. The monsters all need to be able to home in on the player -- a
classic many-to-one pathfinding situation. I implemented A* first, but it's
one-to-one and thus doesn't scale well to large numbers of monsters. So I
figured calculating the shortest path length from the player to each cell
via Dijkstra's method would be a good substitute. But I'm having trouble
implementing an efficient Dijkstra's method for this use case (thousands of
nodes) in Python.

Here's what I have thus far: http://pastebin.com/Pts19hQp

My test case is, I grant, a bit excessive -- a 360x120 grid that is almost
entirely open space. It takes about .4s to calculate on my laptop. Angband,
the game I am basing this on, handles this situation mostly by
"deactivating" monsters that are far away from the player, by not having
large open spaces, and by having fairly dumb pathfinding. I'm hoping that
there's a more elegant solution; at the very least, I'd like this
particular portion of the algorithm to be as efficient as possible before I
move on to heuristic improvements.

Any suggestions? I looked but did not find a builtin Dijkstra calculation
algorithm in numpy, presumably because the situation in which your map can
be represented as a 2D array is fairly rare. Am I simply butting into the
limits of what Python can do efficiently, here?

-Chris
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.scipy.org/pipermail/scipy-user/attachments/20130409/ca2e3bd7/attachment.html 


More information about the SciPy-User mailing list