Code Complete - Steve McConnell

글쓴이: feanor 작성 일시: 일, 2009/05/10 - 8:31오후

Programming Pearls by Jon Bentley (생각하는 프로그래밍)
The Mythical Man-Month by Frederick Brook (맨먼스 미신)

»

Game programming gems......

글쓴이: kkb110 작성 일시: 월, 2009/05/11 - 7:46오전

Game programming gems...... 전 이 씨리즈가 재밌고 볼만하던데요.

게임 프로그래밍에서 실제 필요한 유용한 테크닉들을 프로그래밍/수학/알고리즘/인공지능/ 등 5개 색션으로 나누어
글 묶음 형식으로 만들어 둔 책입니다.

꼭 게임 프로그래밍을 하지 않더라도 충분히 재밌고 유용하다고 생각합니다.

code complete
effective c++
more effective c++
effective STL

등도 읽어봤는데

저책들도 좋지만 다시읽어보고 싶은 책을 고르라면 주저없이 GPG를 찍겠습니다.

gpgstudy.com이란 이책을 주제로 모인 사이트도 있고

http://www.gpgstudy.com/gpgiki/GpgPreview?style=simple 여기에서 몇몇글들을 미리 맛볼 수 있습니다.

Quote:

GPG 3 미리보기

* 1부 프로그래밍 일반 - 1.2 객체 조합식 게임 프레임웍 (Scott Patterson, Next Generation Entertainment )
* 2부 수학 - 2.4 사원수의 압축 (Mark Zarb-Adami, Muckyfoot Productions)
* 3부 인공지능 - 3.5 AI 에이전트, 객체, 퀘스트를 위한 확장성있는 트리거 시스템 (Steve Rabin, Nintendo of America, Inc.)
* 4부 그래픽 프로그래밍 - 4.13 법선 맵을 이용한 곡면 흉내내기 (Oscar Blasco, Aside Software )
* 5부 네트웍 및 멀티플레이어 - 5.6 보안 소켓 (Pete Isensee, Microsoft Corporation)
* 6부 오디오 - 6.1 Ogg Vorbis를 이용한 오디오 압축 (Jack Moffitt, Xiph.org Foundation)

GPG 2 미리보기

* 1부 프로그래밍 일반 - 1.12 윈도우즈 기반 게임을 위한 선형적 프로그래밍 모델 (Javier F. Otaegui, Sabarasa Entertainment)
* 2부 수학 - 2.1 부동소수점 비법들: IEEE 부동소수점을 통한 성능 향상 (Yossarian King, Electronic Arts Canada )
* 3부 인공지능 - 3.1 AI 최적화 전략들 (Steve Rabin, Nintendo of America)
* 4부 기하 관리 - 4.2 맞물린 타일들을 이용한 단순화된 지형 시스템 (Greg Snook)
* 5부 그래픽 디스플레이 - 5.1 카툰 렌더링: 실시간 외곽선 변 검출 및 렌더링 (Carl S. Marshall, Intel Architecture Labs)
* 6부 오디오 프로그래밍 - 6.1 게임 오디오 설계 패턴 (Scott Patterson)

1로 갈수록 원론적이고 그 뒤 씨리즈일수록 자잘한 이야기가 나오는데

1->2->3->.. 등등등 순서로 보는 것을 추천합니다..

»

어떤 분야를 다루는 프로그래머냐에 따라

글쓴이: ldgood 작성 일시: 월, 2009/05/11 - 5:23오후

추천도서의 의미는 다르겠네요.
웹 프로그래머가 크누쓰 책이나 마법사 책을 꼭 읽어야한다고 생각하지는 않습니다만...

분야에 관계없이 추천하고 싶은 책은
pragmatic programmer시리즈 전체와 위에서 말씀하신 고전(맨먼스미신, 소프트웨어 개발의 지혜, 프로그래밍 심리학, Rapid Software Development, 죽음의 행진 등등)이 완전 강추죠.

최근 오픈소스 관련해서 재미있었던 책은 드리밍인 코드 였습니다

------------------------------
모든것은 모든것에 잇닿아 있다.

—

------------------------------
모든것은 모든것에 잇닿아 있다.

Code Complete

게임프로그래머를 위한 자료구조와 알고리즘

Introduction to Algorithms 일단 적어놓자

