[SciPy-User] Efficient Dijkstra on a large grid

[gary ruben]

You could look at using a distance transform (there's one in ndimage and
another one in one of the scikits from memory). Search for "Pursuit Games
in Obstacle Strewn Fields Using Distance Transforms"**


On 10 April 2013 15:24, Gael Varoquaux <gael.varoquaux at normalesup.org>wrote:

> 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 at 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
> _______________________________________________
> 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/07bf5886/attachment.html>