[잡담]EA는 이런것도 하는구나..

http://www.open-std...pers/2007/n2271.html
STL을 개조해서 EASTL이란 것을 만든다는 말을 들었다

출처는 gpgstudy에서이고...

이런것도 하는구만...

왠지 EA라는 회사의 이미지는 안좋은 것이 좀 있었는데...

[Project]AI쪽 구상

인공지능 쪽은 크게 길찾기와 행동설정으로 구분했다
여기서 말하려고 하는 것은 우선 길찾기이다.

길찾기는 Ai Game Programming Wisdom을 참고해서 a*를 기본으로 해서 구현할 생각이다.
길찾기의 특성상 맵그래프와 관계가 생길 것이라고 예상하고 있다.
현재의 구상은 그래프클래스와 휴리스틱함수를 인자로 받아서
그래프의 노드아이디 리스트를 반환하는 형식을 취할 생각이다.
그래야 나중에 최적화를 위해 맵의 노드들을 자동으로 병합한다든지하는 일이 생겨도
길찾기 클래스에서는 변화가 적을 것이라고 생각해서이다.

여기에서는 몇가지 제약사항이 있는데,
1. 노드는 아이디로 바로 접근가능해야하고
2. 노드간의 연결은 맵 그래프에서 함수를 통해 얻어내고
3. 노드간의 이동시의 이동소요시간(이동시 사용되는 포인트)도
맵 그래프에서 함수를 통해 얻어낸다.

현재 생각하고 구현중인 것은 이것이다.
추가적으로 구현이 이루어진다면 계속해서 글을 추가할 예정이다
(어딘가 써놔야지 자꾸 잊어버려서..)

[잡담]RTS를 만들기로 했다!

심심해서는 아니고, 예전회사에서 퇴사하고나서
내 능력을 키우려면 뭔가 만들어보는 것이 가장 나을 것같다는 생각도 있고,
포트폴리오용으로도 사용할 수 있을 것같다는 생각도 있어서다.

지금은 기획은 넘어가고 대략적인 설계가 끝나서 구현에 들어간 상태다.
아무래도 예전에 만들었던 턴제 전략 게임(마이너버전 택틱스같은 하지만 허접한)과는
다른 수준이 나와야할텐데..

[잡담]음.... 이거 카테고리로 나누는건 없나..

아무래도 처음 써봐서 그런건지 카테고리를 설정을 못하겠네..

[기초]분할 정복

음.. 재귀와 함께 알고리즘에서 자주 보이는 분할 정복에 대해서

대충 써보면..

기본적인 컨셉은 큰 하나의 것을 작은 여러개로 분리해서 작은 것들을 전부 끝내고 그것을 합해서 하나로 만드는 것을 말하는 것이다.

이렇게 써 놓으면 뭐 씨뷁하는 생각밖에 들지 않을테고, 알고리즘 책에서도 자주 예를 드는 병합정렬을 예로 들어보면,(여기서는 간단하게 보여주기만 할 것이고, 알고리즘 폴더에 정확한 것을 써 놓을 것이다)

XXXXXXXXXXX 라는 배열을 정렬한다고 했을 때

1.XXXXX 2.XXXXXX 둘로 나누고

1.XX 2.XXX 1.XXX 2.XXX 둘로 나눈 것을 다시 둘로 나누고

1.X 2.X 1.X 2.XX 1.X 2.XX 1.X 2.XX 다시 둘로 나눠서

X X X X X X X X X X X 이렇게 각자 하나가 될 때까지 나누면 하나

의 원소는 정렬된 것이므로 이것들을 합하면서 정렬시키는 것이다.

그래서 저렇게 나눠진 것을 합해서 정렬된 배열이 나타나는데,

이런 식으로 큰 부분을 작게 나누고 작게 나눠진 부분에서 계산이나 실행을 끝내고 합하는 것을 분할 정복이라고 한다.

뭐 잘 이해가 안가는 설명이었는지도 모르겠지만, 나의 설명의 한계는 이정도이므로 여기서 끝낸다..

[기초]재귀

재귀는 말 그대로 자기 자신을 호출하는 것이다.

재귀를 설명할 때의 가장 간단한 프로그램은 역시 피보나치 수열이다.

피보나치 수열은 자기앞의 두 수의 합이 자신의 값이 되는 것이다. 그리고 자기 앞이 존재하지 않는 1, 2번째의 경우 1로 설정된다. 따라서 수열의 모양은 아래와 같다

1 1 2 3 5 8 13 21 34 55.....

이것을 함수로 나타낸다면

int fibo(int index)

{

if(index <= 0)

return 0;

if(index == 1 || index == 2)

return 1;

return fibo(index - 1) + fibo(index - 2);

}

같은 형식이 될 것이다.

재귀의 경우 전부 루프로 나타낼 수 있다고 한다.

c++에서 재귀함수의 문제점이라면

1. 함수이므로 스택이 쌓이면서 메모리 사용양이 증가한다.

2. 위와같은 이유로 느려진다.

[알고리즘]힙정렬

힙정렬이다.. 우선 소스를 보자.