알고리즘책 입문서로 많이 추천

출처 :  http://blog.naver.com/PostView.nhn?blogId=keloc&logNo=40154090761

지난 시간에는 스택과 큐의 개념과 배열로 각각 구현을 해봤습니다. 이번에 살펴 볼 연결리스트(Linked List)는 정적인 배열과 달리 동적인 자료구조로 필요한 경우 할당하여 사용하고 필요가 없어지면 해제하는 식으로 메모리 관리가 가능하기 때문에 메모리를 절약할 수 있다는 장점이 있습니다.

[연결리스트의 기본구조 : 단순 연결리스트]

연결리스트(링크드리스트 : Linked List)의 개념

  연결리스트는 노드(Node)와 링크(Link)로 구성되며, 노드는 실제 정보를 담고 있는 하나의 단위이고, 링크는 노드간의 위치정보를 저장하고 있어 연결리스트의 순서를 유지할 수 있도록 하는 연결고리로 이해 하시면 됩니다.

  연결리스트는 각 노드별 링크의 개수와 연결 상태에 따라 다양한 형태로 구성 될 수 있는데요. 단순 연결리스트, 환형 연결리스트, 이중 연결리스트, 이중 환형 연결리스트 등으로 나눌 수 있습니다.

단순 연결리스트 (Simple Linked List)

  단순 연결리스트는 위 그림과 같이 선형적으로 한방향인 리스트의 형태로서 가장 많이 쓰이는 형태입니다. 여기서 리스트의 시작과 끝을 가리키는 노드가 필요한데요, 각각 머리(Head)와 꼬리(Tail)이라는 이름의 노드로 항상 존재하게 됩니다.

  앞서 본 선형 구조의 자료구조인 스택과 큐에서처럼 연결리스트에도 노드의 추가, 삭제, 탐색 등의 연산이 있습니다. 여기서는 각각을 insert, delete, find라고 부르겠습니다.

  0. 노드 정의

     연결리스트의 노드는 단순히 정수형 데이터 하나만 가진다고 가정하고, 다음과 같이 정의 할 수 있습니다.

typedef struct _node{ 

    int key;

    struct _node *next;

}node; 

      초보자들은 구조체 정의에 _node의 포인터에 당황하실지도 모르겠습니다만, 구조체에서 이런 재귀 정의는 가능하며, 이 의미는 _node라는 구조체 타입을 가리키는 포인터 즉, 다음 노드를 가리킨다는 사실을 아셔야 합니다.

  1. 연결리스트 초기화

     연결리스트의 초기상태는 머리(이하 Head)와 꼬리(이하 Tail)가 연결된 형태로 다음과 같은 모양을 가지고 있습니다.

[빈 연결리스트]

     위와 같이 연결리스트가 비어 있을 경우는 Head가 Tail을 Tail은 그 자신을 가리키는 형태가 되어 있어야 합니다.

node *head, *tail; 

void init_list (void) {

    head = (node *)malloc(sizeof(node));

    tail = (node *)malloc(sizeof(node));

    head->next = tail;

    tail->next = tail;

} 

  2. 연결리스트의 노드추가 - 삽입 : insert_next

    연결리스트의 삽입(이하 insert)은 다음과 같은 순서로 진행됩니다.

    (가) 초기 모양 (t는 head를 가리킴)

    (나) L node를 생성합니다. (s가 가리킴)

    (다) L node가 t의 다음 node를 가리킵니다. (s->next = t->next)

    (라) t의 다음 node 를 L node로 로 변경합니다. (t->next=s)

  위와 같은 과정을 구현하면 다음과 같습니다.

node *insert_next (int key, node *t) {

    node *s;

    s = (node *)malloc(sizeof(node));

    s->key = key;

    s->next = t->next;

    t->next = s;

    return s;

} 

  3. 연결리스트의 노드삭제 - delete_next

    연결리스트의 삭제(이하 delete)는 다음과 같은 순서로 진행됩니다.

    (가) 초기상태 (삭제 전 Node를 t가 가리킴)

    (나) 삭제 대상 Node에 임시 포인터 (s= t->next)

    (다) 삭제 전 Node의 다음 포인터 (t->next = t->next->next)

    (라) 삭제 대상 노드 해제 (free(s))

    코드로 구현하면,,,

