Automatic generation of battle maps from replay data

Abstract

With the advent of online gaming, access to in-game data has become increasingly important for players as it provides great opportunities for them to reflect and improve upon their gameplay or to compare their performance with others. Some of the currently most popular games focus on strategy and tactics, requiring players to skillfully position and maneuver units in order to achieve victory in battle. However, current visualizations for retrospective analysis of battles and that are targeted toward players are mainly limited to heatmaps and hence are not well suited for conveying the flow of battle. By contrast, military planners and historians alike have long used maps to provide a concise visual overview of troop movements. In this article, we are proposing an algorithm for automatically creating such battle maps from tracked in-game data. Several parameters allow to adjust the level-of-detail in the resulting maps. To demonstrate the practicality of our approach for post hoc analysis, we apply it to actual gameplay data obtained from a massively multiplayer online game and collected preliminary feedback among players of the game through an online survey.

Keywords

Player-centric visualization battle map trajectory analysis movement visualization game analytics

Introduction

The growing proliferation of Internet-enabled gaming devices during the last decade has made it possible for game developers to extensively track the in-game behavior of a large number of players. Alongside the rise of big data and data analytics in games user research, visual representations of the collected data have become an inevitable tool in order to make sense of, to interpret, and to communicate the collected data. Apart from their obvious importance for developers and researchers (see, for example, Wallner and Kriglstein¹), visualizations have also become an important resource for post-gameplay analysis for the player community itself. This is, on the one hand, reflected in the growing number of games which offer visualizations of gameplay data, for instance, in form of player dossiers (cf. Medler²) or which offer public application program interfaces (APIs) to access game data, such as Destiny³ or League of Legends.⁴ The player community, on the other hand, makes use of these APIs or other forms of replay data to build external tools or websites (e.g. Scelight⁵ or vBAddict⁶). Giving players access to their gameplay data allows them to reflect upon their progress and improve their skills⁷ and also offers a way for developers to foster competition among players⁸ as well as to promote community involvement⁷ and, in turn, increase the longevity of their games. Thus, it is surprising that the area of player-centric visualization remains hitherto large unexplored in academia. Recent surveys^7,9 reviewing data visualization in games in general (i.e. not limited to visualizing behavioral data of players) also conclude that visual representations within games are currently not very developed.

In this article, we contribute to this body of research by proposing an algorithm to automatically generate so-called battle maps from recorded behavioral data in order to provide a visual summary of how a battle unfolded. Battle maps provide a concise overview of a battle by showing troop movements and encounters of contending armies. Figure 1, for example, depicts a summary of the Battle of Chancellorsville, a major battle of the American Civil War, fought from 30 April to 6 May 1863. Specifically, it shows the events taking place on 2 May where Confederate General Thomas “Stonewall” Jackson led his corps (red) around the Union Forces (blue) to attack their unprotected right flank.

Figure 1.

Battle of Chancellorsville, Jackson’s Flank Attack, 2 May 1863 (Map by Hal Jespersen, www.cwmaps.com).

Currently, the predominant visualization of battle data targeted toward players is likely to be heatmaps of death concentrations or of frequent movements. While these provide a solid overview of aggregated data, they are not suitable for conveying the flow of battle. Given the long history of using maps to illustrate military campaigns (see also section “Related work”), we believe that such maps are also well suited to summarize matches of strategy or team-based (online) games. Battle maps have already been used in games, mostly, as part of briefings in war-themed games, such as Sid Meier’s Gettysburg¹⁰ or Sudden Strike II.¹¹ Other games have gone a step further and adapted battle maps for their user interface. Hearts of Iron 3,¹² for example, gives players themselves the possibility to draw battle plans onto the game map. These battle plans are, however, rather intended as a planning tool and cannot be used for controlling the units themselves. By contrast, the upcoming Hearts of Iron 4¹³ will allow the players to control their armies by using such battle plans, for example, by laying out troop movements or defense lines. A similar interface is used by Ultimate General Gettysburg¹⁴ where forces can also be controlled by dragging movement arrows across the battlefield. However, our setting is different from these examples as the maps are created from actual gameplay data after a battle took place in order to help players understand why a battle turned out the way it did. Several parameters allow to adjust the level-of-detail of the resulting map. As proof-of-concept, we apply our algorithm to replay data from World of Tanks¹⁵—a team-based massively multiplayer online game where two teams compete against each other. An evaluation¹⁶ conducted among World of Tanks players showed that the battle map visualization was well received by the community and that it is deemed useful for certain gameplay analysis tasks.

The remainder of this article is organized as follows. The next section reviews related work on movement aggregation and visualization, as well as approaches in the area of gameplay visualization which are relevant to the work presented here. Following that, the algorithm is described in detail. Afterwards, we present results based on World of Tanks replay data and summarize the findings from our evaluation.¹⁶ Before the paper is concluded, we discuss limitations and outline possible directions for future research.

Related work

For centuries, military forces and historians alike have relied on maps to visually convey the movements and encounters of contending armies. For example, the Library of Congress¹⁷ offers an extensive collection of historic maps of military conflicts and campaigns, whereas the Official Military Atlas of the Civil War¹⁸ provides a variety of maps of battles of the American Civil War. However, we are not aware of any algorithm which automatically creates battle maps from logged trajectory and combat data. Having said that, trajectory data analysis plays an important role in many different disciplines, such as traffic analysis, urban planning, or wildlife ecology and hence a lot of related work on analyzing and visualizing movement data has been published to date which is, however, too numerous to cover here in detail. An extensive review of movement analysis and visualization methods can be found, for example, in the recent review of Demsar et al.¹⁹ However, there are some works which should be specifically mentioned here. First, we make use of the territory tessellation method described by Andrienko and Andrienko.²⁰ In particular, they proposed a method to derive a Voronoi tessellation of the territory based on characteristic points of the trajectories. Bi-directional arrows were used to convey the amount of movement between pairs of adjacent cells. Also closely related to our approach is the work of Janetzko et al.²¹ who used DBSCAN clustering to automatically detect dense regions from the movement data and used their convex hull to visually represent these areas. This is conceptually similar to our approach, except that we perform the clustering on combat data (e.g. origin and target positions of gun fire) and take the temporal dimension into account in order to detect regions of interest (ROIs). An overview of spatio-temporal clustering methods with focus on geographical data in general and trajectory clustering in particular can be found in Kisilevich et al.²² and Parent et al.,²³ and on the other hand, provide an introduction to semantic trajectories—another concept used in our algorithm—whereas measuring the similarity between semantic trajectories has, for example, been addressed by Ying et al.²⁴ and Lin and Schneider.²⁵

