8-Puzzle Game in JAVA

개요

 대학교 재학 중 전공 수업에서 진행한 프로젝트이다. 흔히 우리가 평소에 접할 수 있는 간단한 8-Puzzle 게임이다. 3X3 타일 위에 1부터 8까지 숫자가 놓여 있으며, 초기 상태는 헝클어진 상태이지만 공백 타일을 이동하여 최종 상태로 만들어내면 게임이 종료된다. 

 

완성된 8-Puzzle의 모습

---

1. 문제 분석

앞서 언급했듯이 3X3 타일 위에 1부터 8까지 숫자들이 놓여있다. 공백을 이동하여 숫자를 옮겨 최종 상태로 맞추어내면 게임이 종료된다. 3X3 뿐만 아니라, 4X4, 5X5도 추가하여 게임을 할 수 있는 프로그램을 작성할 수 있다.

 

구현할 때 숫자를 랜덤 함수를 통해 무작위로 배치하면 불가능한 퍼즐이 나오는 경우가 있다. 3X3 타일을 예로 들자면 아래의 그림처럼 숫자가 배치되어 버리면 이 퍼즐은 최종 상태로 갈 수 없다. 따라서, 무작위가 아닌 다른 방법을 초기 상태를 고안해야 한다. 

풀 수 없는 퍼즐

2. 기능 및 설계

 2-1. 기능

 프로그램을 실행하면 사용자가 선택하기 편하게 메뉴 화면을 생성한다. 그리고 게임 모드를 선택하면 새로운 창이 띄워진다. 판의 크기는 5X5가 최대이며, 기본적으로 창이 띄워지고 NEW 버튼을 선택하면 게임이 실행된다. 

 게임의 기능에는 저장또한 존재한다. SVAE 버튼을 선택하면 현재 진행하고 있는 게임이 저장된다. 게임은 1인용 뿐만이 아닌, 2인용 모드와 컴퓨터 대결모드 또한 존재한다. 

 

 2-2. 설계

패키지 설계 1

프로그램의 패키지 설계이다. 기본적으로 메인 함수에서 실행되면 모든 기능들이 구동된다. GUI 패키지는 각 퍼즐들의 화면을 구현하는 함수들이 모여있으며, function 패키지에는 각 퍼즐들의 기능이 구현되어 있다. 

 

패키지 설계 2

이 뿐만 아니라 위의 그림처럼 2인용 퍼즐과 컴퓨터 대결 모드가 존재한다. 

 

 - A* Algorithm

 결론으로 넘어가기전, 간단하게 A* 알고리즘을 설명한다. 본 알고리즘은 컴퓨터와 대결하는 부분에서 컴퓨터가 움직일때 사용되는 알고리즘이다. 

 

 A* 알고리즘은 지금까지 가장 최소의 비용으로 도달한 지점부터 탐색하는 다익스트라 알고리즘을 확장하여 만들어진 최단 경로 탐색 알고리즘이다. 즉, 현재 상태 비용과 다음 상태로 이동할 때 예상되는 추정치의 합을 구해 작은 합을 찾아가 최종으로 도달하는 알고리즘이다. 

 

 원리는 우선순위 큐에 노드를 삽입해 우선순위 큐를 POP하고, 해당 노드에서 이동할 수 있는 노드를 찾는다. 그리고 그 노드의 추정치와 현재 상태 비용의 합을 구하고 그 노드들을 우선순위 큐에 다시 삽입한다. 최종 상태에 도달할 때까지 이를 반복한다. 

 

A* 알고리즘의 식

g(x)는 현재까지의 값, 퍼즐 게임 프로그램에서의 의미는 지금까지 움직인 횟수이다. h(x)는 앞으로 예상되는 값, 퍼즐 게임 프로그램에서는 최종 상태에 존재하지 않는 숫자들의 수로 생각하면 된다. 여기서 f(x)의 값이 작은 것부터 탐색한다. 

 

 

퍼즐 게임에서의 A* 알고리즘 적용 방식

3. 결론

Java를 통해 8-Puzzle 프로그램을 직접 제작해보았다. 조금 더 심화적인 내용을 알기 위해 A* 알고리즘을 직접 공부하고 적용하여 구현해보았다. 처음으로 제작한 게임이라 미숙한 점이 많지만, 좋은 경험이 될 수 있었다. 

 

---

<부록>

 - 소스코드 및 실행파일은 https://github.com/jiyeon2781/puzzleGame에서 확인 가능