int delete_next (node *t) { 

    node *s;

    if (t->next == tail)

        return 0;

 

    s = t->next;                    // (나)

    t->next = t->next->next;  // (다)

    free(s);                         // (라)

    return 1;

} 

  4. 연결리스트 Node 검색 : find

   위와 같이 특정한 key의 다음 Node에 연산을 위해서는 Node를 찾는 연산이 필요한데요. 이는 Head에서 Tail까지 주어진 key가 맞는지 확인 후 return해 주면 됩니다. 바로 코드를 볼께요.

node *find_node (int key) { 

    node *s;

    s = head->next;        // head->next가 연결리스트의 첫 node

    while (s->key != key && s != tail)  // 찾는 key가 맞거나 tail이면 끝

        s = s->next;         // 다음 node로

    return s;

} 

    find_node함수의 return값을 보고 tail이면 검색에 실패, 아니면 성공입니다. 쉽죠?

  연결리스트의 개념을 이해할 때, Node를 그려가면서 연산(insert, delete)을 직접 손으로 해보는게 좋습니다. 주의할 점은 링크의 연결과 제거 그리고 Node의 메모리 해제의 순서가 달라지면 링크가 끊어져 버리는 오류가 발생할 수 있습니다.

  예를 들어 다음과 같은 경우를 보죠.

   (가) insert 하려는 s node를 다음 node에 먼저 연결하지 않은 경우 

    (나) 삭제하려는 Node s의 메모리를 먼저 해제한 경우

   이와 같은 실수를 하지 않도록 주의 하시길 바라면서 연결리스트(단순연결리스트)에 대한 설명을 마치겠습니다.

   다음시간에는 환형연결리스트와 이중연결리스트에 대해서 알아보겠습니다.

Dijkstra's algorithm

Moore's algorithm

오늘은 C언어 연결리스트에 대해서 포스팅을 해보려고 한다.

내가 자료구조라는 것을 처음 접한 대학교 2학년 때 난 이 연결리스트라는 놈을 도저히 이해할 수가 없었다.
왜 이놈들은 함수가 끝나도 계속 메모리에 남아있는 걸까? 라는게 가장 큰 의문점이었고
두번째는 그냥 적당한 라이브러리 쓰면 되는데 왜 굳이 이런걸 만들어야 하는걸까?
라는게 두번째 의문점이었다.

첫번째 의문점은 후에 "다시 체계적으로 배우는 C언어 포인터" 라는 책을 정독한 후에 풀렸고
두번째 의문점은.. 아직도 미스테리다.
다만 우리가 전산학과 학생으로서 이런 것들을 구현해보고 원리를 파악할 수 있다는 이유로 대충 이해하고 넘어가자.



사족이 길었는데..
연결리스트란 무엇인가?
리스트는 자료를 순차적으로 정리해놓은 것을 말한다.
이것들이 메모리상에서 연결되어 있다는 뜻이다.


배열 리스트 같은 경우 리스트의 크기를 미리 크게 정해놓고 그 범위 안에서만 자료의 관리가 가능하기 때문에 
메모리 낭비가 심하다고 볼수 있는데 
연결리스트의 경우는 자료가 입력 될 때마다 동적할당으로 새로운 메모리 주소에 값을 할당하고 
이전 자료와 연결해주기 때문에 메모리 관리가 용이하다.



자료 하나를 담고있는 녀석을 보통 "노드(node)" 라고 부른다.
연결 리스트에 아무것도 없는 상태에서 100이라는 값을 가진 노드를 추가한다고 생각해보자.

노드는 자기 자신의 값과 다음 노드를 가리키는 노드 포인터로 구성된다.
여기서 첫번째 노드는 100이라는 값을 갖고 있으며 다음 노드는 없으므로 NULL 포인터를 가리킨다.
위에 Head라는 노드포인터도 있는데 이것은 연결리스트라는 자료구조에서 일종의 시작점을 알려준다.
배열 리스트 처럼 인덱스를 이용한 간편한 접근이 불가능하므로 첫 노드를 Head 포인터로 가르켜주고
그 Head 포인터를 이용해 다음 노드, 다음 노드 이런 식으로 다른 노드에 접근할 수 있다.

