Track Player Movement in a First-Person Shooter Game 

In a first-person shooter game, an agent is hiding inside a level and waiting to jump out at the player. The agent cannot see the player, but can hear what they are doing and can then match that against its knowledge of the layout to estimate the player’s position. Consider a layout with 27 regions of four types—grass, metal grates, water, and door portals.

show complete Wolfram Language inputhide input

In[1]:=

X grass = Alternatives[1, 2, 4, 5, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]; metal = Alternatives[3, 6, 21, 22, 24, 25]; water = Alternatives[7, 8, 9, 10]; door = Alternatives[23, 26, 27];

Assign colors to the different types of regions.

In[2]:=

X colors = Transpose[{{grass, Green}, {metal, Gray}, {water, Blue}, {door, Brown}}];

Walking on the different terrain types produces different kinds of sounds.

In[3]:=

X {none, footsteps, splashing, creaking, unclear} = Range[5];

Probabilities of giving out sounds depends on the terrain type.

In[4]:=

X em = SparseArray[{ {{grass, none}, {grass, unclear}} -> {0.9, 0.1}, {{metal, none}, {metal, footsteps}} -> {0.1, 0.9}, {{water, splashing}, {water, unclear}} -> {0.9, 0.1}, {{door, creaking}, {door, unclear}} -> {0.9, 0.1}}, {27, 5}];

Visualize the layout of the level.

show complete Wolfram Language inputhide input

In[5]:=

X edges = {27 <-> 1, 1 <-> 2, 2 <-> 3, 3 <-> 4, 3 <-> 7, 4 <-> 5, 5 <-> 25, 25 <-> 24, 24 <-> 22, 22 <-> 21, 21 <-> 23, 21 <-> 20, 20 <-> 19, 19 <-> 18, 18 <-> 17, 17 <-> 7, 17 <-> 8, 18 <-> 9, 19 <-> 10, 10 <-> 9, 9 <-> 8, 8 <-> 7, 10 <-> 26, 10 <-> 14, 9 <-> 14, 8 <-> 13, 8 <-> 12, 14 <-> 15, 15 <-> 16, 14 <-> 13, 13 <-> 12, 13 <-> 11, 12 <-> 11, 11 <-> 6, 6 <-> 1};

In[6]:=

X regions = Range[27] /. MapThread[vert : #1 :> Style[vert, #2] &, colors];

In[7]:=

X gr = Graph[regions, edges, VertexSize -> Large, VertexLabels -> Placed["Name", Above], VertexShapeFunction -> "Square"]

Out[7]=

Assume the player enters through one of the doors with equal probability.

In[8]:=

X p0 = SparseArray[{door -> 1/Length[door]}, 27];

The player remains in the current region with probability 10%, and otherwise is equally likely to move to any of the neighboring regions.

In[9]:=

X adjm = AdjacencyMatrix[gr]; tm = 0.9 adjm/Total[adjm, {2}] + 0.1 IdentityMatrix[27];

In[10]:=

X hmm = HiddenMarkovProcess[p0, tm, em];

The agent hears the following sequence of noises.

In[11]:=

X obs = {creaking, none, footsteps, none, none, splashing, splashing, footsteps, splashing};

This shows that most likely the player entered through the door marked 27 and is currently in region 7.

In[12]:=

X FindHiddenMarkovStates[obs, hmm] /. MapThread[v : #1 :> Framed[v, FrameStyle -> #2] &, colors]

Out[12]=