MSPark's Blog

class __declspec(dllexport)    MSVector
{
public:
    MSVector(VOID);                                                
    MSVector(CONST FLOAT x, CONST FLOAT y, CONST FLOAT z);        

public:
    inline     VOID    Set(CONST FLOAT x, CONST FLOAT y, CONST FLOAT z, CONST FLOAT w=1.0f);

    inline     CONST FLOAT    GetLength(VOID);                                                        
    inline     CONST FLOAT    GetSqrLength(VOID);                                                        

    inline     VOID            Nagative();  
    inline     VOID            Normalize();                                                            

    inline     CONST FLOAT    GetAngle(MSVector& v);                                                    

    inline     VOID            Difference(CONST MSVector& u, CONST MSVector& v);                        

    inline     CONST FLOAT    Dot(CONST MSVector& v);                                                    
    inline     VOID            Cross(CONST MSVector& u, CONST MSVector& v);                            

public:
    VOID            operator += (CONST MSVector& v);
    VOID            operator -= (CONST MSVector& v);
    VOID            operator *= (CONST FLOAT f);
    VOID            operator /= (FLOAT f);

    CONST FLOAT    operator *  (CONST MSVector& v) CONST;

    MSVector        operator *  (CONST FLOAT f) CONST;
    MSVector        operator *  (CONST MSMatrix& m) CONST;
    MSVector        operator +  (CONST MSVector& v) CONST;
    MSVector        operator -  (CONST MSVector& v) CONST;

public:
    FLOAT    x_;
    FLOAT    y_;
    FLOAT    z_;
    FLOAT    w_;
};

FLOAT f;

if (isAvailableSSE)
{
    FLOAT* p = &f;

    w_ = 0.0f;

    // MOVUPS    Move unaligned packed single-precision floating-point values
    // MULPS     Multiply packed single-precision floating-point values
    // SHUFPS    Suffle pakced single-precision floating-point values
    // SQURTSS   Compute square root of scalar single-precision floating-point values
    // ADDPS     Add packed single-precision floating-point values
    // MOVSS     Move scalar single-precision floating-point values

    __asm
    {
        mov        ecx,     p                                                            
        mov        esi,     this                                                        
        movups    xmm0,    [esi]                                                        
        mulps     xmm0,    xmm0                                                        
        movaps    xmm1,    xmm0                                                        
        shufps    xmm1,    xmm1,    4Eh                                                    
        addps     xmm0,    xmm1                                                        
        movaps    xmm1,    xmm0                                                        
        shufps    xmm1,    xmm1,    11h                                                    
        addps     xmm0,    xmm1                                                        
        sqrtss    xmm0,    xmm0                                                        
        movss     [ecx],   xmm0                                                        
    }

    w_ = 1.0f;
}
else
{
    f =  sqrtf(x_ * x_ + y_ * y_ + z_ * z_);
}

return f;

FLOAT f;                              // 결과를 저장할 변수

if (isAvailableSSE)
{
    FLOAT* p = &f;                    // 변수의 주소를 담는 포인터 변수

    w_ = 0.0f;                         // x, y, z값 계산할 때 영향을 끼치지 않기 위해 0.0f으로 설정

 

 

w_ = 0.0f;

// RSQRTPS    Compute reciprocals of square roots of packed single-precision floating-point values

__asm
{
    mov        esi,    this                                                                        
    movups    xmm0,    [esi]                                                                        
    movaps    xmm2,    xmm0                                                                        
    mulps     xmm0,    xmm0                                                                        
    movaps    xmm1,    xmm0                                                                        
    shufps    xmm1,    xmm1,    4Eh    
    addps     xmm0,    xmm1        
    movaps    xmm1,    xmm0        
    shufps    xmm1,    xmm1,    11h    
    addps     xmm0,    xmm1        

    rsqrtps   xmm0,    xmm0                                                                        
    mulps     xmm2,    xmm0                                                                        
    movups    [esi],   xmm2                                                                        
}

w_ = 1.0f;

__asm
{
    mov        esi,    u
    mov        edi,    v

    movups    xmm0,    [esi]
    movups    xmm1,    [edi]

    movaps    xmm2,    xmm0
    movaps    xmm3,    xmm1

    shufps    xmm0,    xmm0,    0xc9
    shufps    xmm1,    xmm1,    0xd2
    mulps     xmm0,    xmm1

    shufps    xmm2,    xmm2,    0xd2
    shufps    xmm3,    xmm3,    0xc9
    mulps     xmm2,    xmm3

    subps     xmm0,    xmm2

    mov        esi,    this
    movups    [esi],   xmm0
}

w_ = 1.0f;

유전 알고리즘이란 무엇인가?

유전 알고리즘은 생물의 진화를 본 따 만든 알고리즘이다.

우선 생물의 진화에 대해서 간단히 알아보자.

1. 생물의 진화

1) 진화의 목적

