Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- [openList add:originalSquare]; // start by adding the original position to the open list
- do {
- currentSquare = [openList squareWithLowestFScore]; // Get the square with the lowest F score
- [closedList add:currentSquare]; // add the current square to the closed list
- [openList remove:currentSquare]; // remove it to the open list
- if ([closedList contains:destinationSquare]) { // if we added the destination to the closed list, we've found a path
- // PATH FOUND
- break; // break the loop
- }
- adjacentSquares = [currentSquare walkableAdjacentSquares]; // Retrieve all its walkable adjacent squares
- foreach (aSquare in adjacentSquares) {
- if ([closedList contains:aSquare]) { // if this adjacent square is already in the closed list ignore it
- continue; // Go to the next adjacent square
- }
- if (![openList contains:aSquare]) { // if its not in the open list
- // compute its score, set the parent
- [openList add:aSquare]; // and add it to the open list
- } else { // if its already in the open list
- // 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
- }
- }
- AStarPath AStarSearch::calculatePath()
- {
- if (!wasInit)
- {
- throw "AStarSearch::calculatePath(): A* Search was not initialized!n";
- }
- /*Create open and closed lists*/
- std::vector<AStarNode*> openList;
- std::vector<AStarNode*> closedList;
- /*Add the start node to the open list*/
- openList.push_back(startNode);
- do
- {
- /*Get square with lowest F score in the open list*/
- AStarNode* currentNode = openList[0];
- for (int index = 0; index < openList.size(); ++index)
- {
- if (openList[index]->getF() < currentNode->getF())
- currentNode = openList[index];
- }
- /*Remove the current nodes from the open list, add it to the closed list*/
- for (std::vector<AStarNode*>::iterator it = openList.begin(); it != openList.end(); ++it)
- {
- if (*it == currentNode)
- openList.erase(it);
- }
- closedList.push_back(currentNode);
- /*Check if the destination is in the closed list*/
- if (std::find(closedList.begin(), closedList.end(), endNode) != closedList.end());
- {
- /*Found a path, break the loop*/
- break;
- }
- /*Find walkable and adjacent nodes*/
- std::vector<AStarNode*> walkableAdjacent = getWalkableAdjacentNodes(currentNode->getX(), currentNode->getY());
- for (std::vector<AStarNode*>::iterator it = walkableAdjacent.begin(); it != walkableAdjacent.end(); ++it)
- {
- /*Skip the node if it is in the closed list*/
- if (std::find(closedList.begin(), closedList.end(), *it) != closedList.end())
- {
- /*Skip to next node*/
- continue;
- }
- /*If the node is not in the open list, set it's parent and add it to the open list*/
- if (std::find(openList.begin(), openList.end(), *it) != closedList.end())
- {
- /*Set the parent to the current node*/
- (*it)->setParent(currentNode);
- /*Add the node to the open list*/
- openList.push_back(*it);
- }
- /*If the node is in the open list*/
- else
- {
- //This is the part I'm having trouble with
- }
- }
- } while (!openList.empty());
- }
Add Comment
Please, Sign In to add comment