Jump to content
  • Advertisement
Sign in to follow this  
pawikan

Search algorithm

This topic is 3244 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello, I have been working on this code to try and get the search algorithm working correctly. To visualise, the green sphere now follows the route determined by the depth first algorithm, following the instructions defined in the stack. The sphere, checks the next target position and looks at the direction moving accordinly and then repeats. The problems seems to be that the stack is never decremented, when putting a break point here, the stack is at 1518 which is should not get that high before all edges have been visited on a given node. In the video below, you can see what happens to the route, the sphere seems to go through all edges available from each node. Can anyone recommend a solution, the data structure is now in place, with each node having the data for the number of edges, number of edges visited, and the X Y start and end details for each edge as well as the direction of the edge. Any help appreciated Video : YouTube -
while (foundRoute == false) {
		//once all edges from the start node have been checked the route should have been found
		if (floorcells[startX][startY].egdesVisted == floorcells[startX][startY].numberOfEdges) {
				foundRoute = true;
		}
		//check if the next edge is the end node
		if (floorcells[floorcells[stackArray[stackPos].X][stackArray[stackPos].Y].edges[floorcells[stackArray[stackPos].X][stackArray[stackPos].Y].egdesVisted].endNode.X][floorcells[stackArray[stackPos].X][stackArray[stackPos].Y].edges[floorcells[stackArray[stackPos].X][stackArray[stackPos].Y].egdesVisted].endNode.Y].exitFinal == true) {
			//foundRoute = true; - each time the final cell is found the route will be transferred to check against alternatives for the fastest route
			stackArray[stackPos].X = floorcells[stackArray[stackPos].X][stackArray[stackPos].Y].edges[floorcells[stackArray[stackPos].X][stackArray[stackPos].Y].egdesVisted].endNode.X;
			stackArray[stackPos].Y = floorcells[stackArray[stackPos].X][stackArray[stackPos].Y].edges[floorcells[stackArray[stackPos].X][stackArray[stackPos].Y].egdesVisted].endNode.Y;
			stackPos++;
		}
		//if the route has not be found
		if (foundRoute == false) {
			//check if there are any more edges to visit from the node 
			if (floorcells[stackArray[stackPos].X][stackArray[stackPos].Y].egdesVisted <  floorcells[stackArray[stackPos].X][stackArray[stackPos].Y].numberOfEdges) {
				//increase stack pointer
				stackPos++;
				if (floorcells[stackArray[stackPos-1].X][stackArray[stackPos-1].Y].nodeChecked == false) {
				//set the XY in the stack of the next target nodes
				stackArray[stackPos].X = floorcells[stackArray[stackPos-1].X][stackArray[stackPos-1].Y].edges[floorcells[stackArray[stackPos-1].X][stackArray[stackPos-1].Y].egdesVisted].endNode.X;
				stackArray[stackPos].Y = floorcells[stackArray[stackPos-1].X][stackArray[stackPos-1].Y].edges[floorcells[stackArray[stackPos-1].X][stackArray[stackPos-1].Y].egdesVisted].endNode.Y;
				stackArray[stackPos].direction = floorcells[stackArray[stackPos-1].X][stackArray[stackPos-1].Y].edges[floorcells[stackArray[stackPos-1].X][stackArray[stackPos-1].Y].egdesVisted].direction;
				//increment edgeds visited variable on node come from
				floorcells[stackArray[stackPos-1].X][stackArray[stackPos-1].Y].egdesVisted++;
				if (floorcells[stackArray[stackPos-1].X][stackArray[stackPos-1].Y].egdesVisted == floorcells[stackArray[stackPos-1].X][stackArray[stackPos-1].Y].numberOfEdges) {
					floorcells[stackArray[stackPos-1].X][stackArray[stackPos-1].Y].nodeChecked = true;
					dbColorObject(floorcells[stackArray[stackPos-1].X][stackArray[stackPos-1].Y].floorCube,dbRGB(255,0,0));
				}
				//increase stack pointer
				} else {
					floorcells[stackArray[stackPos-1].X][stackArray[stackPos-1].Y].egdesVisted++;
				}
				//if all edges have been visited go back down the stack to the previous node
			} else {
				//if all edges have been viisted set the node to checked
				floorcells[stackArray[stackPos].X][stackArray[stackPos].Y].nodeChecked = true;
				//colour the cube red
				dbColorObject(floorcells[stackArray[stackPos].X][stackArray[stackPos].Y].floorCube,dbRGB(255,0,0));
				//decrement stack pointer
				stackPos--;			
			}
		}
}


