[논문]지능형 NPC의 행동 메커니즘에 따른 계층적 유한 상태 기계와 행동 트리의 효율성 평가

이정민; 김정이

doi:10.7236/jiibc.2024.24.2.113

지능형 NPC의 행동 메커니즘에 따른 계층적 유한 상태 기계와 행동 트리의 효율성 평가
Efficiency Evaluation of Hierarchical Finite-State Machines and Behavior Trees according to Behavior Mechanism of Intelligent NPCs

The journal of the institute of internet, broadcasting and communication : JIIBC, v.24 no.2, 2024년, pp.113 - 118

이정민 (성결대학교 미디어소프트웨어학과) , 김정이 (성결대학교 미디어소프트웨어학과)

초록
AI-Helper

본 연구에서는 지능형 NPC의 행동을 효과적으로 구현하기 위한 두 가지 주요 구조, 계층적 유한 상태 기계(Hierarchical Finite State Machine, HFSM)와 행동 트리(Behavior Tree)의 구조를 설계하고 실험용 게임을 제작하여 비교 및 분석하였다. 계층적 유한 상태 기계는 복잡한 상호작용 중심의 동작에 적합하여 상태 변화와 그 전이가 중요한 행동 메커니즘에서 효율적이고, 행동 트리는 동적 환경에서의 수정과 확장이 용이하여 다양한 조건 하에서의 동적반응이 중요한 행동 메커니즘에서 효율적이라는 분석 결과를 도출하였다. 이 두 구조를 유니티 엔진을 활용하여 실험적으로 적용하고 그 효율성을 검증하였다. 본 연구는 기본적인 구조 설계에 초점을 맞췄으며, 추후 개발 예정인 액션 어드벤쳐 탈출 게임에 이 구조를 적용할 예정이다. 본 연구의 결과는 게임 개발자들이 지능형 NPC를 효율적으로 구현하는데 도움을 주며, 게임의 퀄리티와 플레이어 만족도 향상에 기여할 것으로 기대된다.

Abstract ▼ AI-Helper

In this study, we designed and analyzed two main structures for effectively implementing the behavior of intelligent NPCs the Hierarchical Finite State Machine (HFSM) and the Behavior Tree, by creating experimental games. The HFSM was found to be efficient for complex interaction-centered actions where state changes and transitions are crucial, while the Behavior Tree was effective in dynamic environments where ease of modification and expansion are required for dynamic responses under various conditions. These structures were experimentally applied using the Unity engine to verify their efficiency. This study focused on the basic structure design and plans to apply these structures to an upcoming action-adventure escape game. The results of this research are expected to assist game developers in efficiently implementing intelligent NPCs, thereby contributing to the improvement of game quality and player satisfaction.

주제어

표/그림 (8)

그림 그림 1. 지능형 NPC의 계충적 유한 상태 기계 구조 설계 Fig. 1. Hierarchical Finite State Machine Structure Design for Intelligent NPCs
그림 그림 2. 지능형 NPC의 행동 트리 구조 설계 Fig. 2. Behavior Tree Structure Design for Intelligent NPCs
그림 그림 3. HFSM 구조 실험용 게임 화면 Fig. 3. Game Screen for HFSM Structure Experiment
그림 그림 4. HFSM 구조 실험용 게임의 상태 변환 화면 Fig. 4. State Transition Screen of the Game for HFSM Structure Experiment
그림 그림 5. 행동 트리 구조 실험용 게임 화면 Fig. 5. Game Screen for Behavior Tree Structure Experiment
그림 그림 6. 행동 트리 구조 노드의 상태 Fig. 6. Node State for Behavior Tree Structure Experiment
표 표 1. HFSM의 실험 분석 결과 Table 1. Experimental Analysis Results of HFSM
표 표 2. BT의 실험 분석 결과 Table 2. Experimental Analysis Results of BT

AI 본문요약
AI-Helper

문제 정의

본 연구는 지능형 NPC의 행동을 효과적으로 구현하기 위해 계층적 유한 상태 기계(Hierarchical Finite State Machine, HFSM)와 행동 트리(Behavior Tree)의 설계와 검증을 목표로 한다. 연구 방법은 다음과 같다.
본 연구의 목적은 지능형 NPC의 동작을 계층적 유한 상태 기계(HFSM)와 행동 트리(Behavior Tree)를 이용하여 모델링하고 이를 비교하는 것이었다. 유니티 엔진을 활용해 두 구조를 실험하며 다음과 같은 주요 결과 및 분석을 얻었다.

