-2
2 차원 배열에서 A * 길 찾기 알고리즘의 마지막 부분을 구현하는 데 문제가 있습니다. https://www.raywenderlich.com/4946/introduction-to-a-pathfinding 마지막에있는 모든 길에 algorithm에 대한 의사 코드가 있습니다. 나는이 코드를 거의 끝까지 따라갈 수 있었다. 내 코드와 의사 코드의 차이점은 모든 노드에 대해 모든 G, H 및 F 값을 미리 계산한다는 것입니다. 이것이 마지막 단계를 구현하는 데 어려움을 겪는 이유입니다.A * 길 찾기 알고리즘 구현
[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
}
}
} while(![openList isEmpty]); // Continue until there is no more available square in the open list (which means there is no path)
튜토리얼은이 목표 - C로 작성 상태,하지만 내 구현은 C에 ++ 다음은 의사입니다. 이미 많이 도움이 될 다른 문 내에해야하는지에 대한
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 node from the open list, add it to the closed list*/
std::remove(openList.begin(), openList.end(), currentNode);
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());
}
의사 코드 : 여기 내 calculatePath 기능입니다.
편집 :
/*Check if the node has a better G value than the current node*/
if ((*it)->getG() < currentNode->getG())
{
/*Do I have to set a parent here?*/
}
편집 2 : 나는 다른 문 내에서이 쓸 때 내가 수정나요 내 질문 downvotes을 받고있다 참조하십시오. 누군가 내가 잘못하고있는 것을 말해 줄 수 있나요? 그래서 자신을 교정하고 필요할 경우 더 많은 정보를 제공하거나 다음 질문에서 배우십시오.
큰 문제는'openList.erase (it);'가'it'을 무효화하는 것입니다. 그 루프를'std :: remove (openList.begin(), openList.end(), currentNode);로 바꾼다. – molbdnilo
나는 그것을 바꿀 것이다. 그러나 내가 Visual Studio에서 이것을 입력하면, : < stuff> to const char * – MivVG
std :: remove에 대한 참조를 찾았습니다. 문자열이 아닌 벡터 용으로 사용 된 것 같습니다. – MivVG