3 match game 알고리즘 : match3

3 match 게임의 가장 핵심인 match알고리즘을 구현해보자.

이 글에서 구현하려고 하는 Match3 알고리즘은 Swap한 2개의 jewel을 대상으로 이루어지는 검사이며, 주의해야할 점은 다음과 같다.

* match가 되어 jewel이 사라지더라도 실제로 화면에 사라지는 모션이 보여지기 전에는 죽는( 어휘력이 떨어져서 죽는다는 표현밖에 생각 못하겠다. )jewel 위에 있는 jewel이 아래로 떨어지지 않는다. 

( 즉, 데이터의 변경이 모션이 끝난 후에 일어난다. )

* 3개가 맞으면 재자리에서 죽는 모션이 보여지지만, Bejeweled를 기준으로 4개 이상 match가 되었을 때는 Swap했던 mainJewel을 기준으로 나머지 jewel들이 모이고 mainJewel은 승격된다.

( 승격된 jewel은 알다시피 가로, 세로 한줄을 날려버리거나 같은 색을 전부 없애버리거나 하는 폭탄으로 변한다. )

위 주의해야할 점들은 match검출이 성공적으로 이루어지고, match반응 단계에서 일어나는 일이므로 일단 재쳐두고 match검출을 만들어보자.

먼저 mainJewel을 기준으로 검사해야할 대상들을 뽑아보면 다음과 같다.

X	X	O	X	X
X	X	O	X	X
O	O	M	O	O
X	X	O	X	X
X	X	O	X	X

* M은 mainJewel을 뜻한다.    

* X는 검사하지 않을 jewel을 뜻한다.    

* O는 검사할 jewel을 뜻한다.

mainJewel에서 3칸 이상 떨어진 jewel을 검사할 필요가 없다. 3칸 이후까지 연속으로 같은 색이었다면 이전 검사에서 이미 처리되었을 것이다.

일반적인 3 match 게임에서는 대각선 검사도 필요 없다.

이제 각 검사 대상에 번호를 붙히고 비트마스크 기법을 사용하여 조합을 검사한다.

X	X	16	X	X
X	X	1	X	X
128	8	M	2	32
X	X	4	X	X
X	X	64	X	X

* 위처럼 번호를 붙히면 비트마스크를 통해 모든 조합을 1byte로 표현할 수 있다.

검사를 위해 순회해야 할 jewel은 1~8까지 4개의 jewel이다.

// JewelBoard의 Match3 메소드

// mainJewel을 기준으로 3, 4, 5 match를 검출하며 각 jewel의 Kill을 호출한다.

