Welcome!
This is the community forum for my apps Pythonista and Editorial.
For individual support questions, you can also send an email. If you have a very short question or just want to say hello — I'm @olemoritz on Twitter.
A* Pathfinding
-
Tutorial I based this project on: http://www.youtube.com/watch?v=KNXfSOx4eEE
Actual program: https://gist.github.com/52234fc597c5b2aeccef (Update 4/03)This is designed for iPad, landscape viewing. It could be easily tweaked for iPhones, but as I don't own one, I will leave that to you guys hehe
Comments:
This one took a while for me to figure out.. and it still needs some work. But it does what it was intended to do mainly: it uses an A* algorithm to find its path through debri. It can definitely be tweaked more..
The 'player' is the blue block. Its target is the yellow block. Red blocks are randomly placed on the grid. Blue blocks are 'water' and have a speed penalty, so the program tries to avoid them. The algorithm searches for the shortest route.
Every time you click is another step in the not-so-simple algorithm. The numbers on the top left of each grid are the grid index, the numbers on top right are the manhattan distance to goal, the numbers on bottom left are its parent grid, and numbers on bottom right are movement cost (water is 15, land is 10)
This heuristic search is designed so you avoid searching EVERY last pixel for the shortest route, and instead sometimes guess.
-
Thanks, this looks very interesting. You get an A* for working this out! :)
-
It works fine but it needs some tweaking. There is one last step I'm missing.
After it finds a path that it considers the shortest, it should double check the available nodes somehow and alter the parents if an even shorter path is obvious. But I can't figure out quite how to do that (the tutorial doesn't explain that step..)
But yeah it's very interesting. I will be using an A* implementation in the RTS game I am in the process of creating. The next tricky part is how to handle formations, for if you want to control multiple units at once. I know in Age of Empires they would clump the units together into one 'army' first, and then pathfind for the entire army instead of for all the units.
-
https://gist.github.com/52234fc597c5b2aeccef
Minor update that fixed a problem with the heuristic.
My last update was technically a greedy first search algorithm, and while it worked (very nicely in most cases) it would often sacrifice path efficiency and I wanted a straight line. So I researched A* some more. Apparently, the cost to move to the node (the heuristic) is a little more complicated than I had it originally. Instead of only including manhattan distance and move cost, the nodes also need to have the value of their parent node's heuristic. Like before, these values are represented with the purple text in the top right of each box. You will notice now that as the 'player' box moves around, it updates the heuristic value of children boxes to include the parents heuristic as well.
Confusing, but just try it out. You will see a major difference in the behavior of this walk pattern. It often takes more searches than my last version but it also finds the best route pretty much without fail now.
