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--;
}
}
}
Search algorithm
Author
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 -
[Edited by - InnocuousFox on December 3, 2009 7:25:42 AM]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