101이라는 값을 갖고 있는 두번째 노드를 삽입하면 이렇게 된다. (과정은 잠시 후에 설명)
기존에 NULL 포인터를 가리키고 있던 첫번째 노드(100이라는 값을 가진 노드)는 이제 다음 노드로 새로 추가된 노드를 가리키고 두번째이자 마지막 노드가 된 101이라는 값을 가진 노드는 다음 노드로 NULL 포인터를 가리킨다.
연결 리스트는 이와 같은 구조로 자료들을 쭈욱 연결해서 저장한다.

그럼 이제 100 노드와 101 노드 사이에 200이라는 값을 가진 노드를 삽입해보자.
우선 동적할당으로 노드 하나를 만들어주고 200이라는 값을 넣어준다.
이 노드의 다음 노드는 원래 100 노드가 다음 노드로 가리키던 노드를 가리키도록 해준 다음
100노드의 다음 노드를 200 노드로 설정하면 깔끔하게 삽입된다.



나도 공대생 인지라.. 이런 복잡한 그림보다 코드를 보는게 이해가 빠를것 같아서..
설명은 여기까지.





아래는 struct 와 함수 선언부분이다. (헤더파일로 쓸 수 있음)

node 는 정수형인 value 와 node*(노드포인터) 형인 next 라는 변수를 갖고 있다.
이 코드에서 우리는 node 보다는 node pointer를 많이 쓸것이므로 typedef를 이용해 nptr을 지정해줬다.
그다음은 list라는 struct를 정해서 head를 가리키는 노드포인터와 리스트에에 몇개의 노드가 있는지 알려주는 count라는 변수를 만들었다.
그 아래쪽 함수는 생각하는 그대로다. (순서대로 초기화, 삽입, 삭제, 검색, 수정, 출력)




연결 리스트 초기화 함수이다.

메인 함수에서 list를 만들고 그 주소를 init()에 넘겨주어 count와 head를 초기화시킨다.




노드 삽입 함수. 리스트형 포인터 변수와 값, 위치를 인수로 받는다.

처음 if 문은 position 값이 적절한지 체크하는 부분이다. 부적절하면 메시지를 출력하고 종료한다.
다음은 new_nptr 이라는 노드포인터에 node 사이즈만큼의 메모리를 동적할당하고 value변수를 설정해준다.
position이 1인 경우 head포인터가 바뀌어야 하므로 첫부분에서 따로 처리해줬고
그게 아닌 경우는 head 포인터의 값을 tmp라는 변수에 복사해서 for 문을 이용해 의도한 위치에 도달할 때까지 계속 next로 찾아간다.
적정 위치에 도달하면 삽입한 후 리스트의 카운터를 1 증가시킨다.




삭제 함수. 리스트형 포인터변수와 위치를 인수로 받는다.

첫부분은 삽입과 마찬가지로 position의 처리 가능 범위를 체크한다. (단, 삽입의 경우 맨 뒤에도 삽입 가능하기 때문에 기존에 존재하는 노드들의 position만 받아야 하는 삭제 함수와는 범위가 1 차이 난다.)
삽입과 마찬가지로 head 포인터를 tmp로 받아준 다음 position이 1이면 head 노드를 바꿔주고 그게 아니라면 position 변수를 이용해 그 위치로 찾아가서 해당 노드의 연결을 해지시킨다.
삭제될 노드의 앞 노드를 tmp로 받고 그 다음 노드를 tmp2로 받아서 tmp2의 다음노드가 tmp의 다음 노드가 되도록 짰다.
삭제에서 주의할 점은 삭제된 노드가 메모리에서 지워질 수 있도록 free() 함수를 이용해줘야 한다는 것이다.
(이때문에 굳이 tmp2라는 노드 포인터 변수를 선언했다.)




검색 함수. 리스트형 포인터 변수와 값을 인수로 받는다.

값을 입력받아서 리스트를 순회하여 같은 값이 있는지 알아본다.
같은 값이 여러개 있다면 처음 나온 position을 리턴하고 없으면 0을 리턴한다.
테스트를 위해 적절한 printf() 함수를 사용했다.




수정 함수. 리스트형 포인터 변수와 값, 위치를 인수로 받는다.

삽입, 삭제와 비슷한데 다른 점은 head 포인터를 변경할 필요가 없다는 것이다.
해당 위치의 노드만 찾아서 값을 바꿔주면 된다.