먼저 진화의 목적에 대해서 알 필요가 있다.

생물은 생존과 번식에 이로운 방향으로 진화한다.

생물시간에 기린이 처음에는 목이 길지 않았는데 높이 달린 풀을 먹어야 살 수 있는 환경이 만들어 져서

점점 목이 긴 기린들이 살아남다가 결국 현재의 기린이 되었다는 이야기를 들어 본 적이 있을 것이다.

이처럼 환경에 적응하고 살아남는 종끼리 교배가 일어나고 후손들이 태어나면서 후손들이 전체적으로 진화 한

모습을 가지게 된다.

이제 생물의 진화 메커니즘에 대해서 알아보자.

2) 생물의 진화 메커니즘 이해를 위한 기반 지식

먼저 DNA에 대해서 알아볼 필요가 있다.

DNA(DeoxyriboNucleic Acid)는 디옥시리보핵산이라 불리우고 유전자의 본체를 이룬다.

[출처] DNA [deoxyribonucleic acid ] | 네이버 백과사전

DNA는 다음과 같이 이중나선 구조로 되어있다.

자세한 설명은 http://100.naver.com/100.nhn?docid=52655를 참고하자.

모든 생물은 세포로 구성되어 있고 세포는 같은 DNA집합을 갖는다.

세포안의 염색체가 DNA를 갖고 있다.

염색체는 유전자들로 구성되어 있고 유전자는 뉴클레오티드라는 물질로 구성되어 있다.

뉴클레오티드는 4가지 종류로 아데닌(A), 구아닌(G), 사이토신(C), 티민(T)로 나뉜다.

자세한 구조는 나도 모른다.

하지만 우리가 알아야 할 부분은

유전자는 뉴클레오티드 즉 AGCT 값이 연결되어 생명체의 특징에 대해 인코딩되어 있다는 것이다.

유전자가 표현할 수 있는 형질을 대립형질이라고 한다.

즉, 머리가 금색이냐 갈색이냐, 눈이 파란색이냐 갈색이냐 등이 유전자에 인코딩되어 있다는 이야기이다.

위에 글을 정리하면 세포가 가지고 있는 염색체의 집합에는 그 유기체의 모든 정보가 담겨있다.

생물에서 복제가 이슈가 되고 있는데 이 정보를 복제하여 완전히 동일한 유기체를 만들어 내는 것이다.

염색체의 집합을 게놈(Genome)이라 하고 특정 게놈의 대립형질을 유전자형이라고 한다.

그리고 이것이 유기체에서 발현된 것을 표현형이라고 한다.

그리고 DNA는 유전자형을 가지고 있다.

내가 이해한 바를 붕어빵으로 비유하자면 -0-;;

게놈은 붕어빵 틀이다.

유전자형은 붕어빵안에 팥을 넣을 것이냐 슈크림을 넣을 것이냐 이다.

표현형은 만들어진 붕어빵이다.

사람도 기본적인 게놈이라는 인간의 설계도는 같으나 그 안에서

머리색등 유전자형이 다른상태에서 표현형이 되어서 각자 개성있는 사람들이 되었다는 것이다.

3) 생물의 진화 메커니즘

위에서 말했듯 생물의 진화 목적은 생존과 번식을 위함이다.

같은 종이라고 해도 해당 환경에 대해서 생존과 번식에

유리한 유전자형이 있을 것이고 불리한 유전자형이 있을 것이다.

이 때에 유리하고 불리함을 적응도라는 단위로 표현한다.

즉, 적응도가 높을수록 생존과 번식에 유리하다고 볼 수 있다.

두 유기체의 교미를 통해서 번식을 하게 되면 두 유기체의 염색체가 서로 섞이게 된다.

