[SciPy-User] Efficient Dijkstra on a large grid
Wed Apr 10 01:37:05 CDT 2013
On Wed, Apr 10, 2013 at 4:37 AM, Chris Weisiger <firstname.lastname@example.org> 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.
More information about the SciPy-User