제안 방법

본 연구에서는 네비게이션 매쉬를 이용하여 지능형 NPC가 플레이어를 추적하기 위한 시스템을 구축하였고, 계층적 유한 상태 기계와 행동 트리 두 가지 구조를 통해 지능형 NPC 동작을 설계하고, 유니티 엔진을 활용한 실험용 게임에서 구현 및 비교 분석하였다. HFSM 실험에서는 플레이어와의 상호작용 중심의 동작, 특히 발견, 추격, 공격 등의 주요 상태 전환을 중점적으로 관찰했으며, 행동 트리 실험에서는 부모-자식 노드 형태로 구성된 복잡한 행동 패턴과 조건 기반의 동작 판단을 중심으로 분석하였다.
첫째, HFSM과 행동 트리의 구조 설계 후, 유니티 엔진을 사용하여 PC 콘솔 게임 기반의 실험용 게임을 개발한다. 둘째, HFSM은 상태와 전환을 기반으로 한 계층적 구조에, 행동 트리는 조건 반환 결과에 따른 나무 형식 구조에 초점을 맞춰 NPC를 설계 및 개발한다. 셋째, 두 구조의 효율성과 적용성을 비교 분석한다.
비디오 게임 내 지능형 NPC는 게임 경험을 향상하는 중요한 역할을 한다. 따라서, 본 연구에서는 지능형 NPC의 행동을 효과적으로 구현하기 위한 두 가지 주요 구조 계층적 유한 상태 기계(Hierarchical Finite State Machine)와 행동 트리(Behavior Tree)를 설계하고 각 구조의 성능과 효율성을 비교 및 분석에 중점을 두었다. 계층적 유한 상태 기계는 상태 중심의 구조를 확장하여 코드의 재사용성을 높이는 반면, 행동 트리는 노드 기반의 구조로 확장성과 직관성을 갖는다.
본 연구에서는 네비게이션 매쉬를 이용하여 지능형 NPC가 플레이어를 추적하기 위한 시스템을 구축하였고, 계층적 유한 상태 기계와 행동 트리 두 가지 구조를 통해 지능형 NPC 동작을 설계하고, 유니티 엔진을 활용한 실험용 게임에서 구현 및 비교 분석하였다. HFSM 실험에서는 플레이어와의 상호작용 중심의 동작, 특히 발견, 추격, 공격 등의 주요 상태 전환을 중점적으로 관찰했으며, 행동 트리 실험에서는 부모-자식 노드 형태로 구성된 복잡한 행동 패턴과 조건 기반의 동작 판단을 중심으로 분석하였다.
본 연구에서는 두 개의 FSM으로 구성되어 계층적으로 표현한 기본적인 HFSM 구조로 설계되었다. 이는 주요 동작을 정의하는 Root FSM과 전투 동작을 상세하게 나타내는 Fight FSM, 두 개의 FSM으로 구성된다.
둘째, HFSM은 상태와 전환을 기반으로 한 계층적 구조에, 행동 트리는 조건 반환 결과에 따른 나무 형식 구조에 초점을 맞춰 NPC를 설계 및 개발한다. 셋째, 두 구조의 효율성과 적용성을 비교 분석한다. 이 과정에서 유니티 엔진의 네비게이션 메쉬 기능을 활용하는데 이는, 넓은 가상공간에서 길을 찾는 것은 어렵기 때문에 지형지물의 메쉬 형태의 데이터를 생성하여 NPC가 이동할 수 있는 구역을 시각적으로 나타내주는 기능이다.
이 과정에서 유니티 엔진의 네비게이션 메쉬 기능을 활용하는데 이는, 넓은 가상공간에서 길을 찾는 것은 어렵기 때문에 지형지물의 메쉬 형태의 데이터를 생성하여 NPC가 이동할 수 있는 구역을 시각적으로 나타내주는 기능이다. 이를 활용해 NPC의 효과적인 길 찾기 시스템을 개발하고, 실험용 게임에 적용해 각 구조의 성능을 평가함으로써 지능형 NPC의 움직임 제어에 관한 효율적인 구조를 탐구하고 분석하고자 한다.
연구 방법은 다음과 같다. 첫째, HFSM과 행동 트리의 구조 설계 후, 유니티 엔진을 사용하여 PC 콘솔 게임 기반의 실험용 게임을 개발한다. 둘째, HFSM은 상태와 전환을 기반으로 한 계층적 구조에, 행동 트리는 조건 반환 결과에 따른 나무 형식 구조에 초점을 맞춰 NPC를 설계 및 개발한다.