In terms of visualization, flow maps—Minard’s map of Napoleon’s march on Russia (see, for example, Tufte²⁶) being a prime example here—bear some resemblance to our approach as they too visualize the movement of objects between locations by merging edges in order to reduce visual clutter. Despite their popularity, however, few algorithms for automatically generating flow maps have been proposed to date, among them, the approach of Phan et al.²⁷ which makes use of hierarchical clustering. More recently, Verbeek et al.²⁸ presented another algorithm for generating flow maps, addressing some drawbacks of the former technique such as occasionally occurring edge crossings and the sometimes counter-intuitive routing of flows. However, typical flow maps only show the flow from a single source to several destinations (although multiple such flow trees can be combined in a single map) while we also need to take loops between locations into account. In addition, many flow maps abstract from the actual routes of the flow, whereas the routing in our approach is based on the trajectories of the units.

The benefit of aggregating trajectories to facilitate analysis of movement behavior of a large number of individuals has also been recognized in the context of virtual environments and games. Börner and Penumarthy,²⁹ for example, have clustered users of a three-dimensional virtual learning environment into social groups with each group being represented by a single path, specifically by the centroid of the group members’ trails. The spatial distribution of the group members is reflected by the width of the centroid. Chittaro et al.³⁰ made use of flow visualization techniques to visualize navigation patterns. For that purpose, they derived a vector field from the movement data by partitioning the virtual environment into small cells. Turning briefly to flow visualization in general, McLoughlin et al.,³¹ for instance, took advantage of agglomerative clustering to group similar streamlines together in order to reduce the visual complexity of flow visualizations while at the same time ensuring the representation of distinct features of the flow field.

Hoobler et al.’s³² work on visualizing behavior patterns in Return to Castle Wolfenstein: Enemy Territory is perhaps the most closely related work in the domain of gameplay visualization as it is also concerned with conveying the evolution of actions over time in team-based combat games. Indeed, their system visualizes similar aspects of gameplay such as movements and lines of fire (among others) but focuses on individual players and as such may not scale readily to games where larger number of players or units are involved. In contrast, our objective is to provide an aggregated summary of the battle. Also worth mentioning is the work of Gagné et al.³³ which focuses on visualizing player data from a real-time strategy game called Pixel Legions, but contrary to our intention, their system focuses on visualizing non-aggregated data from multiple sessions and is geared toward developers. Mitterhofer et al.³⁴ proposed a method to distinguish between bots and humans based on recorded movement data. Taking advantage of the fact that bots follow a list of predetermined locations, they derive an abstracted route representation by using line simplification and clustering. Miller and Crowcroft³⁵ used Mitterhofer et al.’s³⁴ approach and coupled it with the landmark detection method proposed by Thawonmas et al.³⁶ to characterize avatar movement in World of Warcraft. Contrary to these approaches, we are not relying on traditional line simplification algorithms as these are focused on maintaining the shape and thus do not take specific properties of the movement into account (see, for example, Chen et al.³⁷ and Andrienko et al.³⁸), such as pauses which can be relevant for our purpose.

Narrowing the focus to visualizations specifically concerned with World of Tanks, there exist three noteworthy examples which are orientated toward players themselves. First, the community website vBAddict⁶ provides visualizations that present battles from the perspective of one team, including individual unit trajectories, kill locations, and spotting of enemy units. Again, our goal is different in that we strive for a more global view to depict high-level strategies. WOT Tactics³⁹ and StratSketch,⁴⁰ on the other hand, are tools which allow users to create battle plans by offering drawing tools to, for instance, map out troop movements or suitable areas for lines of defense. However, these tools are rather intended to plan and discuss possible strategies in advance while our proposed approach generates strategic maps from replay data to reflect the actual course of a battle.

Algorithm

The proposed algorithm takes as input a trajectory for each involved unit. In our case, such a trajectory $T$ is a list of chronologically ordered spatio-temporal positions $p = (x, y, t)$ , where $(x, y)$ represents the spatial coordinates at time $t$ (times are expressed relative to the onset of a match, that is, $t = 0$ when the battle commences). In addition, it is necessary to know when a unit attacks another unit. We will refer to such a situation as an encounter. An encounter is characterized by a tuple $e = (p_{A}, p_{T})$ , where $p_{A}$ is the spatio-temporal position of the attacking unit and $p_{T}$ the position of the target. For simplicity and without loss of generality, we will assume in the following that the time stamps of $p_{A}$ and $p_{T}$ are equal. Based on this input data, the algorithm derives a battle map to give a high-level summary of the combat data. Figure 2 gives an overview of the major steps involved in the calculation of a battle map, and Figure 3 visualizes the result after the various steps. Figure 3(a) shows the input data of the example which will be used throughout the description of the algorithm. Trajectories are represented as colored lines with their thickness increasing with time. The colors (red and blue) reflect the forces the units belong to. Positions of units when being attacked or attacking are marked with black dots and arrows depict lines of fire. In the following, the individual steps are discussed in detail.

Figure 2.

Major steps for creating a battle map from in-game data. First, regions of interest (ROI) are extracted from the input data. Afterwards, fights between ROIs are identified and high-level movements are derived from the individual unit trajectories. Finally, the resulting data are visualized.

Figure 3.

Graphical representation of the result after various steps of the battle map algorithm: (a) input data consisting of unit trajectories, shooting and target positions, and lines of fire, (b) identification of battle regions by spatial and temporal clustering of shooting and target positions, (c) Voronoi tessellation of the area based on trajectory data (calculated separately for each opposing force; in the present case for the blue team), (d) derivation of semantic trajectories based on the ROIs identified in steps (b) and (c) and user-defined ROIs (in this case, base camps), and (e) final map, including battle regions and aggregated movement and attack arrows.

Regions of Interest

The resulting battle map will describe high-level unit movements between certain Regions of Interest (ROIs). Such ROIs can, for example, be base camps, locations of objectives, or places where battles were fought—henceforth referred to as battle regions.

Battle regions can be considered as areas with densely distributed shooting and target positions which occur within short succession of each other. This temporal dimension is an important aspect as battles which take place in the same area but at different points in time should be treated as distinct battles rather than a single entity in order to better reflect the chronology of events. Battle regions are automatically extracted from the input data by employing the DBSCAN clustering algorithm.⁴¹ We have opted for DBSCAN because of its ability to discover clusters of arbitrary shape and varying density (the density of points may differ from battle to battle). In addition, outliers are not assigned to any cluster which is beneficial in our case since occasional encounters distant to dense areas are ignored. Moreover, the number of clusters does not need to be specified in advance. Instead, DBSCAN requires to specify the minimum number of points $MinPts$ which need to be within a user-defined radius $ϵ$ around a point $p$ in order to form a cluster (i.e. a battle region). Following Birant and Kut,⁴² we included a second parameter to handle temporal constraints, that is, only points which are within a specified time range $ϵ_{t}$ are considered as temporal neighbors and are thus taken into account for the spatial query.