출력 함수. 리스트형 포인터 변수를 인수로 받는다.

이건 테스트를 위해 만들어본 함수다.
리스트에 들어있는 값들과 count 값을 출력해준다.




메인 함수.

리스트형 포인터변수에 리스트 크기의 메모리를 동적할당 해주고 init(() 함수를 이용해 초기화시켜준다.
저 뒤에 여러가지 테스트 한다고 끄적거려 논거 있는데 너무 길어서 여기까지만 캡쳐.
그래서 뒤에 } 로 닫아줘야 함.



출처 : http://milvus.tistory.com/17

소스코드

/*

 * linkedlist.c

 *

 *  Created on: 2011. 4. 21.

 *      Author: Chwang

 */

#include <stdio.h>

#include <stdlib.h>

typedef struct _node{

int value;

struct _node* next;

}node;

typedef node* nptr;

typedef struct _list{

int count;

nptr head;

}list;

void init(list* lptr);

void insert(list* lptr,int value,int position);

void delete(list* lptr,int position);

int search(list* lptr,int value);

void modify(list* lptr,int value,int position);

void print_list(list* lptr);

void init(list* lptr){

//initialize the list

lptr->count=0;

lptr->head=NULL;

}

void insert(list* lptr,int value,int position){

//insert value to proper position

if(position<1 || position>(lptr->count)+1){

printf("Position Out of Bound\n");

return;

}

nptr new_nptr=(node*)malloc(sizeof(node));

new_nptr->value=value;

if(position==1){

new_nptr->next=lptr->head;

lptr->head=new_nptr;

}

else{

nptr tmp=lptr->head;

int i;

for(i=1;i<position-1;i++){

tmp=tmp->next;

}

new_nptr->next=tmp->next;

tmp->next=new_nptr;

}

lptr->count++;

}

void delete(list* lptr,int position){

//delete an item on the position

if(position<1 || position>(lptr->count)){

printf("Position Out of Bound\n");

return;

}

nptr tmp=lptr->head;

if(position==1){

lptr->head=tmp->next;

free(tmp);

}

else{

int i;

for(i=1;i<position-1;i++){

tmp=tmp->next;

}

nptr tmp2=tmp->next;

tmp->next=tmp2->next;

free(tmp2);

}

lptr->count--;

}

int search(list* lptr,int value){

//traverse the list and

//find the first position of the value (first from head)

//if not exist, return 0

nptr tmp=lptr->head;

int i=1;

while(tmp!=NULL){

if(value==tmp->value) break;

i++;

tmp=tmp->next;

}

if(i>lptr->count){

printf("The value %d is NOT exists\n",value);

return 0;

}

else{

printf("The value %d is at position %d in the list\n",value,i);

return i;

}

}

void modify(list* lptr,int value,int position){

if(position<1 || position>(lptr->count)){

printf("Position Out of Bound\n");

return;

}

nptr tmp=lptr->head;

int i;

for(i=1;i<position;i++){

tmp=tmp->next;

}

tmp->value=value;

}

void print_list(list* lptr){

nptr tmp=lptr->head;

printf("List value: ");

while(tmp!=NULL){

printf("%d ",tmp->value);

tmp=tmp->next;

}

printf("\n");

printf("Total: %d value(s)\n",lptr->count);

}

int main(){

list* mylist=(list*)malloc(sizeof(list));

init(mylist);

insert(mylist,3,1);

insert(mylist,4,2);

insert(mylist,5,3);

insert(mylist,6,4);

insert(mylist,7,5);

insert(mylist,8,6);

insert(mylist,9,7);

insert(mylist,3,3);

print_list(mylist);

delete(mylist,3);

delete(mylist,5);

print_list(mylist);

search(mylist,6);

search(mylist,9);

search(mylist,0);

modify(mylist,100,1);

modify(mylist,101,2);

print_list(mylist);

return 0;

}

#include <stdio.h>

#include <malloc.h>

#include <stdlib.h>

#include <time.h>

typedef struct tagNode

{

       int data;

       struct tagNode *next;

} NODE;

NODE *head, *tail, *working;

// 리스트초기화

void InitList();

// 데이타하나추가

void Insert(int n);

// 주어진데이타를삭제

