요술고양이의 Digital Homebrew

그 때 테트리스를 만들고 나서, 정리하는 기분으로 가볍게 원리만 소개해 볼까하고 작성해놓은 카페 글을 블로그에 다시 한번 정리 해두려고 작성한 포스트입니다. 소스가 공개되어 있거나 특별한 무언가를 기대하신분은 실망하시겠지만.. 마이크로프로세서 상에 게임을 만들어 올려보고 싶다고 생각되시는 분은 한번 참고할만하지 않을까? 싶어서 내용을 작성하였습니다.


1. 테트리스 제작 동기

처음에는 테트리스를 마이크로프로세서 상에서 동작하도록 만들어 보고 싶었습니다. 일단 가장 간단하고 쉬운 룰을 갖고 있어서 프로세서에 포팅하는데 큰 무리가 없을 것 같았고, 개인적 공부가 되지 않을까? 싶어서 였지요.. 그래서 우선 인터넷 상에서  돌아다니는 소스를 참고하려고 했습니다. 그러나 윈도우 프로그래밍에 익숙치 않은 제가 해당 소스를 보자하니 간단할 것이라고 여긴 소스가 꽤나 복잡하게 보였고, 얼핏 보기엔 소형 마이크로 프로세서 용으로 적용하기엔 해당 소스들이 메모리를 낭비하는 경향이 있고 해서 공부하는 겸, 알고리즘 공부하는겸 아싸리 그냥 제가 테트리스 원리를 구현 해보았습니다.

그러므로 일반적으로 알려진 원리랑 다를 수도 있고 매우 단순합니다.
허나 프로그래밍에는 한가지 길만 있는 것은 아니니 너그럽게 봐주셨으면 좋겠습니다. ^^

2. 테트리스는?

테트리스 게임 박스 사진 - 출처 : 테트리스 컴퍼니 http://www.tetris.com

1984년 모스크바의 알렉시파지트노브에 의해 처음으로 개발된, 퍼즐 게임입니다. 게임 방식은 대부분 아리라 생각되는데 각기 다른 모양으로 붙어 있는 4개의 블럭을 차곡차곡 쌓아서 한 줄 이상을 채우면 없어지는 퍼즐형 게임으로 누구나 쉽게 할 수 있어 최근까지도 많은 사람들이 꾸준하게 즐기는 게임입니다.

 Alexey Pajitnov - 출처 : 테트리스 컴퍼니 http://www.tetris.com

2. 테트리스게임의 기본 사항

 테트리스를 제작하기에 앞서 간단하게 알아둘 기본 사항에 대하여 알아보겠습니다.

 # 테트리스의 보드

 < 닌텐도의 테트리스 DS >

  테트리스의 배경이 되는 보드입니다. 보통 테트리스의 보드 사이즈는 가로 10칸, 세로 20칸 정도 입니다. 물론 그것보다 더 큰 사이즈도 있고 작은 사이즈도 있지만 보드 자체가 너무 크면 한줄 없애는데 시간이 오래걸리기 때문에 사이즈 10 x 20가 테트리스의 적정수준으로 여겨져 10 x 20 사이즈를 기본으로 하기로 했습니다.

 # 테트리스의 블럭 모양(Shape)

< 테트리스의 블럭 모양 - 출처 : 네이버 포토 앨범(4004nari 님) >

 위 그림은 가장 기본적인 테트리스의 모양(shape) 입니다. 7가지 모양이 있고 특징이라고 하면 모두 4개의 작은 블록으로 구성되어 있다는 점 입니다. 테트리스 컴퍼니 홈페이지에 가니 이렇게 떨어지는 블럭 모양을 Tetriminos(falling blocks)라고 부르는 것 같습니다. 그러니 위의 패턴은 테트리미노스라고 총칭하고 각각 모양에 대한 특별한 이름은 없으므로 테트리스 컴퍼니 홈페이지에서 표현하는 알파벳 이름으로 부르도록 하겠습니다. 위 그림 순서상으로 O, I, S, Z, T, L, J 가 되겠습니다.

