R&D: Measuring In-Game Distance

Yuhan Fang (@iso646)

Your jungler just secured deep vision near enemy red buff. Where should he head now?

As any analyst will tell you, this depends a lot on positioning and timing. But how do you quantify positioning and timing in a way that uncovers an actionable statistical relationship? When trying to study this fairly innocuous-sounding problem, our team quickly realized that one common theme across many of the metrics we wanted to test was in-game proximity: proximity to tower, proximity to objectives, proximity to wards, proximity to the creep wave, and proximity to other champions.

Unfortunately, in-game proximity is tricky to measure. For most of the map simple linear distance is misleading. You need to consider the impact of terrain, flash, teleport, and champion abilities that can dramatically alter optimal pathing. In principle, you could playtest each champion across multiple pairs of locations in order to estimate proximities for a subset of common scenarios, but these tests would be time consuming, not scalable, and would still be highly sensitive to a number of edge-cases.

CG’s solution has been to build a pathfinding engine. We constructed a model of the map with all obstacles included (small sample depicted below). Combined with some small tweaks to the textbook A* algorithm, this gets us 70% of the way to optimal pathing. After heavy modifications to account for the various details around flash and abilities, and factoring in itemization, masteries, runes, and base stats, we arrive at an accurate “time to impact” (TTI) for any tracked entity between any two points of interest. The end result is a module that we are using to build a highly specialized game engine designed specifically for scenario analysis.

A section of Summoner’s Rift, according to our simulator

To give you some flavor on the level of abstraction we’re talking about, the API endpoint for this feature looks something like this (in Go, which if you haven’t heard, is freaking awesome):

// Simulator approximates in-game behavior with a proprietary
// simulation engine.
type Simulator interface {
// ...
  // Route returns the optimal path for a given player between
// two points, factoring in abilities and summoner skills.
Route(begin, end Point, player *Player) (*Path, error)
}
// TraversalTime returns the time required to execute the path,
// measured in in-game time.
func (p *Path) TraversalTime() (time.Duration, error) { // ...

On the backend, we stream all tracked games into our simulator to get a timeline of the (asymmetric) pairwise entity TTI matrix, and join this data with all of the usual Riot API output. At this point we upload a slightly transformed version to Google BigQuery. With this table cached, it is easy to start defining features and running additional analysis on top to correlate our metrics with various realized outcomes.

There are several immediate applications of this tool. But even more importantly, our approach to this problem has spawned a number of different questions and potential directions for further research. Some of these include the following:

  1. Can we simulate combat? We are exploring the feasibility of combining routing with combat so that we can optimize all-in gank timings as a function of positioning, itemization, experience, and champions.
  2. Can we use the game itself to avoid implementing a separate game engine? We are testing some ways of running experiments without requiring extensive development of our own simulator by scripting similar actions across multiple parallel custom games.
  3. Does the simulator assume a level of optimality that is realistic in actual gameplay? We’re punting this down the road for now, but this will be an interesting question to keep in mind as we examine in-house data in the months to come.

We are super excited to see what direction this research takes us, and how our results can be used to improve gameplay. We look forward to sharing when we learn more and progress in our mastery of the game. Questions? Comments? Suggestions on things to explore? Feel free to reach out!

Yuhan Fang (@iso646) is Head of Research and Development for Clutch Gaming.

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.