The duration of a battle $(t_{start}, t_{end})$ is given by the minimum and maximum time-stamp associated with the points belonging to the battle region. The shape of a battle region is described by its convex hull. Pseudo-code for deriving battle regions from encounters is given in Listing 1. Figure 3(b) shows the extracted battle regions from our input dataset depicted in Figure 3(a). Numbers next to each battle region depict the start and end time of the battle in seconds. Other ROIs, such as the formerly mentioned base camps or locations of mission objectives may, for example, be manually defined or extracted from a map definition file (see, for example, the World of Tanks use case presented later). Such ROIs may also have a duration assigned or may last for the whole match.

Listing 1.

Detection of battle regions (br.points denotes the list of points belonging to the battle region br). Implementation details of the DBSCAN algorithm can be found in Ester et al.⁴¹

Attacks

Once battle regions have been determined, attacks between these regions are identified. Attacks are directed, that is, one region is considered the origin and the other the target of the attack. Thus, at most two attacks between two battle regions $B R_{1}$ and $B R_{2}$ can occur, one originating from $B R_{1}$ and targeting $B R_{2}$ and vice versa. Attacks are derived from the individual encounters by examining the clusters associated with $p_{A}$ and $p_{T}$ of an encounter. If $p_{A}$ is part of a battle region $B R_{x}$ , $t_{start} (B R_{x}) \leq t (p_{A}) \leq t_{end} (B R_{x})$ and $p_{T}$ is part of $B R_{y}$ , $t_{start} (B R_{y}) \leq t (p_{T}) \leq t_{end} (B R_{y})$ then the encounter contributes to the attack from $B R_{x}$ to $B R_{y}$ . In the end, the number of encounters contributing to an attack determines its strength. Listing 2 summarizes these steps.

Listing 2.

Identification of attacks between battle regions (br indicates the battle region a point belongs to).

Trajectory processing

In this step, individual trajectories are simplified and grouped in order to convey high-level movements between ROIs. For this purpose, the trajectories are first pre-processed by extracting their characteristic points, such as start and end points, pauses, and significant turning points, in order to reduce the computational requirements for the subsequent territory tessellation. Based on the territory tessellation and the ROIs, a semantic trajectory $T_{S}$ is then derived from each $T$ . Generally speaking, such a semantic trajectory is a sequence of landmarks (cf. Ying et al.²⁴). Finally, semantic trajectories which are similar to each other are grouped together. This process is performed separately for the trajectories of each involved army.

Territory tessellation

For extracting the characteristic points and territory tessellation (cf. Listing 3), we follow the algorithm described by Andrienko and Andrienko.²⁰ In short, the algorithm takes as input a set of trajectories, extracts their characteristic points, and clusters these points based on their spatial proximity. The centroids of the clusters are then used as generating points for a Voronoi tessellation. The resulting tessellation thus reflects the spatial distribution of the characteristic points of the original trajectories. The algorithm requires several input parameters which influence the extraction of the characteristic points (namely, $d_{\min}$ —the minimum distance below which two positions in the input trajectory are treated as the same position, $d_{\max}$ —the maximum allowed distance between two characteristic points, $α_{\min}$ —minimum angle between two consecutive line segments to be considered a turning point, and $Δ t_{\min}$ —the minimum time spent at approximately the same location to count as pause) and the cell size for the Voronoi tessellation, specifically, the maximum radius $r_{\max}$ of a cluster of positions. Figure 3(c) shows, by way of example, the resulting tessellation for the blue forces.

Listing 3.

Territory tessellation (bounds denotes the extents of the map, $†$ for implementation details, see Andrienko and Andrienko²⁰).

Semantic trajectories

Next, semantic trajectories $T_{S}$ —that is, sequences of landmarks (cf. Ying et al.²⁴)—are derived from the trajectories based on the cells of the Voronoi tessellation (referred to as $V C_{1}$ , $V C_{2}$ , … in the following) and the identified ROIs (see section “ROIs”) using the following procedure. For each trajectory $T$ , we first find the landmark $l_{1}$ containing its first position $p_{1}$ . Next, we iterate through the subsequent positions until a position $p_{n}$ is found which is not contained in $l_{1}$ and determine the landmark $l_{n}$ for $p_{n}$ . Then, the procedure is repeated starting at $p_{n + 1}$ until the next point not contained in $l_{n}$ is found and so on. The time stamps when a trajectory enters and leaves a ROI are stored for later use. When determining the landmark (a ROI or cell) for a position, ROIs are given precedence over Voronoi cells. That is, if a position $p$ is also within the extents of a ROI, then the ROI constitutes the landmark for $p$ . Please note, that $p$ is only considered to be within a ROI $r$ if the unit was at $p$ while $r$ was active, that is, $t_{start} (r) \leq t (p) \leq t_{end} (r)$ . For example, $T_{S}$ of the pink trajectory in Figure 3(d) is given by ( $Bas e_{1}$ , $V C_{0}$ , $V C_{9}$ , $V C_{2}$ , $Battl e_{99 - 111}$ , $V C_{7}$ , $Battl e_{99 - 111}$ , $V C_{7}$ , $V C_{10}$ , $V C_{8}$ , $Battl e_{87 - 195}$ ). In our case, a semantic trajectory can thus be considered as an abstraction from the original geographic trajectory. Based on the choice of $r_{\max}$ for territory tessellation, a semantic trajectory reflects more or less nuances of movement.

As the final map should show movements between ROIs, the semantic trajectories are then divided into sections, with each section starting and ending at a ROI. For instance, taking our former example, $T_{S}$ would be broken into the three sections ( $Bas e_{1}$ , $V C_{0}$ , $V C_{9}$ , $V C_{2}$ , $Battl e_{99 - 111}$ ), ( $Battl e_{99 - 111}$ , $V C_{7}$ , $Battl e_{99 - 111}$ ), and ( $Battl e_{99 - 111}$ , $V C_{7}$ , $V C_{10}$ , $V C_{8}$ , $Battl e_{87 - 195}$ ). However, units may repeatedly move back and forth between two landmarks as it is, for example, the case in the second section of our ongoing example, where the unit leaves the battle region $Battl e_{99 - 111}$ , shortly ventures into $V C_{7}$ only to enter the same battle region shortly thereafter again. Such alternations of two neighboring landmarks may negatively influence the calculation of trajectory similarity later in the process and are thus removed from the sequences. To be more precise, we iterate through the landmarks of a section and if the same landmark appears at the current index $i$ as well as at $i + 2$ , then the landmarks at $i + 1$ and $i + 2$ are removed from the sequence. Sections that consist only of a single landmark after simplification are omitted from further processing. These steps are illustrated for a single trajectory $T$ by the pseudo-code given in Listing 4. The remaining sections are then grouped together based on their similarity in the next step.

Listing 4.

Derivation of a semantic trajectory from a given trajectory and subsequent decomposition into sections (the function splitIntoSections separates a semantic trajectory into individual sections which all start and end at a ROI by iterating through the list of landmarks).

