[SciPy-User] Efficient Dijkstra on a large grid

classic Classic list List threaded Threaded
12 messages Options
Reply | Threaded
Open this post in threaded view
|

[SciPy-User] Efficient Dijkstra on a large grid

Chris Weisiger-2
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
[hidden email]
http://mail.scipy.org/mailman/listinfo/scipy-user
Reply | Threaded
Open this post in threaded view
|

Re: Efficient Dijkstra on a large grid

Daπid
Cython is a good option for this. Using the plain approach (-O2, no annotations), I get a speedup of almost 3x. I guess you could get something better with some type annotations. Also, you could parallelize your for x, y in goals loop, that would give you another extra x2-x4 in that piece of the loop.

If you have mostly open space, far away monsters can behave dumbly, moving directly towards the player. That will be, most of the time, a good strategy, and a good saving in time, if you need it.

David.

On 10 April 2013 01:07, Chris Weisiger <[hidden email]> 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
[hidden email]
http://mail.scipy.org/mailman/listinfo/scipy-user



_______________________________________________
SciPy-User mailing list
[hidden email]
http://mail.scipy.org/mailman/listinfo/scipy-user
Reply | Threaded
Open this post in threaded view
|

Re: Efficient Dijkstra on a large grid

John Gleeson
In reply to this post by Chris Weisiger-2

On 2013-04-09, at 5:07 PM, Chris Weisiger wrote:
>
> Any suggestions?


Hi Chris,

I infer from your code that your edge weights are always equal to 1.  
This is a special case, sometimes called "hop-count shortest path". It  
can be solved with breadth-first search (BFS). The Wikipedia BFS  
article mentions this application.
http://en.wikipedia.org/wiki/Breadth-first_search

-John
_______________________________________________
SciPy-User mailing list
[hidden email]
http://mail.scipy.org/mailman/listinfo/scipy-user
Reply | Threaded
Open this post in threaded view
|

Re: Efficient Dijkstra on a large grid

John Gleeson

On 2013-04-09, at 6:09 PM, John Gleeson wrote:

>  It
> can be solved with breadth-first search (BFS).

After studying your code a bit longer, it looks like you already are  
doing no more (and no less) than BFS.
_______________________________________________
SciPy-User mailing list
[hidden email]
http://mail.scipy.org/mailman/listinfo/scipy-user
Reply | Threaded
Open this post in threaded view
|

Re: Efficient Dijkstra on a large grid

Gael Varoquaux
In reply to this post by Chris Weisiger-2
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
> [hidden email]
> 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
[hidden email]
http://mail.scipy.org/mailman/listinfo/scipy-user
Reply | Threaded
Open this post in threaded view
|

Re: 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 <[hidden email]> 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
> [hidden email]
> 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:  <a href="tel:%2B%2B%2033-1-69-08-79-68" value="+33169087968">++ 33-1-69-08-79-68
    http://gael-varoquaux.info            http://twitter.com/GaelVaroquaux
_______________________________________________
SciPy-User mailing list
[hidden email]
http://mail.scipy.org/mailman/listinfo/scipy-user


_______________________________________________
SciPy-User mailing list
[hidden email]
http://mail.scipy.org/mailman/listinfo/scipy-user
Reply | Threaded
Open this post in threaded view
|

Re: Efficient Dijkstra on a large grid

Robert Kern-2
In reply to this post by Chris Weisiger-2
On Wed, Apr 10, 2013 at 4:37 AM, Chris Weisiger <[hidden email]> 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.

For implementing a roguelike, you may want to use libtcod. It already
has Dijkstra's method implemented for this case.

  http://doryen.eptalys.net/libtcod/
  http://doryen.eptalys.net/data/libtcod/doc/1.5.0/path/path_compute.html

--
Robert Kern
_______________________________________________
SciPy-User mailing list
[hidden email]
http://mail.scipy.org/mailman/listinfo/scipy-user
Reply | Threaded
Open this post in threaded view
|

Re: Efficient Dijkstra on a large grid

Pauli Virtanen-3
In reply to this post by Gael Varoquaux
Gael Varoquaux <gael.varoquaux <at> normalesup.org> writes:
> 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

And another implementation is here:
http://docs.scipy.org/doc/scipy-
dev/reference/generated/scipy.sparse.csgraph.dijkstra.html



_______________________________________________
SciPy-User mailing list
[hidden email]
http://mail.scipy.org/mailman/listinfo/scipy-user
Reply | Threaded
Open this post in threaded view
|

Re: Efficient Dijkstra on a large grid

Gael Varoquaux
On Wed, Apr 10, 2013 at 08:32:56AM +0000, Pauli Virtanen wrote:
> And another implementation is here:
> http://docs.scipy.org/doc/scipy-
> dev/reference/generated/scipy.sparse.csgraph.dijkstra.html

Yes, I had forgotten that it had been backported to scipy.

You should use the scipy version, rather than the scikit-learn version.

G
_______________________________________________
SciPy-User mailing list
[hidden email]
http://mail.scipy.org/mailman/listinfo/scipy-user
Reply | Threaded
Open this post in threaded view
|

Re: Efficient Dijkstra on a large grid

Lars Buitinck-2
In reply to this post by Gael Varoquaux
> Date: Wed, 10 Apr 2013 07:24:16 +0200
> From: Gael Varoquaux <[hidden email]>
> Subject: Re: [SciPy-User] Efficient Dijkstra on a large grid
> To: SciPy Users List <[hidden email]>
> Message-ID: <[hidden email]>
>
> 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
[hidden email]
http://mail.scipy.org/mailman/listinfo/scipy-user
Reply | Threaded
Open this post in threaded view
|

Re: Efficient Dijkstra on a large grid

Zachary Pincus-2
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 <[hidden email]>
>> Subject: Re: [SciPy-User] Efficient Dijkstra on a large grid
>> To: SciPy Users List <[hidden email]>
>> Message-ID: <[hidden email]>
>>
>> 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
> [hidden email]
> http://mail.scipy.org/mailman/listinfo/scipy-user

_______________________________________________
SciPy-User mailing list
[hidden email]
http://mail.scipy.org/mailman/listinfo/scipy-user
Reply | Threaded
Open this post in threaded view
|

Re: Efficient Dijkstra on a large grid

Chris Weisiger-2
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 <[hidden email]> 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 <[hidden email]>
>> Subject: Re: [SciPy-User] Efficient Dijkstra on a large grid
>> To: SciPy Users List <[hidden email]>
>> Message-ID: <[hidden email]>
>>
>> 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
> [hidden email]
> http://mail.scipy.org/mailman/listinfo/scipy-user

_______________________________________________
SciPy-User mailing list
[hidden email]
http://mail.scipy.org/mailman/listinfo/scipy-user


_______________________________________________
SciPy-User mailing list
[hidden email]
http://mail.scipy.org/mailman/listinfo/scipy-user