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