Thread: again on recursion-paths

//if already checked here
if (matrix[currentR][currentC].status==OPEN)
return LARGE;

This dosent look quite right. If you think about it, you are opening 4 new nodes each function call. When you hit a node on the open list from a different node you then need to check to see if the current cost is less than the existing cost, and, if so update it.

I think you should really be keeping track of the parent node you moved from as well. How is this providing a path? Your current code looks as if you need to run the pathfinding each time you want to move a square. Which is very inefficient.

can't see your logic...
if i hit from another node, how am i to know whether the path is better, maybe the cost is low through the new node because it has yet to go through some very expensive node later on in the path that must be gone through, while the old one has allready been through them

What comes in the future does not matter at all. As you will be moving from exactly the same location. So you weigh them entirely on the move cost it took to get there. With branching, there is often multiple ways to get to the same point and you want to take the lowest one right? Since you are opening four nodes at a time you can end up with multiple paths to the same open node on the open list. The second of which may be shorter than the first.

so, in conclusion, what i have to do is add a field for each node- .lowest, all not bother at all searching through it if it is lower than the lowest using the current path?

No, you dont have to add another field. Just check if the new node cost is less then the existing one on your open list and update it if appropriate. Heres what I mean, shown with the bold bit in the pseudocode for dijkstras algorithm off wikipedia:

Code:

 1  function Dijkstra(Graph, source):
 2      for each vertex v in Graph:           // Initializations
 3          dist[v] := infinity               // Unknown distance function from source to v
 4          previous[v] := undefined          // Previous node in optimal path from source
 5      dist[source] := 0                     // Distance from source to source
 6      Q := the set of all nodes in Graph    // All nodes in the graph are unoptimized - thus are in Q
 7      while Q is not empty:                 // The main loop
 8          u := vertex in Q with smallest dist[]
 9          remove u from Q
10          for each neighbor v of u:         // where v has not yet been removed from Q.
11              alt := dist[u] + dist_between(u, v)       // be careful in 1st step - dist[u] is infinity yet
12              if alt < dist[v]              // HERE
13                  dist[v] := alt
14                  previous[v] := u
15      return previous[]

is it correct to say this function (Dijkstra) will work with negative values (costs to go from node to node)?