gpg 1권 376페이지의 소스입니다.
책을 보면서 짜맞춰서 소스를 짜고 있었는데 궁금한 부분이 나와서 해메고 있습니다;
그중에서 findpath 함수를 맞추고 있었는데요...
이하 소스
------------------------------------------------------------------------------------
while(!IsPriorityQueueEmpty(path->open))
{
// 다음으로 검색할 가장 유망한 노드를 얻는다.
// 골을 찾았으면 경로를 만들고 함수를 종료
// 완성된 경로는 저장
Node* bestnode = PopPriorityQueue(path->open);
if(AtGoal(bestnode, GoalPosition))
{
ConstructPathToGoal(StartPosition, *path);
return(true);
}
/////////////////////////////////////////////////////////////////////////////////////////////
// 이쪽 // error 부분 두가지
/////////////////////////////////////////////////////////////////////////////////////////////
// error
while(1 /*가장 유망한 노드의 인접 노드들을 차례로 탐색한다.*/)
{
Node newnode;
// error
// 새 노드의 위치를 설정한다.
newnode.location.PositionX = 0;
newnode.location.PositionY = 0;
if(bestnode->parent == NULL
|| ((bestnode->parent->location.PositionX != newnode.location.PositionX)
&& (bestnode->parent->location.PositionY != newnode.location.PositionY)))
{
newnode.parent = bestnode;
newnode.cost = bestnode->cost + CostFromNodeToNode(&newnode, bestnode);
newnode.total = newnode.cost;
Node* actualnode = GetNode(g_nodelist, newnode.location);
if(!(actualnode->onOpen && newnode.total > actualnode->total) &&
!(actualnode->onClosed && newnode.total > actualnode->total))
{
// 유망한 노드로 간주할 수 있음, 닫힌 목록에서 뽑아내 열린 목록으로 이동
actualnode->onClosed = false;
actualnode->parent = newnode.parent;
actualnode->cost = newnode.cost;
actualnode->total = newnode.total;
if(actualnode->onOpen)
{
UpdateNodeOnPriorityQueue(path->open, actualnode);
}
else
{
PushPriorityQueue(path->open, actualnode);
actualnode->onOpen = true;
}
}}}
bestnode->onClosed = true;
// 찾지 못한경우 시간이걸리던, 너무 오래걸리던. 설정대로
if(ShouldAbortSearch())
{
return(false);
}
///////////////////////////////////////////////////////////////////////////////////////////////
while 부분에서 bestnode의 인접 노드를 탐색한다고 되어있는데,
bestnode의 9방향을 검사하는 것 같은데 맞나요?
그리고 새 노드에 넣어주는 것 같은데...
while이 얼마만큼 돌아야 하는지 새 노드의 위치 설정이라던지 궁금합니다
뭔가 잡힐듯 안잡히네요. 힌트라도 주시면 감사하겠습니다 (__)
[GPG 1 글 3.5] gpg 1권 A* 소스를 보면서 짜맞추고 있었는데요...
Moderator: 류광
-
- Posts: 43
- Joined: 2007-11-05 10:48
Re: gpg 1권 A* 소스를 보면서 짜맞추고 있었는데요...
1. while 부분의 인접한 노드의 개수는?비회원 wrote: while 부분에서 bestnode의 인접 노드를 탐색한다고 되어있는데,
bestnode의 9방향을 검사하는 것 같은데 맞나요?
그리고 새 노드에 넣어주는 것 같은데...
while이 얼마만큼 돌아야 하는지 새 노드의 위치 설정이라던지 궁금합니다
뭔가 잡힐듯 안잡히네요. 힌트라도 주시면 감사하겠습니다 (__)
->인접한 노드의 수에 따라 다르겠죠 2차원 4방향 평면이면 4개이겠고 8방향이면 8개이겠고 그렇겠지요 3차원일 경운 더 많겠구요
2. while부분이 얼만큼 돌아야 하는가?
--> 인접한 노드의 수만큼 돌아야 겠지요
3. while 부분의 새 노드의 위치 설정은?
--> x, y(또는 z포함)에 각각 더하기 1씩, 하던가 빼던가 식으로 경우수를 만들어 내면 됩니다. 4방일경우엔 (x,y)일경우 (x-1, y), (x+1, y), (x, y-1), (x, y+1) 이렇게 4개가 되겠지요
조언 감사드립니다.
현재 2D로 제작중이였습니다. 8방향이 되겠군요.
while도 for문으로 그냥 변경했습니다.
구현은 다했는데, 이것 저것 문제가 많습니다.
도움 말씀 정말 감사드립니다.
while도 for문으로 그냥 변경했습니다.
구현은 다했는데, 이것 저것 문제가 많습니다.
도움 말씀 정말 감사드립니다.