Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

This is cross-posted from StackOverflow, please feel free to answer there too:

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.
share|improve this question
1  
Cross posting is not allowed –  Jonathan Connell Aug 9 '11 at 13:10
1  
ok, I thought it was relevent to both communities, and while the first place I looked was stackoverflow, I thought that this community would approach the issue from a completely different angle. –  theheadofabroom Aug 9 '11 at 15:36
    
I believe it's ok if you tailor your question for the specifics of each community, but copy/pasting is not well looked upon. –  Jonathan Connell Aug 9 '11 at 15:40
1  
I see - I couldn't see much that aught to be changed - if however there's anything you see as inappropriate I'd be happy to alter it. –  theheadofabroom Aug 9 '11 at 15:49

2 Answers 2

The problem is not about the performance of a path-finding library as such. Path-finding is a specific application of state-space search, and the length of time it takes to search a state-space grows (often exponentially) in relation to the size of that state. Therefore the biggest problem here is how you represent that state, and the second biggest problem is the algorithm you choose to search it. Only third comes the quality of the implementation, typically. No matter how good the library, it can only search the state space you provide it with, and if that space is too large, the exponential growth of the search space will dwarf any other optimisations.

Judging by your last set of bullet points, it sounds like you're needlessly generating more solutions than you need. An algorithm such as A* will return the best solution first, solving that problem. Given your topology it would seem like you can generate a path that is combined of nodes (for the current room and the destination room) and super-nodes (for the intermediate rooms where you're going from door to door, and where the costs are precomputed). The number of states to be searched here should be fairly minimal and once the result is returned, a post-processing step would expand the super-nodes out into individual tiles.

I'd be very surprised if such a solution didn't perform perfectly well on Python on pretty much any size of map. However, it's also worth making sure you're using the right data structures - if you're testing a list for membership (eg. the typical 'closed' list) then you'd be better off with a set, and if you're looking up nodes by some value, you're better off with a dict or a set than a list. If you really need a queue object, then a collections.deque may be better than a list. And so on.

Finally, sometimes it is faster to replace the typical A* with something like iterative deepening A* which, although less efficient on paper, can be more efficient in practice due to requiring fewer memory allocations and expensive queue operations. This is less likely to hold true in Python however because the relationship between pseudocode instructions and low-level operations is not as strong as it is with a typical C implementation.

share|improve this answer

Disclaimer

I am not a python programmer primarily; I looked briefly for other libs and came across this.

However, that is not the main thrust of my answer: instead it is to challenge whether you need to find another library at all, or whether you in fact just need to optimise what you have. Ultimately, I'm still trying to help you find a solution to your problem.

First, on simple optimisation issues which may apply:

I'm not sure which mobile platforms you're targeting, but be aware that any floating point math you are doing in a highly iterative algorithm like A* may have a major impact on the mobile device's ability to keep up. Considering that processors in modern mobiles are pretty powerful, it is a little suprising that you're having issues with A*, however this obviously depends very much on what you are trying to achieve. This brings me to my second point.

If you haven't started profiling your code is yet, you cannot know where the bottleneck lies. You cannot just assume you need a different library -- at this late stage, it is far better to assume your code (which you know does what it needs to in the way you want it to) simply has one or two simple failing points causing the bottleneck. It's like a good relationship really -- If you've got something good going already, don't discard it, put the effort in to fix it. You probably understand enough about the heuristics and so on to know how to work in the guts of it.

Lastly, balancing your A* heuristic value appropriately is critical to achieving optimal performance -- I take it you are already aware of this as it is one of the fundamentals for this algorithm.


Assuming there is no simple way to solve your problem after tackling the above, here is a bolt-on approach to improving pathfinding performance:

Let's look at this from the top down. Any pathfinding algorithm makes use of a graph. A* does too -- it's graph is simply a grid of cells, each cell being a 4-connected graph node. Given A*'s ability to process many, many individual cells, is an excellent and generally highly efficient algorithm. But when it comes to the crunch, A* still has to process that many nodes of the graph. So how do we reduce this count?

The immediate answer that comes to mind is spatial subdivision AKA resolution reduction. Essentially what you want to do is to generalise regions of your graph; visually, this could be compared to halving an image's width and height while using a pixel blending algorithm: each group of 4 pixels will be merged into 1, with that 1 being the result of the colours of those 4. In the case of pathfinding, your would for example merge the positions (and perhaps weights, depending on how you implement this) of your nodes.

The basic principle is this: When travelling to a city in another country, does one say, "I'm going to 11 Hill Street, Yoursuburb, Yourcity, Yourstate, Yourcountry"? No, one says "I'm going to Yourcountry, and only when I get through immigration will I start navigating at a smaller level of detail: City, then state, suburb, street etc." until finally one is navigating on a house-by-house and footstep-by-footstep basis (to whatever level of ultimate detail you want -- in your case, your basic tiles). This effectively reduces the number of cells you need to process.

Spatial subdivision can be eg. a quadtree approach for subdividing 2D planar topographies (as you presently have), or something closer to a navigation mesh, where you greatly reduce the number of nodes but the connections are now arbitrary (more organic) rather than grid-aligned.

PS. As a final note, consider any approach that makes heavy use of precalculation to reduce runtime overheads. Spatial subdivision is just one of these, but if after profiling you see other opportunities for improving performance, precalculation is your friend. It is my trusty pocket knife in all such situations -- the time-for-space tradeoff.

share|improve this answer
1  
I am using pre-calculation to a certain degree already, and have sat down with a pen and paper to work out the complexity of my algorithm in big-O (I'll have to check my notes to get the value), and I did manage to reduce it from an exponential to polynomial time (n^2 or n^3 for the worst case). I have also deliberately stuck to integer types in my algorithm, but unfortunately it is not good enough still. I'll have a look at spatial subdivision, but I had already been breaking it down to rooms as opposed to the entire journey... –  theheadofabroom Aug 9 '11 at 15:57
    
OK, the big-O part is more detail than I would have gone into, but that's great. Have you used a profiler to look at which specific parts of your code are now generating the most overhead in iteration? It's really about finding creative solutions to apply to those troublesome parts... And if it's something that isn't your own (e.g. a tardy math function), then you need to find a way around that. Also, how frequently are you actually calling this? I mean, pathfinding doesn't need to be run at eg. 30Hz -- it can be much more infrequent. –  Nick Wiggill Aug 9 '11 at 16:13
    
I'm running my algorithm when a movement action is triggered (this is done by selecting a point on-screen), and then again if there is a collision along the computed path due to a change in the environment, such as another character blocking that path. I guess running this in the background periodically to compute alternate paths would solve the issue of collisions. The remaining problem is on initially being given the move command. I suppose I could keep a list of paths to doors to reduce the first latency. I still need to speed this up more though, and using C would give this... –  theheadofabroom Aug 9 '11 at 19:51
    
Have you profiled your code? Sorry to bug you on this but the answer to this keeps getting lost in your responses. I may be wrong but I get the feeling your're guessing what's going on rather than simply profiling to identify and target the problem areas in a concrete way. And compare your (preferably graphic) profiling results between your desktop and mobile. If the graphs show the same speed reduction throughout, then back to the drawing board. If not, you need to look at the areas where they do differ, find out exactly what the mobile is choking on to find a way around it. –  Nick Wiggill Aug 10 '11 at 7:55
1  
See this, scroll down to "Profiling with callgraphs". The end result is a graphviz output; graphviz is a graph visualisation package. You can then compare your results, call by call, between mobile and desktop. –  Nick Wiggill Aug 11 '11 at 8:30

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.