Path Finding

[cazador7907]

I am not sure where to post this question as it concerns an algorithm and not an aspect of C++ or Qt.

Anyway, I am working on the development of a path finding routine. I put the pseudo code below and wanted to ask for people opinions and thoughts. The routine will search for a path across a sparsely populated Graph Object. The F-Cost is calculated based on the Heuristic of a node, the length of the edge connecting two nodes and efficiency of the edge.

The MasterList is a QMap Object
The OpenList is a Binary Heap
The Path object is a QVector

@
Path finding pseudo code

1. Initialize the two heaps: Open and Master.
2. Initialize the return Path vector object.
3. Is the starting node equal to the ending node?
   a. Add the end node to the return Path.
   b. Exit.
4. Create a new Path element from the starting node. F-Cost will be 0.0.
5. Add the Path element to the Master and Open heaps.
6. Examine each edge connected to the starting node.
   a. If the edge is owned, skip it and move to the next edge.
   b. If the edge is un-owned
   i. Create a new path node out of the destination node
   ii. Calculate the F-Cost for the destination node.
   iii. Set its parent property to the current node.
   iv. If the destination node equals the end point
   1. Add the destination node to the Path vector
   2. Exit
   v. If the destination node is not the end point
   1. Add the destination node to the Master and Open Heaps.
7. Find the current node in the Master heap and mark it closed.
   a. Set its closed property to true.
8. Pop the path node having the lowest F-Cost off of the Open heap and make it the current node.
9. Repeat the above process starting at #6.

@

[leon.anavi]

Hi,

In my opinion it is always easier to explain such kind of algorithm with a block diagram (espesially if it is executed by a single thread) :) You can also get inspiration for optimal solution from existing solutions for path finding algorithms such as the different implementations of the traveling salesman problem ;)

Best regards,
Leon