봄링크 게임 프로젝트-기초 알고리듬
취업 준비와 프로젝트
구직 준비를 하느라 매우매우 바쁘지만, 동시에 여러곳에 서류 탈락하면서 느낀 점이 많았다.
아, 본인은 생각보다 ‘스페시피케이숀(specification)’이 떨어지는 것인가! 그러면 어떤 역량을 키워야 하는가, 자격증인가? 프로젝트 경험인가? 사실 교내/회사 프로젝트는 꽤 자주 접했지만 본인이 개인적으로 날 잡아 진행한 프로젝트는 손에 꼽을 정도였다.
그렇게 미련이 남으며 OO전자의 sw 역량테스트를 준비하던 중 우연찮게 기발한 생각이 떠올랐다!
다들 아는 OO전자 sw 역량테스트는 주로 경로탐색(dfs/bfs)를 사용하는 구현(시뮬레이션) 형태로 출제되기 때문에, 해당 문제만 줄구장창 풀어보다…
‘잠깐만, 이거 비슷한 걸 본 적이 있었던 것 같은데..’
라 생각한 것이 바로 아래의 게임이였다.
(이 게임 아는 사람 최대 Z세대…)
봄링크 게임
창의 가운데 폭탄이 있고, 양옆으로 불이 무작위로 내려온다. 양끝 폭탄의 심지가 불과 맞닿으면(즉 맨 오른쪽 폭탄은 심지가 오른쪽으로, 왼쪽은 그 반대로) 해당 폭탄과 연결된 폭탄들이 전부 터진다.
폭탄은 시간이 지날수록 올라오는데, 테트리스처럼 창의 맨 위에 폭탄이 올라오면 게임 오버다.
폭탄의 심지를 돌려서 한번에 최대한 많은 폭탄을 터트려 게임 오버를 면하자.
이미 다른 개발자들이 구현해놓긴 했지만, 일단 생각이 났으니 구현해보겠다 결심하고 본격적으로 구상을 시작했다.
기초 알고리듬
일단 파이썬으로 핵심적인 알고리듬부터 빠르게 구현해놓기로 했다.
객체화
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Bomb:
# 심지 0-위 1-오른 2-아래 3-왼 -1-비활성화
def __init__(self):
pass
def setBomb(self,x,y,simji):
self.x = x
self.y = y
self.simji = simji
def getBomb(self):
return self.x, self.y, self.simji
def rotate(self):
self.simji+=1
if self.simji>4:
self.simji = 0
폭탄을 나타내는 Bomb 클래스를 만들었다. 좌표를 나타내는 x,y, 심지 위치를 나타내는 simji 이렇게 세 속성을 지니고 있다.
getter/setter와 심지를 회전시키는 rotate() 메소드를 만들었다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Fire:
def __init__(self):
self.x = 0
self.y = 0
def setFire(self,x,y):
self.x = x
self.y = y
def getFire(self):
return self.x,self.y
def lowerFire(self):
x,y = self.getFire()
self.setFire(x,y+1)
def clearFire(self):
self.setFire()
self.y = 0
그 다음은 불을 나타내는 Fire 클래스이다. 마찬가지로 좌표(x,y) 속성을 가지고 있으며, 기본값을 0,0으로 설정했다. 불을 이동시키는 lowerFire() 메소드와 좌표값을 기본값으로 초기화시키는 clearFire() 메소드를 추가로 설정했다.
1
2
3
4
5
6
class Link:
def __init__(self,karo,sero):
self.karo = karo
self.sero = sero
self.fire = fire()
이제 본격적으로, 게임판을 구현할 Link 클래스를 만들었다. 게임판의 가로 길이/세로 길이와 불 객체를 속성으로 가지고 있다. 불은 게임판에서 한 번에 하나만 나타날 수 있기 때문에 속성으로 구현하였다.
이제 이 Link 클래스들의 메소드들을 정의해야 한다.
보드 초기화
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def initBoard(self):
self.board = [[bomb() for i in range(self.karo+2)] for j in range(self.sero+2)]
x,y = randint(0,1),0
if x==1:
x = self.karo+1
self.fire.setFire(x,y)
for i in range(self.sero+2):
for j in range(self.karo+2):
if j==0 or j==self.karo+1:
if i==y and j==x:
self.board[i][j]=self.fire
else:
self.board[i][j]=0
else:
if i<self.sero//2+1:
self.board[i][j].setBomb(j,i,-1)
else:
s = randint(0,3)
self.board[i][j].setBomb(j,i,s)
보드를 초기화하는 initBoard() 메소드를 실행하면 board라는 이름의 속성이 새로 생긴다.
이 board는 bomb() 객체를 가로 길이+2만큼 담은 배열을 세로 길이+2만큼 담은 2차원 배열이다.
가로 길이에 2만큼을 더한 까닭은 불이 들어갈 2칸이 추가로 필요하고,
세로 길이에 2만큼을 더한 것은 게임 오버될 맨 위 칸과 올라올 폭탄들을 알려줄 맨 아래칸이 필요했기 때문이다.
그 다음 fire 속성의 최초값을 정해줘야 한다. x값은 무작위로 하기 위해 random 라이브러리의 randint() 함수를 사용했는데, fire의 x좌표는 board의 양쪽 끝만 가능하므로 0,1 이 둘 중 하나만 나오도록 설정해 1이 되면 x좌표를 오른쪽 끝으로 바꿔주었다.
그 다음 불이 내려갈 board의 x좌표 양 끝들을 0으로 바꿔주고(단순 ‘비어있다’는 표시를 하기 위해서였다) 불의 좌표값 위치를 fire로 바꿔준 다음, y좌표가 세로 길이의 절반인 곳부터 심지 값을 무작위로 하여 폭탄을 활성화시켜주었다.
따라서 그림으로 표현하자면 위와 같이 된다. 화살표는 심지의 위치, 0은 빈칸 또는 비활성화된 폭탄, 1은 불이다.
출력
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def printBoard(self):
for i in range(self.sero+2):
if i==1 or i==self.sero+1:
print('-'*((self.karo+2)*2+3))
for j in range(0,self.karo+2):
if j==1 or j==self.karo+1:
print('|',end=' ')
if j==0 or j==self.karo+1:
if (j,i)==self.fire.getFire():
print('1',end=' ')
else:
print('0',end=' ')
else:
x,y,s = self.board[i][j].getBomb()
if s==0:
print('↑',end=' ')
elif s==1:
print('→',end=' ')
elif s==2:
print('↓',end=' ')
elif s==3:
print('←',end=' ')
else:
print('0',end=' ')
print()
print()
위 그림처럼 현재 게임판 상황을 출력하는 메소드이다.
맨 아래줄은 올라올 폭탄들을 미리 보여주는 곳, 맨 위줄은 폭탄이 여기까지 올라오면 게임 오버되는 곳이다.
또한 양옆 끝은 불이 내려올 곳이다.
게임 실행
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def playBoard(self):
x,y = self.fire.getFire()
self.board[y][x]=0
self.fire.lowerFire()
x,y = self.fire.getFire()
if y<self.sero+1:
self.board[y][x]=self.fire
if x==self.karo+1:
if self.board[y][x-1].simji==1:
print('폭파')
self.destroyBoard(self.board,y,x-1)
elif x==0:
if self.board[y][x+1].simji==3:
print('폭파')
self.destroyBoard(self.board,y,x+1)
return True
return False
불이 한 칸 내려왔을 때의 상황을 구현하는 메소드이다.
우선 현재 불의 위치를 업데이트하기 위해 불의 위치를 가져온 다음, 그 위치의 board값을 0으로 바꿔준다.
그리고 lowerFire() 메소드를 사용해 한 칸 내린 다음 그 위치를 가져온다.
만약 불이 맨 아래줄까지 내려오지 않았으면 내려간 불의 위치의 board값을 fire로 바꿔주고 불과 폭탄 심지가 닿았는지의 여부를 확인한다.
만일 x가 self.karo+1, 즉 불이 오른쪽에 위치한다면 현재 위치에서 1칸만큼 왼쪽으로 간 곳의 심지가 오른쪽(1)임을 확인,
x가 0, 즉 왼쪽에 위치하면 현재 위치에서 1칸만큼 오른쪽으로 간 곳의 심지가 왼쪽(3)임을 확인한다.
만일 그러면, destroyBoard() 메소드를 실행시킨 다음 True를 반환한다.
폭탄 처리
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
def destroyBoard(self,board,y,x):
pokpa = deque([])
pokpa.append([y,x])
board[y][x].setBomb(x,y,-1)
dy = [-1,0,1,0]
dx = [0,1,0,-1]
while pokpa:
cur = pokpa.popleft()
curx,cury,curs = board[cur[0]][cur[1]].getBomb()
for i in range(4):
temx=curx+dx[i]
temy=cury+dy[i]
tosso = False
if 0<temx<self.karo+1 and 0<temy<self.sero+1:
a,b,c = board[temy][temx].getBomb()
if i==0 and c==2:
tosso = True
elif i==1 and c==3:
tosso = True
elif i==2 and c==0:
tosso = True
elif i==3 and c==1:
tosso = True
if tosso:
board[b][a].setBomb(a,b,-1)
pokpa.append([b,a])
for j in range(1,self.karo+1):
top = self.sero
for i in range(self.sero-1, 0, -1):
if board[i][j].getBomb()[2]!=-1:
temp = board[i][j]
a,b,c = temp.getBomb()
board[i][j].setBomb(i,j,-1)
if board[top][j].getBomb()[2] == -1:
board[top][j].setBomb(a,b,c)
else:
top -= 1
board[top][j].setBomb(a,b,c)
이 알고리듬의 핵심인 폭탄을 폭발시키는 메소드이다. BFS를 사용하면 간단하게 구현할 수 있다.
우선 게임판과 맨 처음 폭발할 폭탄의 x,y좌표값을 인자로 받는다.
pokpa라는 큐(queue)를 생성한 뒤 해당 폭탄의 좌표값을 넣고, BFS를 수행하면 된다.
여기서 BFS는 어떻게 수행하는가 하면…
- 먼저 폭발할 폭탄의 심지값을 -1(비활성화-폭발했으니)로 바꾼다. 오리지날 BFS의 ‘이미 방문했음’에 해당된다.
- 현재 폭발할 폭탄으로부터 위/아래/왼/오른쪽 폭탄들을 차례대로 찾는다. 당연히 이미 폭발한 폭탄(심지값이 -1) 및 경계를 벗어나는 경우를 제외한다.
- 만일 해당 폭탄이 폭발할 폭탄과 연결되어 있으면(즉 위쪽 폭탄은 심지가 아래쪽, 왼쪽 폭탄은 심지가 오른쪽 등) 그 폭탄도 폭발하니 심지값을 -1로 바꾸고, pokpa 큐에 넣는다.
- 이를 pokpa 큐가 빌 때까지 반복한다.
그 다음이 조금 어렵다.
만일 위와 같은 상황에서 불이 한칸 더 내려온다면
이렇게 될 것이다.
그러나 위와 같은 상황에서 불이 한칸 더 내려온다면?
일단 폭발한 직후 이런 상황에 놓이게 된다.
그러나! 맨 오른쪽 줄에는 아직 폭발하지 않은 폭탄들이 공중에 붕 떠있다. 이렇게 붕 떠있는 폭탄들을 최대한 아래로 내려보내도록 처리해야 한다.
1
2
3
4
5
6
7
8
9
10
11
12
for j in range(1,self.karo+1):
top = self.sero
for i in range(self.sero-1, 0, -1):
if board[i][j].getBomb()[2]!=-1:
temp = board[i][j]
a,b,c = temp.getBomb()
board[i][j].setBomb(i,j,-1)
if board[top][j].getBomb()[2] == -1:
board[top][j].setBomb(a,b,c)
else:
top -= 1
board[top][j].setBomb(a,b,c)
while문 다음의 for문이 이를 처리하는 코드다.
acmicpc의 2048 문제를 풀었던 경험이 이 알고리듬을 설계하는 데 도움을 많이 주었다.
- 우선 각 세로줄마다 기준값을 맨 아래(여기서는 게임판의 맨 아래에서 2번째 줄)로 정한다.
- 그리고 기준값으로부터 위로 한 칸씩 탐색하면서…
- 만일 그 좌표의 심지값이 -1이 아니면(즉 폭탄이 있으면) temp에다 해당 폭탄 정보를 저장해놓는다. 그리고 그 좌표의 폭탄은 비활성화시킨다.
- 그리고 기준값 좌표의 심지값이 -1이면(즉 빈칸이면) 거기다가 temp값을 복사한다.
- 만약 -1이 아니면 기준값을 한칸 올린 다음, 거기다가 temp값을 복사한다.
여기까지 하면 한 싸이클이 완료된다. 즉 불이 한 칸 아래로 내려왔을 때의 일이 처리되는 것이다.
게임 실행
1
2
3
4
5
6
7
8
9
10
11
class Game:
def __init__(self,karo,sero):
self.link = link(karo,sero)
self.link.initBoard()
def playGame(self):
self.link.printBoard()
while self.link.playBoard():
time.sleep(1)
os.system('clear')
self.link.printBoard()
Game 클래스를 만들어서, 게임판의 가로/세로 길이를 넣어주면 알아서 초기화시켜주도록 한다. playGame()은 자동으로 게임을 실행시키는 메소드로, 불이 맨 아래에 도달할 때까지 1초에 한 칸씩 진행 상황을 출력해준다.
테스트와 배포
https://github.com/kaebalsaebal/BombLink_server
이제 프로젝트는 여기 깃허브 레포지토리에서 관리하기로 했다.
아직은 위 기초 구현을 담아놓은 base.py만 있지만, 서버 및 프론트 개발능력을 활용해 온전한 웹 게임으로 만들어보고자 한다.