# 게임의 룰

 테트리스는 계속 꾸준히 리메이크되어 제작되어 왔기에 테트리스의 기본적인 룰 이외에 세세한 부분에서는 약간씩 차이를 보입니다. 테트리스에서 가장 기본적인 룰은 한줄을 맞추면 그 해당하는 줄이 삭제가 되는 것으로 어느 버젼을 막론하고 모두 동일합니다. 그러나 회전에 관련 된 부분에서 부터는 차이가 생기는데, 여러가지 테트리스를 하다 보면 블럭 회전을 한 방향으로 하는 것도 있고 양방향(왼쪽, 오른쪽) 모두 회전 가능한 버젼도 있습니다. 그리고 회전 시 주변에 벽이나 다른 블럭이 있으면 회전이 안되는 버젼도 있고 벽이나 블럭이 있더라도 반대 방향으로 밀리면서 강제로 회전하는 버젼도 있습니다. 그 외의 부분으로는 시간의 흐름에 따라 블럭이 떨어지는 속도가 빨라지는 룰이나 삭제한 라인수에 따라 블럭이 떨어지는 속도가 빨라지는 룰이 있습니다. 그리고 T스핀, 아이템의 존재 유무, 기본 패턴외에 다른 모양의 존재 유무등 다양한 게임의 룰이 존재합니다.

 물론 여기에서는 가장 쉽고 간편한 룰 몇가지만 설명할 생각입니다. ^^

3. 하드웨어 구성

하드웨어 구성은 자세한 것 까진 필요없는 것 같고 간단하게만 언급하고자 합니다.

가장 먼저 프로세서와 그래픽을 표현할 수 있는 GLCD 또는 TFT-LCD가 필요하고 특이한 테트리스 게임을 만들기 위해서 도트LED가 사용되기도 합니다.

사용자 입력은 터치스크린도 있고 제가 만든 것처럼 조이스틱도 가능하며, 가볍게 택트 스위치 정도만 사용해도 쉬울 것 입니다.

3. 테트리스 기본 알고리즘

 테트리스의 알고리즘은 크게 보자면 테트리미노스의 랜덤 생성, 낙하,  회전, 충돌 확인, 보드의 라인 체크 및 삭제 등이 있겠습니다. 최대한 이해가 쉽게 되도록 올려보겠습니다.

# 테트리미노스와 보드의 표현 방법

 테트리미노스와 보드의 표현 방법이라는 말이 어울릴지 모르겠지만.. 보통 테트리미노스와 보드를 표현하는데 보통은 배열변수를 많이 사용합니다. 요컨테 테트리미노스는 7가지 Shape와 4가지 방향에 대한 Pattern을 갖고 있고 하나의 패턴을 표현하기 위해 메모리 공간은 칸수로 보자면 최대 4 x 4 크기를 갖습니다. (I 모양 때문)

 그래서 위의 패턴들을 배열로 표현한다고 하면 O 모양을 표현한다고 할 시 아래와 같이 선언을 해주게 됩니다. 

 char tetriminos[7][4][4][4] = {
{
    { 1, 1, 0, 0 },                              <-- 얼추 네모 모양이 나오지요? ^^
    { 1, 1, 0, 0 },
    { 0, 0, 0, 0 },
    { 0, 0, 0, 0 }
},

... 생략 ...

게임 보드도 마찬가지로 배열로 마진을 두어 char game_board[12][21] 정도로 선언해줄 수 있겠습니다.

그러나 블록 모양은 const 형으로 선언을 해주면 롬 코드에 삽입이 되기 때문에 램에 대한 부하가 줄지만, 그래도 최대한 자원을 아끼어 램이나 롬이 적은 MCU에도 적용을 가능하게 하고자 일단은 최대한 다이어트를 시켜보기로 하겠습니다.

그렇기 위해서 제일 쉬운 방법은 배열을 쓰되, 바이트의 비트까지 활용을 하는 것입니다.
단, 하단의 방법으로는 단순히 모양만 결정할 수 있습니다. (블럭의 특정 부분에 아이템 등을 삽입한다던가는 불가능)

// 테트리미노스의 7가지 모양과 4가지 방향
 unsigned short tetriminos[7][4] = {

     {0x6600, 0x6600, 0x6600, 0x6600},       // O
     {0xF000, 0x4444, 0xF000, 0x4444}        // I
     {0x6C00, 0x8C40, 0x6C00, 0x8C40},    // S
     {0xC600, 0x4C80, 0xC600, 0x4C80},    // Z
     {0xE400, 0x8C80, 0x4E00, 0x4C40},    // T
     {0x2E00, 0xC440, 0xE800, 0x88C0},    // L
     {0x8E00, 0x44C0, 0xE200, 0xC880},    // J

}

위에 선언된 배열 중 O 모양을 (0x6600) 4비트씩 나누어 보면..

0
x
6      0 1 1 0
6      0 1 1 0
0      0 0 0 0
0      0 0 0 0

(맨 좌측은 0x6600 값을 세로로 쓴 것 입니다.)

위와 같이 모양을 만들어 낼 수 있습니다.  (참고로 위에 나오는 그림과 위치가 조금 다른데 O 모양의 경우 코드 상으로는 중간쯤에 위치 시켰습니다.) 

이보다 더 줄이는 방법은.. 배열로 가장 기본모양만 잡아놓고 삼각함수를 이용하여 해당 테트리미노드의 값을 회전시키는 방법입니다. 이는 연산이 필요하기 때문에 소형 마이크로 프로세서에 오히려 어울리지 않을 수 있지만 또 다른 하나의 방법이 될 수 있습니다.

 PIC18시리즈나 16비트급으로 진행하실 생각이 있는 분들은 롬과 램이 하위 모델에 비해 비교적 넉넉하므로 큰 배열 변수를 사용하여 배열 칸마다 개개별 설정(각기 다른 칼라 적용, 아이템 적용))을 해보시길 바랍니다. 

