Thread: 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

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]

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)