A*

Genghiz Cohen

Sup dewds,
For a project I have to do I need to implement an A* search algo, the map is basically a Pac-Man map

The red points are the nodes. (Small Picture for converting to ASCII for integration)

So anyone know where to get a useful C++ tutorial for implementing A*?

ronivek

How can anyone who is implementing something like an A* algorithm in C++ not know how to find research material?

Here are some links I came up with in a fraction of the time it is taking me to reply to your post;

http://en.wikipedia.org/wiki/A*_search_algorithm
http://www.boost.org/doc/libs/1_38_0/libs/graph/doc/astar_search.html

Cantab.

Russel & Norvig (one of the most cited computer science books in the world) has lots of stuff about A* search.

Would be surprised if there aren't freely-available, open-source A* search libraries available on the web already.

Genghiz Cohen

ronivek wrote:

How can anyone who is implementing something like an A* algorithm in C++ not know how to find research material?

Here are some links I came up with in a fraction of the time it is taking me to reply to your post;

http://en.wikipedia.org/wiki/A*_search_algorithm
http://www.boost.org/doc/libs/1_38_0...ar_search.html

You should assume I have looked at both of those and found them unhelpful.
Because I have, and they are.
I'm looking for more of a tutorial, what are the problems encountered, what methods, classes functions are best?

Cantab. wrote: »

Would be surprised if there aren't freely-available, open-source A* search libraries available on the web already.

Can't use libs, have to write it myself.
while learning from libs is an option, grinding through it is quicker than trying to find a good C++ one, getting used to the coding style, finding the bits that are important, then figuring it out.
At least it is so far.

NeverSayDie

Well, A* is a popular topic, a quick Google turns up dozens of tutorials in C++ and everything else besides, take your pick I guess.

Not sure what you mean by "what methods and functions are the best", but this one on GameDev seems to have a reasonable discussion of implementation issues, and links to further reading;
http://www.gamedev.net/reference/articles/article2003.asp

Genghiz Cohen

NeverSayDie wrote: »

Well, A* is a popular topic, a quick Google turns up dozens of tutorials in C++ and everything else besides, take your pick I guess.

Not sure what you mean by "what methods and functions are the best", but this one on GameDev seems to have a reasonable discussion of implementation issues, and links to further reading;
http://www.gamedev.net/reference/articles/article2003.asp

Yeah, I was having a look at that one alright.