Grouping of sections

First, sections are partitioned into sets $S_{1}, \dots, S_{n}$ , according to their origin and destination ROI. However, sections within the same set cannot simply be considered as a single group for visualization since different units may have used different paths to reach their destination (e.g. a team may split its forces to attack from multiple sides). To provide for such cases, sections within each set are further grouped based on their similarity. For this purpose, we adopt the longest common subsequence (LCS) between two semantic trajectory sections as similarity measurement as it has shown to be well suited for this task (cf. Ying et al.²⁴ and Liu and Schneider²⁵). Given two sections $A$ and $B$ , the similarity $δ (A, B)$ , $0 \leq δ (A, B) \leq 1$ is given by

δ (A, B) = 0.5 (\frac{| LCS (A, B) |}{| A |} + \frac{| LCS (A, B) |}{| B |})

(1)

where $LCS (A, B)$ is calculated using dynamic programming (see, for example, Wagner and Fischer⁴³). If $δ (A, B)$ is greater than a user definable similarity threshold $σ$ , then the two sections are considered similar. If $δ (A, B) = 1.0$ , then $A$ equals $B$ . All sections of a single set $S$ are then grouped using DBSCAN and $δ$ as similarity measurement. The minimum number of elements to be contained in a cluster is set to one. Please note that the clustering is performed individually for each $S$ and not over all sections as otherwise sections that connect different ROIs may be grouped together (which would be contrary to our goal). Listing 5 summarizes this process.

Listing 5.

Grouping of sections.

Representative trajectory

As final step, a representative trajectory that describes the overall movement of the individual sections within each group is derived. To this end, we explored two possibilities: one makes use of the medoid and the other is based on computing the central trajectory.

In the former case, the section with the highest average similarity to all other sections within a group is chosen as representative, whereas similarity is again defined by equation (1) (see also Listing 6). With regard to the latter case, first, the parts of the input trajectories covered by the sections of a group—defined by the time a trajectory enters the starting ROI and the time it leaves the target ROI of a section—are determined. Next, the minimum entry time $t_{\min}$ of all sections and the maximum exit time $t_{\max}$ of all sections of a group are determined. The locations of the centralized trajectory are then calculated by averaging the positions of the individual trajectories at different points in time, starting at $t_{\min}$ and continuing in steps of $Δ t$ until $t_{\max}$ is reached (refer, for example, to Andrienko et al.⁴⁴ for implementation details). If a trajectory is undefined at a certain time point, then this trajectory does not contribute do the average position. Finally, the centralized path is converted back into a semantic trajectory using the process outlined in section “Semantic trajectories.”

Listing 6.

Derivation of a representative trajectory (medoid approach) for a group of sections.

Visualization

Figure 3(e) shows the final battle map for our ongoing example. To arrive at this representation, a closed Bezier spline is first derived from the convex hull of each battle region. The area enclosed by this curve is cross hatched if close encounters within the area have occurred, that is, when at least one unit within the battle region attacks another unit within the same region. Otherwise (e.g. a group of units of an army is attacked from somewhere else by artillery) the area is left blank. Each battle region is further surrounded by a second slightly inflated and thicker spline curve.

Troop movements are visualized by spline curves derived from the representative trajectories, that is, the centers of the landmarks (either a Voronoi cell or a ROI, see section “Semantic trajectories”) of a representative trajectory are used as control points for a spline curve. Arrow heads are used to indicate the direction of movement. Each spline curve is trimmed at the ends such that it starts at the boundary of the starting ROI and ends at the boundary of the target ROI. Finally, curves are shortened by the length of the arrow heads which, in turn, are bent toward the closest point on the target ROI’s boundary. The direction is further accentuated by the thickness which increases along the curve with the thickness at the base of the arrow head being proportional to the number of involved units. Movement arrows are colored based on the army responsible for the troop transfer.

Attacks are represented by an arrow which is either straight if the attack is unidirectional or slightly bent in case the attack is bidirectional. This way attack arrows between the same two battle regions do not occlude each other. Similar to above, the thickness of the arrow reflects the strength of the attack and the color indicates the army that carried out the attack. In the event that more than one army contributes to an attack then the coloring reflects the share of each army’s contribution. Furthermore, attack arrows are rendered semitransparent such that the map and the movement arrows underneath are still apparent. To reduce occlusions further, arrows are also faded out at their base.

Parameters

The resulting battle map can be influenced by adjusting the control parameters of the various steps outlined above. In the following, these parameters are shortly summarized and explained.

Clustering ( $MinPts$ , $ϵ$ , $ϵ_{t}$ )

These parameters influence the size and the number of battle regions. Generally speaking, lower numbers for $MinPts$ and higher values for $ϵ$ will generate larger battle regions, while higher values for $MinPts$ and lower values for $ϵ$ will find more geographically confined and dense battle regions. Similarly, larger values for $ϵ_{t}$ will result in battle regions spanning longer periods of time. However, using too large values for $ϵ_{t}$ can be disadvantageous as it also increases the chance that battles that took place at different points in time are considered as one and the same although they should be treated separately. In contrast, more restrictive values for $ϵ_{t}$ will separate these regions into several regions covering shorter time intervals.

Characteristic points ( $d_{\min}$ , $d_{\max}$ , $α_{\min}$ , $Δ t_{\min}$ )

These parameters influence how well the simplified trajectories correspond to the original input data. As such these parameters ultimately influence—along with other parameters—the final routing of the movement arrows. For example, simplifying the trajectories too much will remove the subtleties and nuances contained in the original trajectory. A detailed explanation of the effect of the various parameters can be found in Andrienko and Andrienko.²⁰

Territory tessellation ( $r_{\max}$ )

The parameter $r_{\max}$ controls the abstraction level of the final movement arrows, with higher values for $r_{\max}$ leading to a coarser tessellation and thus a higher level of abstraction.

Trajectory aggregation ( $σ$ )

This parameter controls the number of movement arrows in the final map. The higher the $σ$ , the more similar the two semantic trajectory sections need to be in order to be combined into a single group. As a consequence, more groups with less members (i.e. units) are likely to be created. While these groups better reflect the individual unit movements—as all contained unit trajectories are very similar—too many individual arrows may impede readability of the map. However, a more lenient threshold will group less similar trajectories together leading to groups with more units and thus to a more generalized representation of the unit trajectories.

We should also stress here that providing default parameter values is difficult as the values need to be chosen with respect to the dimension of the game map and should ideally also take the geographical aspects of the map into account (e.g. a narrow urban map may require different parameters compared to a mostly open map). In the reminder of this article, we will assume that all coordinates range from −1 to +1. Figures 4 and 5 illustrate, by way of example, the influence of the trajectory-related parameters and clustering on the generated battle map. Note that $r_{\max}$ has been kept constant in case of Figure 4(b) but the different point distributions—resulting from the different settings for extracting characteristic points—affect the territory tessellation (and therefore also the final routing of movement arrows).