대상 데이터

본 연구에서 설계된 행동 트리 구조는 대기 노드와 추적 노드에 대한 하위 액션 노드들로 구성되어 있다. 행동 트리에서 노드의 실행 순서는 위에서 아래로, 왼쪽에서 오른쪽으로 실행된다.

성능/효과

Unity의 ML-Agent를 사용하여 목표 추적 AI를 개발하고, 강화학습으로 다양한 환경에서의 효율성을 검증하고 몰입도를 높일 수 있는 방법론[4]과 NavMesh 기능과 헤비사이드 계단 함수를 통해 가중치를 계산하여 NPC를 제어하는 기법[5] 등 게임 내 다양한 상황에 유연하게 대응할 수 있는 지능형 NPC의 구현은 게임 개발의 중요한 연구 주제가 되었다.
그 결과, 두 기법 모두 각자의 장점을 지니며, 각각의 상태가 자연스럽게 전이되어 게임 개발 상황에 따라 최적화된 기법을 선택할 수 있음을 확인하였다. 특히, 본 연구에서 사용된 실험 환경은 이러한 결론을 뒷받침하는 근거로 제공된다.
이는 실시간 NPC 행동 조절과 다양한 조건에 대응하는 능력을 향상시켰다. 따라서, 프로젝트의 특성과 요구사항에 따라 HFSM이나 행동 트리 중 적합한 모델링 기법을 선택하는 것이 중요하다는 결론을 얻었다. 복잡한 동작을 모델링할 때는 HFSM이, 동적 환경에서의 빠른 수정과 확장을 원할 때는 행동 트리가 더 적합할 수 있다.
HFSM은 상위 및 하위 동작을 구분하는 데 강점을 보였으며, 계층적 구조를 통해 복잡한 동작 패턴을 명확하게 표현하여 하위수준의 동작 흐름과 하위 수준의 세부 동작을 명확히 분리하게 했다. 반면, 행동 트리는 부모-자식 노드 구조를 통해 우선순위나 조건에 따른 행동을 명확하게 표현하는 데 유용했으며, NPC의 의사 결정 과정과 노드들을 시각적으로 설계할 수 있는 장점이 있었다. 또한, 노드 간의 명확한 관계와 조건은 빠른 수정과 확장을 가능하게 했다.
따라서, 프로젝트의 특성과 요구사항에 따라 HFSM이나 행동 트리 중 적합한 모델링 기법을 선택하는 것이 중요하다는 결론을 얻었다. 복잡한 동작을 모델링할 때는 HFSM이, 동적 환경에서의 빠른 수정과 확장을 원할 때는 행동 트리가 더 적합할 수 있다.
본 연구와 그 결과물인 두 구조에 대한 비교 및 효율성 평가의 의의는, 게임 개발자들이 지능형 NPC를 구현할 때 효율적인 방법을 선택할 수 있게 한다는 점에서 찾을 수 있다. 또한, 게임 인공지능 분야에서의 기술적인 발전을 바탕으로, 플레이어들에게 더욱 실감 나고 동적인 게임 환경을 제공함으로써, 전반적인 게임의 퀄리티와 플레이어의 만족도를 향상할 수 있는 자료로서의 의미가 있다.
계층적 유한 상태 기계는 상태 중심의 구조를 확장하여 코드의 재사용성을 높이는 반면, 행동 트리는 노드 기반의 구조로 확장성과 직관성을 갖는다. 즉, 계층적 유한 상태 기계는 복잡한 상호작용 중심의 동작에 적합하여 상태 변화와 그 전이가 중요한 행동 메커니즘에서 효율적이고, 행동 트리는 동적 환경에서의 수정과 확장이 용이하여 다양한 조건 하에서의 동적 반응이 중요한 행동 메커니즘에서 효율적이라는 분석 결과를 도출하였다.