// 깊이를 구하기위해서 값이 1이하가 될 때까지 쉬프트 연산을 해

// 주고
// 쉬프트 연산의 회수를 반환
int Lg2(int iVal)
{
int temp = 0;
while(iVal > 1)
{
++temp;
iVal >>= 1;
}
return temp;
}

// root인덱스가 추가되었을 때 힙을 재구성해주는 함수
// 좌우 자식중 큰 값을 부모와 비교하여 부모가 크다면 그대로 두

// 고
// 자식이 크다면 부모와 바꿔준다.
// 만약 부모와 자식을 바꾸었다면, 내려간 부모의 인덱스를 이용해

// 다시 자신을 호출한다.
// 여기서 root는 최대 iVec.size() >> 1 즉 배열 크기의 절반이므

// 로
// 최소한 왼쪽 자식은 존재한다.
void LocalHeapify(vector & iVec, int root)
{
int max; // 두 자식중 큰 값의 인덱스를 저장할 변수
int leftChild = root * 2; // 왼쪽 자식
int rightChild = root * 2 + 1; // 오른족 자식
// 두 자식중 큰값의 인덱스를 max에 저장
if(rightChild != iVec.size()) // 오른쪽 자식이 배열의 크기와 같다

//면
// 오른쪽 자식은 배열의 인덱스를 벗어난 것이다.
{
iVec[leftChild] > iVec[rightChild] ? max = leftChild : max = rightChild;
}else
{
max = leftChild;
}

// 만약 자식이 부모보다 크다면 두 값을 바꿔주고
// 내려간 부모의 인덱스를 이용해 재귀적으로 호출
if(iVec[max] > iVec[root])
{
SwapInt(iVec[max], iVec[root]);
if(max <= (iVec.size() >> 1))
{
LocalHeapify(iVec, max);
}
}
}

// 들어온 배열로 힙을 만들어주는 함수
// 마지막 원소의 인덱스를 2로 나눈 것부터 첫번째 원소까지
// LocalHeapify함수를 호출
// 마지막 원소의 인덱스를 2로 나눈 것이 자식을 가지는 가장 아래

// 의 가장 오른쪽 원소이기때문이다.
void MakeHeap(vector & iVec)
{
int temp = (iVec.size() - 1) >> 1;
for(int i = temp; i > 0; --i)
{
LocalHeapify(iVec, i);
}
}

// 만들어진 힙을 사용해서 힙정렬을 수행하는 함수
// 루트를 마지막원소와 바꿔주는 연산을 계속하면서
// 바꿔준 뒤에 힙을 재구성하는 AcceleratedHeapify함수를 호출
void HSort(vector & iVec)
{
int end = iVec.size() - 1;
while(end > 1)
{
SwapInt(iVec[1], iVec[end]);
AcceleratedHeapify(iVec, --end);
}
}

// 루트의 바뀐 값을 이용해 힙을 재구성 하는 함수
// 깊이의 절반만큼 자식들만 비교해서 내려간뒤
// 들어온 값이 자신의 부모보다 크다면 위로 올라가면서 제자릴 찾

//고 끝내고
// 들오온 값이 자신의 부보보다 작다면 다시 남은 깊이의 절반만큼

//내려간다.
// 만약 리프까지 내려오면 종료한다.
void AcceleratedHeapify(vector & iVec, int end)
{
// 값이 1개도 남지않았다면 종료
if(end < cur =" 1;">

//다.
int treeHeight = Lg2(end); // 정렬되지 않은 트리의 깊이를 구한

//다.
int currentHeight = 0; // 들어온 값이 내려온 깊이를 저장한다.
// 리프까지 내려갈때까지 루프를 돈다.
while(currentHeight <= treeHeight) { int move = (treeHeight - currentHeight) / 2 + 1; // 한번에 내려

//갈 깊이
for(int i = 0; i <>

//내려간다.
{
int leftChild = cur * 2;
int rightChild = cur * 2 + 1;
int max;
if(leftChild > end)
{
break;
}else if(rightChild > end)
{
max = leftChild;
}else if(iVec[leftChild] > iVec[rightChild])
{
max = leftChild;
}else
{
max = rightChild;
}
SwapInt(iVec[cur], iVec[max]);
cur = max;
}
int parent = cur / 2;
if(cur > 1 && iVec[cur] > iVec[parent]) // 만약 내려간 위치에

//서 부모가 자신보다 작다면
{
while(cur > 1 && iVec[cur] > iVec[parent]) // 정확한 위치를

//찾을 때까지 거슬러 올라간다.
{
SwapInt(iVec[cur], iVec[parent]);
cur = parent;
parent = cur / 2;
}
return; // 정확한 위치를 찾았으니 종료
}
currentHeight += move; // 내려간 위치의 깊이를 저장
}
}

주석때문에 보기가 엉망이다... 거기다 힙정렬의 변화형을 사용했기때문에 소스가 길어졌다.

이 소스도 아래의 퀵정렬과 마찬가지로 전에 만들었던 소스를 그냥 올린 것이다.