Jump to content
  • Advertisement
Sign in to follow this  
pawikan

Search algorithm

This topic is 3182 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 - InnocuousFox on December 3, 2009 7:25:42 AM]

Share this post


Link to post
Share on other sites
Advertisement
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!