Guest User

Untitled

a guest
Nov 25th, 2017
79
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.45 KB | None | 0 0
  1. [openList add:originalSquare]; // start by adding the original position to the open list
  2. do {
  3. currentSquare = [openList squareWithLowestFScore]; // Get the square with the lowest F score
  4.  
  5. [closedList add:currentSquare]; // add the current square to the closed list
  6. [openList remove:currentSquare]; // remove it to the open list
  7.  
  8. if ([closedList contains:destinationSquare]) { // if we added the destination to the closed list, we've found a path
  9. // PATH FOUND
  10. break; // break the loop
  11. }
  12.  
  13. adjacentSquares = [currentSquare walkableAdjacentSquares]; // Retrieve all its walkable adjacent squares
  14.  
  15. foreach (aSquare in adjacentSquares) {
  16.  
  17. if ([closedList contains:aSquare]) { // if this adjacent square is already in the closed list ignore it
  18. continue; // Go to the next adjacent square
  19. }
  20.  
  21. if (![openList contains:aSquare]) { // if its not in the open list
  22.  
  23. // compute its score, set the parent
  24. [openList add:aSquare]; // and add it to the open list
  25.  
  26. } else { // if its already in the open list
  27.  
  28. // test if using the current G score make the aSquare F score lower, if yes update the parent because it means its a better path
  29.  
  30. }
  31. }
  32.  
  33. AStarPath AStarSearch::calculatePath()
  34. {
  35. if (!wasInit)
  36. {
  37. throw "AStarSearch::calculatePath(): A* Search was not initialized!n";
  38. }
  39. /*Create open and closed lists*/
  40. std::vector<AStarNode*> openList;
  41. std::vector<AStarNode*> closedList;
  42.  
  43. /*Add the start node to the open list*/
  44. openList.push_back(startNode);
  45.  
  46. do
  47. {
  48. /*Get square with lowest F score in the open list*/
  49. AStarNode* currentNode = openList[0];
  50. for (int index = 0; index < openList.size(); ++index)
  51. {
  52. if (openList[index]->getF() < currentNode->getF())
  53. currentNode = openList[index];
  54. }
  55.  
  56. /*Remove the current nodes from the open list, add it to the closed list*/
  57. for (std::vector<AStarNode*>::iterator it = openList.begin(); it != openList.end(); ++it)
  58. {
  59. if (*it == currentNode)
  60. openList.erase(it);
  61. }
  62. closedList.push_back(currentNode);
  63.  
  64. /*Check if the destination is in the closed list*/
  65. if (std::find(closedList.begin(), closedList.end(), endNode) != closedList.end());
  66. {
  67. /*Found a path, break the loop*/
  68. break;
  69. }
  70.  
  71. /*Find walkable and adjacent nodes*/
  72. std::vector<AStarNode*> walkableAdjacent = getWalkableAdjacentNodes(currentNode->getX(), currentNode->getY());
  73. for (std::vector<AStarNode*>::iterator it = walkableAdjacent.begin(); it != walkableAdjacent.end(); ++it)
  74. {
  75. /*Skip the node if it is in the closed list*/
  76. if (std::find(closedList.begin(), closedList.end(), *it) != closedList.end())
  77. {
  78. /*Skip to next node*/
  79. continue;
  80. }
  81. /*If the node is not in the open list, set it's parent and add it to the open list*/
  82. if (std::find(openList.begin(), openList.end(), *it) != closedList.end())
  83. {
  84. /*Set the parent to the current node*/
  85. (*it)->setParent(currentNode);
  86. /*Add the node to the open list*/
  87. openList.push_back(*it);
  88. }
  89. /*If the node is in the open list*/
  90. else
  91. {
  92. //This is the part I'm having trouble with
  93. }
  94. }
  95.  
  96. } while (!openList.empty());
  97. }
Add Comment
Please, Sign In to add comment