{"id":617,"date":"2020-04-23T16:51:00","date_gmt":"2020-04-23T16:51:00","guid":{"rendered":"http:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/tamas-papp\/?p=617"},"modified":"2020-04-25T00:57:18","modified_gmt":"2020-04-25T00:57:18","slug":"fear-shortest-path-for-challenging-ai","status":"publish","type":"post","link":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/tamas-papp\/2020\/04\/23\/fear-shortest-path-for-challenging-ai\/","title":{"rendered":"F.E.A.R.: shortest path for realistic AI"},"content":{"rendered":"\n<p class=\"wp-block-paragraph\">This is a bit of a different one, but I think it&#8217;s a decent showcase of Occam&#8217;s razor. I&#8217;ll be looking at how the enemy AI is designed in the video game F.E.A.R.<\/p>\n\n\n\n<hr class=\"wp-block-separator\" \/>\n\n\n\n<p class=\"wp-block-paragraph\">F.E.A.R., Monolith Productions&#8217; 2005 first-person shooter game, was critically acclaimed for having some of the best non-player character (NPC) AI at the time. The enemy soldiers can dodge, fire from cover and even work together to ambush the player. This makes for an all-around challenging experience, especially given the survival horror theme of the game. I mean, just check out the showcase below!<\/p>\n\n\n\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<div class=\"video-container\"><iframe title=\"The F.E.A.R. AI\" width=\"740\" height=\"416\" src=\"https:\/\/www.youtube.com\/embed\/KQN3yKYkFmE?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture\" allowfullscreen><\/iframe><\/div>\n<\/div><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">Given that the AI was partly engineered by an MIT graduate student, this comes as less of a surprise \u2014 but what makes it really tick?<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">The recipe is deceptively simple. As Jeff Orkin puts it in his Games Developer Conference paper [1], it&#8217;s &#8220;Three states and a plan.&#8221; Since all an NPC does is play animations or move across the map, at any given time it decides on what action to perform based on being in of the three states below.<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-large is-resized\"><img fetchpriority=\"high\" decoding=\"async\" src=\"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/tamas-papp\/wp-content\/uploads\/sites\/13\/2020\/04\/fsm.png\" alt=\"\" class=\"wp-image-626\" width=\"254\" height=\"217\" srcset=\"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/tamas-papp\/wp-content\/uploads\/sites\/13\/2020\/04\/fsm.png 869w, https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/tamas-papp\/wp-content\/uploads\/sites\/13\/2020\/04\/fsm-300x257.png 300w, https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/tamas-papp\/wp-content\/uploads\/sites\/13\/2020\/04\/fsm-768x657.png 768w\" sizes=\"(max-width: 254px) 100vw, 254px\" \/><\/figure><\/div>\n\n\n\n<p class=\"wp-block-paragraph\">When the NPC is in the &#8220;Goto&#8221; state, it moves to a specific location. The &#8220;Animate&#8221; state specifies an animation from a static position, such as firing a weapon, and the &#8220;Use Smart Object&#8221; state implies an animation involving a prop (such as flipping a table) is performed.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">F.E.A.R. uses a planning system to make NPCs swap between these states. Every character gets its own set of goals (such as &#8220;Patrol&#8221;, &#8220;Kill Enemy&#8221; or &#8220;Ambush&#8221;) and its own set of actions (think &#8220;Reload&#8221;, &#8220;Suppression Fire&#8221;) to achieve those goals. At any given time, the state of the world (a different kind of state from the three ones above) is modelled as a vector, with the NPC starting in one state and progressing towards the state corresponding to its goal. <\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Here&#8217;s where the maths comes in. The possible states of the world are baked into a graph, with adjacent states being linked by weighted edges representing the cost of the action undertaken to perform the transition. The problem of NPC decision-making now becomes one of graph traversal, so each NPC just has to navigate the weighted graph in a sensible way \u2014 Monolith opted for a particularly efficient implementation of the <a href=\"https:\/\/en.wikipedia.org\/wiki\/A*_search_algorithm\">A* shortest path algorithm<\/a>. A* search is also used more conventionally for map navigation when a &#8220;Goto&#8221; state is reached.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">The final piece of the puzzle is a squad manager, which assigns goals according to a pre-specified set of behaviours.  It groups NPCs by proximity, creating the illusion of cooperation even though individual NPCs are blissfully unaware of their squad-mates. Complex behaviours can arise, like pincer movements as a consequence of a command to move to cover closer to the player.<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" src=\"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/tamas-papp\/wp-content\/uploads\/sites\/13\/2020\/04\/pincer-1024x537.png\" alt=\"\" class=\"wp-image-627\" width=\"319\" height=\"167\" srcset=\"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/tamas-papp\/wp-content\/uploads\/sites\/13\/2020\/04\/pincer-1024x537.png 1024w, https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/tamas-papp\/wp-content\/uploads\/sites\/13\/2020\/04\/pincer-300x157.png 300w, https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/tamas-papp\/wp-content\/uploads\/sites\/13\/2020\/04\/pincer-768x403.png 768w, https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/tamas-papp\/wp-content\/uploads\/sites\/13\/2020\/04\/pincer.png 1329w\" sizes=\"(max-width: 319px) 100vw, 319px\" \/><\/figure><\/div>\n\n\n\n<p class=\"wp-block-paragraph\">And that&#8217;s it \u2014 no fancy machine learning methods needed. I think the main takeaway here is that solutions needn&#8217;t be complicated to be effective. For what is essentially repeatedly solving a shortest path problem, the end result is game AI that can really put the player in a pinch and tie the whole experience together. <\/p>\n\n\n<p><strong>Further reading &amp; viewing<\/strong><\/p>\n\n\n<p class=\"wp-block-paragraph\">[1] Orkin, J. (2006),\u00a0<a href=\"https:\/\/alumni.media.mit.edu\/~jorkin\/gdc2006_orkin_jeff_fear.pdf\">Three States and a Plan: The AI of F.E.A.R.<\/a>\u00a0<em>Proceedings of the Game Developer&#8217;s Conference (GDC)<\/em><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">[2] Thompson, T. (2014), <a href=\"https:\/\/www.youtube.com\/watch?v=rf2T_j-FlDE\">Facing your F.E.A.R.<\/a> <em>Lecture on videogame AI<\/em>, University of Derby<\/p>\n","protected":false},"excerpt":{"rendered":"<p>This is a bit of a different one, but I think it&#8217;s a decent showcase of Occam&#8217;s razor. I&#8217;ll be looking at how the enemy AI is designed in the video game F.E.A.R. F.E.A.R., Monolith Productions&#8217; 2005 first-person shooter game, was critically acclaimed for having some of the best non-player&#46;&#46;&#46;<\/p>\n","protected":false},"author":15,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"ngg_post_thumbnail":0,"footnotes":""},"categories":[21],"tags":[],"class_list":["post-617","post","type-post","status-publish","format-standard","hentry","category-miscellaneous"],"_links":{"self":[{"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/tamas-papp\/wp-json\/wp\/v2\/posts\/617","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/tamas-papp\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/tamas-papp\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/tamas-papp\/wp-json\/wp\/v2\/users\/15"}],"replies":[{"embeddable":true,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/tamas-papp\/wp-json\/wp\/v2\/comments?post=617"}],"version-history":[{"count":13,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/tamas-papp\/wp-json\/wp\/v2\/posts\/617\/revisions"}],"predecessor-version":[{"id":632,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/tamas-papp\/wp-json\/wp\/v2\/posts\/617\/revisions\/632"}],"wp:attachment":[{"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/tamas-papp\/wp-json\/wp\/v2\/media?parent=617"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/tamas-papp\/wp-json\/wp\/v2\/categories?post=617"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/tamas-papp\/wp-json\/wp\/v2\/tags?post=617"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}