일단은 다이어트 된 배열 변수로 진행하겠습니다.

# 보드의 표현

그럼 블럭 모양을 다이어트 시켰다면 게임 보드 또한 2차 배열이 아닌 1차 배열 변수로 줄여보겠습니다.

unsigned short game_board[21];     // 16비트 크기를 갖는 변수

그리고 보드에 초기 값을 설정해줍니다.

 for ( i = 0; i < 20; i++ ) game_board[i] = 0xE007;   // 1110000000000111
 game_board[20] = 0xFFFF;                               // 1111111111111111


참고로 위와 같이 초기 값을 설정한 보드는 아래와 같이 벽과 바닥에는 1인 값을 갖게 됩니다.
게임 보드는 최상위가 0 최하위 바닥이 20이 되겠습니다.

00 :   1110000000000111
01 :   1110000000000111
02 :   1110000000000111
          .. 중간 생략 ..
18 :   1110000000000111
19 :   1110000000000111
20 :   1111111111111111

게임이 시작 되면 앞으로는 다음 처럼 진행이 될 것 입니다. 

00 :   1110000000000111
01 :   1110000100000111
02 :   1110000111000111
          .. 중간 생략 ..
18 :   1111100010000111
19 :   1111100111000111
20 :   1111111111111111


그럼 좀 더 참고하기 쉽도록 맵에 대한 벼열 변수 값을 실제로 그래픽으로 표현 해보겠습니다.

unsigned char shape;                  // 테트리미노스의 7가지 모양
unsigned char pattern;                 // 테트리미노스의 4가지 패턴
unsigned char cur_line;               // 테트리니노스의 현재 라인
unsigned char cur_col;                // 테트리니노스의 현재 칸 
unsigned short temp_line[4]          // 테트리미노스 라인 임시 저장소

(변수 이름은 작명에 대한 센스는 그냥 그려려니 하시길 ^^)

위의 변수선언은 간단하게 설정한 테트리미노스 관련 값 들입니다. 테트리스 게임을 제작 시 디스플레이 장치를 GLCD가 아닌 TFT-LCD로 진행하려면 색 정보정도 추가해주는 편이 좋구요.. 위에는 간단하게 설명하기 위해서 일반 변수로 선언을 해주었는데, 구조체로 선언하는 것이 훨씬 좋을 꺼라 고 봅니다. 

그럼 void NewTetriminos(void)라고 함수를 작성하여 새로운 블럭을 설정해보겠습니다.

먼저 생성 함수 이전 또는 생성 함수 자체내에서는 블럭 모양 값을 정해주어야 합니다.

예를 들면, 아래와 같습니다.

shape = TMR2 % 7;    // 단순한 블럭 랜덤 생성 (여기서 TMR2는 dsPIC33F256GP710 Timer2 레지스터 값 임)
pattern = 0;                // 패턴은 초기 패턴 값으로 설정

