잡동사니

//노드에 대한 정의

typedef struct node_s {
int degree; //현재 이 노드의 깊이 값. 즉, 자료 구조 트리에서 깊이 값.

int distance; //이 노드로부터 목적지까지의 거리

int value_factor; //평가치 값( degree + distance )

int x, y; //이 노드의 위치 (그리드의 위치)
struct node_s* direct[8]; //확장 가능한 8방향에 대한 노드
struct noder_s* prev_node; //링크드 리스트 이전 노드
struct node_s* next_node; //링크드 리스트 다음 노드
} node_t;

//노드를 재정렬할 때 쓸 스택.

typedef struct node_stack_s {
node_t* node; //이 스택 위치에서 가리키고 있는 노드
struct node_stack_s* next_node; //이 스택의 다음 위치
} node_stack_t;

node_t *OPEN = NULL, *CLOSED = NULL;

node_stack_t* STACK = NULL;

//리스트와 스택을 초기화 또는 제거 해주는 함수

void init_astar()

{

//OPEN노드를 순회하면서 각 노드를 제거

//CLOSE노드를 순회하면서 각 노드를 제거

//스택을 순회하면서 각 스택에 존재하는 데이터 제거, 스택 공간 제거

}

bool is_available_grid( int x, int y )

{

//캐릭터가 어떤 그리드로 이동하기 전에 그 그리드가 이동가능한지 여부를 판단하는 부분을 구현합니다.

//상황에 따라 다르므로 역시 의사코드.

//이동 가능한 그리드면 TRUE

//블럭된 것과 같이 이동 불가능한 그리드면 FALSE

}

//해당 위치의 노드가 OPEN NODE에 존재하는 지 파악하는 함수

node_t* is_open( int x, int y )

{

//OpenNode를 순회하면서 입력한 위치 값의 노드가 존재하는 지 파악.

//존재하면 해당 노드를 반환

}

//해당 위치의 노드가 CLOSED NODE에 존재하는 지 파악하는 함수

node_t* is_closed( int x, int y )

{

//ClosedNode를 순회하면서 입력한 위치 값의 노드가 존재하는지 파악.

//존재하면 해당 노드를 반환

}

//해당 노드를 스택 공간에 삽입하는 함수

void push_into_stack( node_t* node )

{

//스택 공간 할당

//생성한 스택 공간에 삽입할 노드를 지정

//기존 스택에 생성한 스택 공간을 연결

}

//해당 노드를 스택 공간에 삽입하는 함수

node_t* pop_from_stack()

{

//스택 공간에서 노드 데이터 꺼내옴

//해당 스택 공간 삭제

//노드 반환

}

//출발점 x,y, 목적지 x,y

node_t* find_path( int start_x, int start_y, int dest_x, int dest_y ) {

node_t* present=NULL; //출발점 노드

//시작 위치 노드 추가. 여기서는 시작 위치가 목적지가 되겠습니다. 즉, 목적지에서 -> 출발지 방향으로 탐색.

//위의 그림설명에서 완성된 노드가 역으로 연결된 점을 확인하셨다면, 목적지->출발지로 하면 되겠죠.
present = ( node_t* ) calloc( 1, sizeof(node_t) );
present->degree = 0;
present->distance= pow( (dest_x- start_x ), 2 ) + pow( (dest_y - start_y ), 2 ); //진정한 의미에서는 루트를 씌워야

//겠지만 구지 안씌워도 문제될 건 없죠.
present->value_factor = present->distance; // distance + degree
present->x= dest_x;
present->y= dest_y;

OPEN=present;

node_t* best=NULL; //best는 현재까지 최적의 경로에 대한 리스트입니다.
int count=0; //탐색 깊이 값을 카운팅 합니다. 무한 루프에 빠질 가능성을 제한할 용도이죠.

//탐색 시작합니다. 길 찾기를 실패할 경우에 대비해서 루프문에 제한을 둘 필요가 있습니다.

while(count< FINDPATH_LIMIT) {

//모든 노드에 대한 찾기를 수행했을 경우. 그럴 경우 아마 최적의 길을 찾았겠죠? 아마..

if(OPEN==NULL) {
return best;

}

best = OPEN; //매 루프문을 돌면서 OpenNode의 후보로부터 탐색을 우선 시도합니다.
OPEN = best->next_node; //그리고 그 다음 노드가 OpenNode의 최상위 후보노드로 지정되며
best->next_node = CLOSED; //지금까지 구축된 최적의 노드를 이번에 탐색할 best노드와 연결함으로써

//현재까지 탐색된 최적의 길을 유지하게 됩니다.
CLOSED=best; //이 best노드는 이번 루프에서 탐색 시도되므로 close노드로 들어가게 되는거죠.

//길찾기 실패

if(best==NULL) {
return NULL;

}

//길찾기 성공
if(best->x == start_x && best->y == start_y )
return best;

//현재 탐색 노드를 중심으로 8방향으로 확장.
if(make_child(best, start_x, start_y )==0 && count ==0)
return NULL;

count++;

}

return best;

}