후속연구

향후 연구를 통해 기대되는 결과는 지능형 NPC의 더욱 다양하고 복잡한 행동 패턴 구현이며, 이를 통해 플레이어의 게임 경험을 향상하는 데 큰 기여를 할 것으로 기대된다. 더 나아가, 추후 개발 예정인 액션 어드벤쳐 탈출 게임에서 지능형 NPC의 동적 행동을 구현하기 위해 적용하고, 특정 상황에 맞게 해당 메커니즘에 맞는 구조를 적용해 보다 효율적인 지능형 NPC의 움직임의 구현을 시도할 예정이다.
특히, 본 연구에서 사용된 실험 환경은 이러한 결론을 뒷받침하는 근거로 제공된다. 따라서, 게임 개발자나 연구자들은 이 연구의 결과를 기반으로 지능형 NPC의 동작을 효율적으로 모델링하는 데 필요한 기법을 선택할 수 있을 것이다.
하지만 본 연구에는 아직 지능형 NPC의 행동을 구현한 상태 및 행동 노드들이 기본적인 구조들로만 설계하였다는 한계가 있으므로 향후 연구에서는 더욱 다양한 상태 전이와 행동 노드들로 구성하여 복잡한 환경에서의 움직임을 구현해 추가적인 분석을 할 것이다. 또한, 두가지 기법에 초점을 맞추어 분석하였기에, 다른 인공지능 기술들과의 통합 및 비교는 제한적이었고, 구체적인 게임 시나리오나 다양한 상호작용 따른 분석은 이루어지지 않았다. 이러한 한계점을 극복하기 위한 추가 연구가 필요하다.
또한, 게임 인공지능 분야에서의 기술적인 발전을 바탕으로, 플레이어들에게 더욱 실감 나고 동적인 게임 환경을 제공함으로써, 전반적인 게임의 퀄리티와 플레이어의 만족도를 향상할 수 있는 자료로서의 의미가 있다. 이 연구는 비디오 게임 산업에서의 지능형 NPC의 중요성과 그 구현 방법을 이해하여, 유사한 기능을 설계, 개발하는 게임 개발자들에게 도움이 될 것으로 예상된다.
또한, 두가지 기법에 초점을 맞추어 분석하였기에, 다른 인공지능 기술들과의 통합 및 비교는 제한적이었고, 구체적인 게임 시나리오나 다양한 상호작용 따른 분석은 이루어지지 않았다. 이러한 한계점을 극복하기 위한 추가 연구가 필요하다. 향후 연구를 통해 기대되는 결과는 지능형 NPC의 더욱 다양하고 복잡한 행동 패턴 구현이며, 이를 통해 플레이어의 게임 경험을 향상하는 데 큰 기여를 할 것으로 기대된다.
하지만 본 연구에는 아직 지능형 NPC의 행동을 구현한 상태 및 행동 노드들이 기본적인 구조들로만 설계하였다는 한계가 있으므로 향후 연구에서는 더욱 다양한 상태 전이와 행동 노드들로 구성하여 복잡한 환경에서의 움직임을 구현해 추가적인 분석을 할 것이다. 또한, 두가지 기법에 초점을 맞추어 분석하였기에, 다른 인공지능 기술들과의 통합 및 비교는 제한적이었고, 구체적인 게임 시나리오나 다양한 상호작용 따른 분석은 이루어지지 않았다.
이러한 한계점을 극복하기 위한 추가 연구가 필요하다. 향후 연구를 통해 기대되는 결과는 지능형 NPC의 더욱 다양하고 복잡한 행동 패턴 구현이며, 이를 통해 플레이어의 게임 경험을 향상하는 데 큰 기여를 할 것으로 기대된다. 더 나아가, 추후 개발 예정인 액션 어드벤쳐 탈출 게임에서 지능형 NPC의 동적 행동을 구현하기 위해 적용하고, 특정 상황에 맞게 해당 메커니즘에 맞는 구조를 적용해 보다 효율적인 지능형 NPC의 움직임의 구현을 시도할 예정이다.

