3 match game 알고리즘 : Swap

비주얼드, 애니팡 등으로 알려진 3 match 퍼즐게임을 만들기 위한 알고리즘을 만들어보자.

3 match 게임의 유일한 입력인 Swap을 먼저 구현보자. Swap은 터치 또는 마우스 입력을 받고 드래그를 감지하여 터치한 jewel과 드래그 한 방향의 jewel과 swap 되면서 이루어진다.

Swap을 구현해야할 때 주의해야 할 특징은 다음과 같다.

*입력을 한 즉시가 아닌 Swap Action( jewel이 실제로 화면에서 움직이는 행위 )이 이루어 지고 난 후 다음 동작( match 또는 rollback )이 이루어져야한다.

*아래 코드들은 윈도우 애플리케이션 기준으로 작성한 코드이며, cocos2d-X엔진을 모티브로 작성한 엔진을 사용하여 실제 cocos2d-X 코드와 비슷하지만 내부적인 동작도 같은 것은 아니다.

( 엔진을 사용할 수 없는 환경에서 작성한 코드라서 엔진을 만들어서 사용했다. )

// 마우스 입력을 받는 부분

MouseListener(WPARAM msg, int x, int y){

if(msg == WM_MOUSEDOWN){

_isClick = true;

_oldX = x;

_oldY = y;

}

 

if(_isClick && msg == WM_MOUSEMOVE){

if(x-_oldX > _jewelRadius) // right

_jewelBoard->SwapJewel(_oldX/50, _oldY/50, _oldX/50+1, _oldY/50);

 

if(x-_oldX < -_jewelRadius) // left

_jewelBoard->SwapJewel(_oldX/50, _oldY/50, _oldX/50-1, _oldY/50);

 

if(y-_oldY > _jewelRadius) // up

_jewelBoard->SwapJewel(_oldX/50, _oldY/50, _oldX/50, _oldY/50+1);

 

if(y-_oldY < -_jewelRadius) // down

_jewelBoard->SwapJewel(_oldX/50, _oldY/50, _oldX/50, _oldY/50-1);

}

}

mouse입력이 발생하면 MouseListener가 호출되고 해당 이벤트와 마우스 좌표가 매개변수로 입력된다.

MOUSEDOWN이 발생하면 현재 좌표를 저장하고, MOUSEMOVE가 발생할 때 마다 저장한 좌표와 현재 좌표를 비교하여 드래그를 감지한다.

드래그를 감지했다면 jewelBoard객체의 SwapJewel을 호출한다. 매개변수는 MOUSEDOWN시 선택했던 jewel의 번호와 드래그 하여 swap되어야 할 jewel의 번호이다.

* jewel의 번호는 왼쪽 하단부터 (0,0)으로 매겨져 있다.

0,3	1,3	2,3	3,3
0,2	1,2	2,2	3,2
0,1	1,1	2,1	3,1
0,0	1,0	2,0	3,0

* jewel 번호 예시

// JewelBoard객체에 있는 SwapJewel메소드

void JewelBoard::SwapJewel(int x1, int y1, int x2, int y2, bool isRollback = false){

if(x2<0 || y2<0 || x2>=width || y2>=height)

return;

 

// Jewel* jewels[width][height];

// 각 배열 인자는 jewel객체를 가리키고있다.

_jewels[x1][y1]->Move(x2, y2);

_jewels[x2][y2]->Move(x1, y1);

 

_isStable = isRollback;

 

// int _board[width][height];

// 현재 x, y 위치에 있는 jewel의 번호(종류)(색깔)를 저장하고있다.

_board[x1][y1] = 0;

_board[x2][y2] = 0;

 

swap(jewels[x1][y1], jewels[x2][y2]); // 두 jewels가 가리키고있는 포인터를 swap

 

_jewel1 = _jewels[x1][y2];

_jewel2 = _jewels[x2][y2];

 

_wasSwap = false;

}

_jewels배열에 있는 jewel의 Move를 호출해서 실제 움직임이 일어나도록 한다.

_board배열을 바로 바뀐 jewel의 번호로 채우지 않는 이유는, 바로 채울 경우 update에서 바로 match 검사를 하고, jewel의 움직임이 화면에 보여지기도 전에 사라질 수 있기 때문이다. 그러므로 일단 0으로 채워놓고 jewel의 움직임이 끝날때까지 기다린다.

