[SciPy-User] Efficient Dijkstra on a large grid

[Daπid]

Cython is a good option for this. Using the plain approach (-O2, no
annotations), I get a speedup of almost 3x. I guess you could get something
better with some type annotations. Also, you could parallelize your for x,
 y in goals loop, that would give you another extra x2-x4 in that piece of
the loop.

If you have mostly open space, far away monsters can behave dumbly, moving
directly towards the player. That will be, most of the time, a good
strategy, and a good saving in time, if you need it.

David.

On 10 April 2013 01:07, Chris Weisiger <cweisiger at msg.ucsf.edu> wrote:

> 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
>
> _______________________________________________
> SciPy-User mailing list
> SciPy-User at scipy.org
> http://mail.scipy.org/mailman/listinfo/scipy-user
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.scipy.org/pipermail/scipy-user/attachments/20130410/2e195304/attachment.html>