참고문헌 (13)

Shi-Jie Sun, Seung-Keun Song, "A Study on NPC Using？ChatGpt in the Metaverse: Focusing on Facerig,"？Proceedings of the Comprehensive Korea Contents？Association Conference, pp. 359-360. May 2023.
Hyun-Su Lee, Jung-Yi Kim, "Development of Story？Recommendation through Character Web Drama？Cliche Analysis", The Journal of The Institute of？Internet, Broadcasting and Communication(JIIBC),？Vol. 23, No. 4, pp. 17-22, Aug 2023.？DOI: https://doi.org/10.7236/JIIBC.2023.23.4.17

원문보기 상세보기
Hyun-Su Kim, "Development of Reinforcement？Learning Environment for Smart Base Isolation？Control System using Unity", Journal of the Korea？Academia-Industrial cooperation Society(JKAIS), Vol.？24, No. 5 pp. 433-440, May 2023.？DOI: https://doi.org/10.5762/KAIS.2023.24.5.433

상세보기
Deok-Hyung Kim, Hyun-Jun Jung, "Performance？Analysis of Target Tracking AI based on Unity？ML-Agents", The Journal of KIIT, Vo1. 19, No. 12, pp.？19-26, Dec 2023.？DOI: https://doi.org/10.14801/jkiit.2021.19.12.19

상세보기
Jong-Hyun Kim, Soo-Kyun Kim, "Efficient Path？Tracking of Non-Player Character with Controlling？NavMesh Based on Smoothed Heaviside Step？Function", Proceedings of the Korean Society of？Computer Information Conference, Vol. 30, No. 1,？pp. 339-340, Jan 2022.
Ho-Ryul Kim, Jong-Ho Yoo, Chang-Min Han,？Syoung-Og An, Soo-Kyun Kim, "Development of？Mobile RPG using Unity 3D Engine", in Proceedings of？the Korean Society of Computer Information？Conference, Vo1. 27, No. 2, pp. 81-82, Jul 2019.
Woo-Jin Lee, "Compositional Safety Analysis for？Embedded Systems using the FSM Behavioral？Equivalence Algorithm", The KIPS Transactions : Part？D, Vol. 14, No. 6, pp. 633-640, Oct 2007.？DOI: https://doi.org/10.3745/KIPSTD.2007.14-D.6.633

원문보기 상세보기
Jun-O Choi and Hyun-Joo Park, "DEVELOPMENT OF？GAME AI USING BEHAVIOR TREE : BASED ON THE？UNITY5 ENGINE", Proceedings of the Korea？Entertainment Industry Association Conference, pp.？9-17, Jul 2018.
Kyeong-Jin Baek, "Design and Implementation of？Artificial Intelligence Agent for Real-Time Simulation？Football Game in a Mobile Environment", Proceedings？of the Korea Information Processing Society？Conference, Vo1. 23, No. 1, pp. 636-639, Apr 2016.？DOI: https://doi.org/10.3745/PKIPS.y2016m04a.636
Jae-Won Jo, Jung-Won Bang, "A study on The？Implementation of Monster AI using Finite-State？Machine", Proceedings of the Korean Society of？Computer Information Conference, Vo1. 27, No. 1,？pp. 349-350, Jan 2019
Myoun-Jae Lee, "A Proposal on Game Engine？Behavior Tree", Journal of Digital Convergence, Vol.？14, No. 8, pp. 415-421, Aug 2016.？DOI: https://doi.org/10.14400/JDC.2016.14.8.415

원문보기 상세보기
Sung-Jin Bae and Myung-Ju Kang,"Design And？Development of Game AI Using Unreal Engine 4？Behavior Tree", Proceedings of the Korea Information？Processing Society Conference, Vol. 24, No. 1, pp.？267-269, Jan 2016
Min-Ji Kwon, Jin-Sek Seo, "Game AI Agents using？Deliberative Behavior Tree based on Utility Theory",？Journal of Korea Multimedia Society, Vol. 25, No. 2,？pp. 432-439, Feb 2022.？DOI: https://doi.org/10.9717/kmms.2022.25.2.432？

원문보기 상세보기

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증