출처 - Cocos2dx 사용자 모임 네이버 카페.
목차
개요
1.서론
2.그래서 이걸 왜 알아야 하는데?
3.자료구조
-큐
-스택
-배열
-리스트
-트리
4.STL컨테이너
-std::vector
-std::list
-std::map
5.코코스엔진의 엔진동작 방식
6.코코스엔진과 노드, 장점과 단점
6.읽어봐도 모르겠는데?
7..마치며
개요
자료구조와 C++의 STL에서 지원하는 컨테이너 std::vector, std::list, std::map에 대해 간략하게 알아보면서,
게임 프로그래밍과 자료구조, 트리와 코코스엔진을 고찰하는 글 입니다.
상당히 두서없이 작성되었으며, 경력자가 보시면 틀리거나 어처구니 없는 내용도 포함하고 있으니, 내용이 틀리면 반드시 지적해 주시기 바랍니다.
1.서론
코코스2D-X 엔진은 무료 게임 엔진 치고는 상당히 강력한 게임 엔진입니다. C++, lua, javascript로 작성할 수 있고, 그 결과물은 ios, 윈도우, 안드로이드 환경에서 빌드가 가능합니다. 그러나 코코스2d-x는 게임 엔진으로 게임을 개발하기 앞서서, 기본적인 프로그래밍 지식이 없으면 분명 사용하기 어려운 엔진입니다. 툴을 사용하는 시간보다 코드 작성에 할애하는 시간이 더 많기 때문입니다.
물론, 이러한 전문적인 전산 지식 없이도 나는 코코스로 혼자 게임을 만들었고 이걸로 돈 많이 벌었다는 분들도 있을 겁니다. 이러한 비전공에 운이 좋은 분들이 아닌, 게임 프로그래머 지망생, 앞으로 프로그래밍으로 직업을 두실 분들은 이 글을 보시면서 간단하게 '프로그래머는 대충 무슨 지식이 있는가' 에 대해 알아보시길 바랍니다.
2.그래서 이걸 왜 알아야 하는데?
프로그래머는 무슨 직종의 프로그래머가 되었든 결과적으로 '데이터를 다룰 줄 아는 사람' 입니다.
게임 클라이언트 프로그래머는 캐릭터의 아이디, 채력, 공격력, 방어력, 위치, 이동속도, 이동방향 그리고 적의 개수, 아군의 개수 같은 '데이터'를 다룹니다. 예를 들어 봅시다. 플레이어가 맵에 1000명이 그려져야 합니다. 그런데 이 플레이어중에 아이디가 xxx라는 플레이어가 아이디 yyy라는 플레이어에게 100의 공격을 가했습니다. 그렇다면, 10명의 플레이어중 아이디가 xxx인 플레이어와 yyy라는 플레이어를 '어떻게 찾을' 겁니까? 10명의 플레이어를 한명한명 if문으로 돌아가면서 찾을까요? 아니면 무작위로 하나씩 선택해서 if문으로 조건 비교를 할까요?
화면에 총알이 400개가 있습니다. 총알은 화면에서는 무조건 모두다 그려야 하고, 총알은 화면 밖을 나가면 사라집니다. 또한 총알은 적에게 닿으면 사라집니다. 그렇다면 이 총알들을 어디에 보관해서 어떻게 그릴것이며 이에대한 충돌처리를 통해 지워야 하는 총알은 어떻게 찾을까요? 총알에 하나하나 아이디를 부여해야 할까요?
프로그래머는 이런 자료들을 다루고, 어떻게하면 가장 빠르게 동작을 수행할 수 있는지 알아야 하며, 다른 사람이 사용한 코드를 이해하기 위해서도 자료구조에 대한 이해는 필수일 수 밖에 없습니다.
애초에, 게임 프로그래머 면접에서는 반드시 나옵니다. 다시말해서, 이걸 모르면 입사할 수 없습니다.
자료구조의 기본 개념조차 없이 코코스 엔진을 사용한다면, 처음에는 책보고 따라하면서 기능이 동작하겠지만, 프로젝트가 장기화 되고 구조가 커지면 결국 이 '기초'의 벽에 막히게 됩니다. 도대체 addChild가 무슨 의미가 있는지도 알수가 없습니다. 자식을 붙인다는데 왜 하필이면 자식입니까? 그리고 어떻게 addChild로 '자식'을 붙였는데 화면에는 그림이 그려졌는지 도저히 알 방도가 없기 때문입니다.
3.자료구조
자료구조(Data structure)는 자료를 효율적으로 다루기 위한 일종의 개념이자 이론, 학문입니다.
자료구조는 이 단어 하나만으로 대학교 강의가 하나 존재할 만큼 내용이 방대하니까 최대한 줄여서 설명하겠습니다.
간단하게 설명할 글인데, 그림까지 넣고 구조체 코드까지 짜면서 설명할 순 없습니다. 자세한 원리와 동작을 알고 싶으시다면 시중에서 책을 구매해서 보세요.
그리고 앞으로 간단하게 설명하는 자료구조들은 반드시 한번씩은 스스로 검색, 입력, 출력, 삭제, 삽입 코드를 스스로 작성을 해봐야 합니다. 좋은 회사 들어가려면, 이런 것들이 책과 PC없이 '손으로' 가능해야 입사가 가능합니다.
이것이 안된다면 최소한 특징이라도 알고 있어야 합니다. 언제 무슨 자료구조가 쓰인다. 이는 '자료를 다루는 직업'인 프로그래머라면 반드시 알아야할 지식입니다.
-큐
큐는 쉽게 설명하자면 1렬로 길게 선 줄을 의미합니다.
놀이기구를 탈때, 사람이 많으면 우리는 줄을 섭니다. 처음 선 사람이 처음 들어가고, 마지막에 선 사람은 마지막에 들어갑니다.
선입선출(FIFO)라고 처음 들어간 노드가 처음 나옵니다.
애석하지만, 코코스로 프로그래밍을 하면서 큐를 다룰 일은 거의 없을 겁니다. 왜냐면 지원하는 동작이 넣는것과 빼는것 밖에 없이 때문입니다.
실제적으로 사용될때는 서버 입장 대기, 채팅에 사용됩니다. 주로 서버 프로그래머가 자주 다루는 자료구조이기도 합니다.
파생형으로 디큐같은 것이 있습니다.
-스택
스택은 쉽게 설명하자면 프링글스 통에 있는 감자칩과 같습니다.
프링글스 통 바닥에 있는걸 먹으려면, 앞에있는 갑자칩들을 전부 꺼내야 합니다. 그래서 위에서 부터 먹습니다.
선입후출(FILO) 먼저 들어간것이 가장 나중에 나옵니다.
스택 큐와 마찬가지고 직접적으로 사용할 일은 드물지만, 함수의 호출은 스택으로 이루어 집니다.
디버깅하는데 '호출 스택'이 바로 이것입니다.
A라는 함수에서 B 함수를 호출했다고 합시다.
A라는 함수는 B라는 함수가 끝나기 전까지는 동작이 끝날 수 없습니다.
다시말해 스택에는, A가 먼저 들어갔고 그 후에 B가 들어갔습니다. A를 꺼내려면(A의 동작이 끝나려면) B부터 꺼내야(B의 동작이 끝나야) 합니다.
실무에서 에러가 터졌습니다. 당신은 선배에가 갔습니다. '선배님 에러가 났습니다.' 선배가 말합니다. '호출 스택 찾아봤어?' 당신이 답변합니다. '스택이 뭐에요?' 이러면 인사평가에 심각한 악영향을 끼친다 이말입니다.
-배열
배열은 우리가 생각하는 그 배열이 맞습니다.
int nArrData[10] = {0}; //int의 배열을 10개 선언하고 모두 0으로 초기화 했습니다.
더 정확히 말하자면, int 라는 구조의 메모리를 10개 잡아서 이 첫 주소를 nArrData 에 담았다 라는 말입니다.
첫 주소는 nArrData 이기도하고, &nArrData[0] (배열 첫번째 인덱스의 주소)일수도 있습니다.
(더 이야기를 깊게 하자면, int랑 float이랑 똑같이 32비트 컴파일러 환경에서는 4byte인데 int는 정수고 float은 실수입니다.
int nData = 0;
float fData = 0.0f;
nData = fData; //에러
int도 4바이트고 float도 4바이트인데 이 차이점이 뭘까요? 메모리를 사용하는 방식에 대한 차이입니다. 그러니까 int nArrData[10];은, int 형으로 사용할수 있는 메모리를 10개 잡았다는 말입니다. 순수하게 바이트 단위로 메모리를 잡고 싶으시면 void* 쓰시면됩니다.)
배열은 쉽게 사용할 수 있는 자료구조이고 모든 자료구조 중에서 찾는 속도가 가장 빠릅니다.
믿기 어렵겠지만 배열은 모든 자료구조중에 가장 빠릅니다. 왜냐면 메모리에 있는 주소에 직접적으로 접근할 수 있기 때문입니다.
int nArrData[100000] = {0}; //int형을 십만게 잡았습니다.
printf("%d", nArrData[999]); 999번 인덱스의 값을 출력합니다.
완전 간단합니다. 그리고 완전 빠릅니다. 숫자로 정확인 인덱스를 꺼내는 방식은 데이터를 찾을 때 가장 빠른 방식입니다. 그러나 배열은 단점이 있습니다. 한번 잡은 메모리 최대 인덱스는 무슨수를 써도 늘릴 수도 줄일 수도 없다는 것입니다.
그렇기 때문에 우린 '가변적인' 배열이 필요합니다. 그리고 그렇게 해서 나온 것이 std::vector입니다. 벡터에 대한 이야기는 나중에 합시다.
장점 : 가장 빠르다.
단점 : 한번 잡은 메모리 공간은 늘릴 수도 줄일 수도 없다.
사용예 : 정해진 크기의 데이터를 유일한 숫자(id)를 이용하여 찾을 수 있을 때
결론적으로, 분명히 빠른데 가변할 방법이 없으니 가변이 가능한 std::vector를 사용한다. - 물론 벡터가 가변이라고 중구난방으로 가변하진 않습니다.
-리스트
리스트는 쉽게 이해하자면 꼬리에 꼬리를 문 기차, 지하철을 생각하면 됩니다.
기차는 열차의 칸과 칸이 연결되어서 움직입니다.
노드의 구성은, 요약하면 대충 이런식 입니다.
struct S_LISTNODE
{
int nData //리스트가 가지고 있는 데이터입니다. 실무에서는 절대로 이렇게 int가 쓰일 일이 없습니다. 대신 다른 데이터 구조체가 사용될 것입니다.
S_LISTNODE * pNextNode; //리스트 노드는 '다음 리스트 노드의 주소값'을 가집니다.
}
예를들어
S_LISTNODE* pNode1 = new S_LISTNODE; //노드 1번을 생성
S_LISTNODE* pNode2 = new S_LISTNODE; //노드 2번을 생성
pNode1->pNextNode = pNode2; //노드 1번의 다음 노드는 노드 2번입니다.
우리는 노드 1번의 주소만 알아도, 노드 2번을 알 수 있습니다.
그리고 리스트는 배열과 달리 길이가 가변적입니다. 자료의 길이를 늘리고 싶으면, 계속해서 노드를 만들어서 기존에 만든 리스트의 노드 끝에 이를 붙이면 됩니다. 마지막 노드는 어떻게 알까요?
//pNode1에는 8000개의 리스트 노드가 붙어있다고 합시다.
S_LISTNODE *pTempNextNode = nullptr; //리스트 노드의 마지막을 담을 임시 포인터
pTempNextNode = pNode1; //임시 포인터에 리스트 노드의 첫번째 주소를 넣습니다.
while(pTempNextNode->pNextNode != nullptr) //임시 포인터의 다음 노드가 존재하나요?
{
pTempNextNode = pTempNextNode->pNextNode; //임시 포인터에 임시포인터의 다음 노드를 넣습니다.
}
pTempNextNode // 여기에 나온 노드는 마지막 노드입니다.
리스트는 배열과 달리 가변적이라는 장점이 있습니다.
리스트는 주로 '모든걸 다 사용해야 할때' 사용합니다.
캐릭터가 밟고 서있는 지형의 경우, 일부러 찾아야 하는 일이 없다면 무조건 화면에 그립니다.
총알의 경우, 무조건 화면에 다 보여줘야 한다면, 총알은 리스트로 담을 수 있습니다.
그러나 리스트는 찾는 것에 약합니다.
만약 1000개의 노드가 연결된 리스트에서 899번째 노드의 값을 찾으려면 어떻게 해야 할까요?
우리가 아는 것은 노드의 첫번째 주소밖에 없습니다.
네! 처음부터 899번째 까지 계속 노드를 하나하나 옮겨다니면서 nCount를 비교해서 찾습니다.
리스트에 index를 넣어두면 안되냐구요? 비효율적입니다. 값을 비교하는건 더 오래 걸립니다. 리스트의 노드를 옮겨간 뒤에, 해당 노드에 있는 데이터를 비교하고 또 노드를 옮겨서 데이터를 비교하고... 엄청난 시간이 걸립니다.
애석하지만, 리스트는 사실 잘 사용되진 않습니다. 웹프로그래밍에서 DB서버에서 받은 데이터를 웹페이지에 출력할 때 사용하긴 하는데 게임프로그래밍에서 사용하기엔 조금 무리가 있습니다. 왜냐면 우린 찾아야 하는일이 훨신 더 많기 때문입니다.
실무에서는 잘 사용되지 않지만,(정확히는 활용도를 찾기가 어렵지만) 입사시험에선 정말 잘 나옵니다. 리스트 병합, 검색, 삽입 관련 손코딩은 기술시험의 당골문제입니다.
-트리
트리는 내컴퓨터의 폴더를 떠올리시면 좋습니다. 혹은 프로젝트 네비게이션(익스플로러)에 있는 파일 구조가 트리입니다.
C드라이버를 열면 프로그램파일즈와 윈도우 폴더, 유더 폴더가 있고 유저폴더 밑에는 바탕화면과 다운로드가 있고 이런식입니다.
트리는 역시도 여러가지 구조가 있습니다. 완전 이진트리, 이진트리, 그냥 트리 더 나아가면 AVL 트리 Red black 트리 등등.. 그러나 이 모든 트리를 다 알 필요는 없습니다. 아니 하나라도 더 아시고 이를 혼자서 구현할수 있는 실력이 있으시면, 연봉이 바뀌실 겁니다.
이들은 종류는 다르지만 결국 '최대한 빨리 찾기 위해' 각자 다른 검색 방법을 사용하는데 그 차이가 있습니다. 더 정확히 말하자면, 트리에 자식이 추가 되면 이를 어떻게 '잘 섞는가'에 따라서 종류가 다릅니다. 트리는 검색에 있어서 자료구조들 중에 평균적으로 빠릅니다.
트리는 뭐가 되는 최초 root라고 부르는 부모로 부터 내려옵니다. 부모는 자식이 있고, 자식은 부모가 있는구조 입니다.
리스트가 '다음 노드 주소'를 하나만 가질 수 있다면 트리는 여러개를 가집니다. 뭐 대부분의 경우, 찾는 속도 때문에 이진트리 구조로 가기 때문에
struct S_BNODE
{
int nData;
S_BNODE* pLeftChildNode;
S_BNODE* pRightChildNode;
}
트리는 노드로 구성되기 때문에 배열과 달리 그 메모리 길이가 가변적입니다. 얼마든지 줄이고 늘릴 수 있습니다.
또한 찾는 속도는 당연 배열보다는 느리겠지만 '평균적으로' 빠릅니다. 만약 수백만개의 데이터중, ID가(키값이) "KEY_SCHEDULE_UPDATE" 라는 녀석을 찾아야 한다면, 이건 트리형태의 자료구조만 가능한 찾는 방법입니다.
배열은 어떻게 합니까? 숫자로만 이루어진 index만 사용할 수 있는 배열은 문자 자체를 찾는데 이용 할 수 없습니다.
예를들어
struct S_NODE
{
std::string strKey;
int nData;
}
S_NODE * pArrNode[10000]; //S_NODE 포인터를 만개 선언했습니다.
for문으로 index를 하나하나 돌아가며 S_NODE의 key라는 데이터의 값을 일일이 하나하나 찾을 까요? 이건 리스트나 똑같습니다.
그러나 트리는 숫자가 아닌 문자(키값)로 '찾는' 것이 가능합니다.
이 키값은 트리 검색 특성상 반드시 '유일값' 이어야 합니다. 배열의 인덱스를 중복해서 다른 값을 저장할 수 없듯, 트리에서도 트리에 달려있는 특정 노드를 찾는 근거인 '키 값'은 반드시 유일 값이어야 합니다.
장점 : 메모리의 길이가 가변적, 평균적으로 찾는 속도가 빠르다, 설계, 관리하기 편하다. 문자로 데이터를 찾을 수 있다.
단점 : 그렇다고 탐색이 가장 빠른 것은 아니다. 키값 관리가 확실해야 한다.(유일 값이어야 한다)
트리는 배열만큼 다방면으로 사용되는 자료구조입니다. 가장 대표적인 예는 인벤토리 입니다. 빨간대형 포션이 인벤토리에 있는지 없는지 알려면 어떻게 해야 할까요? 해당 아이템의 아이디로 조회해서 이 아이디를 가진 아이템이 내 인벤토리에 있는지 없는지 검색합니다.
주민등록 번호로 회원을 찾을 때는? 베열은 주민등록 번호 알려면 회원을 0부터 끝까지 다 돌면서 데이터를 꺼내와서 그 값을 비교해야 하지만, 맵은 드민등록번호 자체만으로 아이디를 꺼내기 용이합니다.
4.STL컨테이너
STL 문법과 STL이 가진 모든 내용들에 대해 설명을 해야한다면, 자료구조보다 더 많은 이야기를 다뤄야 합니다. 그러니까 이것도 책 한권은 나오는 분량이지만 실무에서 사용되는 것 위주로 최대한 요약해서 설명합니다.
-std::vector
벡터는 한마디로 배열입니다. 배열은 메모리의 길이가 고정되어 있지만, 벡터는 가변적입니다.
그렇다면, 배열은 가장 빠른 컨테이너니까 벡터가 메모리 가변까지 된다면, id만 잘 관리하면 최강의 컨테이너겠네요? 맞습니다.
벡터는 실무에서 널리 사용되는 STL 컨테이너 이기도 하며, 코코스에서도 쉽게 찾아 볼 수 있는 STL 컨테이너 입니다. 당장에 멀티터치 함수인 touches 시리즈만 보세요. 터치된 값이 무엇으로 넘어옵니까? vector입니다.
물론 벡터는 가변적이지만, 사실 조금 허점이 있습니다. 가변적으로 사용하면, 오히려 속도가 느려진다는 겁니다.
벡터는 배열이라면서, 배열이 찾는 속도가 가장 빠른데, 가변적이라 배열의 한계를 극복한 컨테이너인데 이ㅏ것으로 속도가 느려진다니, 보는 사람이 답답 할 수 있겠지만 이유는 다음과 같습니다.
벡터는 주로 push_back으로 그 크기를 늘립니다.
예를들어서, int형을 5개 선언하고 0번부터 4번 인덱스에 전부 10이라는 값을 입력한다면, 다음과 같습니다.
int nArrData[5] = {0};
for(int i = 0; i < 5; ++i)
{
nArrData[i] = 10;
}
벡터는 다음과 같습니다.
std::vector<int> vec_nData; //벡터를 생성합니다.
for(int i = 0; i < 5; ++i)
{
vec_nData.push_back(10); //벡터에 10을 차곡차곡 밀어넣습니다.
}
출력할때 - 실제로는 벡터꺼낼때 이터레이터 안사용합니다.. 엄청나게 느리기 때문에
실무에서 C++11을 사용하는데 아직도 벡터에 이터레이터 사용하면 조금 문제가 있다고 봅니다.. 아니 애초에 배열연산자를 사용함. 혹은 auto를 혼합한 범위기반 for문,
std::vector<int>::iterator itor; //int라는 자료형을 사용하는 벡터의 이터레이터를 선언
for(itor = vec_nData.begin(); itor != vec_nData.end(); itor++) //이터레이터를 돌면서
{
printf("%d\n", *itor);
}
벡터는 배열이라고 했는데 사용법이 굉장히 이상합니다.
벡터를 사용하는데 push_back을 사용하는 것은 사실상 자살행위와 같습니다. push_back은 가변적으로 배열을 하나하나 늘릴 수 있는 마법의 주문이기도 하지만, 이것의 내부 동작은 다음과 같습니다.
벡터가 생성되고, 여기에 push_back을 하면, 벡터는 임시 메모리를 내부적으로 잡습니다.
그리고 이 임시메모리를 초과해서 계속해서 push_back을 하면, 기존의 메모리보다 조금 더 큰 메모리를 별도로 새로 잡고, 기존에 있던 메모리를 새로 잡은 메모리에 통채로 복사하는 굉장한 연산을 내부적으로 수행합니다. <- 이 복사하는 과정에서 엄청난 시스템 비용을 요구합니다.
벡터 관련해서 메모리 관련 오류, 성능저하의 대부분이 push_back에서 발생한다는 점은 알아둬야 합니다.
그렇다면 벡터는 어떻게 사용해야 할까요? 미리 메모리를 잡는 수 밖에 없습니다.
미리 10개를 잡고
vec_nData.reserve(10);
vec_nData.resize(10);
vec_nData[0] = 10; //배열 연산자로 값을 넣습니다.
그리고 stl 컨테이너의 값을 꺼낼때 사용하는 '이터레이터'는 벡터에선 사용하지 않습니다.
벡터는 배열연산자(대괄호 연산자)를 지원합니다. 물론 배열 인덱스를 넘어서 값을 호출한다면 프로그램이 죽는 것은 맞습니다. 이는 반드시 예외처리가 필요합니다.
단적으로 성능 테스트를 해봐도, 벡터에 만번, 십만번씩 push_back을 하는 것과, 미리 메모리를 잡고 배열연산자로 만번, 십만법 데이터를 입력하는 것은 엄청난 속도차이가 납니다. 이건 무시할 수 없는 속도 차이 입니다.
검색 속도는 배열연산자 >>>>>>>>>>>>>>>>>>>>>>>>>>범위기반 for문>>>>>>>>>>>>>이터레이터 순입니다.
입력 속도는 배열연산자 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> push_back 순 입니다.
뭐 서버통신같이 벡터의 정확한 길이를 알 수 없는 경우는 어쩔 수 없이 push_back을 사용하겠지만, 반드시 정확한 최대 고정값을 알 수 있다면, 벡터는 배열처럼 사용하면됩니다. 미리 최대 메모리를 잡고(가변하고) 대괄호 연산자로 배열처럼 사용한다가 벡터의 사용법입니다.
-std::list
사실 리스트 자료 구조 자체를 사용할 일이 없어 std::list는 자료구조 리스트와 동일 합니다.
std::list에서는 index의 검색이나 해당 위치에 노드 삽입 등 여러가지 기능을 지원하지만 이런 것을 사용할 일이 생긴다면 std::list는 사용할 필요가 떨어집니다.
-std::map
std::map은 트리와 같습니다. map은 first와 second로 나뉘는데, first는 앞서 말한 키값(유일값), second는 저장할 자료가 들어가게 됩니다.
std::map 역시 벡터와 마찬가지로 대괄호 연산자를 지원하기 때문에 mapData["fncFoo"]; 같은 배열에 문자열이 들어가는 코드들도 심심찮게 볼 수 있게 됩니다. std::map은 유용하게 사용되며 map과 관련된 인터페이스를 아는게 좋습니다. map에서 사용하는 대괄호 연산자는 잘못 사용하면 위험한 결과를 초래합니다.
그리고 삭제시에 이터레이터 주소 변화에 대해서 잘 숙지해야 검색, 입력, 삭제가 원활하게 가능하니까 반드시 std::map은 관련 인터페이스를 한번씩은 다 사용는걸 추천합니다. 입력 역시 방법이 다양합니다. insert로 넣는 방법, pair로 넣는 방법, 대괄호 연산자로 넣는 방법 등...
map역시도 벡터 이상의 인터페이스 사용법을 설명해야 하지만 단순하게 맵은 트리다 라는 것만 알아도 접근하기 쉬우실 겁니다.
5.코코스엔진의 엔진동작 방식
코코스 엔진은 OpenGL기반입니다. 다시말해서 우리는 생각없이 addChild를 하고 addChild한 스프라이트가 화면에 출력되니까 단순하게 'addChild는 그림을 그리는데 사용하는 함수이구나!' 라고 착각 할 수 있습니다.
그런데 이건 정말 위험하고 잘못된 생각입니다. addChild의 의미는 자식 노드를 부모에게 붙였다는 의미입니다.
this 는 무엇입니까? 흔히들 this는 java를 배울때나 C++을 배울 때나 '자기자신'이라고 합니다. 더 정확하게 설명하자면, 현재 클래스의 주소입니다.
C_CLASS 라는 이름의 클래스에
class C_CLASS
{
printMyAdress(); //나의 주소를 출력하는 함수를 선언 했습니다.
}
C_CLASS::printMyAdress() //C_CLASS에는 printMyAdress라는 함수가 있고, 이를 구현합니다.
{
printf("my address : %p \n", this); //나(C_CLASS)의 주소값을 출력합니다.
}
main()
{
C_CLASS* pClassData = new C_CLASS; //C_CLASS의 메모리를 동적할당으로 잡았습니다.
cData.printMyAdress(); //this 의 주소를 출력합니다.
printf("pClassData's address : %p", pClassData); //동적할당된 포인터의 주소를 출력합니다.
}
결과 : - 둘다 동일하다.
my address : 0x83757638fe
pClassData's address : 0x83757638fe
이야기가 굉장히 다른곳으로 빠졌는데 그래서 결국 this->addChild(스프라이트)의 의미는 무엇입니까?
나 자신(부모)에게 자식(스프라이트) 를 붙인다 입니다.
-사실 this는 생략이 가능합니다. this->addChild()는 addChild()와 같습니다. 그냥 해당 클래스가 가지고있는 addChild()라는 함수를 호출했다 라는 의미이기 때문입니다.
-이것이 cocos2D(x가 아닌)에서 오브젝트C의 self가 형식상으로 내려온건지.. 왜 예제에 this->가 들어가는지는 솔직히 잘 모르겠습니다.
코코스2D-X는 무엇을 합니까? OpenGL을 기반으로, 그냥 내부적으로 씬에 붙은 수많은 자식들을 죽어라고 갱신하며 새로 그립니다.
auto pSprCircle = Sprite::create("Circle.png"); //스프라이트 를 하나 생성
auto pNode = Node::create(); //일반 노드를 하나 생성
this->addChild(pNode); //부모에게 일반 노드를 붙인다.
pNode->addChild(pSprCircle); // 일반 노드에 스프라이트'노드'를 자식으로 붙인다.
pNode=>setPosition(Vec2(100.0f, 100.0f)); //일반 노드를 100,100 위치로 지정한다.
Vec2 Pos = pSprCircle->getPosition(); //스프라이트 노드의 위치를 Pos라는 변수에 얻는다.
log("Pos.x = %f, Pos.y = %f", Pos.x, Pos.y); // 스프라이트의 위치를 출력한다.
분명히 pSprCircle은 화면의 100, 100 위치에 있는데,
로그의 결과는?
결과 :
Pos.x = 0.0000, Pos.y = 0.00000
왜 그럴까?
스프라이트의 '부모 노드'가 100, 100 위치에 있으니까 당연히 스프라이트는 화면은 100, 100 위치로 간것이 맞고,
스프라이트는 '부모 노드 기준'으로 0,0 위치에 있으니까 스프라이트의 위치는 0,0이 맞습니다.
코코스는 다시 설명하지만, 트리구조 입니다. 우리가 흔하게 사용하는 스프라이트 조차도 부모 클래스는 Node 입니다. (여기서 부모는 트리구조에서의 부모가 아닙니다. 클래스 상속에서의 부모) 내부적으로 메모리 찾기 로직이 어떻게 되어있는지 사용자는 알 수 없지만, 사용자는 트리로 씬을 구성 할 수 있습니다.
노드로 파생되는 클래스에는
Inherited by __NodeRGBA, AtlasNode, AttachNode, BaseLight, Camera, ClippingNode, ClippingRectangleNode, DrawNode, SpritePolygon, TMXLayer, TMXTiledMap, TableViewCell, Layer, MenuItem, MotionStreak, NodeGrid, ParallaxNode, ParticleBatchNode, ParticleSystem, ProgressTimer, ProtectedNode, RenderTexture, Scene, Skybox, Sprite, Sprite3D, SpriteBatchNode, Terrain, TMXTiledMap, Scale9Sprite, and GLNode.
이런 종류가 있습니다. 이러한 노드들이 서로서로 부모가 되기도 하고 자식이 되는 것들을 코코스2D-X는 열심히 그릴 뿐입니다.
그러니까 부모를 둘로 만들거나 해선 안됩니다. 일반적으로 사용하는 트리는 부모가 하나입니다. 다차원 검색트리 같이 부모가 여럿인 거창한 물건이 아닙니다. (애초에 부모를 두개 두려고 하면 에러가 터집니다.)
-이런 트리는 아니라는 겁니다. : http://people.engr.ncsu.edu/efg/506/s03/lectures/annotation/lec26/index.html
그러니까 우린 addChild의 의미를 다시 한번 고찰할 필요가 있습니다. 단순히 addChild는 함수를 호출하는 주체(부모)에게 자식을 붙인다는 의미 입니다.
this->addChild(노드) 나에게 노드를 붙였다. 일 뿐입니다. 노드를 그린다의 의미가 전혀 아닙니다. 단순히 엔진은 자동적으로 무한히 노드들을 그리고 있으니까, 붙인다는 행위 자체가 '그린다' 라는 의미로 착각하기 쉽습니다.
6.코코스엔진과 노드, 장점과 단점
트리구조의 장점은 평균적인 검색 속도 이외에도 관리나 설계가 편합니다.
마치 내컴퓨터 안에서 파일들을 정리할 때 폴더를 분할하여 만들듯, 이러한 정리가 가능합니다.
예를들어 캐릭터 '노드'가 있다고 합시다. 캐릭터에는 캐릭터의 베이스 그림이 있고, 모자를 쓰고 있고, 무기를 장착하고 있고 하단에는 체력게이지가, 상단에는 아이디와 레벨이 표시됩니다.
나는 캐릭터를 이동하고 싶습니다.
여기에서 트리 구조를 아느냐 모르느냐로 노드 설계와 이동 구현이 확연히 차이 납니다.
1.트리 구조를 아는 사람
-캐릭터의 메인 노드를 만든다.
-이 메인 노드에 캐릭터의 베이스 그림을 붙인다.(addChild한다)
-캐릭터의 베이스 그림에 모자, 무기, 아이디, 레벨을 붙인다.(addChild한다)
-캐릭터의 메인 노드를 runAction(MoveTo::create())로 이동시킨다.
(모든 노드들이 캐릭터 메인 노드에 붙어있으니까, 이 부모노드 하나만 움직이면 전체가 다 움직임)
2.트리 구조를 모르는 사람
-캐릭터 베이스 그림 스프라이트를 만들고 this->addchild한다 (addChild가 그림을 그리는 기능이었지!)
-모자 스프라이트를 만들고 this->addchild한다 (addChild가 그림을 그리는 기능이었지!)
-무기 스프라이트를 만들고 this->addchild한다 (addChild가 그림을 그리는 기능이었지!)
-이름 Label을 만들고 this->addchild한다 (addChild가 그림을 그리는 기능이었지!)
-레벨 Label을 만들고 this->addchild한다 (addChild가 그림을 그리는 기능이었지!)
-캐릭터 베이스 그림 스프라이트를 runAction(MoveTo::create()) 한다! (그림 하나를 그렸으니까 이 그림을 이동시켜야 겠지!)
-모자 스프라이트를 runAction(MoveTo::create()) 한다! (그림 하나를 그렸으니까 이 그림을 이동시켜야 겠지!)
-무기 스프라이트를 runAction(MoveTo::create()) 한다! (그림 하나를 그렸으니까 이 그림을 이동시켜야 겠지!)
-이름 Label을 runAction(MoveTo::create()) 한다! (그림 하나를 그렸으니까 이 그림을 이동시켜야 겠지!)
-레벨 Label을 runAction(MoveTo::create()) 한다! (그림 하나를 그렸으니까 이 그림을 이동시켜야 겠지!)
그러나 트리의 노드 구조 설계는 상당히 편하고 좋은 기능 같지만, zOrder 설정 앞에서는 모두 무용지물이 됩니다.
씬 하나에 수십 수백개의 그림들이 붙게 되는데, 이들의 높낮이는 어떻게 설정할 것입니까?
그리고 기획상, 이 그림들의 높낮이가 변경되어야 하는 일이 많다면, 이것들의 관리를 어떻게 할겁니까?
예를들어 부모노드에 A, B 라는 노드가 붙고 B라는 노드에 C가 붙습니다.
A의 zOrder가 10이고 B의 zOrder가 5이고 C의 zOrder는 10000입니다.
A와 C의 그림이 서로 겹치면 누가 더 위에 보일까요? zOrder가 10000인 C일까요? 애석하게도 A가 가장 위에 보입니다.
그러니까 이 노드 단위 설계도 결국 zOrder 앞에선 굉장히 의미 없는 작업이 될 수 있습니다.
그냥 다 동일한 부모노드에 addChild하고 zOrder를 enum으로 확실하게 관리하는 것이 장기적으로는 훨신더 현명한 판단입니다.
물론, 노드 단위 설계가 필요한 부분이 있고 순수 zOrder의 정확한 설계로만 해결이 가능한 부분이 있어 이를 잘 파악하는 것이 코코스 엔진을 사용할 때 중요하다고 볼 수 있겠습니다.
6.읽어봐도 모르겠는데?
왜냐면 글쓴이의 실력이나 내용이 형편없기 때문입니다. 정확한 것은 책을 보셔야 합니다. 사실 파트 하나당 책이 수십권씩은 시중에 나와있습니다. 그 많은 지식들을 글 하나로 알 수 있진 않습니다. (사실은 글쓴이도 잘 몰라서)
자료구조, STL, 코코스엔진 관련 서적을 각 한권씩 보시고 한번씩 코드를 다 사용해보면 감이 오실 겁니다.
자료구조는 물론이고 관련한 탐색 , 정렬 알고리즘만 정확하게 익히고 책이나 컴퓨터 없이 손으로 코딩할 수 있어도 왠만한 회사에는 다 들어가실 수 있을 겁니다.
7..마치며
자료구조는 프로그래머에게 뗄래야 뗄 수 없는 영역입니다. 실무에서 일을 하든, 집에서 혼자 게임을 제작하든, 더 빠르고 적은 연산을 위해서는 끊임 없이 고민하고 선택의 길에 놓이게 됩니다. 이것이 숫자로 찾을 수 있는 건가? 문자로 밖에 못찾는 건가? 유일값인가? 연속되서 계속 호출하는가? 찾을 일이 없는가? 너무나 다양한 데이터들을 접할 기회가 계속해서 생깁니다.
또한 자료구조와 관련된 인터페이스의 설계에 대해 정확하게 내용을 알고 있어야 함수의 쓰임세를 알아보기 용이 합니다. 남이 만든 함수를 뜯어보고 있는데, isRecursive 라는 bool 값과 함께 함수가 자기 자신을 호출하는 재귀 함수 가 등장했다고 합시다. 재귀함수가 사용되는 경우는 두가지가 있습니다. 트리구조에서 자식들을 모두 찾을 때와 스캘레톤 애니메이션(이것도 결국 트리구조입니다) 구동시에 사용합니다. 결국 특정 노드의 자식들을 다 훑어가며 무언가 동작을 하는 함수라는 겁니다. 지식이 없으면 이런 기초적인 유추도 불가능합니다.
아무튼 상당히 두서없이 내용도 없는 글을 올렸는데 뭐 도움이 되셨으면 좋겠고 제가 틀린 부분도 지적 받아서 제 지식을 고쳤으면 합니다.
내용이 틀린 부분은 반드시 말씀해 주세요..
개요
1.서론
2.그래서 이걸 왜 알아야 하는데?
3.자료구조
-큐
-스택
-배열
-리스트
-트리
4.STL컨테이너
-std::vector
-std::list
-std::map
5.코코스엔진의 엔진동작 방식
6.코코스엔진과 노드, 장점과 단점
6.읽어봐도 모르겠는데?
7..마치며
개요
자료구조와 C++의 STL에서 지원하는 컨테이너 std::vector, std::list, std::map에 대해 간략하게 알아보면서,
게임 프로그래밍과 자료구조, 트리와 코코스엔진을 고찰하는 글 입니다.
상당히 두서없이 작성되었으며, 경력자가 보시면 틀리거나 어처구니 없는 내용도 포함하고 있으니, 내용이 틀리면 반드시 지적해 주시기 바랍니다.
1.서론
코코스2D-X 엔진은 무료 게임 엔진 치고는 상당히 강력한 게임 엔진입니다. C++, lua, javascript로 작성할 수 있고, 그 결과물은 ios, 윈도우, 안드로이드 환경에서 빌드가 가능합니다. 그러나 코코스2d-x는 게임 엔진으로 게임을 개발하기 앞서서, 기본적인 프로그래밍 지식이 없으면 분명 사용하기 어려운 엔진입니다. 툴을 사용하는 시간보다 코드 작성에 할애하는 시간이 더 많기 때문입니다.
물론, 이러한 전문적인 전산 지식 없이도 나는 코코스로 혼자 게임을 만들었고 이걸로 돈 많이 벌었다는 분들도 있을 겁니다. 이러한 비전공에 운이 좋은 분들이 아닌, 게임 프로그래머 지망생, 앞으로 프로그래밍으로 직업을 두실 분들은 이 글을 보시면서 간단하게 '프로그래머는 대충 무슨 지식이 있는가' 에 대해 알아보시길 바랍니다.
2.그래서 이걸 왜 알아야 하는데?
프로그래머는 무슨 직종의 프로그래머가 되었든 결과적으로 '데이터를 다룰 줄 아는 사람' 입니다.
게임 클라이언트 프로그래머는 캐릭터의 아이디, 채력, 공격력, 방어력, 위치, 이동속도, 이동방향 그리고 적의 개수, 아군의 개수 같은 '데이터'를 다룹니다. 예를 들어 봅시다. 플레이어가 맵에 1000명이 그려져야 합니다. 그런데 이 플레이어중에 아이디가 xxx라는 플레이어가 아이디 yyy라는 플레이어에게 100의 공격을 가했습니다. 그렇다면, 10명의 플레이어중 아이디가 xxx인 플레이어와 yyy라는 플레이어를 '어떻게 찾을' 겁니까? 10명의 플레이어를 한명한명 if문으로 돌아가면서 찾을까요? 아니면 무작위로 하나씩 선택해서 if문으로 조건 비교를 할까요?
화면에 총알이 400개가 있습니다. 총알은 화면에서는 무조건 모두다 그려야 하고, 총알은 화면 밖을 나가면 사라집니다. 또한 총알은 적에게 닿으면 사라집니다. 그렇다면 이 총알들을 어디에 보관해서 어떻게 그릴것이며 이에대한 충돌처리를 통해 지워야 하는 총알은 어떻게 찾을까요? 총알에 하나하나 아이디를 부여해야 할까요?
프로그래머는 이런 자료들을 다루고, 어떻게하면 가장 빠르게 동작을 수행할 수 있는지 알아야 하며, 다른 사람이 사용한 코드를 이해하기 위해서도 자료구조에 대한 이해는 필수일 수 밖에 없습니다.
애초에, 게임 프로그래머 면접에서는 반드시 나옵니다. 다시말해서, 이걸 모르면 입사할 수 없습니다.
자료구조의 기본 개념조차 없이 코코스 엔진을 사용한다면, 처음에는 책보고 따라하면서 기능이 동작하겠지만, 프로젝트가 장기화 되고 구조가 커지면 결국 이 '기초'의 벽에 막히게 됩니다. 도대체 addChild가 무슨 의미가 있는지도 알수가 없습니다. 자식을 붙인다는데 왜 하필이면 자식입니까? 그리고 어떻게 addChild로 '자식'을 붙였는데 화면에는 그림이 그려졌는지 도저히 알 방도가 없기 때문입니다.
3.자료구조
자료구조(Data structure)는 자료를 효율적으로 다루기 위한 일종의 개념이자 이론, 학문입니다.
자료구조는 이 단어 하나만으로 대학교 강의가 하나 존재할 만큼 내용이 방대하니까 최대한 줄여서 설명하겠습니다.
간단하게 설명할 글인데, 그림까지 넣고 구조체 코드까지 짜면서 설명할 순 없습니다. 자세한 원리와 동작을 알고 싶으시다면 시중에서 책을 구매해서 보세요.
그리고 앞으로 간단하게 설명하는 자료구조들은 반드시 한번씩은 스스로 검색, 입력, 출력, 삭제, 삽입 코드를 스스로 작성을 해봐야 합니다. 좋은 회사 들어가려면, 이런 것들이 책과 PC없이 '손으로' 가능해야 입사가 가능합니다.
이것이 안된다면 최소한 특징이라도 알고 있어야 합니다. 언제 무슨 자료구조가 쓰인다. 이는 '자료를 다루는 직업'인 프로그래머라면 반드시 알아야할 지식입니다.
-큐
큐는 쉽게 설명하자면 1렬로 길게 선 줄을 의미합니다.
놀이기구를 탈때, 사람이 많으면 우리는 줄을 섭니다. 처음 선 사람이 처음 들어가고, 마지막에 선 사람은 마지막에 들어갑니다.
선입선출(FIFO)라고 처음 들어간 노드가 처음 나옵니다.
애석하지만, 코코스로 프로그래밍을 하면서 큐를 다룰 일은 거의 없을 겁니다. 왜냐면 지원하는 동작이 넣는것과 빼는것 밖에 없이 때문입니다.
실제적으로 사용될때는 서버 입장 대기, 채팅에 사용됩니다. 주로 서버 프로그래머가 자주 다루는 자료구조이기도 합니다.
파생형으로 디큐같은 것이 있습니다.
-스택
스택은 쉽게 설명하자면 프링글스 통에 있는 감자칩과 같습니다.
프링글스 통 바닥에 있는걸 먹으려면, 앞에있는 갑자칩들을 전부 꺼내야 합니다. 그래서 위에서 부터 먹습니다.
선입후출(FILO) 먼저 들어간것이 가장 나중에 나옵니다.
스택 큐와 마찬가지고 직접적으로 사용할 일은 드물지만, 함수의 호출은 스택으로 이루어 집니다.
디버깅하는데 '호출 스택'이 바로 이것입니다.
A라는 함수에서 B 함수를 호출했다고 합시다.
A라는 함수는 B라는 함수가 끝나기 전까지는 동작이 끝날 수 없습니다.
다시말해 스택에는, A가 먼저 들어갔고 그 후에 B가 들어갔습니다. A를 꺼내려면(A의 동작이 끝나려면) B부터 꺼내야(B의 동작이 끝나야) 합니다.
실무에서 에러가 터졌습니다. 당신은 선배에가 갔습니다. '선배님 에러가 났습니다.' 선배가 말합니다. '호출 스택 찾아봤어?' 당신이 답변합니다. '스택이 뭐에요?' 이러면 인사평가에 심각한 악영향을 끼친다 이말입니다.
-배열
배열은 우리가 생각하는 그 배열이 맞습니다.
int nArrData[10] = {0}; //int의 배열을 10개 선언하고 모두 0으로 초기화 했습니다.
더 정확히 말하자면, int 라는 구조의 메모리를 10개 잡아서 이 첫 주소를 nArrData 에 담았다 라는 말입니다.
첫 주소는 nArrData 이기도하고, &nArrData[0] (배열 첫번째 인덱스의 주소)일수도 있습니다.
(더 이야기를 깊게 하자면, int랑 float이랑 똑같이 32비트 컴파일러 환경에서는 4byte인데 int는 정수고 float은 실수입니다.
int nData = 0;
float fData = 0.0f;
nData = fData; //에러
int도 4바이트고 float도 4바이트인데 이 차이점이 뭘까요? 메모리를 사용하는 방식에 대한 차이입니다. 그러니까 int nArrData[10];은, int 형으로 사용할수 있는 메모리를 10개 잡았다는 말입니다. 순수하게 바이트 단위로 메모리를 잡고 싶으시면 void* 쓰시면됩니다.)
배열은 쉽게 사용할 수 있는 자료구조이고 모든 자료구조 중에서 찾는 속도가 가장 빠릅니다.
믿기 어렵겠지만 배열은 모든 자료구조중에 가장 빠릅니다. 왜냐면 메모리에 있는 주소에 직접적으로 접근할 수 있기 때문입니다.
int nArrData[100000] = {0}; //int형을 십만게 잡았습니다.
printf("%d", nArrData[999]); 999번 인덱스의 값을 출력합니다.
완전 간단합니다. 그리고 완전 빠릅니다. 숫자로 정확인 인덱스를 꺼내는 방식은 데이터를 찾을 때 가장 빠른 방식입니다. 그러나 배열은 단점이 있습니다. 한번 잡은 메모리 최대 인덱스는 무슨수를 써도 늘릴 수도 줄일 수도 없다는 것입니다.
그렇기 때문에 우린 '가변적인' 배열이 필요합니다. 그리고 그렇게 해서 나온 것이 std::vector입니다. 벡터에 대한 이야기는 나중에 합시다.
장점 : 가장 빠르다.
단점 : 한번 잡은 메모리 공간은 늘릴 수도 줄일 수도 없다.
사용예 : 정해진 크기의 데이터를 유일한 숫자(id)를 이용하여 찾을 수 있을 때
결론적으로, 분명히 빠른데 가변할 방법이 없으니 가변이 가능한 std::vector를 사용한다. - 물론 벡터가 가변이라고 중구난방으로 가변하진 않습니다.
-리스트
리스트는 쉽게 이해하자면 꼬리에 꼬리를 문 기차, 지하철을 생각하면 됩니다.
기차는 열차의 칸과 칸이 연결되어서 움직입니다.
노드의 구성은, 요약하면 대충 이런식 입니다.
struct S_LISTNODE
{
int nData //리스트가 가지고 있는 데이터입니다. 실무에서는 절대로 이렇게 int가 쓰일 일이 없습니다. 대신 다른 데이터 구조체가 사용될 것입니다.
S_LISTNODE * pNextNode; //리스트 노드는 '다음 리스트 노드의 주소값'을 가집니다.
}
예를들어
S_LISTNODE* pNode1 = new S_LISTNODE; //노드 1번을 생성
S_LISTNODE* pNode2 = new S_LISTNODE; //노드 2번을 생성
pNode1->pNextNode = pNode2; //노드 1번의 다음 노드는 노드 2번입니다.
우리는 노드 1번의 주소만 알아도, 노드 2번을 알 수 있습니다.
그리고 리스트는 배열과 달리 길이가 가변적입니다. 자료의 길이를 늘리고 싶으면, 계속해서 노드를 만들어서 기존에 만든 리스트의 노드 끝에 이를 붙이면 됩니다. 마지막 노드는 어떻게 알까요?
//pNode1에는 8000개의 리스트 노드가 붙어있다고 합시다.
S_LISTNODE *pTempNextNode = nullptr; //리스트 노드의 마지막을 담을 임시 포인터
pTempNextNode = pNode1; //임시 포인터에 리스트 노드의 첫번째 주소를 넣습니다.
while(pTempNextNode->pNextNode != nullptr) //임시 포인터의 다음 노드가 존재하나요?
{
pTempNextNode = pTempNextNode->pNextNode; //임시 포인터에 임시포인터의 다음 노드를 넣습니다.
}
pTempNextNode // 여기에 나온 노드는 마지막 노드입니다.
리스트는 배열과 달리 가변적이라는 장점이 있습니다.
리스트는 주로 '모든걸 다 사용해야 할때' 사용합니다.
캐릭터가 밟고 서있는 지형의 경우, 일부러 찾아야 하는 일이 없다면 무조건 화면에 그립니다.
총알의 경우, 무조건 화면에 다 보여줘야 한다면, 총알은 리스트로 담을 수 있습니다.
그러나 리스트는 찾는 것에 약합니다.
만약 1000개의 노드가 연결된 리스트에서 899번째 노드의 값을 찾으려면 어떻게 해야 할까요?
우리가 아는 것은 노드의 첫번째 주소밖에 없습니다.
네! 처음부터 899번째 까지 계속 노드를 하나하나 옮겨다니면서 nCount를 비교해서 찾습니다.
리스트에 index를 넣어두면 안되냐구요? 비효율적입니다. 값을 비교하는건 더 오래 걸립니다. 리스트의 노드를 옮겨간 뒤에, 해당 노드에 있는 데이터를 비교하고 또 노드를 옮겨서 데이터를 비교하고... 엄청난 시간이 걸립니다.
애석하지만, 리스트는 사실 잘 사용되진 않습니다. 웹프로그래밍에서 DB서버에서 받은 데이터를 웹페이지에 출력할 때 사용하긴 하는데 게임프로그래밍에서 사용하기엔 조금 무리가 있습니다. 왜냐면 우린 찾아야 하는일이 훨신 더 많기 때문입니다.
실무에서는 잘 사용되지 않지만,(정확히는 활용도를 찾기가 어렵지만) 입사시험에선 정말 잘 나옵니다. 리스트 병합, 검색, 삽입 관련 손코딩은 기술시험의 당골문제입니다.
-트리
트리는 내컴퓨터의 폴더를 떠올리시면 좋습니다. 혹은 프로젝트 네비게이션(익스플로러)에 있는 파일 구조가 트리입니다.
C드라이버를 열면 프로그램파일즈와 윈도우 폴더, 유더 폴더가 있고 유저폴더 밑에는 바탕화면과 다운로드가 있고 이런식입니다.
트리는 역시도 여러가지 구조가 있습니다. 완전 이진트리, 이진트리, 그냥 트리 더 나아가면 AVL 트리 Red black 트리 등등.. 그러나 이 모든 트리를 다 알 필요는 없습니다. 아니 하나라도 더 아시고 이를 혼자서 구현할수 있는 실력이 있으시면, 연봉이 바뀌실 겁니다.
이들은 종류는 다르지만 결국 '최대한 빨리 찾기 위해' 각자 다른 검색 방법을 사용하는데 그 차이가 있습니다. 더 정확히 말하자면, 트리에 자식이 추가 되면 이를 어떻게 '잘 섞는가'에 따라서 종류가 다릅니다. 트리는 검색에 있어서 자료구조들 중에 평균적으로 빠릅니다.
트리는 뭐가 되는 최초 root라고 부르는 부모로 부터 내려옵니다. 부모는 자식이 있고, 자식은 부모가 있는구조 입니다.
리스트가 '다음 노드 주소'를 하나만 가질 수 있다면 트리는 여러개를 가집니다. 뭐 대부분의 경우, 찾는 속도 때문에 이진트리 구조로 가기 때문에
struct S_BNODE
{
int nData;
S_BNODE* pLeftChildNode;
S_BNODE* pRightChildNode;
}
트리는 노드로 구성되기 때문에 배열과 달리 그 메모리 길이가 가변적입니다. 얼마든지 줄이고 늘릴 수 있습니다.
또한 찾는 속도는 당연 배열보다는 느리겠지만 '평균적으로' 빠릅니다. 만약 수백만개의 데이터중, ID가(키값이) "KEY_SCHEDULE_UPDATE" 라는 녀석을 찾아야 한다면, 이건 트리형태의 자료구조만 가능한 찾는 방법입니다.
배열은 어떻게 합니까? 숫자로만 이루어진 index만 사용할 수 있는 배열은 문자 자체를 찾는데 이용 할 수 없습니다.
예를들어
struct S_NODE
{
std::string strKey;
int nData;
}
S_NODE * pArrNode[10000]; //S_NODE 포인터를 만개 선언했습니다.
for문으로 index를 하나하나 돌아가며 S_NODE의 key라는 데이터의 값을 일일이 하나하나 찾을 까요? 이건 리스트나 똑같습니다.
그러나 트리는 숫자가 아닌 문자(키값)로 '찾는' 것이 가능합니다.
이 키값은 트리 검색 특성상 반드시 '유일값' 이어야 합니다. 배열의 인덱스를 중복해서 다른 값을 저장할 수 없듯, 트리에서도 트리에 달려있는 특정 노드를 찾는 근거인 '키 값'은 반드시 유일 값이어야 합니다.
장점 : 메모리의 길이가 가변적, 평균적으로 찾는 속도가 빠르다, 설계, 관리하기 편하다. 문자로 데이터를 찾을 수 있다.
단점 : 그렇다고 탐색이 가장 빠른 것은 아니다. 키값 관리가 확실해야 한다.(유일 값이어야 한다)
트리는 배열만큼 다방면으로 사용되는 자료구조입니다. 가장 대표적인 예는 인벤토리 입니다. 빨간대형 포션이 인벤토리에 있는지 없는지 알려면 어떻게 해야 할까요? 해당 아이템의 아이디로 조회해서 이 아이디를 가진 아이템이 내 인벤토리에 있는지 없는지 검색합니다.
주민등록 번호로 회원을 찾을 때는? 베열은 주민등록 번호 알려면 회원을 0부터 끝까지 다 돌면서 데이터를 꺼내와서 그 값을 비교해야 하지만, 맵은 드민등록번호 자체만으로 아이디를 꺼내기 용이합니다.
4.STL컨테이너
STL 문법과 STL이 가진 모든 내용들에 대해 설명을 해야한다면, 자료구조보다 더 많은 이야기를 다뤄야 합니다. 그러니까 이것도 책 한권은 나오는 분량이지만 실무에서 사용되는 것 위주로 최대한 요약해서 설명합니다.
-std::vector
벡터는 한마디로 배열입니다. 배열은 메모리의 길이가 고정되어 있지만, 벡터는 가변적입니다.
그렇다면, 배열은 가장 빠른 컨테이너니까 벡터가 메모리 가변까지 된다면, id만 잘 관리하면 최강의 컨테이너겠네요? 맞습니다.
벡터는 실무에서 널리 사용되는 STL 컨테이너 이기도 하며, 코코스에서도 쉽게 찾아 볼 수 있는 STL 컨테이너 입니다. 당장에 멀티터치 함수인 touches 시리즈만 보세요. 터치된 값이 무엇으로 넘어옵니까? vector입니다.
물론 벡터는 가변적이지만, 사실 조금 허점이 있습니다. 가변적으로 사용하면, 오히려 속도가 느려진다는 겁니다.
벡터는 배열이라면서, 배열이 찾는 속도가 가장 빠른데, 가변적이라 배열의 한계를 극복한 컨테이너인데 이ㅏ것으로 속도가 느려진다니, 보는 사람이 답답 할 수 있겠지만 이유는 다음과 같습니다.
벡터는 주로 push_back으로 그 크기를 늘립니다.
예를들어서, int형을 5개 선언하고 0번부터 4번 인덱스에 전부 10이라는 값을 입력한다면, 다음과 같습니다.
int nArrData[5] = {0};
for(int i = 0; i < 5; ++i)
{
nArrData[i] = 10;
}
벡터는 다음과 같습니다.
std::vector<int> vec_nData; //벡터를 생성합니다.
for(int i = 0; i < 5; ++i)
{
vec_nData.push_back(10); //벡터에 10을 차곡차곡 밀어넣습니다.
}
출력할때 - 실제로는 벡터꺼낼때 이터레이터 안사용합니다.. 엄청나게 느리기 때문에
실무에서 C++11을 사용하는데 아직도 벡터에 이터레이터 사용하면 조금 문제가 있다고 봅니다.. 아니 애초에 배열연산자를 사용함. 혹은 auto를 혼합한 범위기반 for문,
std::vector<int>::iterator itor; //int라는 자료형을 사용하는 벡터의 이터레이터를 선언
for(itor = vec_nData.begin(); itor != vec_nData.end(); itor++) //이터레이터를 돌면서
{
printf("%d\n", *itor);
}
벡터는 배열이라고 했는데 사용법이 굉장히 이상합니다.
벡터를 사용하는데 push_back을 사용하는 것은 사실상 자살행위와 같습니다. push_back은 가변적으로 배열을 하나하나 늘릴 수 있는 마법의 주문이기도 하지만, 이것의 내부 동작은 다음과 같습니다.
벡터가 생성되고, 여기에 push_back을 하면, 벡터는 임시 메모리를 내부적으로 잡습니다.
그리고 이 임시메모리를 초과해서 계속해서 push_back을 하면, 기존의 메모리보다 조금 더 큰 메모리를 별도로 새로 잡고, 기존에 있던 메모리를 새로 잡은 메모리에 통채로 복사하는 굉장한 연산을 내부적으로 수행합니다. <- 이 복사하는 과정에서 엄청난 시스템 비용을 요구합니다.
벡터 관련해서 메모리 관련 오류, 성능저하의 대부분이 push_back에서 발생한다는 점은 알아둬야 합니다.
그렇다면 벡터는 어떻게 사용해야 할까요? 미리 메모리를 잡는 수 밖에 없습니다.
미리 10개를 잡고
vec_nData.reserve(10);
vec_nData.resize(10);
vec_nData[0] = 10; //배열 연산자로 값을 넣습니다.
그리고 stl 컨테이너의 값을 꺼낼때 사용하는 '이터레이터'는 벡터에선 사용하지 않습니다.
벡터는 배열연산자(대괄호 연산자)를 지원합니다. 물론 배열 인덱스를 넘어서 값을 호출한다면 프로그램이 죽는 것은 맞습니다. 이는 반드시 예외처리가 필요합니다.
단적으로 성능 테스트를 해봐도, 벡터에 만번, 십만번씩 push_back을 하는 것과, 미리 메모리를 잡고 배열연산자로 만번, 십만법 데이터를 입력하는 것은 엄청난 속도차이가 납니다. 이건 무시할 수 없는 속도 차이 입니다.
검색 속도는 배열연산자 >>>>>>>>>>>>>>>>>>>>>>>>>>범위기반 for문>>>>>>>>>>>>>이터레이터 순입니다.
입력 속도는 배열연산자 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> push_back 순 입니다.
뭐 서버통신같이 벡터의 정확한 길이를 알 수 없는 경우는 어쩔 수 없이 push_back을 사용하겠지만, 반드시 정확한 최대 고정값을 알 수 있다면, 벡터는 배열처럼 사용하면됩니다. 미리 최대 메모리를 잡고(가변하고) 대괄호 연산자로 배열처럼 사용한다가 벡터의 사용법입니다.
-std::list
사실 리스트 자료 구조 자체를 사용할 일이 없어 std::list는 자료구조 리스트와 동일 합니다.
std::list에서는 index의 검색이나 해당 위치에 노드 삽입 등 여러가지 기능을 지원하지만 이런 것을 사용할 일이 생긴다면 std::list는 사용할 필요가 떨어집니다.
-std::map
std::map은 트리와 같습니다. map은 first와 second로 나뉘는데, first는 앞서 말한 키값(유일값), second는 저장할 자료가 들어가게 됩니다.
std::map 역시 벡터와 마찬가지로 대괄호 연산자를 지원하기 때문에 mapData["fncFoo"]; 같은 배열에 문자열이 들어가는 코드들도 심심찮게 볼 수 있게 됩니다. std::map은 유용하게 사용되며 map과 관련된 인터페이스를 아는게 좋습니다. map에서 사용하는 대괄호 연산자는 잘못 사용하면 위험한 결과를 초래합니다.
그리고 삭제시에 이터레이터 주소 변화에 대해서 잘 숙지해야 검색, 입력, 삭제가 원활하게 가능하니까 반드시 std::map은 관련 인터페이스를 한번씩은 다 사용는걸 추천합니다. 입력 역시 방법이 다양합니다. insert로 넣는 방법, pair로 넣는 방법, 대괄호 연산자로 넣는 방법 등...
map역시도 벡터 이상의 인터페이스 사용법을 설명해야 하지만 단순하게 맵은 트리다 라는 것만 알아도 접근하기 쉬우실 겁니다.
5.코코스엔진의 엔진동작 방식
코코스 엔진은 OpenGL기반입니다. 다시말해서 우리는 생각없이 addChild를 하고 addChild한 스프라이트가 화면에 출력되니까 단순하게 'addChild는 그림을 그리는데 사용하는 함수이구나!' 라고 착각 할 수 있습니다.
그런데 이건 정말 위험하고 잘못된 생각입니다. addChild의 의미는 자식 노드를 부모에게 붙였다는 의미입니다.
this 는 무엇입니까? 흔히들 this는 java를 배울때나 C++을 배울 때나 '자기자신'이라고 합니다. 더 정확하게 설명하자면, 현재 클래스의 주소입니다.
C_CLASS 라는 이름의 클래스에
class C_CLASS
{
printMyAdress(); //나의 주소를 출력하는 함수를 선언 했습니다.
}
C_CLASS::printMyAdress() //C_CLASS에는 printMyAdress라는 함수가 있고, 이를 구현합니다.
{
printf("my address : %p \n", this); //나(C_CLASS)의 주소값을 출력합니다.
}
main()
{
C_CLASS* pClassData = new C_CLASS; //C_CLASS의 메모리를 동적할당으로 잡았습니다.
cData.printMyAdress(); //this 의 주소를 출력합니다.
printf("pClassData's address : %p", pClassData); //동적할당된 포인터의 주소를 출력합니다.
}
결과 : - 둘다 동일하다.
my address : 0x83757638fe
pClassData's address : 0x83757638fe
이야기가 굉장히 다른곳으로 빠졌는데 그래서 결국 this->addChild(스프라이트)의 의미는 무엇입니까?
나 자신(부모)에게 자식(스프라이트) 를 붙인다 입니다.
-사실 this는 생략이 가능합니다. this->addChild()는 addChild()와 같습니다. 그냥 해당 클래스가 가지고있는 addChild()라는 함수를 호출했다 라는 의미이기 때문입니다.
-이것이 cocos2D(x가 아닌)에서 오브젝트C의 self가 형식상으로 내려온건지.. 왜 예제에 this->가 들어가는지는 솔직히 잘 모르겠습니다.
코코스2D-X는 무엇을 합니까? OpenGL을 기반으로, 그냥 내부적으로 씬에 붙은 수많은 자식들을 죽어라고 갱신하며 새로 그립니다.
auto pSprCircle = Sprite::create("Circle.png"); //스프라이트 를 하나 생성
auto pNode = Node::create(); //일반 노드를 하나 생성
this->addChild(pNode); //부모에게 일반 노드를 붙인다.
pNode->addChild(pSprCircle); // 일반 노드에 스프라이트'노드'를 자식으로 붙인다.
pNode=>setPosition(Vec2(100.0f, 100.0f)); //일반 노드를 100,100 위치로 지정한다.
Vec2 Pos = pSprCircle->getPosition(); //스프라이트 노드의 위치를 Pos라는 변수에 얻는다.
log("Pos.x = %f, Pos.y = %f", Pos.x, Pos.y); // 스프라이트의 위치를 출력한다.
분명히 pSprCircle은 화면의 100, 100 위치에 있는데,
로그의 결과는?
결과 :
Pos.x = 0.0000, Pos.y = 0.00000
왜 그럴까?
스프라이트의 '부모 노드'가 100, 100 위치에 있으니까 당연히 스프라이트는 화면은 100, 100 위치로 간것이 맞고,
스프라이트는 '부모 노드 기준'으로 0,0 위치에 있으니까 스프라이트의 위치는 0,0이 맞습니다.
코코스는 다시 설명하지만, 트리구조 입니다. 우리가 흔하게 사용하는 스프라이트 조차도 부모 클래스는 Node 입니다. (여기서 부모는 트리구조에서의 부모가 아닙니다. 클래스 상속에서의 부모) 내부적으로 메모리 찾기 로직이 어떻게 되어있는지 사용자는 알 수 없지만, 사용자는 트리로 씬을 구성 할 수 있습니다.
노드로 파생되는 클래스에는
Inherited by __NodeRGBA, AtlasNode, AttachNode, BaseLight, Camera, ClippingNode, ClippingRectangleNode, DrawNode, SpritePolygon, TMXLayer, TMXTiledMap, TableViewCell, Layer, MenuItem, MotionStreak, NodeGrid, ParallaxNode, ParticleBatchNode, ParticleSystem, ProgressTimer, ProtectedNode, RenderTexture, Scene, Skybox, Sprite, Sprite3D, SpriteBatchNode, Terrain, TMXTiledMap, Scale9Sprite, and GLNode.
이런 종류가 있습니다. 이러한 노드들이 서로서로 부모가 되기도 하고 자식이 되는 것들을 코코스2D-X는 열심히 그릴 뿐입니다.
그러니까 부모를 둘로 만들거나 해선 안됩니다. 일반적으로 사용하는 트리는 부모가 하나입니다. 다차원 검색트리 같이 부모가 여럿인 거창한 물건이 아닙니다. (애초에 부모를 두개 두려고 하면 에러가 터집니다.)
-이런 트리는 아니라는 겁니다. : http://people.engr.ncsu.edu/efg/506/s03/lectures/annotation/lec26/index.html
그러니까 우린 addChild의 의미를 다시 한번 고찰할 필요가 있습니다. 단순히 addChild는 함수를 호출하는 주체(부모)에게 자식을 붙인다는 의미 입니다.
this->addChild(노드) 나에게 노드를 붙였다. 일 뿐입니다. 노드를 그린다의 의미가 전혀 아닙니다. 단순히 엔진은 자동적으로 무한히 노드들을 그리고 있으니까, 붙인다는 행위 자체가 '그린다' 라는 의미로 착각하기 쉽습니다.
6.코코스엔진과 노드, 장점과 단점
트리구조의 장점은 평균적인 검색 속도 이외에도 관리나 설계가 편합니다.
마치 내컴퓨터 안에서 파일들을 정리할 때 폴더를 분할하여 만들듯, 이러한 정리가 가능합니다.
예를들어 캐릭터 '노드'가 있다고 합시다. 캐릭터에는 캐릭터의 베이스 그림이 있고, 모자를 쓰고 있고, 무기를 장착하고 있고 하단에는 체력게이지가, 상단에는 아이디와 레벨이 표시됩니다.
나는 캐릭터를 이동하고 싶습니다.
여기에서 트리 구조를 아느냐 모르느냐로 노드 설계와 이동 구현이 확연히 차이 납니다.
1.트리 구조를 아는 사람
-캐릭터의 메인 노드를 만든다.
-이 메인 노드에 캐릭터의 베이스 그림을 붙인다.(addChild한다)
-캐릭터의 베이스 그림에 모자, 무기, 아이디, 레벨을 붙인다.(addChild한다)
-캐릭터의 메인 노드를 runAction(MoveTo::create())로 이동시킨다.
(모든 노드들이 캐릭터 메인 노드에 붙어있으니까, 이 부모노드 하나만 움직이면 전체가 다 움직임)
2.트리 구조를 모르는 사람
-캐릭터 베이스 그림 스프라이트를 만들고 this->addchild한다 (addChild가 그림을 그리는 기능이었지!)
-모자 스프라이트를 만들고 this->addchild한다 (addChild가 그림을 그리는 기능이었지!)
-무기 스프라이트를 만들고 this->addchild한다 (addChild가 그림을 그리는 기능이었지!)
-이름 Label을 만들고 this->addchild한다 (addChild가 그림을 그리는 기능이었지!)
-레벨 Label을 만들고 this->addchild한다 (addChild가 그림을 그리는 기능이었지!)
-캐릭터 베이스 그림 스프라이트를 runAction(MoveTo::create()) 한다! (그림 하나를 그렸으니까 이 그림을 이동시켜야 겠지!)
-모자 스프라이트를 runAction(MoveTo::create()) 한다! (그림 하나를 그렸으니까 이 그림을 이동시켜야 겠지!)
-무기 스프라이트를 runAction(MoveTo::create()) 한다! (그림 하나를 그렸으니까 이 그림을 이동시켜야 겠지!)
-이름 Label을 runAction(MoveTo::create()) 한다! (그림 하나를 그렸으니까 이 그림을 이동시켜야 겠지!)
-레벨 Label을 runAction(MoveTo::create()) 한다! (그림 하나를 그렸으니까 이 그림을 이동시켜야 겠지!)
그러나 트리의 노드 구조 설계는 상당히 편하고 좋은 기능 같지만, zOrder 설정 앞에서는 모두 무용지물이 됩니다.
씬 하나에 수십 수백개의 그림들이 붙게 되는데, 이들의 높낮이는 어떻게 설정할 것입니까?
그리고 기획상, 이 그림들의 높낮이가 변경되어야 하는 일이 많다면, 이것들의 관리를 어떻게 할겁니까?
예를들어 부모노드에 A, B 라는 노드가 붙고 B라는 노드에 C가 붙습니다.
A의 zOrder가 10이고 B의 zOrder가 5이고 C의 zOrder는 10000입니다.
A와 C의 그림이 서로 겹치면 누가 더 위에 보일까요? zOrder가 10000인 C일까요? 애석하게도 A가 가장 위에 보입니다.
그러니까 이 노드 단위 설계도 결국 zOrder 앞에선 굉장히 의미 없는 작업이 될 수 있습니다.
그냥 다 동일한 부모노드에 addChild하고 zOrder를 enum으로 확실하게 관리하는 것이 장기적으로는 훨신더 현명한 판단입니다.
물론, 노드 단위 설계가 필요한 부분이 있고 순수 zOrder의 정확한 설계로만 해결이 가능한 부분이 있어 이를 잘 파악하는 것이 코코스 엔진을 사용할 때 중요하다고 볼 수 있겠습니다.
6.읽어봐도 모르겠는데?
왜냐면 글쓴이의 실력이나 내용이 형편없기 때문입니다. 정확한 것은 책을 보셔야 합니다. 사실 파트 하나당 책이 수십권씩은 시중에 나와있습니다. 그 많은 지식들을 글 하나로 알 수 있진 않습니다. (사실은 글쓴이도 잘 몰라서)
자료구조, STL, 코코스엔진 관련 서적을 각 한권씩 보시고 한번씩 코드를 다 사용해보면 감이 오실 겁니다.
자료구조는 물론이고 관련한 탐색 , 정렬 알고리즘만 정확하게 익히고 책이나 컴퓨터 없이 손으로 코딩할 수 있어도 왠만한 회사에는 다 들어가실 수 있을 겁니다.
7..마치며
자료구조는 프로그래머에게 뗄래야 뗄 수 없는 영역입니다. 실무에서 일을 하든, 집에서 혼자 게임을 제작하든, 더 빠르고 적은 연산을 위해서는 끊임 없이 고민하고 선택의 길에 놓이게 됩니다. 이것이 숫자로 찾을 수 있는 건가? 문자로 밖에 못찾는 건가? 유일값인가? 연속되서 계속 호출하는가? 찾을 일이 없는가? 너무나 다양한 데이터들을 접할 기회가 계속해서 생깁니다.
또한 자료구조와 관련된 인터페이스의 설계에 대해 정확하게 내용을 알고 있어야 함수의 쓰임세를 알아보기 용이 합니다. 남이 만든 함수를 뜯어보고 있는데, isRecursive 라는 bool 값과 함께 함수가 자기 자신을 호출하는 재귀 함수 가 등장했다고 합시다. 재귀함수가 사용되는 경우는 두가지가 있습니다. 트리구조에서 자식들을 모두 찾을 때와 스캘레톤 애니메이션(이것도 결국 트리구조입니다) 구동시에 사용합니다. 결국 특정 노드의 자식들을 다 훑어가며 무언가 동작을 하는 함수라는 겁니다. 지식이 없으면 이런 기초적인 유추도 불가능합니다.
아무튼 상당히 두서없이 내용도 없는 글을 올렸는데 뭐 도움이 되셨으면 좋겠고 제가 틀린 부분도 지적 받아서 제 지식을 고쳤으면 합니다.
내용이 틀린 부분은 반드시 말씀해 주세요..