_isStable이 false일 때만 update에서 match검사를 하도록 설계했기 때문에 match가 되지 않아서 다시 되돌아가는 rollback이 true이면 isStable도 true이어야 한다. 

* 아니면 무한 rollback이 된다.

// Jewel객체의 Move메소드

// 실제로 jewel을 움직이게 하는 연산이 이루어진다.

void Jewel::Move(int x, int y){

// cocos2d에 있는 action을 모티브로 구현한 Action 시스템

auto act1 = MoveTo::create(Vector(x, y)*_radius, 0.2f);

auto act2 = CallFunc::create(Jewel::MoveDone, this);

auto seq = Sequence::create(act1, act2, NULL);

 

this->runAction(seq);

_x = x; _y = y;

}

jewel의 Move는 단순히 움직이는 action을 수행하고 자신이 가지고 있는 x, y 변수를 변경한다.

action은 cocos2d 엔진에 있는 것이지만 비슷하게 쉽게 구현할 수 있다.

// Jewel객체의 MoveDone메소드

// 움직임이 끝나자마자 해야 할 처리들을 수행한다.

void Jewel::MoveDone(){

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

}

Move action이 끝나면 JewelBoard의 _board배열 값을 자신의 _kind로 채운다. 

// JewelBoard객체의 update메소드

// 매 프레임마다 호출되며 JewelBoard의 상태를 갱신한다.

void JewelBoard::update(float dt){

int m = 0;

bool b1, b2;

 

if(!_isStable){

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

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

m = min(m, _board[i][j]);

}

}

 

if(m>0){

if(_wasSwap){

b1 = match3(_jewel1);

b2 = match3(_jewel2);

if(!(b1||b2)) // 일치하는 조합이 하나도 없다면 다시 원래 상태로 rollback시킨다.

SwapJewel(_jewel1->GetX(), _jewel1->GetY(), _jewel2->GetX(), _jewel2->GetY(), true);

}

else

CrossCheck();

}

}

}

매 프레임마다 호출되는 update에서는 _isStable이 false일 경우 _board배열이 정상인지 검사한다.

정상이라는 말은 배열에 0인 인자가 없고 모두 값을 가지고 있다는 뜻이다.

JewelSwap에서 해당 jewel번호의 board를 0으로 만들어주었기 때문에 board가 다시 0이 아닌 값으로 채워질 때 까지 match 검사를 수행하지 않는다.

Jewel의 action이 끝나고 SetBoard로 _board의 값을 채워넣으면 if문을 통과하여 match 검사를 수행한다.

Swap 동작을 천천히 따라가며 변화하는 _board의 상태를 그림으로 설명해 보면 다음과 같다.

* 예를 쉽게 들기 위해 4*4 Board를 사용한다.

* X는 의미없는 칸을 뜻하고 각 숫자는 jewel의 종류를 뜻한다. 즉, 같은 숫자는 같은 색깔 jewel을 뜻한다.

T(0)  // 시간단계(0)

X	X	X	X
X	4	1	X
X	2	4	X
X	4	3	X

위 상태에서 (1,1)[2]과 (2,1)[4]을 Swap하면 코드는 다음과 같은 상태가 된다.

_jewel1 = _jewels[1][1];

_jewel2 = _jewels[2][1];

_isStable = false;

// 이 swap후부터 _jewels[1][1]은 4를 가리키고, _jewels[2][1]은 2를 가리킨다.

swap(_jewels[1][1], _jewels[2][1]);

T(0.0 ~ 0.2)    // jewel들이 Move Action으로 움직이고 있다.

X	X	X	X
X	4	1	X
X	0	0	X
X	4	3	X

JewelBoard::update는 계속 _board[][]를 순회하며 최솟값이 0이 아니길 기다리고 있다.

T(0.2)    // jewel들이 다 도착했다.

X	X	X	X
X	4	1	X
X	4	2	X
X	4	3	X

Jewel::MoveDone이 호출되어 _board가 바뀐 번호로 채워진다.

_board의 최솟값이 0이 아니기 때문에 if(min>0) 구문을 통과하고 match 검출을 수행한다.

이제 남은 것은 어떻게 match를 검사할 것인지 생각해 보는 것이다.

match에 대해서는 다음 글에서 알아보도록 하겠다.