Towards statistical client prediction - analysis of user behavious in distributed interactive media

© IJIGS/Uni e si y o Wol e hamp on/EUROSIS TOWARDS STATISTICAL CLIENT PREDICTION – ANALYSIS OF USER BEHAVIOUR IN DISTRIBUTED INTERACTIVE MEDIA Aa on McCoy*, Declan Delaney^, D . Seamus McLoone* and D . Tomás Wa d* *Depa men o Elec onic Enginee ing, ^Depa men o Compu e Science Na ional Uni e si y o I eland Maynoo h Maynoo h, Co. Kilda e I eland E-mail: [email protected] KEYWORDS Dis ibu ed in e ac i e media, To que game engine, Time- se ies da a analysis, Beha iou al modeling, S a is ical clien p edic ion, Ne wo ked mul iplaye games, Dead- eckoning. ABSTRACT Dis ibu ed in e ac i e media such as ne wo ked mul iplaye compu e games o e use s he oppo uni y o in e ac and sha e expe iences wi hin a i ual en i onmen . Mo e o en han no , hese in e ac ions a e equi ed o be pe o med in eal- ime, a cons ain which poses p oblems gi en he unde lying ne wo k capabili ies used o ansmi in o ma ion. In hese eal- ime dis ibu ed sys ems, he amoun o in o ma ion ha needs o be sha ed be ween pa icipan s in o de o main ain comple e game-s a e ideli y is oo la ge. As a esul , ade-o s mus be made o e wha in o ma ion equi emen s a e necessa y o main ain a le el o consis ency ha will p o ide adequa e quali y o in e ac ion o he use s. One possible solu ion o his p oblem is he use o s a is ical modeling echniques ha a emp o cap u e he indi idual beha iou o sys em use s. These models can hen be used o p edic he likely u u e beha iou o he use s, hus educing he sha ed in o ma ion equi emen s. In his pape we p esen some p elimina y analysis o he beha iou o use s wi hin a dis ibu ed in e ac i e applica ion, wi h a goal owa ds u u e wo k o a emp ing o de elop and inco po a e s a is ical models o use beha iou o he pu pose desc ibed abo e. INTRODUCTION Dis ibu ed in e ac i e media (DIM) such as ne wo ked mul iplaye games a e p one o quali y-o -in e ac ion and scalabili y p oblems as a consequence o non-ideal communica ion in as uc u e cha ac e is ics such as ne wo k la ency and bandwid h. This well-known p oblem is gene ally deal wi h h ough ca e ul en i y s a e upda e p ocedu es ha il e he game-s a e based on c i e ia such as clien ele ancy o s a e changes. An example o he o me is a ea-o -in e es echniques (Singhal 1999) while examples o he la e a e del a-comp ession (Van Hook e al. 1994) and dead- eckoning (IEEE 1993). In addi ion QoS echniques a e some imes used o ensu e ha all pa icipa ing clien s a e gi en su icien ne wo k esou ces o mee quali y- o -in e ac ion c i e ia (In e ne 2 2004). The communica ion o game s a e changes is he key issue in all o he abo e and he games indus y-s anda d echniques a e based chie ly on a ian s o dead- eckoning, which is an example o an en i y s a e ex apola ion mechanism. Ra he han upda ing en i ies o e he ne wo k once pe simula ion loop (which we will e e o as he game loop) all clien s in he DIM main ain a local model, usually a linea ex apola ion, o en i y dynamics. This model is only upda ed when he clien esponsible o he en i y de e mines ha he di e ence be ween he ue en i y s a e and ha o he model as used by all o he clien s has de ia ed by some p e-de ined h eshold amoun . Only his upda e hen needs o be ansmi ed o all he pa icipa ing clien s hence educing he numbe o packe s equi ed o main ain a ole able ideli y ac oss he DIM. Such a echnique ob iously helps educe bandwid h equi emen s and he e o e aids in scalabili y. Mo e sub ly i also aids in he educ ion o communica ion la ency, one o he key ac o s in main aining a high quali y o in e ac ion o he use . This is appa en i we look a he indi idual componen s which make up la ency in dis ibu ed in e ac i e media o any pa icula link be ween wo pa icipa ing clien s i and j : ij ij ij cij O B K++=Τ τ (1) whe e K ep esen s he gene a ion a e o s a e in o ma ion du ing he global gameloop in bi s pe second and B is he bandwid h o he link o he pa icula clien in ques ion. τc ep esen s he physical p opaga ion delay. O ep esen s all o he p ocessing o e heads. Ob iously h ough an inc ease in link bandwid h o a educ ion in K he la ency can be educed. I is h ough such in o ma ion a e educ ion echniques such as in dead- eckoning ha la ency p oblems can be deal wi h in DIM. Recen ly in an a emp o u he imp o e he powe o en i y s a e upda e mechanisms using he concep o s a e ex apola ion, a echnique known as he hyb id model app oach has been p oposed (Delaney e al. 2003). This concep is e y powe ul and ye qui e simple. In his pa adigm en i y s a e a e ex apola ed based on a combina ion o low o de sho e m ex apola ion and longe e m s a is ical in e ence. Essen ially he echnique elies on ex apola ing s a e changes based on p e ious examples o s a e beha iou in simila ci cums ances. In he absence o good in o ma ion on ypical s a e changes o an en i y, he model is swi ched o simple low o de ex apola ion as in dead- eckoning. By swi ching be ween he wo models, hence he e m hyb id model, en i y s a es can be ex apola ed u he han cu en ly possible unde dead- eckoning and o he en i y s a e ex apola ion schemes. Fu he , in he absence o good s a is ical in o ma ion, long- © IJIGS/Uni e si y o Wol e hamp on/EUROSIS e m heu is ic models can be used in lieu as p o ided by he DIM designe . Consequen ly he echnique has supe io pe o mance o dead- eckoning alone as demons a ed in (Delaney e al. 2003). Howe e o he echnique o ealize i s po en ial in he ield o DIM i is impe a i e ha echniques and me hods should be de eloped o i s o all ecognize, and second o all ep esen , such s a is ical models. All wo k in his a ea so a has concen a ed on demons a ing he concep o ixed s a is ical spa ial models ha na u ally a ise ou o s a ic na iga ion asks in ypical DIAs (Ma shall 2004). We a e cu en ly s udying he possibili y o au oma ic ecogni ion o s a is ically simila beha iou among en i y dynamics in impo an classes o DIM. In a p e ious pape we ha e shown ha pa e ns o beha iou eme ge o human-human in e ac ion in such DIM (McCoy 2004). Howe e , in an a emp o b idge he mo e solid s a is ical ca ego iza ion ha a ose ou o ixed spa ial models wi h such pa e ns, an in e media e s udy has been conduc ed in which he eac i e coupling be ween human agen s has been loosened h ough he in es iga ion o in e ac ion be ween human use s and ini e-s a e machine- d i en agen s (BOTS). This pape epo s on wo k done on his a ea so a in explo ing such human use beha iou in hese mul iplaye compu e games. I is hoped ha h ough he analysis o such beha iou ha ca ego iza ion can be de e mined wi h he goal in mind ha s a is ically simila pa e ns o beha iou can be ecognized and ul ima ely exploi ed o p edic u u e beha iou in o de o p e-emp games a e changes ahead o ime and so educe la ency p oblems in such DIM h ough bo h upda e packe a e educ ion and pe haps p e-emp i e ansmission. TEST ENVIRONMENT AND TEST SCENARIOS We use he To que Game Engine om Ga ageGames (Ma shall 2004) o cons uc simple es en i onmen s and es scena ios. This allows us o pe o m expe imen s in a ela i ely con olled manne , and p o ides us wi h he abili y o eco ding in o ma ion. Du ing a use ’s in e ac ion wi hin he es en i onmen , a ious da a is ime-s amped and collec ed in a log ile o subsequen analysis. Fi s ly, 3- dimensional posi ional da a o each use is eco ded a egula sampling in e als (a he a e o a leas 1 He z, bu usually highe ), allowing us o econs uc a use ’s posi ional s a e o e ime wi h espec o ha o ano he use and any e en s ha occu . This posi ional da a is ep esen ed as ime- se ies da ase s o analysis, examples o which can be seen in he esul s and da a analysis sec ion. Secondly, di ec in e ace con ol in e ac ions (i.e. keyboa d and mouse bu on p esses) pe o med by he use o con ol hei playe onsc een a e ime-s amped and eco ded whene e hey occu ( his consis s o p ima ily mo emen and weapon i ing ins uc ions). This allows us o econs uc a use ’s con ol sequence o ac ions wi h espec o any e en s ha occu . Gi en he limi ed complexi y o ou es en i onmen desc ibed below, he only e en s which we a e conce ned wi h he e a e bo h weapon i ing e en s and disabled e en s (whe e one use is disabled by weapons i e om ano he ), and hese a e eco ded and ime-s amped when hey occu . The es en i onmen ha we used o he expe imen s epo ed in his pape is a simple enclosed en i onmen consis ing o se e al building and owe like s uc u es along wi h se s o ees and ocks. These p o ide some isual s imula ion o he use s and also helps obscu e hei iew in ce ain a eas, o cing hem o mo e abou . The expe imen s a e pe o med in he s yle o a Fi s -Pe son Shoo e (FPS) game, whe eby use s in e ac wi h he en i onmen as hough hey we e looking h ough he eyes o hei playe (see Figu e 1). FPS games a e one o he mos popula gen es o games cu en ly in he ma ke , and hei ne wo ked mul iplaye capabili ies make hem on ob ious choice o esea ch in o dis ibu ed in e ac i e sys ems in gene al. Figu e 1: In-game sc eensho o he es en i onmen . Tes Scena io 1 This was a simple es scena io se up wi h he in en ion o analyzing he beha iou o a use owa ds a pseudo-dynamic goal. A he beginning o he game, he use is spawned andomly inside one o he buildings. In addi ion, a compu e con olled opponen ( ypically e e ed o as a ‘bo ’) is spawned andomly a one o he p ede ined pa hnodes ha we e placed be o ehand h oughou he en i onmen . These pa hnodes join oge he o o m a pa h ne wo k, and his pa h ne wo k is a e sed by he bo pa hnode-by-pa hnode (a ep esen a ion o his pa h ne wo k can be seen below in Figu e 2). The bo is se on a looping un so ha all i does is cons an ly ollow he pa h o e and o e again – no a i icial ‘ hinking’ o eac ing occu s o he bo . The goal o he use in his case is o disable he bo a speci ied numbe o imes using hei weapon be o e he speci ied ime-limi uns ou . The use is encou aged o sco e as high as possible o e a numbe o uns such ha mo e ypical ocused beha iou is exhibi ed a he han ca e ee wande ing h ough he en i onmen . This is so as o eplica e he ypical condi ions unde which FPS games ope a e. Typical beha ou ial pa e ns we would expec o see should be a ge seeking, pu sui and i ing ac ion. Such classes o beha iou a e use ul labels (albei no always clea ly dis inguishable) and ha e been applied wi h some success in ou p e ious wo k (McCoy 2004). © IJIGS/Uni e si y o Wol e hamp on/EUROSIS Figu e 2: Pa h ne wo k used o na iga ion by he bo . Tes Scena io 2 This es scena io was se up wi h he in en ion o analyzing he use ’s beha iou owa ds a bo ha had limi ed eac i e capabili ies owa ds hei own ac ions, namely he abili y o i e i ’s own weapon and damage he use . I was se up in exac ly he same manne as desc ibed o es scena io 1, wi h he excep ion ha he bo is gi en a senso ield ha can be used o de ec he p esence o he use . I he use comes wi hin he bo ’s senso ield and wi hin di ec line-o -sigh (LOS) o he bo , he bo is ins uc ed o i e i ’s weapon in he di ec ion o he use . I he use goes ou o LOS o he bo o ou o i ’s senso ield adius, hen he bo is ins uc ed o s op i ing i ’s weapon. The mo emen capabili y o he bo is ixed as in es scena io 1, meaning ha i ne e de ia es i ’s posi ion o o he pa h ne wo k on which i na iga es h ough he en i onmen , ega dless o whe he i is cu en ly i ing i ’s weapon a he use o no . Again, he goal o he use in his case is o disable he bo a speci ied numbe o imes be o e he ime-limi is eached. Unlike es scena io 1 howe e , i was now possible o he bo o win he game by disabling he use he speci ied numbe o imes. The mo i a ion o his es scena io is o de e mine i any esul an de ensi e o e asi e beha iou can be ecognized in addi ion o hose beha iou s s a ed o he p e ious scena io. RESULTS AND DATA ANALYSIS In his sec ion, we shall p esen a speci ic selec ion o esul s aken om da a ha was collec ed o use s o a ying ‘expe ise’ wi h ega d o no only his pa icula es en i onmen , bu also wi h compu e games in gene al and FPS speci ic games. Each use was asked o play a numbe o successi e games in each es scena io, and hey we e gi en a speci ic sco e ha hey had o each o comple e he game. Tes Scena io 1 Figu es 3-5 below p esen s a e da a o e ime o se e al di e en use s o a ying abili y. In each igu e, he i s 3 subplo s p esen posi ional da a o he use (Playe 1) and he bo (Playe 2), and a e b oken in o x, y and z coo dina es and plo ed sepa a ely. O e laid on each o hese a e solid e ical lines ep esen ing each poin in ime whe e he use disabled he bo , and hese lines allow us o segmen he da a in o pa i ions. The inal subplo wi hin each igu e uses solid e ical lines o ep esen each poin in ime whe e he use i ed hei weapon. In Figu es 9-11, we ha e plo ed he ela i e posi ion o he use wi h espec o he bo (i.e. aking he bo ’s posi ion as he o igin o each ime-s ep). Each o he da a pa i ions a e plo ed indi idually, wi h a da k ci cle ep esen ing he s a ing posi ion o he use , and a da k ‘x’ ma king hei end posi ion (i.e. when hey disabled he bo ). F om isual inspec ion o Figu e 3 (no ice use ), we can see se e al a eas whe e he posi ional da a o he use and he bo seem o co ela e highly, wi h one essen ially ‘ ollowing’ he o he one. This co esponds o a pu sui s a egy, whe e he use has ound he bo and is now pu suing hem wi h he in en ion o disabling hem ( om ime 50 o 100 o ins ance). I is in e es ing o no e ha his is less p onounced in he da a o he ad anced and expe use . The p ima y eason o his is ha hese use s end o wai in a cen al a ea and le he bo come o hem a he han engage in pu sui , due o he ac ha hey o en quickly lea n he ixed mo emen pa e n o he bo along he pa h ne wo k. As a esul , hei mo emen pa e ns end o display signi ican ly less a ia ion han ha o he no ice use . Also, hey end o ake less ime disabling he bo han less expe ienced use s. This is e iden om he shoo ing e en s seen in each igu e, whe e we see ha he no ice use ends o i e hei weapon in la ge sp eads, while he mo e ad anced use s i e sho e , accu a e bu s s ha end o disable he bo quickly, as e idenced by he co ela ion be ween he shoo ing e en s and disabled e en s. Ob iously i he bo had lea ning beha iou o was con olled by ano he expe use such a ixed s a egy would only p o ide sho - e m esul s, as Playe 2 would soon adap o deal wi h his. Indeed i is his cons an in e play be ween a ious s a egies in he human-human case ha makes such online games bo h enjoyable o he use and di icul o p edic o esea che s (McCoy 2004). Ano he poin o in e es is he co ela ion o he dis ance be ween use and bo , he i ing e en s o he use , and he bo being disabled. In mos cases, we can see he posi ions con e ging close oge he igh be o e he bo is disabled, indica ing he use mo ing close owa ds he bo . This is pa icula ly e iden om inspec ion o Figu es 9-11, whe e we can see he con e gence o he use ’s ajec o ies ela i e o he bo (whe e each ajec o y s a s as a da k ci cle and wo ks i s way owa ds a da k ‘x’ ma ke ). This ag ees wi h ou in ui i e no ion ha in o de o disable he bo quicke , we should ge close o hem (pa icula ly in his case whe e he bo does no i e back). We also no ice he a iance in he ajec o ies ha appea unde di e en ci cums ances. Fo ins ance, long-winding ajec o ies ypically ep esen some andom o wande ing ype beha iou o a use , whe eas sho e mo e con e gen ajec o ies would o en ep esen a ack- ype beha iou . O in e es a e he ajec o ies ha appea o bo h di e ge and subsequen ly con e ge a he sha ply. These o en ep esen cases whe e a use has engaged he bo bu no disabled i , and ha ing lea ned he bo s p edic able mo emen s a egy, chooses no o pu sue i bu ins ead chooses o wai in a sui able a ea o ambush. © IJIGS/Uni e si y o Wol e hamp on/EUROSIS Figu e 3: S a e da a o e ime o a no ice use . Figu e 4: S a e da a o e ime o an ad anced use . Figu e 5: S a e da a o e ime o an expe use . Figu e 6: S a e da a o e ime o a no ice use . Figu e 7: S a e da a o e ime o an ad anced use . Figu e 8: S a e da a o e ime o an expe use . © IJIGS/Uni e si y o Wol e hamp on/EUROSIS Figu e 9: T ajec o y o no ice use ela i e o bo . Figu e 10: T ajec o y o ad anced use ela i e o bo . Figu e 11: T ajec o y o expe use ela i e o bo . Figu e 12: T ajec o y o no ice use ela i e o bo . Figu e 13: T ajec o y o ad anced use ela i e o bo . Figu e 14: T ajec o y o expe use ela i e o bo . Tes Scena io 2 Figu es 6-8 below p esen s a e da a o e ime o use s o a ying le el o abili y as in he p e ious sec ion. Howe e , he e we ha e chosen o omi he z posi ional da a subplo in a ou o a subplo showing he 3-dimensional Euclidean dis ance be ween he use and he bo a each ime s ep. As be o e, he i s wo subplo s o each igu e ep esen he x and y posi ional da a o bo h he use and he bo , o e laid wi h disabled e en s o bo h (unlike he las sec ion, which only showed disabled e en s o he bo ). Finally, he las subplo shows shoo ing e en s o bo h use and bo (whe e he shoo ing e en s o he use a e abo e he cen e line and he shoo ing e en s o he bo a e below he cen e line). Figu es 12-14 p esen plo s o he use ’s posi ion ela i e o he bo o each imes ep, as de ailed in he p e ious sec ion. F om inspec ion o he plo s, we can see ha in gene al he dis ance be ween he use and he bo ends o con e ge be o e a disabled e en occu s, implying he use mo ing close o he bo in an a emp o inc ease hei chances o disabling i . This is again e iden om he plo s o use ajec o ies ela i e o he bo (Figu es 12-14), whe e we can see he con e gence o he ajec o ies (al hough in he case o he expe use , i is less p onounced). These disabled e en s p o ide na u al pa i ions o he da a due o he andom espawning o a playe wi hin he en i onmen a e hey a e disabled, leading o jumps in he posi ional s a e ( andom espawning is a e y common sys em used in FPS game in gene al). In he case o he no ice use (Figu e 6), © IJIGS/Uni e si y o Wol e hamp on/EUROSIS we end o see less o he pu sui s a egy ha was so p ominen o es scena io 1 (Figu e 3). This is qui e e iden om he subplo showing shoo ing e en s, whe e we see bu s s o i ing sp ead apa , indica ing mo e apid engagemen s be ween use and bo a he han p olonged pu suing. Pa o he eason o his is ha because he bo now has he abili y o i e back, use s a e much mo e cau ious abou how hey app oach he bo , and o en like o hide behind co e and a emp o ‘ambush’ he bo as i na iga es along i ’s pa h ne wo k. I is in e es ing o no e he a ia ion in dis ance be ween use and bo o he case o he expe use , whe e we can see an ex ended pe iod o ime ( om 50 seconds onwa ds) du ing which dis ance con e ged bu subsequen ly di e ged, coupled wi h a easonably high deg ee o shoo ing e en s. This would indica e ha he use engaged he bo and subsequen ly b oke o hei a ack, bu did no engage he bo in di ec pu sui . Ra he , ha ing lea ned he bo ’s mo emen pa e n, hey mos likely wai ed o he bo o e u n on i s cou se and hen e-engage i , a which poin hey inally disabled he bo . This is consis en wi h he esul s shown in Figu e 14, whe e we can obse e he di e gence o he use ’s ajec o ies coupled wi h he subsequen con e gence, indica ing a sec ion o ime ha mos likely in ol ed mul iple pe iods o in e ac ion be ween use and bo . Also e iden is he ac ha he end poin s o he expe use ’s ajec o ies (ma ked by da k ‘x’ poin s) ha e a highe sp ead as opposed o bo h he no ice and ad anced use s (Figu es 12 and 13 espec i ely) – his would indica e g ea e accu acy on he pa o he expe use a disabling he bo wi h his weapon. CONCLUSION F om he esul s al eady shown o a numbe o use s i is clea ha ce ain pa e ns o beha iou do eme ge. In bo h es scena ios i is ha co ela ed dynamical beha iou can occu indica ing ha he espec i e en i y s a es canno be s a is ically independen . In in ui i e e ms his means o example ha i he a ge playe changes eloci y d ama ically i is o en he case ha he pu suing playe will do likewise. This a he ob ious obse a ion could be exploi ed in en i y s a e ex apola ion h ough p edic ing such changes whe e he con en ional pa adigm o dead- eckoning would ha e had o ansmi a packe indica ing a eloci y change. I may e en be possible o p eemp shoo ing e en s which con en ional echniques ha e no possibili y o p edic ing. In ano he s ep owa ds modeling he human- human in e ac ion ha is so impo an in DIM ano he in e media e s ep will be aken in which he bo can exhibi mo e human-like beha iou . This can be as simple as a hun ing and pu sui beha iou whe e he bo ha ing spo ed Playe 1 will a emp o close he dis ance be o e a emp ing o disable he opponen . Such beha iou should elici mo e in e es ing de ensi e o e asi e beha iou in he human use ha will be impo an o analyze. Fu he analysis along hese lines should yield insigh , ools and esul s ha will allow be e and mo e comp ehensi e analysis o human use s in e ac ing in he same en i onmen s. Consequen ly i will be possible o make be e guesses abou wha such use s may do nex and hence achie e quali y o in e ac ion and scalabili y bene i s o he dis ibu ed case. ACKNOWLEDGEMENT This ma e ial is based upon wo ks suppo ed by En e p ise I eland unde g an no. SC/2002/129/. REFERENCES Delaney, D., Wa d, T., and S. McLoone. 2003. “Reducing Upda e Packe s in Dis ibu ed In e ac i e Applica ions using a Hyb id App oach”. 16 h In e na ional Con e ence on Pa allel and Dis ibu ed Compu ing Sys ems (PDCS 2003). Augus 13-15, Reno, USA, pp.417-422. IEEE. 1993. IEEE S anda d o in o ma ion echnology – p o ocols o dis ibu ed simula ion applica ions: En i y in o ma ion and in e ac ion. IEEE S anda d 1278-1993. New Yo k: IEEE Compu e Socie y, 1993. In e ne 2. 2004. WebSi e: h p://www.in e ne 2.edu Ma shall, D., McCoy, A., Delaney, D., Wa d, T., and S. McLoone. 2004. “A Realis ic Dis ibu ed In e ac i e Tes bed o S a ic and Dynamic En i y S a e Da a Acquisi ion”. In P oceedings o The I ish Signals and Sys ems Con e ence 2004. June 30 - July 2, Bel as , No he n I eland, pp. 83 - 88. McCoy, A., Delaney, D., McLoone, S., and T. Wa d. 2004. “In es iga ing Beha iou al S a e Da a-Pa i ioning o Use - Modelling in Dis ibu ed In e ac i e Applica ions”. To appea in p oceedings o The 8- h IEEE In e na ional Symposium on Dis ibu ed Simula ion and Real Time Applica ions. Oc obe 21-23, Budapes , Hunga y. Singhal, S. and M. Zyda. 1999. Ne wo ked Vi ual En i onmen s: Design and Implemen a ion. Fi s Ed, Addison-Wesley, pp. 195 - 213. Van Hook, D.J., J.O. Cal in, and D.C. Mille . 1994. “A p o ocol independen comp ession algo i hm (PICA)”. Ad anced Dis ibu ed Simula ion Memo andum 20PM-ADS-005, MIT Lincoln Labo a o ies, Lexing on, MA. BIOGRAPHY Aa on McCoy ecei ed his B.Sc. deg ee om he Na ional Uni e si y o I eland, Maynoo h in 2002, specializing in compu e science and heo e ical physics. His main a eas o in e es a e dis ibu ed sys ems, ne wo ked i ual en i onmen s and he use o a i icial in elligence in in e ac i e games. He is cu en ly s udying o his PhD a NUI Maynoo h in he a ea o use modeling in Dis ibu ed In e ac i e Applica ions.