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 - Zahlman on December 2, 2009 10:30:41 PM]
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 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).
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]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
