# [SciPy-User] Efficient Dijkstra on a large grid

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

## [SciPy-User] Efficient Dijkstra on a large grid

 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/Pts19hQpMy 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

 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 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/Pts19hQpMy 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

 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

 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

 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.pyxGael 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

 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 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:  ++ 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

 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

 In reply to this post by Gael Varoquaux Gael Varoquaux 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

 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

 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.pyxDijkstra'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

 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.htmlThe 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

 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. -ChrisOn Wed, Apr 10, 2013 at 9:54 AM, Zachary Pincus 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