Are there any usable path-finding libraries for python? [closed]

Question

I'm working on a real-time isometric RPG in python, and wish to target mobile devices as a platform. The main area where I'm having difficulties is with my pathfinding. I have tried a few algorithms including A* and a few tweaks to better fit the maps I'm using.

I am satisfied with the results of my algorithm - they give the illusion of some intelligence while being deterministic, and being consistent in either direction so that two characters targeting each others' locations will collide in the middle.

My problem is that while the results look good on the PC where I have all the processing power I could ask for, on my mobile it's quite another story, and there is often a second or more delay while the algorithm is calculated. For this reason I am considering writing a library for this with the most performance-intensive code written in C, however if there is an existing solution for this, or a better way I could do this, I would be all ears.

I stumbled across python-pathfinding but this seems to be slower than what I have built myself for my use case.

---

My use case:

My maps are build from levels, which are surrounded by walls (visible or invisible), and must be linked by doors (visible or invisible).

My current approach is to have two different algorithms:

• Within a room I search individual tiles as nodes, with each boundary as an equal-cost edge, using a depth-first in the direction of the target location

• Between rooms where each door is a node. The shortest possible path through a room (from door to door) is calculated using the first algorithm and stored in a hash table as the edge cost between those nodes. Sets of edges that can be traversed to get from one node to another are then calculated and also stored in the hash table, and it is not permitted to include the same edge more than once in the same path.

I spawn a separate process on start-up that generates a graph for the second algorithm using the first, and this solves many of my issues, rooms tend to be relatively small and so the penalty of on-the-fly path-finding is kept lower than it otherwise could be, and then for longer distances:

• the first algorithm is used to calculate the distance from the current location to every door in the current room.
• the first algorithm is used to calculate the distance from each door in the target room to the target location.
• the output of the second algorithm is used to get the set of paths between rooms
• the cost of these is added to the cost of getting to the first door and from the last door
• the set of solutions is sorted by cost in such a way that the order of paths of the same cost will always be consistent
• the first item in the set of solutions is chosen.

Answer 1

First of all, I know a quite efficient and generic library to handle A* search algorithm. It is lib2dp. You may easily plug your python-generated graph into this library and get a quick answer.

Second, A* is essentially good to find an optimal path according that:

• You have perfect and total information about your surrounding.
• Your surrounding is considered as 'static'.

If you break one of these rules you may want to consider an alternative algorithm called 'D*'.

Of course, this has a huge cost in term of performance. So, it's up to you to find the best trade-off for your program.

Answer 2

If you can reduce your game environment into a graph, then http://networkx.lanl.gov/ has lots of good built in algorithms for this sort of thing.

Answer 3

If you already have a python version you're happy with, then why not run it through py2cmod? That should get you most of the way to a c version of your current algorithm.

Another alternative is psyco, though it has a high overhead.

Answer 4

You may want to check out libtcod and the libtcodpy Python wrapper. Personally, though, I don't quite like how the wrapper isn't very Pythonic, being an unnecessarily monolithic script with excessive usage of function name prefixes (at least, the last time I used it). I refactored the wrapper at one point and fixed it up for Python 3, but that was a year ago and so things may have changed since then.