# recursive pathfinding

• 02-10-2009
msshapira
recursive pathfinding
Hi,
This function is a solution for recursivly finding the lowest cost path between two points in a 2D matrix. the cost of each step is its ".value". it's passed with the cordinates for the start and end points.
However, somethings not working here and I get the wrong results.
i think this is similar to the A* pathfinder but the only examples i have seen are not recurisive...

LARGE is the limit of "long int"

Code:

```#include "targ62.h" long int GetMin(Node** matrix,int currentR,int currentC,int endR,int endC,                                 int rows,int columns,Node* father) {         long int result;         //if out of bounds return max of field         if (currentR==rows || currentC==columns || currentR<0 || currentC<0)                 return LARGE;         //if reached end         if (currentC==endC && currentR==endR)                 return (matrix[currentR][currentC].value);         //if already checked here         if (matrix[currentR][currentC].status==OPEN)                 return LARGE; /*record distance from beggining*/         //if first node         if (father==NULL)                 //assign first value as best value                 matrix[currentR][currentC].bestFromStart=                         matrix[currentR][currentC].value;         //if not first node         else         {                 //if bestFromStart old value higher than current value                 if ( (matrix[currentR][currentC].value +                         father->bestFromStart ) <                         matrix[currentR][currentC].bestFromStart )                         //then...                         matrix[currentR][currentC].bestFromStart=                                 matrix[currentR][currentC].value+                                                                father->bestFromStart;                 else                         /*this is a bad path -                         this way is not shorter than previously found way*/                         return LARGE;         }                        //if not reached end                matrix[currentR][currentC].status=OPEN;         result=Smallest4(                 GetMin(matrix,currentR,currentC+1,endR,endC,rows,columns,                         matrix[currentR,currentC]),                 GetMin(matrix,currentR,currentC-1,endR,endC,rows,columns,                         matrix[currentR,currentC]),                 GetMin(matrix,currentR+1,currentC,endR,endC,rows,columns,                         matrix[currentR,currentC]),                 GetMin(matrix,currentR-1,currentC,endR,endC,rows,columns,                         matrix[currentR,currentC]));         //set current status to closes- can try here again                matrix[currentR][currentC].status=CLOSED;                 //if was blocked all directions         if (result==LARGE)                 return LARGE;         return matrix[currentR][currentC].value+result; }```
the function is called with the following starting parms:
Code:

`result=GetMin(matrix,startR,startC,endR,endC,rows,columns,NULL);`
• 02-10-2009
IceBall
hm..

is matrix[currentR][currentC].bestFromStart already filled at this line?
expecting "value" is a positive number - i would say this statement is never true when matrix[currentR][currentC].bestFromStart is zero

Code:

```                if ( (matrix[currentR][currentC].value +                         father->bestFromStart ) <                         matrix[currentR][currentC].bestFromStart```
• 02-10-2009
msshapira
oops, forget to write that all bestFromStart values are initilized to LARGE
• 02-10-2009
IceBall
:confused: so my best guess is that theres something wrong with matrix[currentR,currentC] <- i'm not sure about that. i'd have used somthing linke &matrix[currentR][currentC]
• 02-10-2009
matsp
Code:

`matrix[currentR,currentC]`
is definitely, absolutely, wrong. It is the same as
Code:

`matrix[currentC]`
(Except it also evalautes currentR and throws away the result).

I expect the compiler will complain about "statement with no effect" or some such if you turn up the warning level sufficiently high.

--
Mas
• 02-10-2009
msshapira
obviously!!
i should have written
Code:

`&matrix[currentC][currentR]`
• 02-10-2009
msshapira
but it's still not working....
(!!!!!!!!)

what's going wrong?? is there a problem with my logic?

Code:

```long int GetMin(Node** matrix,int currentR,int currentC,int endR,int endC,                                 int rows,int columns,Node* father) {         long int result;         //if out of bounds return max of field         if (currentR==rows || currentC==columns || currentR<0 || currentC<0)                 return LARGE;         //if reached end         if (currentC==endC && currentR==endR)                 return (matrix[currentR][currentC].value);         //if already checked here         if (matrix[currentR][currentC].status==OPEN)                 return LARGE; /*record distance from beggining*/         //if first node         if (father==NULL)                 //assign first value as best value                 matrix[currentR][currentC].bestFromStart=                         matrix[currentR][currentC].value;         //if not first node         else         {                 //if bestFromStart old value higher than current value                 if ( (matrix[currentR][currentC].value +                         father->bestFromStart ) <                         matrix[currentR][currentC].bestFromStart )                         //then...                         matrix[currentR][currentC].bestFromStart=                                 matrix[currentR][currentC].value+                                                                father->bestFromStart;                 else                         /*this is a bad path -                         this way is not shorter than previously found way*/                         return LARGE;         }                        //if not reached end                matrix[currentR][currentC].status=OPEN;         result=Smallest4(                 GetMin(matrix,currentR,currentC+1,endR,endC,rows,columns,                 &(matrix[currentR][currentC])),                 GetMin(matrix,currentR,currentC-1,endR,endC,rows,columns,                         &(matrix[currentR][currentC])),                 GetMin(matrix,currentR+1,currentC,endR,endC,rows,columns,                         &(matrix[currentR][currentC])),                 GetMin(matrix,currentR-1,currentC,endR,endC,rows,columns,                         &(matrix[currentR][currentC])));         //set current status to closes- can try here again                matrix[currentR][currentC].status=CLOSED;                 //if was blocked all directions         if (result==LARGE)                 return LARGE;         return matrix[currentR][currentC].value+result; }```
• 02-10-2009
IceBall
can you tell us what u are expecting and what u are getting..?
• 02-10-2009
msshapira
i gave it a 3X3 matrix when one of the values is -1000 and all the others are 1
looking for a path from 0,0 t0 1,0 i was expecting -991 but got 2
• 02-11-2009
IceBall
pasted it into my ide - works fine for me (result is -997 in a random matrix setup like yours)