-
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);
-
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
-
oops, forget to write that all bestFromStart values are initilized to LARGE
-
: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]
-
Code:
matrix[currentR,currentC]
is definitely, absolutely, wrong. It is the same as
(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
-
obviously!!
i should have written
Code:
&matrix[currentC][currentR]
-
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;
}
-
can you tell us what u are expecting and what u are getting..?
-
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
-
pasted it into my ide - works fine for me (result is -997 in a random matrix setup like yours)