Printable View
Sorry, I never got around to making the tutorial. I need to, but life (and more interesting projects) always seem to get in the way.
The technique I outlined isn't actually my own. It's from an article by Smith Surasmith I believe. I posted the details in the other thread. I just implemented it in Flash using Brandon Hall's Dijkstra implementation.
Have fun!
Hello,
Sounds like you guys are figuring this out pretty well! I just wanted to throw one more piece of information at you.
It is common in games to use multiple pathfinding algorithms. As someone else mentioned, A* can be pretty expensive CPU-wise. So you don't want to load it down on 20 npcs or anything. But you could use A* or some other "smart" algorithm on your main character and the occasional Boss npc. But your run-of-the-mill idiot npcs can just bop around using a very light algo. This is a common technique.
which algorithm would you recommend for the run of the mill NPCs then?
LittleRed,
Well, that just depends on what you want to do. I'd probably just come up with my own from scratch for little npcs. I'd just have them walk in random directions and at some time in the future choose a new path. I might do something like if a NPC happens to be within a certain range of the hero then the NPC gets a little smarter and will move toward the hero.
There is no single algo that I'd recommend. Tracing and robust tracing are pretty easy and light weight. If you have my book then check out the AI chapter, I have a little fuzzy logic AI algo that allows npcs to chace the hero. They just hit walls and then turn toward the hero.
yeah, I think buying your book would help immensely.
right - I'm off to Amazon...!
I made little example of the best-first search, which in my example map is more then 10 times faster compared to the A*.
http://www.tonypa.pri.ee/test/best_first1.html
http://www.tonypa.pri.ee/test/astar2.html
Astar from zeh uses free A* published by zeh.
Other search is from the Jobe's book (MX version).
And robust tracing version is from Klas Kroon.
Hi tonypa,
Nice job :)
Yeah, A* isn't known for its speed at all. There are a couple of things I'd like to point out here. Choosing a search algorithm is a very custom task for every situation.
If all you need is blazing speed and you don't care much for the path used, then some sort of tracing is great.
If on the other hand you need the "lowest cost" path over a multi-terrain environment taking just all possible environmental concern into account, then you need to use the swiss army knife of the pathfinding world: A*
Most successfull retail games that make use of pathfinding use several different algorithms for different characters. If you are playing a game like Diablo and you click on the other side of a puddle or river, then A* will attempt to find a bridge for you to cross. If there is no bridge close enough then you'll swim across.
On the other hand, if a dumb enemy see's you on the other side of the river it might walk toward you till it hits the water, and then stop, or turn in a random direction.
Anyway, I also wanted to point out that it looks as if there is an error in those A* algorithms or they were implimented improperly. They both return the same number of steps, which is good. But both of them failed to return the shortest path, which is guaraneed. The shortest path uses diagonals. (Note: if 'diagonals' were marked as illegal in the algo, then this probably is the shortest legal path)
Moving diagonal is a distance of 1.41. But moving over and then down is a distance of 2.
Anyway, if you ever get a hold of my latest game book I have greatly improved on the A* algorithm. Although it probably would still take 200-300 ms to calculate the path you have in this grid.
As always, just use the right algo for the right situation! If you have two robots going at it in an empty room. Don't waste CPU with A*. If you have your hero running through the ruins of Pompei, you might want to consider A* :)
Thanks, Jobe, for comments :)Quote:
Originally posted by jobemjobem
Anyway, I also wanted to point out that it looks as if there is an error in those A* algorithms or they were implimented improperly. They both return the same number of steps, which is good. But both of them failed to return the shortest path, which is guaraneed. The shortest path uses diagonals. (Note: if 'diagonals' were marked as illegal in the algo, then this probably is the shortest legal path)
I did turn off the diagonal moves to compare them.
I absolutely agree on the multi-terrain feature, which best-first search cant handle.
I am also aware that if the possible path would lead long time in one direction, but actually should go around the corner, then best-first search is wasting more time.
Im sure your new A* is much faster, but I suppose its also created using AS2. Would you say code compiled using AS2 runs somehow faster? Or it doesnt matter until you run it in the Flash player 7?
tonypa,
I'd say it's mostly related to the Flash 7 player. But my latest version is a little faster than the previous for other reasons as well (removed inefficiencies).
Anyway, nice work on creating the algo. I'm sure it will come in handy!
Hey! No one showed the speed of pre-computed pathfinding techniques! I personally feel that pre-computed pathfinding is the superior choice in static maps like this.
Number crunching time! In general, the best way to compare overall performance is to establish a base line and then use all other times as a percentage of the base line. It sounds much harder then it is.
I have run three tests of each algorithm presented in this thread on my machine. I marked the results in milliseconds of each of the tests below. The Avg. column indicates these three tests averaged together. I used "Best First" as the base line and set it to 100%. I then computed the percentage of difference for the other algorithms by dividing their average time by the average time of "Best First" and multipling by 100.
The percentage is used to illustrate differences in performace across machines better then straight milliseconds. This means that if something is 50%, then it is 2x faster then the base line. Specifically, it will take 50% LESS time then the base line took.
Without further delay, here are the results:
Pre-computed is dramatically faster on every run. I attached a picture to show this test. Intersting to note that pre-computed also generated the most "accurate" path of all the ones listed. In fact, it generated a "perfect" path in that it is the shortest possible solution. There might be multiple solutions as short, but none shorter. If the A* algos were allowed to support diagonals, then they would have had as short solutions.Code:Algo. 1st 2nd 3rd Avg Percentage
Best First 43 40 38 40.33 100%
Precomputed 1 1 1 1.00 2.48%
Klas RT 10 10 11 10.33 25.62%
Zeh A* 415 408 410 411.00 1019.01%
Jobe A* (MX) 675 675 681 677.00 1678.51%
The whole point of this is that there are many different options when pathfinding and it's doubtful that you will find a perfect one for any game. Leveraging several at once is almost certainly the best option. I know for a fact that most commercial games do this.
Here is a breakdown of some high-level algorithms.
A*
Pros - Can be tuned many ways to be usably fast. Handles multiple terrain types. Guarantees shortest paths. Will adapt to ANY situation
Cons - Can be slow so needs to be used sparingly. The map needs to have lots of costing data for the search algorithm to use
Tracing
Pros - Pretty fast. Works on dynamic maps.
Cons - Paths are not "perfect". No terrain handling
Precomputed
Pros - Blazing speed, no technique is faster. Guarantees shortest paths (based on the implementation used to pre-compute)
Cons - Doesn't handle dynamic maps. Storing the search data might be difficult or cumbersome.
Have fun!