한국산학기술학회논문지 Vol. 11, No. 12 pp. 5083-5088, 2010 NPC 인공지능을위한무리짓기구현 유현지 1, 이면재 1, 김경남 2 1 백석대학교정보통신학부 2 중앙대학교첨단영상대학원 Flocking Implementation for NPC AI Hyun-ji yoo 1, Myoun-Jae Lee 1 and Kyoung-Nam Kim 2 1 Department of Information & Communication, Baekseok University 2 GSAIM, Chung-Ang University 요약무리를형성하는 NPC들의인공지능을실세계의무리짓기와유사하게구현하는것은게임의재미를증가시키는요인이될수있다. 이를위하여, 본논문에서는분석된실세계에서의물고기무리짓기의행동패턴을설계하고오우거엔진을이용하여구현한다. 구현된무리짓기의효용성을판단하기위하여실세계의물고기떼의행동패턴과비교한다. 비교결과, 구현된물고기떼의행동패턴과실세계의행동패턴은비슷함을보인다. Abstract An implementation of NPC AI(artifical intelligence) is similar with real world's flocking can increase fun factor of game. To this end, we design fish flocking patten of analyzed real world, implement using Ogre engine in this paper. To determine the usefulness of implemented fish flocking, we compare fish flocking in real world with implemented fish flocking. Implemented behavioral patterns of fish flocking show similar behavioral patterns of fish flocking in real world. Key Words : Artificial intelligence(ai), NPC flocking, NPC AI 1. 서론 우리가살고있는현세상에서는다양한동물들이무리를지어행동한다. 새무리들이일정한패턴을만들어목적지까지날아가거나, 물고기들이떼를지어다니거나, 개미들이일렬로맞추어다니거나벌들이무리를지어공격하는것등의여러동물들이떼를지어생활하고있다. 이러한실세계의무리짓기 (Flocking) 에대한연구는생물학적관점으로진행되고있다. 새가있을경우와없을경우에열대숲에서병정개미들이먹이포획양을측정하거나 [1], 병정개미들이먹이를먹을수있는세개의경로를만들어놓은후각병정개미들의움직임을살펴보거나 [2], 먹을것을제공하거나물고기의찢겨진조각을어항에던져서물고기떼에게공포감을조성하는경우등에서물고기들의무리짓기형태를분석하거나 [3], 무리들가운데정보를전달하는방법 [4] 에관한연구등이있 다. 그림 1은병정개미와물고기무리짓기를보여주고있다. (a) 병정개미 (b) 물고기 [ 그림 1] 무리짓기게임에서무리짓기는그룹을형성하는 NPC(Non Player Character) 의행동에주로사용된다. 대부분의게임에서 NPC들은이동시스템과애니메이션재생시스템을통하여조정된다 [5]. 즉무리를형성하여일정한패턴 * 교신저자 : 김경남 (hsfruit@lycos.co.kr) 접수일 10 년 10 월 15 일수정일 10 년 10 월 28 일게재확정일 10 년 12 월 17 일 5083
한국산학기술학회논문지제 11 권제 12 호, 2010 으로캐릭터를공격하거나, 도망갈때사용된다. 또한일정한패턴으로무리를지어특정목표에난입하거나대열을맞추어서이동하는데사용된다. 이러한방법들은무리에속한모든 NPC에적용된다. 무리에적용되는 AI(Artifical Intelligence) 알고리즘같은것이단순할경우움직임의패턴이단순하므로게임의재미가반감된다. 결과적으로, 게이머들은 NPC들의단순한이동때문에쉽게게임을정복할수있으며, 게임의재미또한감소될수있다. 본논문은이를개선하기위하여생물학적인무리짓기이론을게임 NPC 인공지능에접목하기위한것이다. 이를위하여물고기무리짓기연구 [3] 를설계하고, 오우거 (Ogre) 엔진을이용하여구현한다. 그리고, 구현된무리짓기와실세계의무리짓기의패턴을비교하여실세계의무리짓기형태를 NPC들의인공지능에적용될수있음을보여준다. 본논문의구성은다음과같다. 2장에서물고기무리짓기연구 [3] 와오우거엔진을간략하게소개한다. 3장에서물고기무리짓기를설계하고, 구현한다. 그리고 4장에서결론및추후연구방향을기술한다. 의집단행동을보이도록유도하는규칙이다 [6,7]. Reynolds가제안한무리짓기행동에는충돌회피와응집이있다. 충돌회피는개체간충돌을피하기위한최소거리를유지하기위한규칙으로충돌회피영역 (δ) 을항상모든개체들이최소로유지해야한다. 응집은개체들이모두동일한방향을향하거나모일수있는규칙으로상호작용영역 (ρ) 안에있는개체들간에서로방향과위치정보를교환한다. 식 (1)[4] 은충돌회피를위한것으로 시간에개체 의충돌회피영역에개체 가포함된경우에개체 의이동방향을나타낸다. 와 는각각 시간의 개체 의위치벡터와방향벡터를각각의미하며 는 개체가이동하려는이동방향을나타낸다. 개체 의회피영역에있는개체 에대하여개체 와의거리에대한개체 와의벡터요소의차이를모두합한값의음의방향, 즉반대방향으로이동함을표현한다. (1) 2. 관련연구 2.1 오우거엔진 오우거엔진은 3D 그래픽엔진으로영국의 Stave ' sinbad' Streeting라는소프트웨어엔지니어가 2001년개발하고, 2010년 4월에 1.7 버전까지배포되었다. 오우거엔진은 C++ 기반의객체지향인터페이스방식의설계로간결한클래스와인터페이스를제공하고, Direct 3D와 OpenGL을동시에지원한다. 오우거 3D 그래픽엔진의구조는 Root를기준으로장면관리자 (Scene Manager), 랜더링 (Rendering), 자원관리자 (Resource Manager) 의 3부분으로나뉜다. 장면관리자는화면에보여지는객체, 카메라, 광원, 평면과같이장면을보여주기위해필요한것들을모두관리한다. 자원관리자는이미지, 객체에입힐메쉬, 하늘을꾸미기위한메쉬, 음악과같이화면을꾸며주는자원들을관리한다. 렌더링은장면관리자와자원관리자에의해설정된객체의내용을화면에출력해주는일을한다. 2.2 무리짓기이론무리짓기는 1987년 Craig Reynolds가발표한논문에서처음소개된기법으로물고기떼, 새떼와같이무리 응집은개체 ὶ의상호작용영역 ρ에개체 가위치했을때같은방향으로모이게하는것으로식 (2) 는이를나타낸다. 첫번째항은위치벡터를나타내고두번째항은방향벡터를나타낸다. (2) 충돌회피영역 δ와상호작용영역 ρ에있지않는개체들은각개체가진행하는방향대로이동한다. 식 (3) 은이동하려는방향벡터가이전방향벡터값을그대로반영함을보여준다. (3) 식 (4) 는식 (1) 과식 (2) 와식 (3) 의경우중에서개체의방향벡터를구하고새로운위치벡터를구하는것을보여준다. 첫번째항은위치벡터를나타내고 2번째항은식 (1), 식 (2), 그리고식 (3) 을이용하여계산된방향벡터와일정한시간 ( ), 그리고이동속도인 를곱한것이다. (4) 5084
NPC 인공지능을위한무리짓기구현 3. 무리짓기설계및구현 3.1 물고기무리짓기의설계 표 1은 2장에서언급된실세계의물고기무리짓기형태 [3] 과기존연구들 [8,9] 를바탕으로물고기무리짓기를의사코드 (pseudo code) 로설계한것이다. 는현재위치벡터와방향벡터를계산하기위한물고기번호이고, j는참조되는물고기번호이다. N은총물고기마리수이다. 단계 (5) 에서는물고기 i의충돌회피영역안에물고기 j가있는지판단하여이값이참인경우에, 단계 (6) 에서식 (1) 을이용하여방향벡터를구한다. 단계 (7) 에서는물고기의상호작용영역안에물고기 j가있는지판단하여이값이참인경우에, 단계 (8) 에서식 (2) 을이용하여방향벡터를구한다. 단계 (9) 에서는단계 (5) 와단계 (7) 에서의이두조건을만족하지못한물고기의경우단계 (10) 에서식 (3) 을이용하여위치벡터를구한다. 단계 (11) 에서는식 (4) 을이용하여물고기 i의새로운위치벡터를구한다. [ 표 1] 물고기무리짓기설계 (1) for(i=1;i<=n;i++) (2) generate position vector, direction vector (3) for(i=1;i<=n;i++) (4) for(j=1;j<=n;j++){ (5) if j in avoidance range of collision (6) compute using equation(1) (7) else if j in interaction range of (8) compute using equation(2) (9) else (10) compute using equation(3) (11) compute position vector(equation(4)) (12) 라의위치 ( 단계 (5)) 와시점 ( 단계 (6)) 을설정하고단계 (4) 에서생성된카메라를갖는뷰포트를만든다 ( 단계 (7)). 그리고주변광원을설정한다 ( 단계 (8)). 단계 (9) 부터단계 (13) 까지는물고기개체를만드는과정이다. 단계 (10) 에서는물고기메쉬 (f.mesh) 를로드하여엔티티를생성하고단계 (11) 에서는위치벡터를생성하기위하여어항의크기인 200보다작은숫자를랜덤하게생성하는과정이다. 현재구현되는프로그램은 x, z 평면에물고기가그려진다. 단계 (12) 에서는장면노드인 fish를생성하고이노드의위치를단계 (11) 에서생성된좌표로설정한다. 단계 (13) 에서는단계 (10) 에서생성된 fishent 엔티티를장면노드인 fish에연결시킨다. [ 표 2] MainListener 클래스생성자 class MainListener : public FrameListener{ public: MainListener(){ (1) mroot=new Root(); (2) mwindow=mroot->getautocreatedwindow(); (3) mscenemgr=mroot->createscenemanager(); (4) mcamera = mscenemgr->createcamera("cam"); (5) mcamera->setposition(); (6) mcamera->lookat(); (7) mviewport = mwindow->addviewport(mcamera); (8) mscenemgr->setambientlight(); (9) for(i=0; i<n<i++)){ (10) fishent[i]=mscenemgr->createentity(n,"f.mesh"); (11) x= rand()%200, z= rand()%200; (12) fish[i]=mscenemgr->getrootscenenode()->create ChildSceneNode(String(name)",Vector3(x,0,z); (13) fish[i]->attachobject(fishen[i]); 3.2 물고기무리짓기구현 표 2는 FrameListener 클래스를상속받은 MainListener 의일부를보여준다. FrameListener 클래스는프레임단위로처리해야할일들을기술하는클래스로이클래스를상속한클래스를오우거엔진에등록하면자동적으로프레임이시작되기전에는 framestarted() 함수를호출하고렌더링이된후에는 frameended() 함수를호출한다. 루트객체 ( 단계 (1)) 와윈도우 ( 단계 (2)) 와장면관리자 ( 단계 (3)), 카메라 ( 단계 (4)) 를각각생성한다. 이후에카메 표 3은 MainListener 클래스의 framestarted() 메소드의일부분을보여주는데이는 [ 표 1] 의단계 (3) 부터단계 (11) 까지의과정을구현한것이다. 단계 (10) 은물고기의새로운위치를설정하는부분이다. 해당프레임이렌더링된후에 frameended() 메소드에서는별도의일을처리하지않고항상 true를반환한다. 5085
한국산학기술학회논문지제 11 권제 12 호, 2010 [ 표 3] Main Listener 클래스의 framestarted() (1) bool framestarted(const FrameEvent &evt){ (2) for(i=0; i<n;i++) (3) for(j=0;j<n;j++) { (4) if (i==j) continue; (5) if (collision_range(i,j)) (6) d[i]=equation(1); (7) else if (interaction_range(i,j)) (8) d[i]=equation(2); (9) else d[i]=equation(3); (10) fishnode[i]->setposition(fish[i]->getposition() (11) +d[i]*t*s); (12) (13) (14) (15) bool frameended(const FrameEvent &evt){ (16) return true; (17) 표 4는초기화과정과렌더링을기술하는 game 클래스의일부를보여준다. 단계 (2) 에서는루트객체인 mroot를생성하고단계 (4) 에서는윈도우를생성하고단계 (6) 에서는리소스그룹관리자를초기화한다. 단계 (8) 에서는 mmainlistener 객체를생성하고, mroot 객체의프레임리스너로 mmainlistener를등록한다 ( 단계 (9)). go() 함수에서는 startrendering() 함수를호출하여렌더링을지속한다 ( 단계 (13)). [ 표 4] game 클래스 class game { (1) game() { (2) mroot = new Root("plugins.cfg","ogre.cfg", (3) "log.txt"); (4) mwindow = mroot->initialise(true, "init"); (5) (6) // 리소스그룹관리자초기화 (7) (8) mmainlistener = new MainListener(mRoot); (9) mroot->addframelistener(mmainlistener); (10) (11) (12) void go() { (13) mroot->startrendering(); (14) 표 5는 main.cpp의일부를보여준다. 게임클래스객체인 app를생성하고 ( 단계 (1)), 단계 (3) 에서게임루프에진입한다. 그리고, 예외가발생한경우에예외처리를수행한다 ( 단계 (4)). [ 표 5] main() 함수 int main(int argc, char *argv[]) { (1) game app; (2) try { (3) app.go(); (4) catch( Ogre::Exception& e ) { (5) MessageBox( NULL, "exception has occurred!"); (6) (7) return 0; 3.3 성능평가물고기무리짓기를구현하기하기위해사용된오우거 SDK 버전은 1.4.6이고컴파일러는 Visual C++ express 2005이다. 실험에사용된컴퓨터 CPU는 Intel core E7200 으로 2.53GHz이고 RAM은 2GB, 그래픽메모리는 512MB이고운영체제는 Microsoft XP Pro이다. 실험에사용된조건은 D.J. HOARE et al.[3] 에서의무리짓기환경과동일하다. 구현시사용된물고기의수는 10마리, 어항의크기는정사각형크기로가로 200, 세로 200의크기를갖는다. 응답대기시간 를 0.1로설정하고물고기의이동속도 s는 1.25, 물고기의크기는 4cm 로설정한다. 충돌회피영역 δ은 1BL(Body Length) 로설정하는데, 1BL은 4cm의값을갖는다. 상호작용영역 ρ는 2BL로설정한다. 물고기의초기위치와방향은랜덤함수를이용하여생성된다. 그림 2는시뮬레이션시작시의화면으로물고기의위치와, 방향이모두랜덤하게주어진상태로응집과정렬이되어있지않음을확인할수있다. [ 그림 2] 시작화면 5086
NPC 인공지능을위한무리짓기구현 그림 3은부분정렬및부분응집상태를보여주는것으로오른쪽상단부분에물고기들이 2마리씩무리를짓거나머리부분이동일한지점으로정렬되는모습을볼수있다. [ 그림 3] 부분정렬및응집그림 4는물고기 10마리가무리를형성하는과정을 4 단계로나누어놓은것이다. 그림 4(a) 는시작후 30초가경과된상태의화면으로혼자움직이는물고기들이많다. 그림 4(b) 는시뮬레이션실행후 5분후의화면으로 2~3 마리들이무리를짓거나정렬하고있다. 그림 4(c) 는 10 분후의화면으로 10마리의물고기가일정한크기의무리를형성하고있다. 이후부터는물고기들이일정크기의무리를형성하여서보다큰무리를형성하는데에많은시간이소요되었다. 그림 4(d) 는물고기 10마리가모두무리를형성했을때의모습이다. 마리로무리를짓는횟수를백분율로표현한것이다. 시뮬레이션의경우전체실험시간동안 1마리로무리짓는비율이전체무리짓기비율의약 80% 를차지한다. 두경우모두 60% 이상의시간을무리를짓지않고 1마리씩독자적으로움직이고있다. 두경우모두시간이경과될수록물고기들의응집과정렬로인해물고기무리의크기가커짐을알수있다. 그러나, 시뮬레이션의경우에서 10마리모두무리로되는형성되는비율은약 43분정도에 10마리가모두응집되어서 6마리에서 9마리가무리로형성되는비율에비해상대적으로높고, 실세계에서 10 마리가모두무리로형성되는비율에비해높다. 이러한이유는시뮬레이션의경우실세계에서와어항의크기와유사한화면의크기설정과벽면에부딪혔을경우에부자연스럽게구현되는것등의한계를가지고있기때문이라고판단된다. 이경우를제외하면실세계에서의무리짓기와시뮬레이션의무리짓기형태는유사함을보인다. 이와같이실세계와시뮬레이션의무리짓기비율은대부분의경우에무리짓기변화정도가비슷하며변화형태또한유사하다. 이는구현된무리짓기를게임의무리짓기에응용하게되는경우실세계에서와비슷한형태의 NPC 무리짓기를게이머에게제공할수있음을보여준다. (a) 시작화면 (b) 5 분경과후화면 [ 그림 5] 시뮬레이션과실세계의무리짓기비교 4. 결론및향후연구방향 (c) 10분경과후상태 (d) 40분경과상태후 [ 그림 4] 무리짓기상태변화그림 5는실세계의무리짓기실험 [3] 과오우거엔진을이용하여무리짓기를구현한비교결과이다. 두실험모두 30초간격으로 60분간관찰하며실험환경은그림 3 과그림 4에서와동일하게설정한다. 가로축은무리짓기를형성하는물고기들의마리수이고, 세로축은각마리로구성되는무리짓기횟수를모두합한값에대해해당 본논문에서는물고기의무리짓기행동을설계하고오우거엔진을이용하여구현하였다. 그리고구현된결과를실세계의무리짓기와비교하였다. 실험결과, 실세계의무리짓기와시뮬레이션의무리짓기는유사함을보였다. 본논문의무리짓기알고리즘을게임의 NPC 무리짓기에적용하는경우게이머들에게실세계와비슷한무리짓기환경을제공하여게임의몰입을증가시킬수있을것으로판단된다. 추후에는 BL 크기와어항크기, 그리고물고기수등의다양한조건에서구현된무리짓기알고리즘에대한 5087
한국산학기술학회논문지제 11 권제 12 호, 2010 성능을평가할예정이다. 참고문헌 이면재 (Myoun-Jae Lee) [ 종신회원 ] [1] PETER H.WERGE, MARTIN WIKESKI, et al., "ANTIBIRDS PARASITIZE, FORAGING ARMY ANTS", Ecology, 86(3), pp.555-559, 2005. [2] I.D.Couzin and N.R.Franks,"Self-Organized lane formation and optimized traffic flow in army ants", Proceedings of the Royal Society of London, Series B. 270: 139-146, 2003. [3] D.J.HOARE, I.D. COUZIN, J.-G.J. GODIN& J. KRAUSE, "Context-dependent group size choice in fish", Elsevier Ltd. ANIMAL BEHAVIOUR, pp.155-164, 2004. [4] Iain D. Couzin1,2, Jens Krause, et al., Effective leadership and decision-making in animal groups on the move, Nature 433, pp.513-516, February 2005. [5] Alt, G., and King, K, "Intelligent Movement Animation for NPCs", AI Game Programming Wisdom 2, Charles River Media, 2003. [6] Steven Woodcock, 플로킹 : 집단행동을흉내내는간단한기법, Game Programming Gems 1, pp.401-415, 2001. [7] Steven Woodcock, 먹고먹히는플로킹 : 포식자와먹이, Game Programming Gems 2, 이 pp.423-430, 2002. [8] 유현지, 이면재, Ogre 엔진을이용한물고기떼시뮬레이션, 한국산학기술학회추계학술발표논문집, 제 10권, 제2호, pp782-784, 2009.12. [9] 유현지, 박종호, 이면재, 물고기무리짓기구현, 한국산학기술학회춘계학술발표논문집제11권, 제1호, pp1010-1013, 2010.5. < 관심분야 > 게임인공지능, 게임엔진 1992 년 2 월 : 홍익대학교전자계산학과졸업 ( 이학사 ) 1994 년 2 월 : 홍익대학교전자계산학과대학원졸업 ( 이학석사 ) 2009 년 3 월 ~ 현재 : 백석대학교정보통신학부교수 김경남 (Kyoung-Nam Kim) [ 정회원 ] < 관심분야 > 미디어아트, 게임아트 1994 년 2 월 : 홍익대학교미술대학회화과졸업 ( 학사 ) 1997 년 2 월 : 홍익대학교미술대학회화과졸업 ( 석사 ) 2008 년 ~ 현재 : 중앙대학교첨단영상대학원예술공학박사과정수료 유현지 (Hyun-Ji Yoo) [ 준회원 ] 2011 년 2 월 : 백석대학교정보통신학부멀티미디어전공졸업예정 < 관심분야 > 게임인공지능, 안드로이드프로그래밍 5088