생성되는 블럭은 랜덤 관련 함수를 만들어 사용해주시는 편이 좋고.. 테트리스는 지속적으로 사용자 입력을 받기 때문에.. (회전, 강제 낙하, 좌, 우 이동) 위와 같이 단순하게 타이머로 계산해도 맨 처음을 제외하고눈 게임 도중 계속 일정한 패턴으로 블럭이 생길 확률은 적은 편 입니다.

그리고 일단은 현재 낙하되는 테트리미노스외에 다음으로 생성될 테트리미노스(Next Block)까진 고려하지 않겠습니다. (실제 동영상에는 적용되어 있습니다.)

다음으로는 shape 값에 해당하는 테트리미노스 모양을 4비트씩 추출해서 저장합니다.

temp_line[0] = (tetriminos[shape][pattern] & 0xF000) >> 6;
temp_line[1] = (tetriminos[shape][pattern] & 0x0F00) >> 2;
temp_line[2] = (tetriminos[shape][pattern] & 0x00F0) << 2;
temp_line[3] = (tetriminos[shape][pattern] & 0x000F) << 6;

보시면 시프트 연산을 같이 수행하는데, 이는 임시 라인 변수의 temp_line(16비트) 중간에 블럭 값을 추출하여 저장하기 위함입니다.

만약 T 모양 테트리미노스 값을 추출한다고 하면.. 다음과 같이 됩니다.

16bit      MSB 15|14|13|12|11|10|09|08|07|06|05|04|03|02|01|00 LSB
temp_line[0] = 0   0   0   0   0   0   0   1   0   0   0   0   0   0   0   0 
temp_line[1] = 0   0   0   0   0   0   1   1   1   0   0   0   0   0   0   0 
temp_line[2] = 0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 
temp_line[3] = 0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0  

연두색으로 하이라이트 된 부분은 보드의 벽이 있는 부분으로 절대 테트리스 모양이 상위 3비트와 하위 3비트 위치에 생성되거나 위치되지 않도록 조심합니다.

그리고 이 녀석은 보드와 최상단과 보드의 중간에 생겨야 하므로 

cur_line = 0;                 // 테트리미노스 현재 라인 (최상위 라인)
cur_col = 9;                // 테트리미노스의 현재 칸  (그림 상 붉은 색으로 하이라이트 된 부분이 위치할 곳)

현재 라인과 현재 칸을 위와 같이 초기화 해줍니다. 참고로 빨간색으로 하이라이트 된 것은 테트리미노스 위치의 기준점 입니다.

# 테트리미노스의 회전

회전은 특별할 것이 없습니다. 회전은 pattern 를 하나씩 증가 시키거나 감소시켜 해당 값을 추출해서 임시저장소에 넣어주면 됩니다.

pattern++;            // 패턴 값 증가

일단 한쪽 방향으로만 도는 것만 고려한다고 가정하면 

if(pattern == 4) pattern = 0;

배열의 포인터를 벗어나지 않도록 위와 같이 작업을 추가해주면 되겠지요? 다만 회전을 어느 위치에서(칸) 했는지 모르므로 일단 각 4비트를 제일 최하위로 시프트 한 후

