[SciPy-User] Efficient Dijkstra on a large grid
Zachary Pincus
zachary.pincus@yale....
Wed Apr 10 11:54:20 CDT 2013
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
More information about the SciPy-User
mailing list