이를 재조합 또는 교차라고 한다.

부모의 좋은 유전자를 받아 훌륭한 개체가 될 수 있고

반대로 좋지 못한 유전자를 받아 더 나빠질 수도 있다.

자식도 결국 같은 유기체이므로 휼륭한 개체가 살아남게 되고 결국 남은 자손들은

훌륭한 유기체의 유전자를 따라가게 된다.

하지만 교차가 일어날 때 유전자의 변이가 일어 날 수 있다.

자주 일어나지는 않지만 여러 세대를 거친다면 충분히 일어 날 수 있다.

돌연변이가 일어난다고 무조건 나쁜 것도 좋은 것도 아니다.

변이되고 나서 더 생존과 번식이 용이해졌다면 나중에는 돌연변이였던 유전자형으로

자손들이 진화하게 될 것이다.

정리해 보면 적응도 높은 유기체가 생존 혹은 번식을 하게 되며 돌연변이가 유전된다면

그 돌연변이는 보통 좋을 것이다.

2. 컴퓨터에서의 진화

1) 유전 알고리즘

유전 알고리즘은 진화를 본 떠 만든 알고리즘이다.

유전자가 AGCT로 형질을 인코딩 하는 것 처럼

우리가 구하고자 하는 답을 인코딩 하여서 디지털 염색체를 만들어 낸다.

그리고 임의의 염색체 집합을 만들고 이 염색체가 어떠한 방법을 나타내게 한다.

특정 기준을 이용해서 염색체 집합 중 적응도가 높은 것을 남기고 가끔씩 돌연변이도 일으키며

답을 나타내는 유전자가 생성될 때 까지 염색체 집합을 진화시킨다.

2) 유전 알고리즘의 장점과 단점

문제해결에 있어서 임의성이 들어가기 때문에 빠른 속도로 해결할 수 있고 해결 못 할 수도 있다.

또한 유전 알고리즘을 통해 얻어진 해결책이 최선의 해결책이라는 보장도 없다.

하지만 잘 사용만 한다면 상당히 재미있는 결과를 얻어 낼 수 있다.

유전 알고리즘은 임의성에 의해 해결책이 만들어 지므로 문제를 어떻게 풀어야 하는지 몰라도 된다.

또한 다양한 해법이 나올 수 있다는 것도 장점이 될 수 있다.

3) 디지털 염색체

전형적으로 디지털 염색체는 이진 비트로 인코딩된다.

0, 1값을 바꿔 바꿔가면서 진화시킨다.

이는 비트연산등을 통해서 쉽게 적용할 수 있고 비교적 자유롭게 값을 만들어 낼 수 있다.

중요한 것은 우리가 실제 게임에서 어떤 해법을 구하기 위해서 방법들을 이진 비트로 인코딩하고

유전 알고리즘을 통해서 해법을 구한 뒤 그 해법을 나타내는 이진 비트를 다시 디코딩하여 게임에

적용해야 한다는 것이다.

4) 의사코드

유전 알고리즘의 의사코드를 보자.

1. 각 염색체가 문제를 푸는데 얼마나 적당한가를 검사하고 그에 맞는 적응도를 부여한다.

2. 현재 염색체 집단에서 적응도를 확률로 이용하여 두 개의 염색체를 골라낸다.(보통 룰렛 선택이라 한다.)

3. 두 염색체의 비트중 임의의 비트를 선택하고 교차가 일어날 확률을 계산해 교차시킨다.

4. 선택된 염색체의 비트들을 돌연변이 확률을 계산해 변이시킨다.

5. 100개(원하는 만큼)의 새로운 염색체가 생길 때까지 위 과정을 반복한다.

유전 알고리즘의 한 루프를 세대(Generation)이라 하고 전체 루프를 시대(Epoch)라 한다.

의사코드는 상당히 간단하고 위에서 본 생물의 진화와 무척 닮아있다.

새로 만들어진 염색체들은 문제를 해결하기 위한 다양한 방법들이 되며 이 중 해결책이 나온다면

이를 이용해 해결하면 된다.

5) 룰렛 선택, 교차, 돌연변이

룰렛 선택은 염색체의 적응도에 비례하여 염색체가 선택되게 하는 방법이다.

각 염색체들의 적응도를 원형 그래프로 나타냈다 생각하고 이 원형 그래프를 회전시키고 그 위에 공을

