최근에는 사용자들이 좀 더 정교하고 복잡한 게임 인공지능을 기대하기 때문에, 많은 연구자나 개발자들은 인공지능 LOD 기법에 더 많은 관심을 갖게 되었다. 하지만, 전통적인 기하 LOD와는 달리, 기존의 인공지능 LOD 기법은 제한된 범위밖에 활용되지 못한다. 이에 본 논문에서는 게임 객체를 제어하기 위한 수단으로 계층적 상태 기계와 Lua스크립트 언어를 사용하는 인공지능 LOD 기법을 제안하고 있다. 제안된 접근 방식을 이용하면, LOD를 위한 다단계의 인공지능 모델을 쉽게 도출할 수 있으며 상태기계를 직접 하드 코딩하지 않고 다양한 객체를 설계할 수 있다. 더불어, 제안된 기법의 효용성을 보여주기 위해, 프로토타입 엔진을 이용하여 수행한 성능 시험 결과도 보여 주고 있다.
최근에는 사용자들이 좀 더 정교하고 복잡한 게임 인공지능을 기대하기 때문에, 많은 연구자나 개발자들은 인공지능 LOD 기법에 더 많은 관심을 갖게 되었다. 하지만, 전통적인 기하 LOD와는 달리, 기존의 인공지능 LOD 기법은 제한된 범위밖에 활용되지 못한다. 이에 본 논문에서는 게임 객체를 제어하기 위한 수단으로 계층적 상태 기계와 Lua 스크립트 언어를 사용하는 인공지능 LOD 기법을 제안하고 있다. 제안된 접근 방식을 이용하면, LOD를 위한 다단계의 인공지능 모델을 쉽게 도출할 수 있으며 상태기계를 직접 하드 코딩하지 않고 다양한 객체를 설계할 수 있다. 더불어, 제안된 기법의 효용성을 보여주기 위해, 프로토타입 엔진을 이용하여 수행한 성능 시험 결과도 보여 주고 있다.
Many researchers and developers take a greater interest on the LOD AI techniques as users demand more elaborate and sophisticated game AI in recent years. However, contrary to the traditional geometry LOD, existing LOD AI techniques can be used only to a limited extent. Therefore, in this paper, I p...
Many researchers and developers take a greater interest on the LOD AI techniques as users demand more elaborate and sophisticated game AI in recent years. However, contrary to the traditional geometry LOD, existing LOD AI techniques can be used only to a limited extent. Therefore, in this paper, I propose an LOD AI technique, which uses HSM(Hierarchical State Machine) and the Lua script language as the method to control game objects. Using the proposed approach, we can easily produce multilevel AI models for LOD and design various objects without hard-coding state machines. Moreover, in order to show the effectiveness of the presented technique, this paper exemplifies the results of the efficiency test through the prototype engine.
Many researchers and developers take a greater interest on the LOD AI techniques as users demand more elaborate and sophisticated game AI in recent years. However, contrary to the traditional geometry LOD, existing LOD AI techniques can be used only to a limited extent. Therefore, in this paper, I propose an LOD AI technique, which uses HSM(Hierarchical State Machine) and the Lua script language as the method to control game objects. Using the proposed approach, we can easily produce multilevel AI models for LOD and design various objects without hard-coding state machines. Moreover, in order to show the effectiveness of the presented technique, this paper exemplifies the results of the efficiency test through the prototype engine.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
본 연구에서는 위와 같이 다중 계층으로 구성된 HSM을 C/C++로 구현된 네이티브 코드를 수정할 필요 없이 Lua 스크립트 파일의 추가만으로도 쉽게 구현할 수 있도록 하였다.
본 연구에서는 이 접근 방법을 더욱 확장하여 평면적인 FSM뿐만 아니라 계층적인 구조를 갖는 HSM 구조 전체를 스크립트 언어로 작성할 수 있도록 하였다. 즉, HSM의 시뮬레이션을 위한 핵심 클래스만 C++로 하드 코딩하고, HSM의 전체적인 계층 구조 및 각 계층에서 노드를 구성하고 있는 FSM을 스크립트 언어로 구현하는 방식을 사용하였다.
이에 본 논문에서는 계층적인 상태 기계인 HSM(Hierarchical State Machine) 기반의 인공 지능 LOD 기법을 소개하고자 한다. 제한하는 방법은 인공 지능 뿐만 아니라 LOD 모델과 관련된 부분도 모두 스크립트 언어로 노출하여 LOD 정책 결정 및 디버깅하는데 걸리는 시간을 단축시킬 수 있으며, 자연스러운 다단계의 LOD 모델이 가능하여 popping 효과를 줄이면서도 성능을 최적화할 수 있다.
가설 설정
실험에서는 LOD가 제대로 작동하는지 확인하기 위해 가상의 게임 세계를 실제 디바이스의 화면보다 25배 큰 사각형 영역으로 정의하였다. 만약 2차원 스크롤이 가능한 RPG 게임이라면, 원래는 커다란 2차원 세계를 사용자가 이동하면서 플레이하는 것이 보통이지만, 실험에서는 가상 세계의 정 가운데에 고정되어 있다고 가정하였다.
제안 방법
본 논문에서는 계층적 상태 기계인 HSM을 이용하여 게임 객체의 인공지능 LOD가 가능하다는 것을 보여주었다. HSM의 특성인 계층적 구조를 이용하여, 보다 복잡한 시뮬레이션이 필요한 경우에는 HSM의 깊은 레벨의 노드에 있는 상태 기계까지 시뮬레이션하고, 그렇지 않은 경우엔 객체의 LOD 레벨과 HSM 각 노드의 레벨을 비교하여 상태 기계 시뮬레이션 여부를 결정하였다.
더불어, 인공지능 구현에 필요한 시스템 부하를 시뮬레이션하기 위한 게임 객체의 액션 함수가 필요하기 때문에, Cocos2d-x에서 제공하는 기능을 이용하여 6가지의 액션 함수를(이동, 회전, 깜박임, 투명도 변화, 색상 변화 등) 구현하였다. HSM이 복잡해지면 동시에 수행해야할 함수가 6개 이상이 될 수도 있는데, 이 경우에는 랜덤 함수를 이용하여 5퍼센트의 확률로 다음 상태로의 전이가 발생하도록 구현하였다. 그리고 공평한 실험을 위하여 각 상태에서 실행할 액션 함수는 현재 실행되고 있지 않은 액션 함수 중에서 랜덤하게 선택하도록 하였다.
LOD 기법을 사용한 효과가 있는지 여부를 확인하기 위하여 Box라는 객체의 수를 점점 늘여 가며 실험을 수행하였다. 실험 환경은 iPhone4이며, 처음 200 프레임의 SPF(Seconds per Frame)값들의 평균을 계산하였다.
HSM이 복잡해지면 동시에 수행해야할 함수가 6개 이상이 될 수도 있는데, 이 경우에는 랜덤 함수를 이용하여 5퍼센트의 확률로 다음 상태로의 전이가 발생하도록 구현하였다. 그리고 공평한 실험을 위하여 각 상태에서 실행할 액션 함수는 현재 실행되고 있지 않은 액션 함수 중에서 랜덤하게 선택하도록 하였다.
원래, 게임 객체를 위한 LODAIObject라는 최상위 레벨의 클래스는 HSM의 상태에 해당하는 State라는 클래스로부터 상속받게 되어 있지만, 실험을 위하여 Cocos2d-x에서 제공하는 CCSprite라는 스프라이트 클래스도 다중 상속받도록 구현하였다. 더불어, 인공지능 구현에 필요한 시스템 부하를 시뮬레이션하기 위한 게임 객체의 액션 함수가 필요하기 때문에, Cocos2d-x에서 제공하는 기능을 이용하여 6가지의 액션 함수를(이동, 회전, 깜박임, 투명도 변화, 색상 변화 등) 구현하였다. HSM이 복잡해지면 동시에 수행해야할 함수가 6개 이상이 될 수도 있는데, 이 경우에는 랜덤 함수를 이용하여 5퍼센트의 확률로 다음 상태로의 전이가 발생하도록 구현하였다.
(그림 5)에서 보여준 전체적인 HSM을 트리 구조로 표현하면 (그림 6)과 같다. 본 연구는 그림에서와 같이 계층 구조의 깊이에 따라 LOD 레벨을 결정하도록 하였다. Lua 스크립트로부터 자식 노드인 새로운 FSM을(State는 해당하지 않음) 발견하면, 추가되는 FSM은 자동으로 LOD 레벨이 증가하도록 하였다.
본 연구에서 모든 FSM은 반드시 “initial”로 끝나는 상태를 하나 갖게 하였는데, 이는 (Figure 1)의 HSM에서 볼 수 있는 검은색 동그라미를 나타내는 것으로 해당 FSM이 시작되었을 때의 초기상태를 말한다.
원래, 게임 객체를 위한 LODAIObject라는 최상위 레벨의 클래스는 HSM의 상태에 해당하는 State라는 클래스로부터 상속받게 되어 있지만, 실험을 위하여 Cocos2d-x에서 제공하는 CCSprite라는 스프라이트 클래스도 다중 상속받도록 구현하였다. 더불어, 인공지능 구현에 필요한 시스템 부하를 시뮬레이션하기 위한 게임 객체의 액션 함수가 필요하기 때문에, Cocos2d-x에서 제공하는 기능을 이용하여 6가지의 액션 함수를(이동, 회전, 깜박임, 투명도 변화, 색상 변화 등) 구현하였다.
위 HSM이 구동되면 게임 엔진의 메인 루프에서는 “box”라는 클래스로부터 생성된 모든 객체의 LOD 레벨을 매 프레임마다 갱신하며, 각 객체는 HSM 트리를 루트 노드로부터 순회하면서 자신의 LOD 레벨과 자식 노드인 FSM의 레벨을 비교하여 순회할 것인지 여부를 결정하면 된다.
본 연구에서는 이 접근 방법을 더욱 확장하여 평면적인 FSM뿐만 아니라 계층적인 구조를 갖는 HSM 구조 전체를 스크립트 언어로 작성할 수 있도록 하였다. 즉, HSM의 시뮬레이션을 위한 핵심 클래스만 C++로 하드 코딩하고, HSM의 전체적인 계층 구조 및 각 계층에서 노드를 구성하고 있는 FSM을 스크립트 언어로 구현하는 방식을 사용하였다. 이로 인하여 복잡한 HSM을 직접 하드 코딩할 필요가 없으므로, HSM의 단점이라고 할 수 있는 구현과 디버깅의 어려움을 해소할 수 있으며, 더불어 LOD 모델의 성능 평가 및 조율에 소모되는 시간과 경비를 절약할 수 있다.
대상 데이터
LOD 기법을 사용한 효과가 있는지 여부를 확인하기 위하여 Box라는 객체의 수를 점점 늘여 가며 실험을 수행하였다. 실험 환경은 iPhone4이며, 처음 200 프레임의 SPF(Seconds per Frame)값들의 평균을 계산하였다. 위의 <표 1>과 (그림 9)가 결과를 보여주고 있다.
성능/효과
개발된 프로토타입 엔진을 이용하여 실험한 결과, 스크립트 언어의 사용 및 HSM 자체의 시뮬레이션에 필요한 오버헤드가 있음에도 불구하고, LOD 기능을 사용하였을 경우 더욱 많은 객체를 안전하게 시뮬레이션할 수 있음을 알 수 있었다.
(그림 9)의 그래프를 보면 대부분의 모바일 게임에서 권장하는 60 FPS(Frames Per Second)를 얻기 위해서는, LOD를 사용하지 않았을 경우엔 10개 이하의 객체만 생성해야 하지만, LOD를 사용한 경우 약 45개까지도 안전하게 생성이 가능한 것을 알 수 있다. 그리고 30 FPS를 얻기 위해서는 LOD를 사용하지 않았을 경우 약 70개 이하만 생성 가능하지만, LOD를 사용한 경우 100개 이상의 객체도 시뮬레이션이 가능한 것을 알 수 있다.
본 논문에서는 계층적 상태 기계인 HSM을 이용하여 게임 객체의 인공지능 LOD가 가능하다는 것을 보여주었다. HSM의 특성인 계층적 구조를 이용하여, 보다 복잡한 시뮬레이션이 필요한 경우에는 HSM의 깊은 레벨의 노드에 있는 상태 기계까지 시뮬레이션하고, 그렇지 않은 경우엔 객체의 LOD 레벨과 HSM 각 노드의 레벨을 비교하여 상태 기계 시뮬레이션 여부를 결정하였다.
본 연구에서는 제안된 LOD 기법의 효용성을 검증하기 위해 프로토타입 엔진을 개발하였는데, 표준 C++언어와 Lua API로만 되어 있기 때문에 어떤 게임엔진에서도 쉽게 사용될 수 있도록 하였다.
위 그림은 LODAIObject의 서브클래스인 Box클래스의 객체를 여러 개 생성하여 시뮬레이션하고 있는 모습이다. 실험에서는 LOD가 제대로 작동하는지 확인하기 위해 가상의 게임 세계를 실제 디바이스의 화면보다 25배 큰 사각형 영역으로 정의하였다. 만약 2차원 스크롤이 가능한 RPG 게임이라면, 원래는 커다란 2차원 세계를 사용자가 이동하면서 플레이하는 것이 보통이지만, 실험에서는 가상 세계의 정 가운데에 고정되어 있다고 가정하였다.
군집 시뮬레이션을 위한 LOD 기법과는 달리, 복잡한 단일 객체의 자연스러운 LOD를 위한 시도도[7] 있었다. 이 연구에서는 식물의 특성을 고려하여 여러 단계의 LOD 모델을 미리 계산하여 만들었기 때문에 모델간 전환에서 발생하는 popping 효과를 최소화할 수 있었다.
이에 본 논문에서는 계층적인 상태 기계인 HSM(Hierarchical State Machine) 기반의 인공 지능 LOD 기법을 소개하고자 한다. 제한하는 방법은 인공 지능 뿐만 아니라 LOD 모델과 관련된 부분도 모두 스크립트 언어로 노출하여 LOD 정책 결정 및 디버깅하는데 걸리는 시간을 단축시킬 수 있으며, 자연스러운 다단계의 LOD 모델이 가능하여 popping 효과를 줄이면서도 성능을 최적화할 수 있다.
질의응답
핵심어
질문
논문에서 추출한 답변
알고리즘의 최적화가 충분히 이루어진 단계에 이르면 사용해야 하는 기법은 무엇인가?
하지만, 충분히 최적화된 알고리즘은 더 이상 개선하기가 어려울 뿐만 아니라 개선하기 위한 노력에 비하여 얻는 이득이 매우 적기 마련이다. 이 단계에 이르면, 최적화 대신 단순화(simplification) 기법을 이용해야 한다.
실시간 처리가 중요한 컴퓨터 게임에서 항상 신경써야 하는 것은 무엇인가?
컴퓨터 게임은 실시간 처리가 매우 중요하므로 컴퓨팅 자원의 최적화에 항상 신경 써야 한다. 특히 스마트 폰과 같은 이동 단말기에서는 더욱 중요하다.
LOD(Level Of Detail)는 어떤 기법인가?
게임과 같이 실시간 렌더링이 필요한 분야에서 적극 활용되고 있는 LOD(Level Of Detail)는 카메라(사용자)로부터 멀리 떨어진 물체의 기하모델 상세도를 줄이는 방식으로 제한된 자원을 절약할 수 있는 대표적인 단순화 기법이다. 이 LOD 기법은 [1]의 "점진적인 메쉬(progressive meshes)"와 같이 임의의 복잡도를 갖는 연속적인 메쉬의 생성도 가능해졌으며, [2]에서는 시점의 방향에 따라 최적화된 메쉬의 생성 방법을 제안하기도 하였다.
참고문헌 (11)
H. Hoppe, "Progressive meshes," Proceedings of the 23rd annual conference on Computer Graphics and interactive techniques, pp. 99-108, 1996.
H. Hoppe, "Smooth View-Dependent Level-of-Detail Control and Its Application to Terrain Rendering," Ninth IEEE Visualization, pp. 35-42, 1998.
D. A. Carlson and J. K. Hodgins, "Simulation Levels of Detail for Real-time Animation," Proceedings of Graphics Interface 1997, pp. 1-8, 1997.
S. Chenney.: Simulation Level-Of-Detail. In: GDC (2001), http://www.cs.wisc.edu/-schenney/research/culling/chenney-gdc2001.pdf [6-3-2007]
C. O'Sullivan et al., "Levels of Detail for Crowds and Groups," Computer Graphics Forum, 21(4), pp. 733-741, 2002.
C. Brom, O. Sery, and T. Poch, "Simulation Level of Detail for Virtual Humans," Lecture Notes in Computer Science, 4277, 1-14, 2007.
J. Beaudoin and J. Keyser, "Simulation levels of detail for plant motion," Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation, pp. 297-304, 2004.
D. Harel, On Visual Formalism, Communication of ACM, 31(5), pp. 514-530, 1988.
J. Seo, G. J. Kim, and K. C. Kang, "Levels of Detail(LOD) Engineering of VR Objects," Proceedings of the ACM symposium on Virtual reality software and technology, pp. 104-110, 1999.
J. Seo and J. Youn, "Study on Statecharts-based Progressive Behavior LOD Model for Virtual Objects," Journal of Digital Contents Society, 12(2), pp. 185 -194, 2011.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.