void Delete(int n);

// 데이타를모두삭제

void RemoveAll();

// 현재리스트의값들을모두더해서보여준다.

void AddAll();

// 주어진데이타와같은노드개수를카운트

int Count(int n);

// 현재리스트의모든내용을보여준다.

void DisplayList();

int main()

{

       // 리스트초기화

       InitList();

       Insert(10);

       Insert(20);

       Insert(30);

       Insert(40);

       Insert(50);

       Insert(10);

       // Display 함수를이용하여연결리스트의데이터들을출력한다.

       DisplayList();

       // 전체합출력

       AddAll();

       // 데이타값이10 인노드의개수를카운트

       Count(10);

       // 노드삭제

       Delete(10);

       DisplayList();

       Delete(50);

       DisplayList();

       Delete(20);

       DisplayList();

       RemoveAll();

       return 0;

}

void InitList()

{

       // 리스트초기화

       head = NULL;

       tail = NULL;

       working = NULL;

}

void Insert(int n)

{

       // 새로노드를하나만들어서값을대입

       working = (NODE *)malloc(sizeof(NODE));

       printf("Adding %d\n", n);

       working->data = n;

       // 이것이꼬리임

       working->next = NULL;

       // 만약머리가비었으면이것이머리임

       if ( head == NULL )

       {

             head = working;

             tail = working;

             return;

       }

       // 머리가아니라면마지막에노드를삽입하고

       tail->next = working;

       // 이것이꼬리임

       tail = working;

}

void Delete(int n)

{

       // 아무런데이타도없으면

       if ( head == NULL )

             // 지울일도없다.

             return;

       // 일단머리를가져온다.

       working = head;

       NODE* node;

       // 같은값을찾아서삭제

       while ( working )

       {

             if ( working->data == n )

             {

                    printf("Deleting %d...\n", working->data);

                    if ( working == head )

                    {

                           head = working->next;

                           delete working;

                    }

                    else

                    {

                           node->next = working->next;

                           delete working;

                    }

                    Delete(n);   // 다른값이있으면또지움

                    break;

             }

             node = working;

             working = working->next;

       }

}

void RemoveAll()

{

       // 머리를가져와서

       working = head;

       // 끝까지지움

       while ( working )

       {

             NODE *node = working;

             // 다음노드준비

             working = working->next;

             // 노드삭제

             printf("Deleting %d\n", node->data);

             free(node);

             node = NULL;

       }

       InitList();

       printf("All elements deleted.\n");

}

void AddAll()

{

       int sum = 0;

       working = head;

       while ( working )

       {

             sum += working->data;

             working = working->next;

       }

       printf("Sum of all : %d\n", sum);

}

int Count(int n)

{

       int count = 0;

       working = head;

       while ( working )

       {

             if ( working->data == n )

                    ++count;

             working = working->next;

       }

       printf("Count of %d : %d\n", n, count);

       return count;

}

void DisplayList()

{

       printf("Display all element : ");

       printf("head = ");

       working = head;

       while ( working )

       {

             printf("%d -> ", working->data);

             working = working->next;

       }

       printf("= tail\n");

}출처 : http://blog.naver.com/PostView.nhn?blogId=xtelite&logNo=50086163288&redirect=Dlog&widgetTypeCall=true

출처 :  http://blog.naver.com/PostView.nhn?blogId=hermet&logNo=95405999

대학교 2학년, 홀로 어두운 방 안에서 만두로 끼니를 때우며 프로그래밍을 하던 시절...

당시 나도 울티마나 한번 따라 만들어본다고 했던 게임이 불현듯 떠올라, 소스를 훑어보다가 A* 알고리즘을 다시금 정리하게 됐습니다.

(뭥미... -_- )

A* 는 길찾기 알고리즘이며 적절한 비용을 요구한다는 점에서 유용하게 사용됩니다.

넓이 우선과 깊이 우선 탐색을 조합하고 목적지까지의 거리를 고려하여 최적의 비용을 찾아 가는 휴리스틱(Heuristic)한 기법을 이용하죠.