void JewelBoard::Match3(Jewel* m){

    int x = m->GetX();

    int y = m->GetY();

    int kind = m->GetKind(); // jewel의 종류

    bool match3;

    bool ret = false;

 

    for(int i=0; i<4; i++){

        // searchX[8] = { 0, 1, 0, -1, 0, 2, 0, -2 };

        // searchY[8] = { 1, 0, -1, 0, 2, 0, -2, 0 };

        // 순서대로 jewel의 종류가 mainJewel과 같은지 검사한다.

        if(_jewel[x+searchX[i]][y+searchY[i]]->GetKind() == k){

            // 3개가 L 모양으로 match되는 경우를 방지하기 위해 맞은편에 있는 jewel를 검사

            if(_jewels[x+searchX[(i+2)%4][y+searchY[(i+2)%4]->GetKind() == k){

                match3 = true;

            }

            // 검사하는 jewel 뒤에있는 jewel도 같은 종류라면 list에 넎는다.

            if(_jewels[x+searchX[i+4]][y+searchY[i+4]]->GetKind() == k){

                _killList.push_back(_jewels[x+searchX[i+4]][y+searchY[i+4]]);

                mask |= 1<<(i+4);

                match3 = true;

            }

            // match3 가 확정되면 jewel도 list에 넣는다.

            if(match3){

                _killList.push_back(_jewels[x+searchX[i]][y+searchY[i]]);

                mask |= 1<<i;

            }

        }

    }

    switch(mask){

    // match 0

    case 0:

        break;

    // match 2

    case 1: case 2: case 4: case 8:

        break;

    // match 3

    case 5: case 10: case 17: case 34: case 68: case 132:

        m->Kill(1, m->GetPosition());

        this->Kill(_killList, 1, m->GetPosition());

        ret = true;

        break;

    // match 4

    case /* ... 생략 ... */

        m->Kill(2, m->GetPosition());

        this->Kill(_killList, 2, m->GetPosition());

        ret = true;

        break;

    // ... 이하 생략

    }

 

    return ret;

}

12시 방향 jewel부터 시계방향으로 4개의 jewel을 검사한다. 이 jewel이 같다면 맞은편 jewel을 검사한다. ( 1번 jewel을 검사하고 있다면 4번 jewel )

맞은편 jewel도 같은 종류라면 이제 match3 는 확정이므로 검사중인 jewel을 killList에 삽입한다. 맞은편 jewel을 검사하는 이유는 3개의 jewel이 L형태로 match되는 경우롤 방지하기 위함이다.

검사를 하지않고 바로 jewel을 삽입한다고 가정해보자. 1, M, 2, 4 jewel이 같은 종류일 때 4개의 jewel이 모두 죽는 경우가 발생한다.

X	X	2	X	X
X	X	1	X	X
2	2	1	1	2
X	X	1	X	X
X	X	2	X	X

* 위 경우에 (3,2)위치에 있는 1번 jewel은 죽으면 안된다.

Match3를 자세히 보면 이 함수가 단지 3match( 3개가 연속되는 경우 ) 만을 검사하는게 아니라는 것을 알 수 있다. 범위에 있는 jewel들을 검사하다보면 4match, 5match, L match, T match 등을 모두 검사할 수 있다. JewelBoard::Kill은 죽여야 할 jewel들의 list와 기준 jewel이 승격되는지 여부, 기준 jewel의 위치를 매개변수로 받는다.

승격이 된다면 재자리에서 죽는 모션이 아닌 기준 jewel로 흡수되는 모션이 재생되어야 하기 때문이다.

void Jewel::KillDone(){

    _board->SetBoard(_x, _y, 0);

}

죽는 모션이 끝나면 board를 0으로 만들어 해당 자리를 비운다.

void JewelBoard::SetBoard(int x, int y, int kind){

_board[x][y] = kind;

if(kind == 0){

// std::vector<Jewel*> _jewels[8];

Jewel* temp = _jewels[x][y];

temp->SetPositionY(_jewels[x].last()->GetPositionY()+_jewelRadius);    // 위치를 먼저 변경한다.

_jewels[x].erase(_jewels[x].begin()+y);

_jewels[x].push_back(temp);

for(int i=0; i<height; ++i)

_jewels[x][i]->SetIndexY(i);    // index를 변경하여 스스로 떨어지도록 한다.

}

}

JewelBoard::SetBoard는 전달받은 좌표의 _board를 전달받은 kind로 바꾸는 연산을 한다.

* _jewels는 vector자료구조로 만들었기 때문에 빼고 넣는 행위를 위처럼 읽기 쉽게 구현이 가능하다.

이 때 전달받은 kind가 0이라면 _jewels에서 해당 jewel을 빼서 해당 줄의 제일 위로 올린다. index를 새로 설정해주는 이유는 Jewel::update에서 자신의 위치와 index 번호를 비교하며 제자리를 찾아갈 때 까지 중력을 받아 떨어지도록 설정해놓았기 때문이다.

y좌표가 3인 jewel을 빼서 위로 넣고 순서대로 다시 index를 설정하면 y index가 4~7이었던 jewel들은 index가 1씩 줄어들어 한칸씩 떨어질 것이고, 3이었던 jewel은 7이 되어 7 위치에 도달할 때 까지 떨어질 것이다.

여기까지 만들어 보면 새로운 변수가 하나 생기는 것을 알 수 있다. 죽은 jewel자리를 새로 채우는 jewel로 인해 match가 발생하는 경우다.

다음 글에서 이 변수를 처리하는 방법을 알아보자.