|
[x]
Posted via EE Mobile
|
||
Search, ask, and monitor your questions on the go with EE Mobile. Visit Experts Exchange from your mobile device and never be out of touch again. |
||
| Question |
|
[x]
Attachment Details
|
||
|
[x]
The Solution Rating System
|
||
With so many solutions, how can you tell which solutions are most likely to help you and which ones are not? To provide you with a tool to use, we rate our solutions based on various elements that most accurately determine if a solution is a quality solution. To explain what factors affect the solution rating, here are the elements we take into consideration when formulating our solution rating.
Your Input Matters If you have any suggestions that you would like to make for our rating system, please ask a question in the Suggestions Zone of Community Support. Thank you! |
||
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61: 62: 63: 64: 65: 66: 67: 68: 69: 70: 71: 72: 73: 74: 75: 76: 77: 78: 79: 80: |
list<int> Level::planPathBFS(short currentX, short currentY, short goalX, short goalY, short debugMode)
{
/*
Each node in the graph has an index.
For and given x and y position this can be found b calling index(x,y) e.g.
goalIndex = index(goalX, goalY);
This function returns a path, a linked list of nodes, give a route through the map e.g.
<555, 554, 553, 552, 551>
This path is contructed using a breadth first approach.
The initial node is added to possible path list.
This possible papth list is added to a second list, the list of possible paths.
So after initialisation this list of possible paths only has one element,
a list containing the current nodes index:
<<555>>
This list is then expanded as follows:
For each element in the list:
Take the tail of the list as the current node
Check for connections from this node to other nodes (using the adjacency matrix)
If there is a connection
Add a new path to the list consisting of the current path + the (other) new node
Check if this new is the goal node, if so return the current path
End
Should look something like this:
Start node is 555
Goal node is 552
<<555>>
<<555,554>,<555,556>>
<<555,554,553>,<555,554,555>,<555,556,555>,<555,556,557>>
<<555,554,553,552>,... goal found to return path: <555,554,553,552>
*/
list<int> path; // Final path to be constructed
list<list<int>> pathTree; // BFS tree
list<list<int>> pathTreeTmp; // BFS tree - used in working
list<int> ppath;// Partial path used in BSF tree construction
list<list<int>>::iterator ptIter; // Iterator used for looping through the list of partial paths
int goalIndex; // Index of the goal node
int currentIndex; // Index of the current node
int otherIndex; // Index of a second node
bool goalFound = false; // Has the goal been found?
goalIndex = index(goalX, goalY); // Set the goal index
currentIndex = index(currentX, currentY); // Set the index of the current node
ppath.push_front(currentIndex); // Add the current index to a partial path
pathTree.push_front(ppath); // Add that partial path to the list of partial paths
while (!goalFound) // Until we find the goal node
{
// Loop through the partial paths
for(ptIter=pathTree.begin();ptIter != pathTree.end(); ++ptIter)
{
ppath = *ptIter; // Take the next partial path
currentIndex = ppath.back(); // Find the index of the current node, the last node in the curretn partial path
// Look in the adjacency matrix for connections to other nodes
for(otherIndex = 0; otherIndex < nNodes; otherIndex++)
{
// Check for a connection
if(adjacencyMatrix[currentIndex][otherIndex])
{
// If so make a new partial path which is equal to the current path
list<int> ppathTmp = ppath;
// Add the index of the new node to the end of the path
ppathTmp.push_back(otherIndex);
// Add this new partial path to the list of partial paths
pathTreeTmp.push_back(ppathTmp);
// If the new node is the goal node
if(otherIndex == goalIndex)
{
goalFound = true; // Set goal found to true
cout << pathTreetmp ;
path = ppathTmp; // Set the path which will be return to the current partial path
}
}
}
}
pathTree = pathTreeTmp; // Set the list of paths to the new list
pathTreeTmp.erase(pathTreeTmp.begin(),pathTreeTmp.end()); // Delete everything in the new list so it's ready to be filled again
}
return path; // Return the path - starts with th current node ends in the goal node
}
|
Advertisement
| Hall of Fame |