Figure 4.

Examples of movement arrows generated by varying the values of the input parameters. Individual unit trajectories are depicted with light blue lines. In each case, the medoid of the groups has been chosen as their representative trajectory: (a) influence of the parameters σ and r_max on the derived movement arrows. A stringent threshold for σ keeps the individual unit trajectories separate (left) while reducing the threshold by half groups the three trajectories together (middle). r_max controls the level of abstraction with smaller values preserving the variations in movement of the representative trajectory and larger radii smoothing out these variations (right). (b) settings for extracting characteristic points (represented by small dots) influence how well the simplified trajectories resemble the original data. Left: fine approximation of the original trajectory. Right: very strong simplification of the input trajectories.

Figure 5.

Impact of the clustering parameter $ϵ$ on the size of the extracted battle regions. $MinPts$ and $ϵ_{t}$ were kept constant.

Use case: World of Tanks

In this section, we apply the algorithm to replay data from World of Tanks¹⁵—a free-to-play massively multiplayer online action game that pits two teams against each other on different maps. Each player controls a single armored vehicle, and once the vehicle gets destroyed, the player is out of the game and cannot re-enter the battle. To win a battle, a team must either destroy all units of the opposing team or capture the enemy base, depending on the game mode.

Methodology

World of Tanks allows the player the record battles and store them in a replay file. Replay files contain information necessary to re-simulate a battle such as unit locations and tanks getting shot or destroyed. However, replay files are recorded from the viewpoint of a specific player. In other words, a replay file only contains the complete movement data from units of the player’s own team. Movement of enemy units is only available while they are within the field of view of the recording player’s team members. This means that in order to reconstruct the full battle, two replay files are necessary, one from a player of each team. To obtain such pairs of replays, we searched the results section of the Wargaming League Europe Bronze Series on the ESL website⁴⁵ for matches where replays from both sides were available. All matches which replays are used in the following took place between December 2014 and January 2015. During this period, matches were played in assault mode with two capture circles and each team consisting of seven players. The maximum duration of a match was 7 min. In this mode, one team acts as attacker (henceforth the red army) which has to capture one of the two bases (i.e. capture points) of the defenders or destroy all enemy vehicles in order to win. The defenders (blue army), in turn, have to destroy all attacking units or survive the battle with at least one unit while at the same time protecting their bases from being conquered.

The obtained replays were then decoded and converted to text-based JSON (JavaScript Object Notation) files for further processing using the World of Tanks Replay Parser.⁴⁶ Movement data of the individual units can be readily extracted from the JSON files. However, shoot and target locations need to be reconstructed as these locations are not directly stored; rather, the replay contains information which player is doing damage to another player at what time. To determine the shoot and target positions of encounters, we thus use the time-stamp $ts$ associated with the damage event to search through the formerly extracted trajectories of the involved units and obtain the position with the time-stamp closest to $ts$ . Base positions and spawn points were defined as circular areas in which center was obtained from map definition files.⁴⁶ All positions were normalized to the range $[- 1 \dots 1]$ . The extracted data, that is, unit trajectories, encounters, and base and spawn locations, were then fed into the battle map algorithm.

Results

Figures 6 and 7 show battle maps—along with the original input data—derived from replay data of two battles taking place on the maps: Cliff and Steppes, respectively. In both cases, the centralized path was chosen as the representative trajectory for movement arrows. Capture points (bases) are depicted with a flag while the spawn points of the teams are shown using a cabin icon in the respective color. In case of Cliff, the spawn point of the blue team coincides with the capture point in the north-west corner of the map. Steppes is an open expanse of fields and gentle hills with some rock formations on the boundary of the map offering opportunities for cover and ambush while Cliff features a more mountainous landscape with valleys and rocky hills. Generally, the same settings have been used to generate both maps, but in case of Cliff, the parameter for territory tessellation and the $ϵ$ -radius for clustering have been reduced to account for the spatially more confined territory.

Figure 6.

Red forces win by capturing the enemy base located in the top left corner. Left: input data; right: corresponding battle map ( $ϵ = 0.15$ , $ϵ_{t} = 60$ , $MinPts = 5$ , $r_{\max} = 0.15$ , $σ = 0.7$ ).

Figure 7.

Red forces win by destroying all enemy units. Left: input data; right: corresponding battle map ( $ϵ = 0.20$ , $ϵ_{t} = 60$ , $MinPts = 5$ , $r_{\max} = 0.20$ , $σ = 0.7$ ).

In case of Figure 6, the red army followed a more successful strategy, ultimately winning the battle by capturing one of the two bases of the blue team. As evident from the map, the red team has decided to split its forces at its base with the majority of the units moving to the north-east. About half of these units proceeded up the hill located at the eastern side of the map—taking advantage of the elevated position to overlook and attack the blue forces to the north—while the other half took position at the foot of this hill to prevent the enemy team from breaking through. The blue team, however, concentrated all their forces to the east, attacking the tanks of the red army located on the hill and the field below. Meanwhile, a few units of the red team advanced along the valley on the western side of the map to outflank the enemy and capture their base.

Continuing with the second example (Figure 7), the red army has won again but this time by destroying all enemy units. First, the red army moved units to the western flank of the battlefield using the rock formations as cover and firing at the enemy units moving toward the open field in the center of the map. Counterattack by the blue forces proved less efficient—either because the tanks of the red team were more difficult to hit due to the shelter provided by the rocks or because players were less skilled—as conveyed by the much thinner blue attack arrow. Second, the red team has positioned some tanks immediately to the east of its base to defend it against the blue forces. These tanks were heavily under fire from the blue army’s tanks located at the eastern flank while at the same time attacking units located in the battle regions to the east and north. Close combat concentrated on the two battle regions (cross hatched) in the middle of the map.

Figures 8 and 9 show two further examples to illustrate how changes in the parameters influence the resulting battle maps. Figure 8 shows a battle that took place on the game map Himmelsdorf—an urban map largely made up of narrow streets. To account for this confined environment, the left map depicted in Figure 8 uses a small value of 0.1 for $r_{\max}$ . This way the tessellation consists of smaller cells and the resulting movement arrows better reflect the actual paths taken by the tanks. They thus follow the actual street layout more closely. In contrast, the larger value of $r_{\max} = 0.27$ used in the right map produces larger cells which do not capture the spatial characteristics of this particular map very well. This causes the movement arrows to deviate from the actual roads and cut through buildings, particularly observable in the red movement arrows (e.g. in the lower right quadrant). The distance threshold $ϵ$ used for clustering has also been set to a smaller value such that encounters taking place in neighboring streets are not grouped into a single battle region. It is also worth noting that long-range attacks are seldom and confined to the square at the northern boundary of the map. This is, however, not surprising given that the closely spaced buildings make long-distance attacks difficult.

