[SciPy-User] Efficient Dijkstra on a large grid

Gael Varoquaux gael.varoquaux@normalesup....
Wed Apr 10 00:24:16 CDT 2013


In scikit-learn, we have a Dijkstra implemented in cython, using
Fibonacci heaps:

https://github.com/scikit-learn/scikit-learn/blob/master/sklearn/utils/graph_shortest_path.pyx

Gael

On Tue, Apr 09, 2013 at 04:07:46PM -0700, Chris Weisiger 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@scipy.org
> http://mail.scipy.org/mailman/listinfo/scipy-user


-- 
    Gael Varoquaux
    Researcher, INRIA Parietal
    Laboratoire de Neuro-Imagerie Assistee par Ordinateur
    NeuroSpin/CEA Saclay , Bat 145, 91191 Gif-sur-Yvette France
    Phone:  ++ 33-1-69-08-79-68
    http://gael-varoquaux.info            http://twitter.com/GaelVaroquaux


More information about the SciPy-User mailing list