I recently made a program using Python and Pygame that finds that find the shortest path from point A to point B using the A* algorithm described in Patrick Lester's article in the resources section. My question is this. How can I use the A* algorithm to do time based movements of sprites? Currently I have a grid with 192 nodes and depending on how the obstacles are set up it can take a few seconds for the shortest path to be discovered. Would that mean that units in the game would just be standing still until the complete path is discovered and only then move? On a much larger gird this problem will only become worse. Obviously this is not what happens in games, so how do you move your unit in the direction of the target when the complete path has not yet been discovered. I am currently only doing movement in 2D space. Thanks. Maulin

There's an article in AI Programming Wisdom that discusses this.

Something fairly easy you can do is write your AStar pathfinder so that it will run X number of iterations, save the data, and then allow other components to do there thing. This means that your pathfinder will not take up a large portion of the game loop. Of course this won't fix your problem yet.

Next, when initially finding a path return a "guess". This would entail running your pathfinder for X loops and then returning that guess to your entity so it can begin moving immediately. I can't remember how many loops I used, probably around 20-50.

That guess is not going to get you to your destination but, while the entity is moving to that guess you can work out the rest of the path. All you need to do then is return that path, hook up the current position of the entity to your real path, and you're set.

I used a messaging system to get this working when I implemented it. My entities would "request" paths and the pathfinder would immediately send that guess. Then the pathfinder would keep track of who wants paths and where they want to go. When the paths are found I sent out a message and that was that.

It seemed to work out fairly well.

Thanks Peter, I'll check it out.

Quote: Original post by mpathare
I have a grid with 192 nodes and depending on how the obstacles are set up it can take a few seconds for the shortest path to be discovered

That seems like an awfully long time for a small search space, even if no path exists and your A* implementation had to process every node. Perhaps you should examine your code for potential bottlenecks?

In comparison, the implementation of A* that I'm using searches 400 nodes, each with three or less connections, in less that a millisecond on a 1.8 Ghz processor. Assuming a similar speed computer, if it's taking you two seconds to search 200 that's at least 4000 times faster!

Jackson Allan

Yeah, the algorithm can definitely be optimised first, long before you need to start thinking about following partial paths and so on. Feel free to post your code for some hints (perhaps in the Scripting Languages forum if you're hoping for Python specific help).

If you guys have any tips on how to speed up my code it will be much appreciated! I have recently started learning Python, so please be gentle :)

I could try to implement the open list as a binary tree as has been mentioned some article.

I don't know how to attach files or paste code into the reply, so here is a pastebin link to my code.

http://pastebin.com/m63c584d0

If you decide to run the code, clicking the right mouse button will set a node as an obstacle, clicking the left button once will set a node as the starting point and clicking it a second time will set a node as the destination. Once the start and end nodes are set a path will be calculated.

Thanks guys,

PS: could you point me to the name of the article Peter was talking about that talks about initially moving units with a "guess"

Quote: Original post by mpathare
On a much larger gird this problem will only become worse. Obviously this is not what happens in games, so how do you move your unit in the direction of the target when the complete path has not yet been discovered.

Lots of games (particularly RTS games) cheat - they'll play a sound to acknowledge you've told them to move, then just move directly towards the goal. When the final path is calculated then they'll switch to following that instead. Most of the time the guessed direction will be correct (or close enough) and you'll not notice a difference. On some really complicated maps it's possible you'll see the unit double back on itself (which actually does happen in some RTS games).

Your nodes' use of rects is a bit confusing, and your path finding code has drawing code scattered around inside of it. The most important thing is to make the code clear and to make it do just the thing it is supposed to do (find a path, let some other system worry about drawing the path). The use of exceptions is also awkward. Exceptions should be used for the uncommon, possibly unexpected cases, not the expected program flow.

I think you're also looping through every node in the map each iteration? That's extremely inefficient. And in some cases, the program is giving me slightly suboptimal paths, so there is an error somewhere.

Quote: Original post by Vorpy
Your nodes' use of rects is a bit confusing, and your path finding code has drawing code scattered around inside of it. The most important thing is to make the code clear and to make it do just the thing it is supposed to do (find a path, let some other system worry about drawing the path). The use of exceptions is also awkward. Exceptions should be used for the uncommon, possibly unexpected cases, not the expected program flow.

I think you're also looping through every node in the map each iteration? That's extremely inefficient. And in some cases, the program is giving me slightly suboptimal paths, so there is an error somewhere.

Thanks for taking the time to go through my code.
This program was just meant as a way for me to understand the A* algorithm and thats why I had the drawing code in there, so I could follow what was happening. You are correct, the best way would be to let the find_path() function just find the path and have some other system draw the game components.

The try except block was confusing to me too! I couldn't think of another way to do it at the time.

What part about using the rects did you find confusing? I loop through the entire list of nodes to find adjacent nodes, is there another way to do this? And can you post a screen shot of the suboptimal paths you are getting? i would like to correct the bug.

The simplest case that gives incorrect results is having a single wall, putting the start space 3 tiles left and 1 tile up from the wall, and the end space 1 tile to the right from the wall. Unless diagonal moves are supposed to cost the same as horizontal ones, but from the code it looks like they aren't.

The use of rects is confusing because I think you're using them to store adjacency information in some overcomplicated way. In a grid world, you can store the nodes in a 2d array and quickly find adjacent cells by looking at the neighbors in the array, given the node's position. In general, the nodes are connected in a graph structure and given a node you just need to find the adjacent nodes. One way is to have a list of adjacent nodes for each node in the graph. Depending on the problem, the adjacency list could even have a mix of an implicit and an explicit representation.