Figure 8.

Varying $r_{\max}$ influences the level of abstraction of the movement arrows. The finer tessellation employed in the left image is better suited to capture the movement in the narrow streets (resulting territory tessellation for the red team has been added for illustration purposes).

Figure 9.

The clustering parameters $ϵ$ and $ϵ_{t}$ influence the size and number of battle regions. While the left map provides a more detailed perspective on combat, the higher $ϵ$ -threshold used in the right map abstracts away most of these details. The finer territory tessellation utilized in the right image, however, leads to more—and more accurate—movement arrows.

The battle depicted in Figure 9 was fought on the map Prohorovka, a map offering large expanses of open but hilly terrain with clusters of trees and little opportunities for cover. As with the Steppes map above, these open spaces allow for more variety and freedom in movement. To smooth out these subtleties, a larger threshold of $r_{\max} = 0.26$ was used for territory tessellation for the battle map on the left. Furthermore, a rather small distance threshold of $ϵ = 0.15$ was chosen to obtain more geographically confined battle regions. In addition, the minimum number of points $MinPts$ was set to 7 to exclude small fights from the final map. A number of interesting observations can be made from this map. First, both teams moved about half of their units toward the center of the map where they got engaged in close combat. The red forces then eventually retreated to the west with both teams continuing to fire at each other. Meanwhile, the red team also flanked the blue troops by following the road on the west side of the map northwards and provides supporting fire for their teammates caught up in battle in the center of the map. However, these units also got entangled in close fights with the blue forces and in the end the blue army successfully defended both bases. The right map, by contrast, leaves out much of these combat-related details as the larger $ϵ$ -threshold groups the shoot and target locations into larger clusters. Most obviously, the three individual battle regions of the left map near the center of the map are combined into one large battle region. The lower radius used for territory tessellation for the right map, however, produces movement arrows which more accurately resemble the actual routes taken by the players. In addition, as the map offers plenty of room for movement, the finer subdivision also makes it less likely that individual trajectories are grouped together (as the similarity threshold $σ$ has been kept constant in both maps) thus resulting in a larger number of movement arrows.

Evaluation

To assess the appropriateness of our approach for post hoc battle analysis, we conducted an evaluation with World of Tanks players by means of an online survey. The survey compared three battle visualizations, including the battle map discussed here, the so-called versus view offered by the popular statistics website vBAddict⁶ which juxtaposes two maps with each one showing the battle from the perspective of one team, and one-third visualization which merges the two views of the versus visualization and augments it with the lines of fire (akin to the visualization used to visualize the input data in this article, for example, Figure 7, left).

All three visualizations were evaluated, among others, with respect to different cartographic and data visualization design principles such as clarity and esthetics, how well the maps can be interpreted, and for which tasks the visualizations are deemed suitable. For each visualization, three versions (based on different replay files, including the maps shown in Figures 6 and 7) were created yielding a total of nine visualizations of which each participant was shown three (one of each type) in randomized order to control for ordering effects. The results of this evaluation are described in detail elsewhere.¹⁶ Nevertheless, in order to make this article self-contained, we will summarize the most important findings concerning the battle map in the following.

In total, we received 41 complete responses from players aged 15–51 years ( $M = 27.1$ , $STD = 9.8$ ) with four respondents being female. The vast majority of the participants can be considered to be very experienced or at least intermediate World of Tanks players as they fought on average 12,000 battles and have amassed, on average, approximately 6,700,000 experience points.

Figure 10 summarizes the ratings (across all three maps) of the battle map with respect to seven different quality measures which were rated by the participants on a 5-point scale anchored by poor (1) and excellent (5). In general, the visualization was rated quite positively with mainly accuracy and ease of extraction being rated lower. The lower ratings in case of the former are, however, not surprising giving that the battle map approach trades accuracy for a concise and high-level view of a battle. In terms of the latter, participants were divided in their ratings with some of them finding it easier to extract information from a battle map than others. However, these mixed ratings are only partly reflected by the data collected to assess how well the visualization is interpreted by the players. For that purpose, each participant had to answer 10 true/false statements which covered different facets of the depicted battle, including questions about troop movements and attacks (to avoid ambiguities in the statements and ease referencing of areas, labels were added to the visualizations). As a consequence, these statements differed from battle map to battle map, yielding a total of 30 questions. For example, concerning troop movements, the survey included statements such as Team 1 moved part of their units to area B and then continued to area C with the same number of units or Team 1 split its forces at their base with the larger fraction going to area A. Examples of attack-related statements are as follows: Attack rate from area A to C was larger than from C to A; A battle between units of different teams took place within area A; and Team 2 attacked units in area A from areas B and C.

Figure 10.

Boxplot—median, interquartile range, minimum, and maximum (whiskers)—summarizing the ratings (1 = poor, 5 = excellent) with respect to seven different criteria.

On average, statements were answered correctly by 84.3% of the respondents. Participants mostly struggled with statements concerned about troop movements when movement arrows of the same color were overlapping each other like it is, for example, the case for the red arrows in Figure 6 (right). In such cases, the mean correctness ranged between 40.0% and 64.3%.

As part of the online questionnaire, participants were also asked for which types of questions they believe the battle map is most suitable. A qualitative content analysis (cf. Schreier⁴⁷) identified five major categories of questions for which the battle map was considered useful, namely, questions concerning:

Areas of interest such as zones of conflict, areas where troops gather, or choke points (18 statements)

Map strategies and tactics (12 statements)

Team movements (11 statements)

A quick overview of the flow of battle (8 statements) and, to a lesser degree, also for questions about

Combat (5 statements)

However, participants found the visualization to be particularly ill suited for questions dealing with the movement and positioning of individual units as well as for understanding aspects of reconnaissance such as where enemy units were spotted. In summary, we can state that the battle map proved to be suitable for gaining a general understanding of a battle, that is, high-level information about areas of interest and troop movements. The good readability and the general overview of a battle were also the major reasons for some participants to prefer the battle map over the other two investigated visualizations. For others, however, the lack of detail was the main reason for ranking the battle map lower in terms of personal preference.

In addition, to the results summarized above and reported previously,¹⁶ we asked players ( $N = 41$ ) for suggestions for improvement and about any important information they think is absent from the battle map. Responses to this question were then explored through qualitative content analysis by two researchers. Differences in the coding were resolved through discussion. Eventually, this process revealed five key areas for improvement. First and foremost, players were missing information about the exact death (and shooting) locations of units (15 statements). Respondents also wished for a more precise designation of troop numbers (14 statements). For instance, one participant noted that the arrow thickness while being an indicator is very unclear. Respondents would also have liked to have more details regarding the temporal qualities of the battle (7 statements) such as the ordering of attacks and movements, duration of certain events, and the like. Others, in turn, asked for some kind of possibility to see where units of the enemy team were spotted (5 statements). Five participants also expressed a need for further details regarding the types of units (e.g. light or heavy tanks, artillery) that were involved in a battle or of which troop formations were composed of. Beside these five frequently raised suggestions, respondents also recommended to include information about firing lines (3 statements), the types of attacks (2 statements), the outcome of each battle region including details concerning the winner/loser, the number of tanks lost, and so on (2 statements), and about the speed of the moving units (1 statement).

