[GPG 1 글 3.5] gpg 1권 A* 소스를 보면서 짜맞추고 있었는데요...

GPG 시리즈 관련 질답, 논의 공간.

Moderator: 류광

비회원

gpg 1권 A* 소스를 보면서 짜맞추고 있었는데요...

Post by 비회원 »

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이 얼마만큼 돌아야 하는지 새 노드의 위치 설정이라던지 궁금합니다
뭔가 잡힐듯 안잡히네요. 힌트라도 주시면 감사하겠습니다 (__)
stpapa
Posts: 43
Joined: 2007-11-05 10:48

Re: gpg 1권 A* 소스를 보면서 짜맞추고 있었는데요...

Post by stpapa »

비회원 wrote: while 부분에서 bestnode의 인접 노드를 탐색한다고 되어있는데,
bestnode의 9방향을 검사하는 것 같은데 맞나요?
그리고 새 노드에 넣어주는 것 같은데...
while이 얼마만큼 돌아야 하는지 새 노드의 위치 설정이라던지 궁금합니다
뭔가 잡힐듯 안잡히네요. 힌트라도 주시면 감사하겠습니다 (__)
1. 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개가 되겠지요
비회원

조언 감사드립니다.

Post by 비회원 »

현재 2D로 제작중이였습니다. 8방향이 되겠군요.

while도 for문으로 그냥 변경했습니다.

구현은 다했는데, 이것 저것 문제가 많습니다.

도움 말씀 정말 감사드립니다.
Post Reply