The issue of a multi-part tutorial covering all the aspects of path planning. This issue looks at the global picture, explaining the abstract concepts behind route generation. A formal definition, as well as a mathematical model of the problem is explained.

http://ai-depot.com/BotNavigation/Path.html

Sorry about the delay in new features everyone, these are busy times for me ;) Things should pick up over the next few days!

The second part has been posted. This issue looks into single source algorithms more closely. A prototype definition is given, and the Dijkstra approach is detailed thereafter.

Hello,

I added a pseudo code for Dijkstra's Algorithm to wikipedia. It's from Rivest's algorithm book. You may find it readable and elegant (at least I do). Perhaps even useful for your article.

http://www.wikipedia.com/wiki/Dijkstras_Algorithm

Heikki Orsila
heikki.orsila@tut.fi
http://www.ee.tut.fi/~heikki

Hi!

i can't understand the implementation of Dijistar's algorithm.
i want to find a shortest path from one source to one destination.
i have 50 nodes.
can any one help me in implementation in VC++.
or refer me any site from where i can take some help.
i am very thankful.

The algro is not correct. Temporary should get all nodes. The link
to the other tutorial should work.

Trailcode

The third part of the series has been posted, discussing negative arc-lengths and algorithms that use the label-correcting approach.

The 4th article in the series has just been posted, discussing all-pairs shortest path algorithms, naive implementations, and dynamic programming approaches. Improvements and optimisations are briefly analysed.

This issue discusses single-pair shortest paths, and how different kinds of search algorithms solve them. A* (star) is then explained as a heuristic approach; pseudo-code is provided and optimisation are overlooked.

Hello, I dont know if here is a right place to ask question or not;
The problem is in matrix form, there are walls, and stones like a puzzle. Our agent can not pass from the coordinates that it has passed before(and from walls) and should find the path from start to end that has the most number of stones. The agent can go in only 4 direction(right,up,down,left) not cross.
Which kind of search method do I use. Is there a general solutions to this kind of problems. Is it in which kind?... Thank You for having such a useful site.

i've learned that
f*(n) = g*(n) + h*(n)
where g*(n) estimates minimum cost fro start to n,
and h*(n) estimates minimum cost from n to goal.

from tutorial in http://ai-depot.com/BotNavigation/Path-AStar.html, "using the distance "as birds fly". This is a Euclidian distance", in order to get the h*(n), do i have to include location/coordinate as well, so that i can calculate the h*(n)?
or do we have another alternatives without involving the cordinate?

2. i am trying to figure out what are the following functions do.
edges.begin();
edges.end();
GetEndNode();

i wish to know what's input, and what it returns. that would be great if there 's a picture explains what the term refers to.

Thank you!

I think that this link will be very useful for you, a lot of information about heuristics used in A* :
http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html

Or just look at the whole site about A* :
http://theory.stanford.edu/~amitp/GameProgramming/