[SciPy-User] Efficient Dijkstra on a large grid

Chris Weisiger cweisiger@msg.ucsf....
Thu Apr 11 10:07:46 CDT 2013


Thanks for the response, everyone! Sounds like I have some premade
solutions to check out. And if those don't prove suitable, then switching
to Cython and/or making the pathfinder more intelligent about large open
spaces will also help. A bit more work than the initial ~hour I spent on my
implementation, but if it gets me the speed I need then it'll be worth it.

-Chris


On Wed, Apr 10, 2013 at 9:54 AM, Zachary Pincus <zachary.pincus@yale.edu>wrote:

> Hi all,
>
> In the image scikit (skimage) we also have a very efficient cython
> implementation of Dijkstra's algorithm for pathfinding through *dense* n-d
> grids.
> http://scikit-image.org/docs/dev/api/skimage.graph.html
>
> The specific utility of this code is that it operates on raw numpy arrays
> (as opposed to sparse arrays as in the scikit-learn and scipy
> implementations). The algorithm uses the values in the array as weights for
> pathfinding from a given start point either to one or more end-points, or
> to every point in the array. Valid moves through the grid can be given as a
> set of offsets, so you could, say, simulate different chess-peice moves.
>
> There is a second class that is savvy about image geometry, so "travel
> costs" are weighted to account for the fact that axial moves in a grid are
> shorter than diagonal moves. In this way, the travel costs from a given
> point through a uniform array will look more like circles than
> axis-oriented diamonds, which is what you get with a naive algorithm.
>
> It's built on an extremely fast heap implementation by Almar Klein, so the
> algorithm runs in essentially real-time for point-to-point finding for
> 1024x1280 image arrays. (I use it in interactive image-segmentation tools.)
>
> As such, I think this would probably be a useful codebase for your monster
> pathfinding -- especially the dense grid part.
>
> Zach
>
>
>
> On Apr 10, 2013, at 10:02 AM, Lars Buitinck wrote:
>
> >> Date: Wed, 10 Apr 2013 07:24:16 +0200
> >> From: Gael Varoquaux <gael.varoquaux@normalesup.org>
> >> Subject: Re: [SciPy-User] Efficient Dijkstra on a large grid
> >> To: SciPy Users List <scipy-user@scipy.org>
> >> Message-ID: <20130410052416.GB8796@phare.normalesup.org>
> >>
> >> 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
> >
> > Dijkstra's is in SciPy as well:
> >
> https://github.com/scipy/scipy/blob/master/scipy/sparse/csgraph/_shortest_path.pyx#L32
> >
> > --
> > Lars Buitinck
> > Scientific programmer, ILPS
> > University of Amsterdam
> > _______________________________________________
> > SciPy-User mailing list
> > SciPy-User@scipy.org
> > http://mail.scipy.org/mailman/listinfo/scipy-user
>
> _______________________________________________
> SciPy-User mailing list
> SciPy-User@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/20130411/2bc41db3/attachment.html 


More information about the SciPy-User mailing list