스텔스 게임 레벨 디자이너는 다양한 난이도의 흥미로운 게임환경(레벨)을 제작해야 한다. J. Temblay와 공동 연구자들은 이 과정의 자동화를 돕는 Unity-기반 레벨 디자인 툴을 개발했다. 이 툴은 디자이너가 지도에서 경비병의 경로, 속도, 감시 영역, 플레이어의 출발점과 도착점 등 여러 게임 요소들을 입력하면 플레이어가 취할 수 있는 가능한 경로들을 포함한 다양한 시뮬레이션 결과들을 보여준다. 이를 이용해 디자이너는 현재의 게임 요소들이 자신이 의도한 난이도 및 플레이어 경로를 만드는지 실시간으로 확인할 수 있고, 필요한 경우 이들을 조정할 수 있게 되었다. 여기서는 두 가지 면에서 이 툴의 개선점을 제시한다. 첫째, 디자이너가 몇 개의 지점을 입력하면 이 지점들을 포함하는 흥미로운 경비병의 감시 경로를 난이도별로 추천해주는 기능을 추가해서 레벨 디자인 툴로서의 편의성과 유용성을 높였다. 둘째, 기존의 충돌 체크 함수 및 RRT-기반 경로 탐색 함수를 새로운 충돌 체크 함수와 델로네 로드맵-기반 경로 탐색 함수로 대체하여 시뮬레이션 속도를 크게 향상시켰다.
스텔스 게임 레벨 디자이너는 다양한 난이도의 흥미로운 게임환경(레벨)을 제작해야 한다. J. Temblay와 공동 연구자들은 이 과정의 자동화를 돕는 Unity-기반 레벨 디자인 툴을 개발했다. 이 툴은 디자이너가 지도에서 경비병의 경로, 속도, 감시 영역, 플레이어의 출발점과 도착점 등 여러 게임 요소들을 입력하면 플레이어가 취할 수 있는 가능한 경로들을 포함한 다양한 시뮬레이션 결과들을 보여준다. 이를 이용해 디자이너는 현재의 게임 요소들이 자신이 의도한 난이도 및 플레이어 경로를 만드는지 실시간으로 확인할 수 있고, 필요한 경우 이들을 조정할 수 있게 되었다. 여기서는 두 가지 면에서 이 툴의 개선점을 제시한다. 첫째, 디자이너가 몇 개의 지점을 입력하면 이 지점들을 포함하는 흥미로운 경비병의 감시 경로를 난이도별로 추천해주는 기능을 추가해서 레벨 디자인 툴로서의 편의성과 유용성을 높였다. 둘째, 기존의 충돌 체크 함수 및 RRT-기반 경로 탐색 함수를 새로운 충돌 체크 함수와 델로네 로드맵-기반 경로 탐색 함수로 대체하여 시뮬레이션 속도를 크게 향상시켰다.
In the stealth game design, level designers are to develop many interesting game environments with a variety of difficulties. J. Tremblay and his co-authors developed a Unity-based level design tool to help and automate this process. Given a map, if the designer inputs several game factors such as g...
In the stealth game design, level designers are to develop many interesting game environments with a variety of difficulties. J. Tremblay and his co-authors developed a Unity-based level design tool to help and automate this process. Given a map, if the designer inputs several game factors such as guard paths and velocities, their vision, and the player's initial and goal positions, then the tool visualizes simulation results including (clustered) possible paths a player could take to avoid detection. Thus with the help of this tool, the designer can ensure in realtime if the current game factors result in the intended difficulties and players paths, and if necessary adjust the factors. In this note, we present our improvement on this tool in two aspects. First, we integrate a function that if the designer inputs some vertices in the map, then the tool systematically generates and suggests interesting guard paths containing these vertices of various difficulties, which enhances its convenience and usefulness as a tool. Second, we replace the collision-detection function and the RRT-based (player) path generation function, by our new collision-check function and a Delaunay roadmap-based path generation function, which remarkably improves the simulation process in time-efficiency.
In the stealth game design, level designers are to develop many interesting game environments with a variety of difficulties. J. Tremblay and his co-authors developed a Unity-based level design tool to help and automate this process. Given a map, if the designer inputs several game factors such as guard paths and velocities, their vision, and the player's initial and goal positions, then the tool visualizes simulation results including (clustered) possible paths a player could take to avoid detection. Thus with the help of this tool, the designer can ensure in realtime if the current game factors result in the intended difficulties and players paths, and if necessary adjust the factors. In this note, we present our improvement on this tool in two aspects. First, we integrate a function that if the designer inputs some vertices in the map, then the tool systematically generates and suggests interesting guard paths containing these vertices of various difficulties, which enhances its convenience and usefulness as a tool. Second, we replace the collision-detection function and the RRT-based (player) path generation function, by our new collision-check function and a Delaunay roadmap-based path generation function, which remarkably improves the simulation process in time-efficiency.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
이렇게 만들어진 다면체를 이용하여 플레이어의 시간별 위치로 만들어지는 선분과의 충돌 체크를 함으로써 경비병의 감시 영역에 플레이어가 들어갔는지 확인할 수 있다. 물론, 플레이어의 시간별 동선을 의미하는 이 선분은 장애물 영역에 들어가서도 안 되므로 장애물을 표현하는 다면체와의 충돌 여부도 검사한다. 이러한 방법을 통해 기존 방식보다 빠르게 충돌 검사를 할 수 있게 된다.
본 논문에서는 Tremblay 등이 Unity를 이용해서 개발한 스텔스 게임의 레벨 분석 툴에 대해 두 가지 개선사항을 연구했다. 첫째는 디자이너가 몇 개의 지점을 입력하면 이 지점들을 포함하는 흥미로운 경비병의 감시 경로를 난이도별로 추천해주는 기능을 추가해 레벨 제작을 돕는 툴로서의 유용성과 편의성을 높였고, 둘째는 기존의 충돌 체크 함수 및 RRT-기반 경로 탐색 함수를 새로운 충돌 체크 함수와 델로네 로드맵 기반 경로 탐색 함수로 대체하여 시뮬레이션 속도를 크게 향상시켰다.
본 논문은 두 가지 면에서 이 툴을 개선하는 방법을 제시한다. 첫째, Xu 등[4,5]의 아이디어를 발전시켜, 제작자에게 유용하고 흥미로울 가능성이 있는 경비병 감시 경로들을 미리 계산해 놓고, 디자이너가 몇 개의 지점을 입력하면 이 지점들을 포함하는 감시 경로들만 이 집합으로부터 난이도별로 추출해 보여주는 기능을 추가한다.
이러한 문제점을 극복하기 위해 우리는 더 시간 효율적인 충돌 체크 함수를 제안한다. 감시 경로가 정해지고 나면 경비병의 시간에 따른 위치와 바라보는 방향을 계산할 수 있다.
가설 설정
① 각 정점의 Degree만큼 탐색을 반복한다.
③ 두 알고리즘 모두 플레이어의 속력은 최대속력 범위 안에서 무작위로 변하며 경비병의 속력은 항상 일정하다.
제안 방법
RRT는 지도를 60×60의 Grid로 나누어서 샘플링했으며, 1000번의 샘플링 횟수 제한을 두었다.
6-1]은 3명의 경비병이 반드시 경유해야 할 감시 경로의 예로서 3가지 색깔로 표시하였다. 감시 경로 후보 집합 Z로부터 이들을 포함하는 경로로서 총 40개의 경로가 추출되었으며, 이들에 대해 DEL 알고리즘으로 시뮬레이션한 뒤 성공률을 계산하였다. [Fig.
델로네 삼각화(Delaunay Triangulation)[9]는 주어진 정점들을 연결하는 삼각화의 한 종류로서 유클리드 최소신장트리(EMST)를 포함한다거나 삼각형들의 내각의 최소값이 최대가 되는 등의 최적의 성질을 많이 갖고 있다. 따라서 본 논문에서는 델로네 삼각화를 이용하여 경로 탐색에 사용되는 로드맵을 생성한다. 주어진 지도에서 장애물 위에 있지 않은 100개의 정점을 무작위로 샘플링하여 델로네 삼각화를 만든다.
본 논문에서는 Xu 등[4,5]의 아이디어를 발전시켜, 주어진 지도에서 개발자에게 유용한 경비병의 감시 경로 후보들을 모두 계산해 놓은 후, 개발자가 원하는 정점들을 입력하면 이 정점들을 포함하는 후보 경로들을 난이도별로 출력해주는 기능을 제안한다. 또한, 다수 플레이어 경로들을 생성하고 시뮬레이션하는 부분에서, 기존의 충돌 체크 함수와 RRT-기반 경로 탐색 함수 대신, 새로운 충돌 체크 함수와 로드맵-기반 깊이우선탐색(DFS)을 사용하는 방안을 제시한다.
본 논문에서는 Xu 등[4,5]의 아이디어를 발전시켜, 주어진 지도에서 개발자에게 유용한 경비병의 감시 경로 후보들을 모두 계산해 놓은 후, 개발자가 원하는 정점들을 입력하면 이 정점들을 포함하는 후보 경로들을 난이도별로 출력해주는 기능을 제안한다. 또한, 다수 플레이어 경로들을 생성하고 시뮬레이션하는 부분에서, 기존의 충돌 체크 함수와 RRT-기반 경로 탐색 함수 대신, 새로운 충돌 체크 함수와 로드맵-기반 깊이우선탐색(DFS)을 사용하는 방안을 제시한다.
여기서는 개발자에게 유용하고 흥미로운 감시 경로의 후보 집합 Z를 구하고(Step 1과 2), Z의 경로 중 원하는 형태의 경로들만을 난이도별로 추천하는 알고리즘(Step 3)을 제안한다. 디자이너는 주어진 지도에서 감시 경로 후보 집합 Z를 한번 계산해 놓고, 필요할 때마다 Step 3를 시행하여 원하는 형태 및 난이도의 감시 경로들을 선택, 시뮬레이션할 수 있다.
새로운 충돌 체크 함수와 델로네 로드맵을 이용한 시뮬레이션 방법을 정리하면 다음과 같다. 주어진 지도에서 델로네 로드맵(플레이어 경로)과 미디얼 액시스(경비병의 감시 경로)를 계산해 놓는다. 경비병의 감시 경로와 속도 등을 포함한 모든 게임요소들이 정해지면 충돌영역을 동적으로 만들기 위해 미리 시간에 따른 경비병의 위치와 바라보는 방향을 계산해둔다.
따라서 본 논문에서는 델로네 삼각화를 이용하여 경로 탐색에 사용되는 로드맵을 생성한다. 주어진 지도에서 장애물 위에 있지 않은 100개의 정점을 무작위로 샘플링하여 델로네 삼각화를 만든다. 장애물과 겹치는 간선은 제거하고 겹치지 않는 간선들로만 로드맵을 구성한다.
본 논문은 두 가지 면에서 이 툴을 개선하는 방법을 제시한다. 첫째, Xu 등[4,5]의 아이디어를 발전시켜, 제작자에게 유용하고 흥미로울 가능성이 있는 경비병 감시 경로들을 미리 계산해 놓고, 디자이너가 몇 개의 지점을 입력하면 이 지점들을 포함하는 감시 경로들만 이 집합으로부터 난이도별로 추출해 보여주는 기능을 추가한다. 이러한 기능은 디자이너가 레벨을 제작하는데 많은 편의성과 유용성을 제공할 것이다.
본 논문에서는 Tremblay 등이 Unity를 이용해서 개발한 스텔스 게임의 레벨 분석 툴에 대해 두 가지 개선사항을 연구했다. 첫째는 디자이너가 몇 개의 지점을 입력하면 이 지점들을 포함하는 흥미로운 경비병의 감시 경로를 난이도별로 추천해주는 기능을 추가해 레벨 제작을 돕는 툴로서의 유용성과 편의성을 높였고, 둘째는 기존의 충돌 체크 함수 및 RRT-기반 경로 탐색 함수를 새로운 충돌 체크 함수와 델로네 로드맵 기반 경로 탐색 함수로 대체하여 시뮬레이션 속도를 크게 향상시켰다.
Step 3: 디자이너가 입력한 정점들을 포함하는 감시 경로를 Z에서 무작위로 일정 개수(여기서는 80개)만큼 추출한다. 추출된 감시 경로 각각에 대해 다음 절들에서 소개하는 플레이어 시뮬레이션을 시행, 난이도를 계산하고 난이도별로 구분하여 출력한다.
1]), 3개 이상의 장애물로부터 같은 거리에 있는 점이 정점(vertex), 나머지 부분, 즉 정점과 정점 사이를 연결하는 선들이 간선(edge)이며, 장애물의 코너로 연결된 간선을 제외하고 모든 간선이 감시 경로의 후보가 된다. 특히, 문법적인 요소를 도입하여 감시 경로의 각 선분을 더 나누어 잠깐 멈춤, 회전 등과 같은 요소를 재귀적으로 삽입할 수 있도록 하였다. 하지만 이 논문에서 이미 지적된바, 무작위 경로 생성 방법은 레벨 디자이너가 원하는 난이도의 감시 경로들을 생성하기에는 적합하지 않다.
대상 데이터
① 비교실험은 총 3회 실시한다. 각 실험에 사용된 감시 경로는 3.1절의 [Table 1]에 나타난 감시 경로들 중, 경비병 2명과 3명에 대해 각각 무작위로 80개씩 추출한 것이다.
각 지도에는 미디얼 액시스가 함께 나타나 있다. 실험에 사용된 PC의 사양은 Intel i5-2500 3.30GHz, 8GB RAM이다.
성능/효과
[Table 4]는 [Table 2, 3]의 실험에서 80개 경로에 대한 시뮬레이션을 수행하는데 걸린 시간(50회 시행한 평균값)이다. 경비병 2명/3명의 감시 경로 80개를 시뮬레이션하여 난이도별로 구분할 때 필요한 시간이 RRT는 12.4초/15.6초, DEL은 3.7초/5.1초이며, 하나의 감시 경로만을 테스트할 때 걸리는 시간은 RRT는 0.2초, DEL은 0.05초이다. 따라서 새로운 충돌 체크 함수와 델로네 로드맵을 이용한 DEL은 개발자가 게임요소들을 변경한 후 그에 따른 플레이어 변화를 실시간으로 분석하고 조정하기에 적합함을 알 수 있다.
RRT는 자유영역 어디에나 수많은 샘플링을 통해 경로 탐색할 수 있으므로, 적은 개수의 정점을 가진 델로네 로드맵 위에서만 경로 탐색을 하는 DEL에 비해 언제나 높은 성공률을 보일 수밖에 없다. 그러나, 80개의 감시 경로 중 상대적으로 난이도가 높은 감시 경로들에 대해서는 둘 다 낮은 성공률을, 난이도가 낮은 감시 경로들에 대해서는 둘 다 높은 성공률을 보인다는 것을 보여야 한다. 여기서는 통계학에서 흔히 쓰이는 두 가지 상관계수를 조사한다.
이러한 기능은 디자이너가 레벨을 제작하는데 많은 편의성과 유용성을 제공할 것이다. 둘째, 플레이어의 다양한 경로들을 생성하고 시뮬레이션하는 데 사용되는 두 가지 주요 함수들 - 충돌 체크 함수 및 RRT-기반 경로 탐색 함수 - 을 새로운 충돌 체크 함수과 델로네 로드맵(Delaunay Roadmap)-기반 깊이 우선 탐색 함수로 대체하여 시뮬레이션 속도를 크게 향상시킬 수 있다. 2장에서는 기존 연구를 좀 더 자세히 소개하고, 3장과 4장에서는 두 가지 개선사항을 구체적으로 기술한 뒤, 실험을 통해 검증한다.
RRT는 수많은 샘플링을 통해 경로 탐색의 성공률을 높이지만, 로드맵을 사용하는 DEL에 비해 많은 시간을 소모한다. 또한, 경로 탐색에서 단위 연산으로 기능하는 충돌 체크 함수가 효율적으로 구현되어 플레이어 시뮬레이션의 속도가 크게 향상되었음을 확인할 수 있다. [Table 4]는 [Table 2, 3]의 실험에서 80개 경로에 대한 시뮬레이션을 수행하는데 걸린 시간(50회 시행한 평균값)이다.
[Table 2, 3]은 지도 1, 2에 대한 RRT 성공률과 DEL 성공률 간의 스피어만 상관계수와 피어슨 상관계수를 나타낸다. 스피어만 상관계수를 통해 두 성공률 간에 순위관계가 비교적 일치함을 알 수 있고, 피어슨 상관계수는 이들 간에 선형관계 또한 강함을 보여준다.
후속연구
향후 연구방향으로서, 디자이너가 입력한 지점들을 포함할 뿐만 아니라 각 지점들에서 주어진 난이도를 만족하는 감시 경로들만을 추천하는 방법을 개발하는 연구와, 시뮬레이션 결과로부터 유의미한 통계 및 자료를 출력해 주는 방법에 대한 연구 등이 있다.
질의응답
핵심어
질문
논문에서 추출한 답변
RRT알고리즘은 무엇인가?
스텔스 게임 레벨 디자인 툴은 Tremblay와 공저자들에 의해 제작, 연구되었는데[1,2,3,4,5], RRT 알고리즘을 이용, 다수의 플레이어의 행동을 시뮬레이션하여 레벨을 분석할 수 있도록 Unity 기반으로 제작되었다. RRT(Rapidly-exploring Random Tree) 알고리즘은 LaValle[6]에 의해 제안된 로보틱스 분야의 대표적인 경로 탐색 방법이다. 한 쌍의 출발점과 도착점에 대해 무작위 샘플링을 통해 경로를 확장하며, 다수 유저들의 움직임을 생성하고 시뮬레이션하는 데 적합하지만, 수많은 무작위 샘플링과 최단 거리 이웃탐색 때문에 속도가 느리다는 단점이 있다[7].
스텔스 게임이란?
스텔스 게임이란 FPS(First-Person Shooter) 게임 장르의 한 분야로서 대규모 전투보다는 은신하여 비밀공작, 암살 등의 특수목적을 달성하는 게임을 말한다. 레벨 디자이너는 플레이어가 재미와 성취감을 느낄 수 있도록 다양한 난이도의 게임환경(레벨)을 제작하는데, 경비병의 감시 경로나 속도, 장애물 위치 등이 난이도 조절의 주요 요소이다.
스텔스 게임의 레벨 분석 툴 개선사항에 대해 연구한 것은?
본 논문에서는 Tremblay 등이 Unity를 이용해서 개발한 스텔스 게임의 레벨 분석 툴에 대해 두 가지 개선사항을 연구했다. 첫째는 디자이너가 몇 개의 지점을 입력하면 이 지점들을 포함하는 흥미로운 경비병의 감시 경로를 난이도별로 추천해주는 기능을 추가해 레벨 제작을 돕는 툴로서의 유용성과 편의성을 높였고, 둘째는 기존의 충돌 체크 함수 및 RRT-기반 경로 탐색 함수를 새로운 충돌 체크 함수와 델로네 로드맵 기반 경로 탐색 함수로 대체하여 시뮬레이션 속도를 크게 향상시켰다.
참고문헌 (9)
J. Tremblay, P. A. Torres, N. Rikovitch, and C. Verbrugge, "An exploration tool for predicting stealthy behaviour", Proc. of the 2013 AIIDE Workshop on Articial Intelligence in the Game Design Process, pp.34-40, 2013.
J. Tremblay, P. A Torres, and C.Verbrugge, "An algorithmic approach to analyzing combat and stealth games", Proc. of the 2014 IEEE Conference on Computational Intelligence and Games (CIG), pp.1-8, 2014.
J. Tremblay, P. A. Torres, and C. Verbrugge, "Measuring Risk in Stealth Games", Proc. of the 9th International Conference on Foundations of Digital Games (FDG), 2014.
Q. Xu, J. Tremblay, and C. Verbrugge, "Procedural Guard Placement for Stealth Games", Proc. of the 5th workshop on Procedural Content Generation (PCG), 2014.
Q. Xu, J. Tremblay, and C. Verbrugge, "Generative Methods for Guard and Camera Placement in Stealth Games", Proc. of the Tenth Annual AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment (AIIDE), 2014.
S. M. LaValle, "Rapidly-exploring random trees: A new tool for path planning.", Technical Report No. 98-11, October 1998.
H. Choset et al, "Principles of Robot Motion: Theory, Algorithms, and Implementations", MIT Press, Boston, MA, 2005.
Y. Shi and R. Crawfis, "Optimal Cover Placement against Static Enemy Positions", Proc. of the 8th International Conference on Foundations of Digital Games (FDG), pp. 109-116, 2013.
J. O'Rourke, "Computational geometry in C", Cambridge university press, 1998.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.