3 match game 알고리즘 : CrossCheck

3 match 게임에는 변수가 하나 있는데, 바로 다음에 나올 jewel의 종류가 불규칙적이고 새로 생성되는 jewel로 인해 어떤 연쇄작용이 일어날지 예상할 수 없다는 것이다.

* 애니팡의 경우에는 적절한 계산을 통해 진행 불가능한 board가 나오지 않게 새로운 동물이 생성된다고 한다. 그래도 새로운 동물로 인한 연쇄작용은 예측하기 힘들다.

새로 생성되는 jewel이 일으키는 연쇄작용은 생성되는 jewel과 기존 jewel이 match를 이루는 경우이다.

새로운 jewel이 바닥( 자신 index번호에 맞는 위치 )에 도달할 때 마다 그 jewel을 기준으로 match3검출을 수행하는 것은 별로 좋지 않은 방법인 것 같다. 4x2 범위에 있는 jewel이 모두 새로 생성되어 아래와 같은 board가 되었을 때 (1,0), (2,0) jewel이 모두 승격처리 된다.

* 승격 : 4개 이상 match되어 가로줄을 없애던, 같은 색깔을 없애던 하는 폭탄 jewel이 되는 현상

2	2	3	3
4	4	4	4

좌하단부터 검출을 한다고 했을 때 (1,0)위치에 있는 jewel이 먼저 승격된다. 그 다음 순간 (2,0)위치에 있는 jewel에 대한 검출에서도 4개가 match되기 때문에 (1,0), (2,0) jewel이 모두 승격된다.

그보다 먼저 8개의 jewel이 모두 재자리를 찾아서 board배열이 위처럼 완성되었을 때 검출을 수행한다는 보장이 없기 때문에 아직 떨어지고있어서 해당 board가 0일 수도 있는 경우 재대로 match검출을 할 수 없다.

* jewel이 죽을때 자신 index번호에 맞는 board를 0으로 바꾸고 재자리를 찾아갔을 때 board를 자신의 kind로 채워넣기 때문에

2	0	0	0
4	4	0	0

(0,0), (0,1), (1,0) jewel은 떨어져서 board배열이 재값으로 채워졌지만 나머지 jewel은 아직 떨어지지 않아서 board배열이 아직 0이다. 최종적으로 아래줄은 모두 4로 채워질 것이기 때문에 match가 되어야 하지만 위 상태에서는 검출해낼 수 없다.

3match게임의 대명사라고 할 수 있는 Bejeweled는 생성된 jewel이 위와 같을 경우 (3,0)위치의 jewel을 기준으로 (3,0) jewel이 승격되고, 나머지 (0,0), (1,0), (2,0) jewel이 흡수된다.

* 영상을 첨부할 수 있으면 좋겠는데

여러가지 경우의 수를 시도해 본 결과 생성되는 jewel은 오른쪽 상단 jewel을 기준으로 match검사를 수행하면 될 것 같다. 그렇다면 L이나 T형태로 match가 되는 경우 어떤 jewel을 기준으로 검출을 할까 L, T match라면 응당 주위 9칸을 날려버리는 폭탄 jewel로 승격되야하는데 우상단부터 검출을 해서 3match만된다면 화가 많이 날테니까 가로줄과 세로줄이 교차하는 jewel을 기준으로 검출을 수행하면 되겠다.

고려해야 할 사항을 정리해보면 다음과 같다.

1. 모든 jewel이 제자리로 돌아간 후에 match 검출을 해야한다.

2. 생성된 jewel중에 L 또는 T match가 있다면 먼저 처리한다.

3. 남은 board에서 5match 또는 4match 또는 3match가 있다면 우상단 jewel을 기준으로 처리한다.

1번은 이미 해결한 것과 다름없다. Jewel::KillDone에서 board[x][y]를 0으로 만들었고 바닥에 다다르면 board[x][y]를 자신의 kind로 만든다.

void Jewel::update(float dt){

if(_position.y > _y*_radius){

// 지금 위치가 재자리보다 높다면 중력가속도를 받아 떨어진다.

_accel += GRAVITYACCEL*dt;

_speed += _accel*dt;

_position.y += _speed*dt;

if(_position.y <= _y*_radius){

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

_position.y = _y*_radius;

}

}

}

