[SciPy-User] Efficient Dijkstra on a large grid
Wed Apr 10 11:54:20 CDT 2013
In the image scikit (skimage) we also have a very efficient cython implementation of Dijkstra's algorithm for pathfinding through *dense* n-d grids.
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.
On Apr 10, 2013, at 10:02 AM, Lars Buitinck wrote:
>> Date: Wed, 10 Apr 2013 07:24:16 +0200
>> From: Gael Varoquaux <email@example.com>
>> Subject: Re: [SciPy-User] Efficient Dijkstra on a large grid
>> To: SciPy Users List <firstname.lastname@example.org>
>> Message-ID: <20130410052416.GB8796@phare.normalesup.org>
>> In scikit-learn, we have a Dijkstra implemented in cython, using
>> Fibonacci heaps:
> Dijkstra's is in SciPy as well:
> Lars Buitinck
> Scientific programmer, ILPS
> University of Amsterdam
> SciPy-User mailing list
More information about the SciPy-User