recursive pathfinding

This is a discussion on recursive pathfinding within the C Programming forums, part of the General Programming Boards category; Hi, This function is a solution for recursivly finding the lowest cost path between two points in a 2D matrix. ...

  1. #1
    Registered User
    Join Date
    Jan 2009
    Posts
    43

    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);

  2. #2
    Registered User
    Join Date
    Jun 2003
    Location
    Austria
    Posts
    55
    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

  3. #3
    Registered User
    Join Date
    Jan 2009
    Posts
    43
    oops, forget to write that all bestFromStart values are initilized to LARGE

  4. #4
    Registered User
    Join Date
    Jun 2003
    Location
    Austria
    Posts
    55
    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]

  5. #5
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  6. #6
    Registered User
    Join Date
    Jan 2009
    Posts
    43
    obviously!!
    i should have written
    Code:
    &matrix[currentC][currentR]

  7. #7
    Registered User
    Join Date
    Jan 2009
    Posts
    43
    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;
    }

  8. #8
    Registered User
    Join Date
    Jun 2003
    Location
    Austria
    Posts
    55
    can you tell us what u are expecting and what u are getting..?

  9. #9
    Registered User
    Join Date
    Jan 2009
    Posts
    43
    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

  10. #10
    Registered User
    Join Date
    Jun 2003
    Location
    Austria
    Posts
    55
    pasted it into my ide - works fine for me (result is -997 in a random matrix setup like yours)

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. recursive pathfinding vs linker
    By ichijoji in forum C++ Programming
    Replies: 2
    Last Post: 09-21-2004, 01:24 PM
  2. difference between recursive and iterative
    By Micko in forum C Programming
    Replies: 33
    Last Post: 07-06-2004, 09:34 PM
  3. Algorithm help (Changing from Recursive to Non Recursive)
    By Thantos in forum C++ Programming
    Replies: 1
    Last Post: 04-25-2004, 07:27 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  5. How to change recursive loop to non recursive loop
    By ooosawaddee3 in forum C Programming
    Replies: 1
    Last Post: 06-24-2002, 08:15 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21