However, when asked about if the battle maps contain any unnecessary information, almost all participants (92.7%) agreed that none of the elements displayed is superfluous.

Discussion

When interpreting the results of the player questionnaire presented above, it should be kept in mind that all the respondents were rather experienced World of Tanks players and as such are likely to have certain expectations on what information should be represented in a battle summary. This may also explain the comparatively low rating of accuracy as experienced players may be more interested in more detailed information (e.g. spotting of enemy units, exact locations of kills) than, for example, casual players. However, we should point out that our evaluation¹⁶ did not show any correlation between the accuracy rating and the number of collected experience points nor with the number of battles fought, though this might result from the our skewed sample toward highly experienced player. In future work, it may thus be worthwhile to explore differences between novices and experts in greater detail.

Further work will also focus on ways to include the additional information asked for by the participants (e.g. information about troop strengths, kill locations, details about units, and battle outcomes) into the battle map visualization. For example, the strength of forces could be conveyed by adding numerical labels to movement arrows and the outcomes of battle sites could be indicated by coloring the hull enclosing a battle region with the winning team’s color. However, a fundamental challenge in map making is to avoid information overload while at the same time ensuring clarity and readability. At this point, we should also emphasize that the goal of this work was to produce maps which provide all the important information regarding a battle at a single glance. A natural progression of this work would thus be to explore ways of including more detailed information by offering possibilities for interaction. For instance, details regarding the types of unit troops are composed of or about the particulars of a battle (e.g. types and number of units lost) could be displayed on demand with tooltips while information about the exact locations of kills and lines of fire could be displayed by allowing users to zoom into battle regions.

Apart from this, one of our next steps will also be to explore ways to reduce the visual complexity further. As our evaluation has shown, players had difficulties to correctly trace the movement of troops in case the arrows (partly) occluded each other. One possible solution could be to—instead of using individual arrows—merge arrows together as long as they follow the same route. For example, the two red movement arrows running along the eastern border of the map in Figure 6 (right) could be merged into a single arrow which splits into two distinct branches after the valley. This would reduce overlappings of arrows and perhaps also convey troop strengths more clearly.

In this article, we used data from World of Tanks to demonstrate our approach because (a) its theme and gameplay make it well suited for the technique presented here and (b) it is one of the few games which currently exposes all the necessary data. However, it should be emphasized that the algorithm is general enough to be applied to other games with similar gameplay mechanics or where more than two teams compete against each other as well—as long as the game provides time-stamped data on the trajectories of the units as well as about the shooting and target locations.

One drawback of the datasets we had available is the relatively small number of players on which they are based. However, most online multiplayer games similar to World of Tanks limit the number of concurrent players per battle to a few tens for performance or gameplay reasons. Battle maps for strategy games may be computationally more expensive to compute because such games may involve hundreds of units per player. However, given the computational complexity of the various steps, we expect the algorithm to also scale well to larger datasets. Extracting the battle regions with DBSCAN has an average runtime complexity of $O (n \log n)$ ⁴¹ where $n$ —in our case—is the number of shooting and target locations. Extracting the characteristic points and determining the centroids for territory tessellation are both linear with respect to the number of input points (see Andrienko and Andrienko²⁰) as is the derivation of the semantic trajectories. Finding the LCS of two semantic trajectories can be computed in time proportional to the product of their lengths using dynamic programming.⁴³ The complexity of determining the representative trajectory depends on if either the medoid or centroid is used. The cost of computing the medoid of a group of trajectories is quadratic with respect to the number of trajectories in the group whereas the method used for calculating the centroid runs in linear time.

With regard to the representative trajectory, we found that both the medoid- and centroid-based approaches produce visually similar results in case a high similarity threshold is used to group the trajectory sections and if the territory is finely tessellated. However, if the sections in a group become more dissimilar, the average central trajectory may deviate too much from the routes actually taken (due to averaging the locations) and may thus lead to false impressions. In such cases, we found the medoid to be more suitable because it corresponds to an actual route taken by a unit. However, this issue should be explored in more detail in the future.

Conclusion

In this article, we described an algorithm for generating battle maps based on in-game data. Several parameters can be adjusted to control the level-of-detail desired in the final map. As proof-of-concept we used the algorithm to produce battle maps based on replay data from World of Tanks. However, the algorithm is not restricted to this specific game but can be applied to other games as well, provided that the game records unit trajectories as well as shooting and target locations. Feedback was generally positive with players highlighting especially the good readability of the battle maps and the concise general overview they offer. However, future work may concentrate on finding ways to include more detailed information to further improve the utility of the approach. Moreover, while player feedback showed the appropriateness of the approach for retrospective analysis of battles, more detailed long-term studies will be required to better understand how effective the visualization is for skill-building, that is, does analyzing battle maps result in better in-game performance.

Footnotes

Acknowledgements

The author thanks all the participants who took part in the evaluation for their valuable contributions.

Funding

The author(s) received no financial support for the research, authorship, and/or publication of this article.

References

Wallner

Kriglstein

Visualization-based analysis of gameplay data: a review of literature. Entertain Comput 2013; 4(3): 143–155.

Medler

Player dossiers: analyzing gameplay data as a reward. Int J Comput Game Res 2011; 11, http://gamestudies.org/1101/articles/medler

Bungie Inc. Destiny API, https://www.bungie.net/platform/destiny/help/ (accessed January 2016).

Riot Games. Riot Games API, https://developer.riotgames.com/api-methods/(accessed January 2016).

Andras Belicza Scelight, https://sites.google.com/site/scelight/ (accessed January 2016).

Czyz

. vBAddict, http://www.vbaddict.net/replays (accessed January 2016).

Bowman

Elmqvist

Jankun-Kelly

. Toward visualization for games: theory, design space, and patterns. IEEE T Vis Comput Gr 2012; 18(11): 1956–1968.

Medler

Magerko

. Analytics of play: using information visualization and gameplay practices for visualizing video game data. Parsons J Inform Map 2011; 3: 1–12.

Zammitto

. Visualization techniques in video games. In: Proceedings of EVA, London, UK, 22–24 July 2008, pp. 267–276. BCS: The Chartered Institute for IT.

10.

Firaxis Games. Sid Meier’s Gettysburg (PC). Baltimore, MD: Firaxis Games, 1997.

11.

Fireglow Games. Sudden Strike II (PC). 2002 Bruchsal, Germany: Cdv Software Entertainment.