//현재 탐색할 노드, 목적지 x, y, 반환값은 현 노드의 확장 여부

bool make_child( node_t* node, int dest_x, int dest_y ) {

bool extended = false; //하나라도 확장된 사실이 있으면 true
int x = node->x;
int y = node->y;

//각 8방향에 대해 이동 가능한 지역에 대해서 자식 노드 생성

//왼편.
if( is_available_grid( x - 1, y ) ) {
extend_child_node( node, x-1, y, dest_x, dest_y, LEFT_IDX );
extended=1;
}

//그 외 7방향에 대해서는 해당 x, y값을 주어서 똑같이 호출하면 되겠습니다.

//여기서는 생략.

//오른편 x + 1, y

//상단 x, y - 1

//하단 x, y + 1

//좌측 상단 x - 1, y - 1

//우측 상단 x + 1, y - 1

//좌측 하단 x - 1, y + 1

//우측 하단 x + 1, y + 1

return extened;

}

//확장할 노드, 현재 노드 위치, 목적지 위치, 확장할 방향 인덱스

void extend_child_node( node_t* node, int cur_x, int cur_y, int dest_x, int dest_y, int cur_direct ) {

node_t *old = NULL, *child = NULL;
int i;
int degree= node->degree+1;

//확장할 노드가 OpenNode에 존재한다면,
if( old = Is_open( cur_x, cur_y ) ) {

node->direct[ cur_direct ] = old;

//그리고 노드 재연결 및 설정 . 참고로 노드 방향이 반대로 적용된다는 걸 고려할 것.
if( degree < old->degree ) {
old->prev_node = node;
old->degree = degree;
old->value_factor = old->distance + old->degree;
}

//확장할 노드가 CloseNode에 존재한다면,

}else if( old = is_close( cur_x, cur_y ) ) {

node->direct[ cur_direct ] = old;

//어떤 경우에는 기존 CloseNode에 있는 노드의 degree가 더 적을 경우가 발생할 수도 있는데

//이 때 순서를 다시 설정
if(degree<old->degree) {
old->prev_node = node;
old->degree = degree;
old->value_factor = old->distance + old->degree;
make_sort( old );
}

//확장할 노드 생성 및 OpenNode 리스트에 추가

}else {

if( ( child = ( node_t* ) calloc( 1, sizeof( node_t ) ) ) == NULL )
return; //lack of memory

child->prev_node = node;
child->degree = degree;
child->distance = ( cur_x - dest_x ) * ( cur_x - dest_x ) + ( cur_y - dest_y ) * ( cur_y - dest_y );
child->value_factor = child->distance + child->degree;
child->x = cur_x;
child->y = cur_y;

Insert_node_( child );

node->direct[ cur_direct ] = child;

}

}

//재평가힐 노드의 기준

void make_sort( node_t* old ) {

node_t *direct, *previous;
int i;
int degree = old->degree+1;

for(i=0; i<8; i++) {

if( ( direct = old->direct[i] ) == NULL )
continue;

//순서 재정렬로 인한 연결된 노드들의 설정값이 얽힌경우 재설정을 해줍니다.

//자식 노들들을 위해 스택 공간을 이용합니다.

if( direct->degree > degree ) {
direct->prev_node = old;
direct->degree = degree;
direct->value_factor = direct->distance + direct->degree;

push_into_stack( direct );
}

}

//스택 공간을 이용하여 차례차레 노드들을 재 설정.

while( STACK ) {

previous = pop_from_stack();

for( i=0; i<8; i++ ) {

if( ( direct = previous->direct[i]) == NULL )
break;

if( direct->degree > previous->degree + 1 ) {
direct->prev_node = previous;
direct->degree = previous->degree + 1;
direct->value_factor = direct->distance + direct->degree;

push_into_stack( direct );
}
}
}
}

//확장한 새 노드

void Insert_node( node_t* present ) {

node_t* old = NULL, *temp = NULL;

if(OPEN == NULL) {
OPEN = present;
return;
}

temp=OPEN;

//OpenNode에 있는 노드가 현재 자식 노드보다 평가치가 낮으면
//OpenNode를 추적해서 현재 자식 노드보다 평가치가 높은 노드를 찾는다.
while(temp && (temp->value_factor < present->value_factor ) ) {
old=temp;
temp=temp->next_node;
}

//낮은 평가치의 OpenNode 중 출발지에 가장 가까운 노드 -> 추가할 자식 노드 -> 높은 평가치의 OpenNode 중 출발지에 가

//장 먼 노드
if(old) {
present->next_node = temp;
old->next_node = present;
}else {
present->next_node = temp;
OPEN = present;
}

}