Hi all, I have a simple question: where can I find the BEST article on A* and a couple of other pathfinding algorithm tutorials? I basically need to know how to implement it into C++, not just a straight code. Also, what the hell is the heuristic function, how you calculate it using starting, ending and other values on 2D grid? and how do you calculate and use f(n) = g(n) + h(n) formula with given values like start/end/etc? Thanks all. " Do we need us? "

Ionware Productions - Games and Game Tools Development

In what way is this ''different''?

The best way to work these things out is to read more than one article. All your questions, especially the simple ones about the heuristics, are answered there. There have been plenty of links posted in the past so it should just be a case of searching for them.

[ MSVC Fixes | STL | SDL | Game AI | Sockets | C++ Faq Lite | Boost | Asking Questions ]

Thanks Kylotan,
I now uderstand what heuristic function is (thanks to "Programming AI in Object Oriented way"), but I still have complains to articles that are in links of GameDev and some others, though they DO NOT explain what the hell is heuristic function is applied to the problem or simply to the position of start/end in pathfinding on 2d map.
Thanks for reply.

Are you telling me you''ve looked at several A* articles and not seen a single mention of concepts such as the Manhattan distance or Pythagorean distance with regards to the heuristic for 2D maps?

[ MSVC Fixes | STL | SDL | Game AI | Sockets | C++ Faq Lite | Boost | Asking Questions ]

I''m going to describe A* in terms of the evolution of searching algorithms.

Imagine a simple breadth first search, like a flood-fill algorithm, that searches readially outward from the starting point towards the ending point. As soon as you reach the destination, you trace back through its parents and you have the path. Simple.

Now, realize this: Rather than simply blindly moving outward, you can use an educated guess: Chances are, if I''m trying to get from point A to point B, and point B is to the north, the path will tend to extend in a northerly direction. So you use a heuristic, an estimate, that says "we should probably try looking at this possibility first."

The heuristic cannot be an overestimate. If it is, then it can cause longer paths to be evaluated as being more optimal.

The best heuristic function is generally one which estimates the exact minimum distance between two points. Without any constraints as to movement, this is a straight line, and is given simply by the Euclidian distance. In an RTS game, however, you are often constrained to ninety-degree angles, and, though you can still use Euclidian distance as your heuristic, manhattan distance works better. What is Manhatten distance, you ask? Well, let''s say you need to get from A=(4,5) to (B=8,2). Vector AB=(4,-3). Now, the Euclidian distance would be |AB|=sqrt(42+(-3)2)=5. However, since you''re constrained to 90 degree angles, you can''t just go southeast; you have to go south, then east, then south, then east. Also, you know that going south, south, south, south, east, east, east is the same as going south, east, south, east, south, east. In other words, using Manhattan distance, the length of the hypotenuse of a triangle is given by the sum of the lengths of its other two sides. If you think about it for a little, it''ll make sense.

On hex maps, you may want to develop another heuristic. Of course, the Euclidian one can work, but you can do better - just like Manhattan was better than Euclidian for square-tile maps.

I know often it helps to simply hear the same thing said in different words. I hope my post was helpful.

Cheers!