again on recursion-paths

This is a discussion on again on recursion-paths within the C Programming forums, part of the General Programming Boards category; Ok, here's my final for pathfinding: it works fine (all status start "CLOSED"), on matrices under 7*7, but it hangs ...

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

    again on recursion-paths

    Ok, here's my final for pathfinding:
    it works fine (all status start "CLOSED"), on matrices under 7*7, but it hangs on bigger ones. I've made it sweet and simple but not so efficient... any ideas?
    (my previous post on the issue)recursive pathfinding
    Code:
    long int GetMin(Node** matrix,int currentR,int currentC,int endR,int endC,
    				int rows,int columns)
    {
    	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;
    
    	//if not reached end	
    	matrix[currentR][currentC].status=OPEN;
    	result=Smallest4(
    		GetMin(matrix,currentR,currentC+1,endR,endC,rows,columns),
    		GetMin(matrix,currentR,currentC-1,endR,endC,rows,columns),
    		GetMin(matrix,currentR+1,currentC,endR,endC,rows,columns),
    		GetMin(matrix,currentR-1,currentC,endR,endC,rows,columns));
    
    	//set current status to closed- 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;
    }
    oh, and of course
    Code:
    #define LARGE LONG_MAX
    Last edited by msshapira; 02-15-2009 at 11:41 AM.

  2. #2
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    //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.

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

  4. #4
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    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.

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

  6. #6
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    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[]

  7. #7
    Registered User
    Join Date
    Jan 2009
    Posts
    43
    is it correct to say this function (Dijkstra) will work with negative values (costs to go from node to node)?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Template Recursion Pickle
    By SevenThunders in forum C++ Programming
    Replies: 20
    Last Post: 02-05-2009, 09:45 PM
  2. convert Recursion to linear can it be done
    By umen242 in forum C++ Programming
    Replies: 2
    Last Post: 10-15-2008, 03:58 AM
  3. Recursion... why?
    By swgh in forum C++ Programming
    Replies: 4
    Last Post: 06-09-2008, 10:37 AM
  4. Q: Recursion to find all paths of a maze
    By reti in forum C Programming
    Replies: 7
    Last Post: 11-26-2002, 09:28 AM
  5. a simple recursion question
    By tetra in forum C++ Programming
    Replies: 6
    Last Post: 10-27-2002, 10:56 AM

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