[SciPy-User] Efficient Dijkstra on a large grid

[Robert Kern]

On Wed, Apr 10, 2013 at 4:37 AM, Chris Weisiger <cweisiger at msg.ucsf.edu> 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