떨어뜨리고 원형 그래프가 멈췄을 때 공이 서있는 위치의 염색체를 선택한다고 보면 된다.

다음과 같이 6개의 염색체가 있다면 1번 염색체가 선택 될 확률이 매우 높지만

그렇다고 무조건 선택되는 것도 아니다.

교차는 두 염색체를 통해 새로운 자식을 생성할 때 비트값을 서로 바꾸는 것이다.

책에는 0.7정도의 교차율이 적당하다고 한다.

상황에 따라서 적당한 교차율을 적용시키는 것이 필요하다.

100010011 10010010

010100010 01000011

이렇게 두 개의 염색체가 있는데 10번째 비트에서 교차가 일어나기로 결정되었다면

100010011 01000011

010100010 10010010

다음과 같이 서로 비트를 바꿔 버리는 것이다.

돌연변이는 염색체의 어떤 비트를 뒤집어버리는 것을 말한다.

즉 0이면 1로 1이면 0으로 바꾼다는 이야기다.

책에서는 0.001정도의 확률을 적용시켰다.

3. 결론

지금까지 유전 알고리즘의 이론적인 부분에 대해서 정리해 보았다.

정리한 내용은 유전 알고리즘의 첫 부분이자 기초내용이다.

유전 알고리즘이라는 것이 어떤 것인지 맛보았다.

실제로 어떤 상황에서 쓰이는지와 적용된 코드등은 공부를 더 하고 정리하도록 하겠다.

참고자료 : 쉽게 풀어 쓴 인공지능 프로그래밍(AI Techniques For Game Programming)

인공지능을 구현 할 때 가장 기본적으로 생각하는 것이

상태의 변화를 통한 인공지능이다.

이 상태일 때 만약 이 조건이면 상태를 어떤 상태로 바꾸어라 뭐 이런 것이다 -0-;;

예를 들어

상태가 stand일 때 적이 시야에 들어오면 walk로 상태를 바꿔야 한다고 해보자.

state = STATE_STAND;

switch( state )

{

        case STATE_STAND:

                if ( SEEN_ENEMY )      // 적을 봤다는건 내 FOV안에 적이 들어왔다는 것인데 일단 이렇게 간단하게 표현하겠다.

                    state = STATE_WALK;

                break;

        case STATE_WALK:

                if ( .... )

                  ....

}

이런식으로 구현이 될 것이다.

유한 상태 기계는 위와 같은 구현을 쉽게 할 수 있게 도와주는 일종의 도구이다.

기본적인 아이디어는 상태를 하나의 객체로 두고 이 상태를 관리하는 매니저를 둔다.

하나의 상태객체는 어떤 현상이 오면 어떤 상태로 변할 것이다라는 것을 저장해 둔다.

매니저는 현재 상태를 유지하면서 어떤 현상이 발생하면 현재 상태객체에서

현생이 발생하면 변하는 상태를 구해 적용시킨다.

말로 쓰니까 뭔가 이상한데 쉽게 설명하면

STATE_STAND

일 때

SEEN_ENEMY면 STATE_WALK로 변해라.를 저장하고 있는 것이다.

그래서 현재 상태가 STATE_STAND인데

SEEN_ENEMY라는 현상이 일어나면 매니저는

STATE_STAND에서 SEEN_ENEMY라는 현상이 일어나면 STATE_WALK로 변해라 라는 것을 구할 수 있기 때문에

현재 상태는 STATE_WALK로 변하게 된다.

다음은 GPG 1권에 나오는 구조다.

위에 것은 상태를 나타내는 객체이다.

위는 상태를 관리하는 매니저 이다.

사용할 때는 위 처럼 일단 상태를 만들고 객체가 나타낼 상태와 이 상태가 변화할 수 있는 가지수를 적어준다.

그리고 특정 현상이 생기면 어떤 상태로 변화할 지를 등록시킨다.

다 등록시키면 매니저를 만들고 추가 시켜준다.

등록을 다 했으면 다음과 같이 현상만 넘겨주면 상태가 계속 변화한다.

ProcessState에서 하고 싶은 걸 구현하면 되겠다.

테스트 해 본 결과다..-0-;;;

유한 상태기계를 사용하면 간단한 인공지능은 쉽게 구현할 수 있겠다.