Nikhil Ketkar

Typically in FPS/MMORPGs players spawn on some location in the map, move around performing tasks or shooting enemies. Given player movements in the form of walks in a map how can we cluster them to identify common trends? The first thing to do is to go from a continuous representation (series of x,y,z coordinates) to a discrete graph-based  representation of the map as a graph and player movements as walks ()on this graph (sequence of vertices). Once we have such a representation, we define a distance measure between two walks . There are may ways to do this, based on what we are interested in. For example, we might just be interested in the length of walks in which case the distance between two walks is the difference in the number of vertices. Another example would be where we are interested in the redundancy in the walks. Here we first compute the ratio of the unique vertices visited to the total vertices in the walk (for the two walks under consideration) and then compute the difference between these ratios for the two walks. Once we have a distance measure we can apply various clustering algorithms to the task.

Given this general idea, the next step would be to identify properties  we are interested in and come up with distance measures for them. It would also be a good idea to do some survey on clustering walks in graphs. It is quite hard to evaluate unsupervised learning but if interesting patterns are found, we will know that we are on the right track. Another way to evaluate this is to use the human player data and see if the clusters we produce match the different scenarios.