JewelBoard::update에서는 board의 최소값이 0보다 클 경우에만 행동을 취하도록 구현해 놓았으므로 자동으로 모든 jewel이 재자리를 찾아갔을 때 딱 한 번 검출을 수행할 수 있다.

2번과 3번을 해결하기 위해 maskBoard라는 마스크 배열을 사용한다.

void JewelBoard::CrossCheck(){

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

        for(int j=0; j<height; ++j){

            _maskBoard[i][j] = 0;

        }

    }

 

    // 마스킹

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

        for(int j=0; j<height; ++j){

            if(VChain(_jewels[i][j]) > 2) // 자신을 제외하고 세로로 자신과 같은 색깔인 jewel갯수를 반환

                _maskBoard[i][j]++;

            if(HChain(_jewels[i][j]) > 2) // 자신을 제외하고 가로로 자신과 같은 색깔인 jewel갯수를 반환

                _maskBoard[i][j]++;

        }

    }

 

    // L, T match 검출

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

        for(int j=0; j<height; ++j){

            if(_maskBoard[i][j] == 2)

                // Match3는 3match뿐 아니라 L, T 등 모든 match를 검출할 수 있다.

                // 다만 매개 jewel을 기준으로 범위가 2까지 이므로 여기서는 L, T match만 검출된다.

                Match3(_jewels[i][j]);

        }

    }

 

    // 우상단부터 역순으로 순회

    for(int i=width; i>=0; --i){

        for(int j=height; j>=0; --j){

            if(_maskBoard[i][j] == 1)

                Match5(_jewels[i][j]); // 매개 jewel을 기준으로 좌, 하단 방향 5match를 검출

            if(_maskBoard[i][j] == 1)

                Match4(_jewels[i][j]); // 매개 jewel을 기준으로 좌, 하단 뱡향 4match를 검출

            if(_maskBoard[i][j] == 1)

                Match3(_jewels[i][j]);

        }

    }

}

CrossCheck는 먼저 maskBoard를 0으로 초기화한다.

그 후, 모든 jewel을 순회하며 자신과 연결된 같은 색 jewel의 갯수를 세어 이 갯수가 2 이상일 경우 maskBoard의 해당 칸을 1 증가시킨다. 가로, 세로 각 1회씩 실시하므로 만약 해당 jewel이 L, Tmatch의 교차점이었다면 maskBoard의 값은 2가 될 것이다.

1	1	2
0	0	1
0	0	1

1	2	1
0	1	0
0	1	0

완성된 maskBoard의 모습은 위와 같을 것이다.

그 다음 완성된 maskBoard를 순회하며 값이 2인 jewel에 대해 Match3를 수행한다.

* 이 때 죽는 모든 jewel의 maskBoard를 0으로 만든다.

위 연산을 하면 다음과 같은 모양의 maskBoard만 남을 것이다.

0	0	0	0
1	1	1	1

1	1	1	1	1
0	0	0	0	0

남은 maskBoard는 선형으로 연결된 5, 4, 3match를 나타낸다.

이제 maskBoard를 우상단부터 역순으로 순회하며 Match5->Match4->Match3 순서로 검출한다.

Match5, Match4는 좌측 또는 아래로 연속된 5개, 4개의 jewel이 있는지 검사하고 있다면 Kill시킨다.

여기까지 만들면 어느정도 Bejeweled와 비슷하게 게임이 진행되는 것을 볼 수 있다.

* 동영상을 찍어서 올릴 수 있으면 좋겠다

아직 남은 문제들이 몇가지 있다.

1. 이펙트가 없다.

2. 폭탄 jewel이 일으킨 폭발로 인해 연쇄폭발이 일어났을 때 Bejeweled는 그 연쇄가 시간차를 두고 보여지지만 여기서 만든 게임은 연쇄가 한번에 일어난다.

* DelayedKill을 구현해서 내가 폭탄 jewel이라면 일정시간 대기한 후 죽도록 해보았지만 뭔가 어색하다. 더 생각해볼 문제다.