적절한 설명을 위해서 당시 게임을 참고 하겠습니다.

 자, 왼편이 실제 게임 화면이라고 가정했을 때, 오른편은 맵의 내부 구조를 시각화 한 것이라고 보시면 됩니다. 위 게임의 2D 맵은 격자들로 구성하여 지형 데이터를 관리하죠. (격자는 실제보다 크게 그렸습니다)  여기서 색깔이 칠해진 격자는 블록된 구역이라고 보시면 됩니다. 즉 장애물 등으로 캐릭터가 갈 수 없는 곳이죠. 응? 저 벽은 지나갈 수 없는 것 아닌가? 라고 생각하실 수도 있는데 원근감을 생각하시면 캐릭터는 벽 뒤쪽으로 지나갈 수가 있기 때문에 블록된 곳이 아닙니다.

자, 어쨌든... 여기서 임의의 위치로 캐릭터가 이동한다고 가정하고 A* 알고리즘이 어떤 순서로 길을 탐색하는지 보도록 합시다. (모든건 수작업이라는 사실... ㅜㅜ)

노란색 그리드가 목적지라고 가정했을 때, 캐릭터 위치로부터 이동 가능한 그리드를 탐색합니다. 즉, 넓이 우선 탐색을 하는 거죠. 그리고 이동 가능한 8방향에 대한 그리드 검색을 마친 후, 목적지에 가장 가까운 노드를 선택하게 됩니다. 여기서는 녹색화살표.

여기서 데이터는 다음과 같이 관리를 하게 됩니다. Open Node와 Close Node라고 하는 두 개의 링크드 리스트를 구축하게 되는데, Open Node는 앞으로 탐색을 시도할 여지가 있는 노드들의 후보 리스트로 볼 수 있습니다. 즉 한 노드는 8 방향에 대해서 탐색 여부를 시도해야 하는데, 이것을 아직 수행하지 않은 노드가 OpenNode 목록에 추가되는 것이고,  CloseNode는 현재 검색한 노드들 중 더 이상 탐색을 시도할 여지가 없는 노드 리스트로 볼 수 있습니다.  그리고 OpenNode에 목록이 추가될 땐, 항상 목적지까지의 거리의 비용이 적은 순으로 정렬 상태를 유지하죠.

따라서 현재, OpenNode 리스트는 녹색을 비롯한 노란색 화살표의 노드들이 연결되어 있고  CloseNode 리스트는 출발점 노드 하나가 됩니다.  

다음 탐색을 시도합니다. 이번에는 이동 경로의 후보로 선택된 녹색 화살표를 중심으로 8방향을 탐색하게 됩니다. (즉, A*는 가장 가능성이 있는 노드들을 우선적으로 따라가며 탐색을 하므로 깊이 우선 탐색을 하게 되는 것이죠.)

OpenNode에는 새로 탐색한 노란색 화살표의 노드가 새로 추가되었으며

CloseNode에는 출발점과 옅은 녹색 화살표의 노드로 구성이 됩니다.

참고)

 노란색 화살표 - OpenNode에 새로 추가된 노드

 연한 노란색 화살표 - OpenNode에 기존에 추가된 노드

 녹색 화살표 - CloseNode에 새로 추가될 노드

 연한 녹색 화살표 - CloseNode에 기존에 추가된 노드

하지만  막다른 길이어서 다시 OpenNode의 후보로부터 탐색을 하게 됩니다. 하지만, 갈 수 있는 길은 바로 아래 한 칸 밖에 없겠지요.

자, 결국 다음 탐색 역시 모두 블럭되어 있거나 이미 탐색된 지역이기 때문에 OpenNode 리스트의 후보로 탐색을 다시 시도하게 됩니다. 결국 위와 같이 되는 것이지요.

그리곤 다음 탐색 후보는 OpenNode 중에서 목적지와 가장 가까운 노드가 되므로 결국 출발점에서 바로 오른쪽 위치에 대해 탐색 시도를 하게 됩니다. 물론 그 노드는 이미 여덟 방향에 대해 탐색이 되었기 때문에 결국, 바로 CloseNode로 들어가게 되겠죠. 그리고 그 다음 후보는 바로 시작점의 바로 위 노드가 되며 역시 같은 이유로 CloseNode로 들어가며, 그 다음 후보는 맨 상단의 노드가 될 겁니다. (아래 그림)

물론 맨 상단 노드를 확장했을 땐, 새로 탐색한 노드들은 기존 OpenNode 후보보다 모두 멀기 때문에 다음 후보는 시작점 바로 오른쪽 하단 노드가 되는 것이지요.

