help with recursive C pathfinding

Intel / Centrino
February 10, 2009 at 23:12:37
Specs: Windows XP, 2.0 3GB
Hi all,
I have written recurisve pathfinding fuction
from matrix[i][j] to matrix[x][y]. however
it's not returning the right values. It is
supposed to return the minimal cost from 2
points using any possible path.
all ".value" are the cost to use this Node
all ".bestFromStart" are the max of long int
field.
all ".status" are "CLOSED"
any help would be appriciated!!

/* a brief breakdown of this algorithm:
We have defined a high value (currently the 
limit of "long int") as the "error"
return.
We start searching the matrix. If at any 
point it we find that the way we are
trying is longer allredy that the best 
existing way through specific node, we
return LARGE, meaning do not continue 
searching throuh this node.
We make sure we dont recourse though a node 
that has allready been included in
the current path by setting it's status to 
OPEN upon enterting the recusrive
part of the program. If we now will reach any 
node which is OPEN, we return 
LARGE- an ending value.
We then search in all derections for any 
result that doesnt return large and 
return to the main fuction the smallest of 
all directions.
This way is not entirely fault tolerent 
because it does not deal with the case
of value=LARGE, but on the other hand it's 
not meant to deal with value>LARGE
either.
*/
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=OPE
N;
	result=Smallest4(
		
GetMin(matrix,currentR,currentC+1,endR,endC,r
ows,columns,
		
&(matrix[currentR][currentC])),
		
GetMin(matrix,currentR,currentC-
1,endR,endC,rows,columns,
			
&(matrix[currentR][currentC])),
		
GetMin(matrix,currentR+1,currentC,endR,endC,r
ows,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=CLO
SED;
	
	//if was blocked all directions
	if (result==LARGE)
		return LARGE;

	return 
matrix[currentR][currentC].value+result;
}


the function all first called with
father==NULL


See More: help with recursive C pathfinding

Report •


#1
February 18, 2009 at 22:48:16
wrote this long time ago based on an algorithm book i found at the library.

map.cpp

// method to set the algorithm used on shortest path
void Map::setAlgorithm(int algorithm)
{
	this->algorithm = algorithm;
}

// method to find the shortest path from one point to another
// Reference: Data Structure and Algorithm Analysis in C (005.133 C-WE)
POINTSTACK Map::shortestPath(int srcCol, int srcRow, int destCol, int destRow, int who)
{
	// codes for thread-synchronization, seems not working at all
	CRITICAL_SECTION cs;
	InitializeCriticalSection(&cs);
	EnterCriticalSection(&cs);
	WaitForSingleObject(hSema, 60000);	// wait 60 seconds;
	
	while (flag == TRUE)
	{SleepEx(100, FALSE);}


	POINTSTACK route;
	INTQUEUE q;
	int index;

	/* init routing table */
	for (int row=0; row<mapSize.cy; row++) 
		for (int col=0; col<mapSize.cx; col++)
		{
			index = (row*mapSize.cx)+col;
			vRoutingTable.at(index).init();
		}

	/* set source distance to 0 */
	index = (srcRow*mapSize.cx)+srcCol;
	vRoutingTable.at(index).setDistance(0);
	vRoutingTable.at(index).setPath(index);

if (algorithm == UNWEIGHTED)
{
	q.push(index);

	/* Unweighted shortest path algorithm */

	while (!q.empty())
	{
		index = q.front();
		q.pop();
		vRoutingTable.at(index).setKnown(TRUE);
		{
			// for each possible direction
			for (int direction = 0; direction < 4; direction++)
				if (!this->getWall(index, direction))
				{
					int next = getNextPoint(index, direction);
					if (vRoutingTable.at(next).getDistance() == MAX_INTEGER)
					{
						vRoutingTable.at(next).setDistance(vRoutingTable.at(index).getDistance() + 1);
			 			vRoutingTable.at(next).setPath(index);
						q.push(next);
					}
				}
		}
	} 
}
else if (algorithm == DIJKSTRA)
{
	/* Dijkstra's Algorithm, find the shortest path for weighted graph */
	while (true)
	{
		int smallest = MAX_INTEGER;
		// find smallest unknown distance vertex
		for (int i=0; i<mapSize.cx*mapSize.cy; i++) 
			if (!vRoutingTable.at(i).isKnown() && vRoutingTable.at(i).getDistance() < smallest)
			{
				smallest = vRoutingTable.at(i).getDistance();
				index = i;
			}
		if (smallest == MAX_INTEGER) break;

		vRoutingTable.at(index).setKnown(TRUE);
		
		int cost, index2;
		// for each possible direction
		for (int direction = 0; direction < 4; direction++)
			if (!this->getWall(index, direction))
			{
				int next = getNextPoint(index, direction);
				if (!vRoutingTable.at(next).isKnown())
				{
					cost = 0;
					// check if there are bullets on the route
					for (vIterator = pvBullet->begin(); vIterator != pvBullet->end(); vIterator++)
					{
						// if the bullet is not his bullet, increase the cost to travel that path
						if (vIterator->getOwner() != who)
						{
							index2 = div(vIterator->getPos().x, cellSize.cx).quot+
								(div(vIterator->getPos().y, cellSize.cy).quot*mapSize.cx);
							if (index == index2)
								cost += (int)(vIterator->getPower()/4);
						}
					}
	
					if (vRoutingTable.at(index).getDistance() + getCost(next) + cost <
						vRoutingTable.at(next).getDistance())
					{
						vRoutingTable.at(next).setDistance(
							vRoutingTable.at(index).getDistance() + getCost(next) + cost);
						vRoutingTable.at(next).setPath(index);
					}
				}
			}
	} 
}
	/* extract the shortest path from the table */
	POINT temp;
	temp.x = destCol;
	temp.y = destRow;

	route.push(temp);
	do {
		int path;
		path = vRoutingTable.at((temp.y*mapSize.cx)+temp.x).getPath();
		temp.x = div(path, mapSize.cx).rem;
		temp.y = div(path, mapSize.cx).quot;
		route.push(temp);
	} while (!(temp.x == srcCol && temp.y == srcRow));



	POINTSTACK routeTemp = route;
	LeaveCriticalSection(&cs);
	ReleaseSemaphore(hSema, 1, NULL);
	flag = FALSE;

	return routeTemp;
}

map.h

typedef stack<POINT> POINTSTACK;
typedef vector<Cell> CELLVECTOR;
typedef vector<Routing> ROUTINGTABLE;
typedef queue<int> INTQUEUE;		// used in unweighted shortest path
typedef vector<Bullet> BULLETVECTOR;

#define MAX_INTEGER		0xFFFF
#define CELLSIZE		70
// algorithm type
#define UNWEIGHTED		0
#define DIJKSTRA		1


Report •
Related Solutions


Ask Question