temp_line[0] = ((tetriminos[shape][pattern] & 0xF000) >> 12) << (cur_col - 3);
temp_line[1] = ((tetriminos[shape][pattern] & 0x0F00) >> 8) << (cur_col - 3);
temp_line[2] = ((tetriminos[shape][pattern] & 0x00F0) >> 4) << (cur_col - 3);
temp_line[3] = ((tetriminos[shape][pattern] & 0x000F) << (cur_col - 3);

현재 커서만큼 재차 왼쪽으로 시프트해주면 됩니다. 현재 커서에서 3을 빼주는 것은 게임상 보드의 벽에 해당하는 3비트 값을 제하기 위해서 입니다. 위의 연산은 사용자에 따라 최적화 할 수 있으니 실제 코딩시에는 간결하게 작성해보시기 바랍니다. ^^

 # 테트리미노스의 이동

이동도 특별하게 해줄 것은 없고 cur_col은 왼쪽으로 이동하면 +1 해주고 오른쪽으로 이동하면 -1 해주고 temp_line 값을 그에 맞게 왼쪽, 오른쪽 시프트를 1씩 해주면 됩니다. 낙하의 경우는 단순히 cur_line을 증가시켜 주면 되는 것이지요..

좌우 이동의 경우 temp_line[i] <<= 1; 또는 temp_line[i] >>= 1;
낙하의 경우 cur_line++;

단, cur_line 값이 최소 2보다 커야하고 13보다 작은 3 ~ 12 사이의 값을 유지하도록 하는

즉, 벽에 해당하는 상위 3비트와 하위 3비트에 테트리미노스의 영역이 진입하지 않도록 유의해야 하는데. 

아직 설명하지 않았지만.. 그전에 충돌 확인을 먼저 하게 되므로 특별히 이동으로 인한 충돌 걱정 필요는 없습니다.

# 충돌 확인

충돌확인이 늦게 설명되었는데, 테트리미노스의 생성, 낙하, 회전, 이동은 모두 충돌 확인을 거친 이후 실행해야합니다.

예를 들어, 테트리미노스의 생성 시 만약 충돌이 감지되었다면 최상위에 어떠한 블럭이 있는 상태에서 블럭이 생성되는 것이므로 그것은 게임 오버를 뜻하게 되고 낙하 시 충돌이 감지되었다면 바닥이므로 그곳에 테트리미노스가 굳어버리게 되며, 이동 및 회전 중에 충돌이 감지되면 이동 또는 회전을 금지시키면 됩니다.

signed char Collision(void)
{

     if( ((game_board[cur_line] & temp_line[0]) != 0) | ((game_board[cur_line + 1] & temp[1]) != 0) |
      ((game_board[cur_line + 2] & temp[2]) != 0) | ((game_board[cur_line + 3] & temp[3]) != 0) )
        return -1;         // 충돌
     else

        return 0;  // 충돌 없음
}

충돌 감지는 어렵지 않습니다. 게임 보드 배열 변수의 현재 라인부터 4줄과 AND 연산을 하여 0이 나오는지 1이 나오는지
확인하면 되는 것 입니다.

예를 들어.. cur_line이 5이고 cur_col이 12에 T모양이 위치한 상태에서 왼쪽 이동을 누른다고 할 시

테트리미노스

16bit      MSB 15|14|13|12|11|10|09|08|07|06|05|04|03|02|01|00 LSB
temp_line[0] = 0   0   0   0   1   0   0   0   0   0   0   0   0   0   0   0  
temp_line[1] = 0   0   0   1   1   1   0   0   0   0   0   0   0   0   0   0 
temp_line[2] = 0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 
temp_line[3] = 0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0  

게임보드

16bit           MSB 15|14|13|12|11|10|09|08|07|06|05|04|03|02|01|00 LSB
game_board[5] =  1   1   1   0   0   0   0   0   0   0   0   0   0   1   1   1  
game_board[6] =  1   1   1   0   0   0   0   0   0   0   0   0   0   1   1   1  
game_board[7] =  1   1   1   0   0   0   0   0   0   0   0   0   0   1   1   1  
game_board[8] =  1   1   1   0   0   0   0   0   0   0   0   0   0   1   1   1  

일단은 temp_line 배열변수를 전부 왼쪽으로 1만큼 시프트 연산을 시킵니다. 다음 게임 보드와 AND 연산을 합니다. temp_line[1]과 game_board[6]의 AND 연산 시 0이 아니게 되므로 충돌이라고 반환하면 됩니다.

그렇게 때문에 생성, 낙하, 회전, 이동은 모두 아래와 같은 방식으로 루틴을 수행하면 됩니다.

1. cur_line 또는 cur_col, pattern 등을 증, 감 시켜 temp_line 값을 수정한다.

2. 충돌 검사를 시도한다. 
   만약 충돌이 아니면 해당 값을 그대로 적용시키고, 만약 충돌이라면 해당 값을 이전으로 되돌린다.



일단 가벼운 원리만 제공하고자 해서 썰렁하지만 여기 까지 입니다. -_-;

항상 제가 쓴 글치고 용두사미가 아닌 글이 없을정도로.. 제 스스로도 수정하면서 다시 보니 허전~~ 하네요~

그리고 천천히 다시 살펴보니 제 스스로도 무식하게 코딩을 했구나 또는 안해도 될 연산을 한게 아닌가 하는 부분이 눈에 보입니다. 차후에 기회가 되면 천천히 다시 제작하면서 제대로 된 원리와 제작 방법에 대해 남겨 보고자 합니다.