[Edited by - Zahlman on December 2, 2009 10:30:41 PM]

Share this post


Link to post
Share on other sites
Advertisement
Hi. My eyeballs are bleeding after trying to read that code.

I recommend you edit the post using [ source] and [ /source] tags for areas that are code. It will format them nicely, and may help to encourage more responses (check the FAQ link in the top right corner for more info on formatting).

Share this post


Link to post
Share on other sites
Quote:
Original post by supamike
Hi. My eyeballs are bleeding after trying to read that code.

I recommend you edit the post using [ source] and [ /source] tags for areas that are code. It will format them nicely, and may help to encourage more responses (check the FAQ link in the top right corner for more info on formatting).


I'm a step ahead of you. ;)

Anyway, the first thing I'd do is organize the code a little. A few tips here:

1) Don't compare to 'true' or to 'false'. Instead, just use the condition (or the opposite) directly.

2) Make some aliases to avoid repeating common patterns of access. For example, 'stackArray[stackPos]' appears all over the place, so assign the result to a variable and use that instead. Notice how pointers are used to avoid copying objects. Normally, I would use references for this, but here we need to re-seat them.


while (foundRoute == false) {
//once all edges from the start node have been checked the route should have been found

// I'll use a reference for this one, because it doesn't need to be
// re-seated, and so you can see the technique.
Cell& startCell = floorcells[startX][startY];

if (startCell.egdesVisted == startCell.numberOfEdges) {
foundRoute = true;
}

Position* topLocation = &stackArray[stackPos];
Cell* topCell = &floorcells[topLocation->X][topLocation->Y];
Position* lastNode = &(topCell->edges[topCell->edgesVisited].endNode);
Cell* lastCell = &floorcells[lastNode->X][lastNode->Y];

//check if the next edge is the end node
if (lastCell->exitFinal) {
//foundRoute = true; - each time the final cell is found the route will be transferred to check against alternatives for the fastest route
topLocation->X = lastNode->X;
topLocation->Y = lastNode->Y;
stackPos++;
// Because the stackPos changed, we need to fix all the other
// values accordingly.
topLocation = &stackArray[stackPos];
topCell = &floorcells[topLocation->X][topLocation->Y];
lastNode = &(topCell->edges[topCell->edgesVisited].endNode);
lastCell = &floorcells[lastNode->X][lastNode->Y];
}

//if the route has not be found
if (!foundRoute) {
//check if there are any more edges to visit from the node
if (topCell->egdesVisted < topCell->numberOfEdges) {
// This code becomes a lot simpler if we increment
// stackPos *after* doing the other work, and adjust
// the array indices accordingly. We make an alias for
// the next value in the stack after the top.
if (!topCell->nodeChecked) {
Position* nextLocation = &stackArray[stackPos + 1];
// set the XY in the stack of the next target nodes
nextLocation->X = lastNode->X;
nextLocation->Y = lastNode->Y;
nextLocation->direction = lastNode->direction;
//increment edgeds visited variable on node come from
topCell->egdesVisted++;
if (topCell->egdesVisted == topCell->numberOfEdges) {
topCell->nodeChecked = true;
dbColorObject(topCell->floorCube, dbRGB(255, 0, 0));
}
//increase stack pointer
} else {
topCell->egdesVisted++;
}

stackPos++;
//if all edges have been visited go back down the stack to the previous node
} else {
//if all edges have been viisted set the node to checked
topCell->nodeChecked = true;
//colour the cube red
dbColorObject(topCell->floorCube, dbRGB(255,0,0));
//decrement stack pointer
stackPos--;
}
}
}



Does this help you find the problem?

[Edited by - Zahlman on December 2, 2009 10:00:23 PM]

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!