[📜일지] 개발 일지 2

[Uhyo(egod1537)]

개발 일지 1 : https://gall.dcinside.com/mgallery/board/view?id=game_dev&no=116398

이번 일지에서는 절차적 맵 생성? 만든 것을 정리할 거임.

알고리즘도 길고 아이디어도 괜찮다고 생각해서.

먼저 개발 일지를 많이 적은 것도 아니라서 어떤 게임의 맵을 만들려고 하는 지 모를거임.

기본적인 게임의 규칙은 2D Tilt Maze를 따르고, 부가적으로 적과 아이템 등이 존재하는 게임을 제작할 거임.

아래의 링크에서 간단하게 2D Tilt Maze를 플레이할 수 있고, 금방 어떤 게임인지 알게 될거임.

https://www.mathsisfun.com/games/tilt-maze.html

맵 생성에서 중요한 것은 플레이어의 시작 위치, 벽의 배치, 목표물의 배치임.

이 세가지 요소가 쿵짝이 잘 맞아야지 클리어할 수 있는 맵이 되는 거임.

맵을 랜덤으로 생성하고, 맵의 클리어 여부는 완전 탐색으로도 해결할 수 있지만 너무 경우의 수가 많고, 기기의 부담을 줄 수도 있음.

효율적으로 맵의 클리어 여부를 확인할 수 있는 방법을 고안해볼 거임.

이 게임에서 나타는 중요한 관찰은 어떤 한 지점에서 출발해서 다시 돌아올 수 있는 그룹이 존재한다는 거임.

(빨간색 동그라미는 시작 위치, 파란색 사각형은 얻어야할 목표물)

가능한 맵 중 하나인 데, 초록색으로 된 경로들은 계속 와리가리할 수 있음. 이러한 형태를 그룹이라고 말할거임.

초록색 말고도 보라색으로 된 그룹도 계속 와리가리 할 수 있음.

보라색으로 된 그룹에서 있다가 초록색 그룹으로 이동할 수도 있음.

하지만 초록색으로 된 그룹에서 보라색으로 된 그룹으로는 이동할 수 없음.

관찰할 수 있는 점은 그룹들의 이동으로 게임을 클리어할 수 있다는 거야.

그리고 그룹안에서는 다시 제자리로 돌아올 수 있으므로 모두 방문하는 게 제일 이득이고.

위의 맵은 대충 이렇게 그룹을 나눌 수 있고, 현재 시작점(빨간색 동그라미)에서 출발하면

보라색 그룹 -> 하늘색 그룹 -> 주황색 그룹 -> 파란색 그룹

이 순서대로 그룹을 옮기면 맵을 클리어할 수 있음.

그렇다면 맵이 주어진다면 위에서 말한 그룹들로 나누어야 됨.

이 그룹을 구하는 방법은 생각보다 간단함.

맵을 그래프 자료 구조로 만들어 준 다음 강한 연결 요소 (SCC)를 구하는 알고리즘을 적용하면 됨.

구체적으로 말하자면 맵의 각 칸마다 상하좌우로 갈 수 있는 칸들로 단방향 간선을 이어주고

SCC를 구하는 알고리즘을 구하면, 각 SCC가 위에서 말한 그룹이 된다는 거임.

SCC의 정의를 살펴보면 앞에서 말한 그룹과 같은 뜻인걸 알 수 있을 거임.

각 그룹을 하나의 정점으로 압축해서 본다면 DAG(Directed acyclic graph)가 된다는 사실을 알 수 있음.

정의에 대한 것은 생략하고 위에서 봤던 상황을 생각하면됨.

보라색 -> 초록색은 가능하지만, 초록색 -> 보라색은 불가능하다는 거.

초록색으로 이동한 다음 어떤 방법으로도 다시 보라색으로 이동할 수 없음.

목표물이 여러개 있는 예제도 가져와 봤는 데, 보라색, 주황색, 연두색 그룹은 무조건 방문해야된다는 것을 알 수 있음.

이제 문제를 "DAG에서 시작 정점과 무조건 방문해야되는 정점이 있을 때, 이를 만족하는 경로가 있는가?"으로 환원할 수 있음.

이 문제는 2-SAT (2-Satisfiability Problem)으로 해결할 수 있음.

각 정점마다 boolean 변수 x_i를 배정해줄 거임.

- 시작 정점과 무조건 방문해야되는 정점은 무조건 true여야됨.

- 시작 정점에서 도달할 수 없는 정점은 무조건 false여야됨.

- 어떤 두 정점 u, v를 함께 방문할 수 없는 경우 !x_u || !x_v를 만족해야됨.

이 조건을 만족하게 boolean 변수를 배정할 수 있으면, 이 맵은 해결할 수 있는 것과 같은 말이 됨.

완전 탐색같은 경우 지수 시간 복잡도를 가지지만, 이 방법은 다항 시간 복잡도를 가져서 훨배 빠름.

이것을 응용하면 실제 클리어 가능한 경로도 구할 수 있음. 다양한 방법이 있겠지만 나는 bfs + bitmask를 사용 했음.

유니티에서 잘 작동하고 인스펙터 MapModel 스크립트를 확인하면 해결할 수 있는 방법도 나옴.

소스코드는

https://ideone.com/gmXcJf

에서 확인할 수 있음.

주어진 맵이 클리어 여부와, 클리어 방법을 찾아주는 알고리즘 코드임.

최근 이불에만 있어서 게을러 졌는데 다들 힘내서 개발하자 파이팅

[소닉쫄따구테일즈(dcz3xv7zgu14)]

[속쓰림(sorute)]

역시 개발자는 달라 콘