결국 이런식으로 확장을 하다 보면, 최종적으로 목적지에 도착하게 될 겁니다.

그리고 이 흰색 화살표의 노드들을 역으로 추적하면 결국 최단거리가 나오는 것이지요. 물론 흰색 노드는 ClosedNode에 포함된 노드들이며 최종적으로 목적지에 도달했을 때의 노드를 역으로 추적하면 되는 겁니다.

어때요.. 참 쉽죠잉?  (아 힘들어.. 이거야 말로 충격과 공포 ㅡㅜ)

자, 이론은 이해하셨을 거라고 믿고... 이제 구현 한번 들어가 보도록 하겠습니다.

참고로 평가치 값은 degree + distance로 구하는데 거리와 degree의 값의 단위는 해당 프로그램에 맞게 적절하게 정하시면 될 것 같습니다. (degree간의 값의 차이가 1이라고 본다면 인접한 노드들 간의 거리도 1로 지정하는게 적절할 것 같습니다.)

그리고,  OPEN_NODE와 CLOSE_NODE 그리고 스택을 위한 전역 데이터를 각각 선언합니다.

다음 함수들은 구현하기에 어렵지도 않고 중요하지도 않으니 간단한 주석 설명으로 대처 하였습니다.

물론 위의 의사코드 부분은 첨부파일에 완성되어 있으니 참고하시기 바랍니다.

자, 이제부터 좀 중요한 부분들을 보도록 하죠. 먼저 길찾기 시작 함수입니다.

자 다음으로, 현재 탐색 노드를 확장하는 함수를 보도록 합시다.

여기까지는 이해가 되셨길 합니다. 사실 위의 예에서 보여준 게임같은 경우, 대각선 이동은 인접한 두 그리드가 이동 가능할 때 허용되도록 컨셉을 잡는게 더 현실적일 겁니다. 따라서 대각선 판단은 인접한 두 노드가 이동 가능할 때 판단하면 될 듯 합니다. 그건 직접 수정 가능하시겠죠? :)

-인접한 두 노드의 블럭 상태로 대각선 이동 안됨-

자, 다음 함수를 보도록 합시다. 이번 함수는 노드를 확장하고 필요한 경우 리스트를 재정렬합니다.

이제 좀 머리가 아파오실 수도 있습니다. 본 내용과 소스만으로 이해가 되지 않는다면 직접 가상의 길을 그린 후에 이 알고리즘을 따라 직접 확장해 보시는걸 추천드립니다. 그러면 확실해지겠죠.

주석 설명이 다소 부진할 수 있을지도 모르겠습니다. 예제의 경우에 나타나지 않았던  예외적인 상황에 대한 처리부분이지요. 이 부분은 CloseNode의 순서가 바뀌면서 그에 따른 연결된 노드들을 재평가합니다.

마지막으로 노드를 OpenNode에 추가합니다.  주석 내용이 번잡하게 들릴 수도 있는데 결국은, 노드 삽입 시 목적지에 가까운 순서를 유지 한다는 점.

제 역량 부족으로 설명이 힘들군요. 이중 연결 리스트 2개와 스택이 서로 얽혀있어서 말로는 다소 이해하기 힘들 수도 있구요.

예제 소스를 활용하여 진행 노드 상황을 직접 표현하여 이해해보는 것이 명확할 듯 합니다. ㅎㅎ (이런 무책임한...)

자, 어쨌든 A*에 대한 설명은 여기서 마치렵니다. 사실 최적화 방안은 여러 존재합니다. 예를 들면 직선 이동 노드들에 대해선 생략을 한다던지, 맵에 대한 WayPoint 정보를 추가로 삽입하여 이를 토대로 길찾기를 수행한다든지.. 적어도 위 게임에서 문에 대한 위치 정보를 참고할 수만 있어도 매우 최적화된 탐색이 수행되겠지요.

또한 3D 공간에 대해서는 다소 데이터 자체가 매우 상이할 겁니다. (추가적인 정보는 Game Programming Gems 1권을 추천합니다.)

부족한 설명은 첨부 소스를 참고하여 보충하시기 바랍니다.

https://github.com/qiao/PathFinding.js