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_______________________________________________ SciPy-User mailing list [hidden email] http://mail.scipy.org/mailman/listinfo/scipy-user |
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:
_______________________________________________ SciPy-User mailing list [hidden email] http://mail.scipy.org/mailman/listinfo/scipy-user |
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 |
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 |
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 |
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 _______________________________________________ SciPy-User mailing list [hidden email] http://mail.scipy.org/mailman/listinfo/scipy-user |
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 |
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 |
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 |
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 |
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 |
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 <[hidden email]> wrote: Hi all, _______________________________________________ SciPy-User mailing list [hidden email] http://mail.scipy.org/mailman/listinfo/scipy-user |
Free forum by Nabble | Edit this page |