12.

Paradox Interactive. Hearts of Iron 3 (PC). Stockholm: Paradox Interactive, 2009.

13.

Paradox Interactive. Hearts of Iron 4 (PC). Stockholm: Paradox Interactive, 2016.

14.

Game-Labs. Ultimate General Gettysburg (PC). 2014. Game-Labs.

15.

Wargaming. World of Tanks (PC). Nicosia, Cyprus: Wargaming, 2010.

16.

Wallner

Kriglstein

Visualizations for retrospective analysis of battles in team-based combat games: a user study. In: Proceedings of the 2016 annual symposium on computer-human interaction in play, CHI PLAY ‘16, pp. 22–32. ACM.

17.

Library of Congress. Military battles and campaigns, http://www.loc.gov/collections/military-battles-and-campaigns/ (accessed January 2016).

18.

Davis

Perry

Kirkley

. The official military atlas of the civil war. New York: Barnes & Noble, 2003.

19.

Demsar

Buchin

Cagnacci

. Analysis and visualisation of movement: an interdisciplinary review. Mov Ecol 2015; 3(1): 1–24.

20.

Andrienko

. Spatial generalization and aggregation of massive movement data. IEEE T Vis Comput Gr 2011; 17(2): 205–219.

21.

Janetzko

Jäckle

Deussen

. Visual abstraction of complex motion patterns. In: Proceedings of SPIE, visualization and data analysis, San Francisco, CA, 2 February 2014, vol. 9017.

22.

Kisilevich

Mansmann

Nanni

. Spatio-temporal clustering. In: Maimon

Rokach

(eds) Data mining and knowledge discovery handbook. New York: Springer, 2010, pp. 855–874.

23.

Parent

Spaccapietra

Renso

. Semantic trajectories modeling and analysis. ACM Comput Surv 2013; 45(4): 42: 1–42.

24.

Ying

JJC

EHC

Lee

. Mining user similarity from semantic trajectories. In: Proceedings of the 2nd ACM SIGSPATIAL international workshop on location based social networks, San Jose, CA, 2 November 2010, pp. 19–26. New York: ACM.

25.

Liu

Schneider

. Similarity measurement of moving object trajectories. In: Proceedings of the third ACM SIGSPATIAL international workshop on GeoStreaming, Redondo Beach, CA, 6 November 2012, pp. 19–22. New York: ACM.

26.

Tufte

. The visual display of quantitative information. Cheshire, CT: Graphics Press, 2001.

27.

Phan

Xiao

Yeh

. Flow map layout. In: Proceedings of the IEEE symposium on information visualization, Minneapolis, MN, 23–25 October 2005. Washington, DC: IEEE Computer Society, pp. 219–224.

28.

Verbeek

Buchin

Speckmann

. Flow map layout via spiral trees. IEEE T Vis Comput Gr 2011; 17(12): 2536–2544.

29.

Börner

Penumarthy

. Social diffusion patterns in three-dimensional virtual worlds. Inform Visual 2003; 2: 182–198.

30.

Chittaro

Ranon

Ieronutti

. VU-Flow: a visualization tool for analyzing navigation in virtual environments. IEEE T Vis Comput Gr 2006; 12(6): 1475–1485.

31.

McLoughlin

Jones

Laramee

. Similarity measures for enhancing interactive streamline seeding. IEEE T Vis Comput Gr 2013; 19(8): 1342–1353.

32.

Hoobler

Humphreys

Agrawala

. Visualizing competitive behaviors in multi-user virtual environments. In: Proceedings of VIS, Austin, Texas, 10–15 October 2004, pp. 163–170. Washington, DC: IEEE Computer Society.

33.

Gagné

Seif El-Nasr

Shaw

. Analysis of telemetry data from a real-time strategy game: a case study. Comput Entertain 2012; 10(1): 2.1–2.25.

34.

Mitterhofer

Kruegel

Kirda

. Server-side bot detection in massively multiplayer online games. Secur Priv 2009; 7(3): 29–36.

35.

Miller

Crowcroft

. Group movement in World of Warcraft battlegrounds. Int J Adv Media Commun 2010; 4(4): 387–404.

36.

Thawonmas

Kurashige

Chen

. Detection of landmarks for clustering of online-game players. The Int J Virt Real 2007; 6: 11–16.

37.

Chen

Jiang

Zheng

. Trajectory simplification method for location-based social networking services. In: Proceedings of the international workshop on location based social networks, Seattle, WA, 4–6 November 2009, pp. 33–40. New York: ACM.

38.

Andrienko

Bak

. Visual analytics of movement. Berlin: Springer, 2013.

39.

Kalith, WOT Tactics, http://wottactic.com/ (accessed June 2017).

40.

StratSketch: Pyratron Studios. Stratsketch, https://www.pyratron.com/projects/stratsketch (accessed January 2016).

41.

Ester

Kriegel

Sander

. A density-based algorithm for discovering clusters in large spatial databases with noise. In: Simoudis

Han

Fayyad

(eds) 2nd international conference on knowledge discovery and data mining. Palo Alto, CA: AAAI Press, 1996, pp. 226–231.

42.

Birant

Kut

. ST-DBSCAN: an algorithm for clustering spatial-temporal data. Data Knowl Eng 2007; 60(1): 208–221.

43.

Wagner

Fischer

. The string-to-string correction problem. J ACM 1974; 21(1): 168–173.

44.

Andrienko

Barrett

. Space transformation for understanding group movement. IEEE T Vis Comput Gr 2013; 19(12): 2169–2178.

45.

Electronic Sports League. Wargaming.net league Europe bronze series, http://play.eslgaming.com/worldoftanks/europe/wot/open/bronze-series/ (accessed January 2016).

46.

Temmerman

. World of Tanks replay parser, https://github.com/evido/wotreplay-parser (accessed January 2016).

47.

Schreier

. Qualitative content analysis in practice. Thousand Oaks, CA: SAGE, 2012.

Automatic generation of battle maps from replay data

Abstract

Keywords

Introduction

Related work

Algorithm

Regions of Interest

Attacks

Trajectory processing

Territory tessellation

Semantic trajectories

Grouping of sections

Representative trajectory

Visualization

Parameters

Clustering ( MinPts , ϵ , ϵ t )

Characteristic points ( d min , d max , α min , Δ t min )

Territory tessellation ( r max )

Trajectory aggregation ( σ )

Use case: World of Tanks

Methodology

Results

Evaluation

Discussion

Conclusion

Footnotes

Acknowledgements

Funding

References

Clustering ( $MinPts$ , $ϵ$ , $ϵ_{t}$ )

Characteristic points ( $d_{\min}$ , $d_{\max}$ , $α_{\min}$ , $Δ t_{\min}$ )

Territory tessellation ( $r_{\max}$ )

Trajectory aggregation ( $σ$ )