Six Degrees of Dota 2

You may have heard of the Bacon number before, a measure of the number of steps from any two actors or actresses who’ve been in a movie together until you reach Kevin Bacon. It comes from a larger idea that suggests everyone on this planet is six or fewer ‘friend of a friend’ connections to each other. I wanted to take this idea into the realm of Dota 2, to see how many steps it would take you to get from any one professional player to the next.

The premise is this; imagine I draw a circle for every professional player, then I draw a line between them if they have played or coached on the same team together. That’s exactly what the Six Degrees of Dota 2 graph is.

Diving into the data

Basic Graph

The graph was aligned using the Fruchterman-Reingold Algorithm, which produces a nice circular pattern and allows us to see how some players group together.

For instance, it’s interesting to look at how the nationalities of players impacts the layout. Players from the same or close countries cluster together, from the giant blob of China at the bottom to CIS players on the east side. It would appear that player’s who speak English as their primary or secondary language tend towards the centre more, which would make sense as common communication is vital in succeeding on a Dota team.

Black^ hole at the centre

Black^ Sitting in the middle of the graph is longtime player Black^. If you had to guess which player would be the most centralised in the network he would be a lot of people’s first choice, but I was still impressed that the graph picked this up.

According to my data, Black^ has been a part of 18 teams under 16 different team names. He has played alongside 34 other players in North America, Europe, China and Southeast Asia in a Dota career spanning 7 years. This makes him the 4th most connected player.

Six degrees of Arteezy

While Black^ might be the Kevin Bacon of Dota, it’s interesting to see how other famous players shape up in the who-knows-who world. Arteezy Number Plot Consider now the Arteezy number, or how many steps of teammates do you need to go through to reach this famous player. Anybody who has played alongside him before, for instance Fear, would have an Arteezy number of 1. Merlin “Luft” Seibel of team Valkyrie eSports is one of a only a few players to have an Arteezy number of 6. It does seem to hold for this dataset that you really can find a path from any player to Arteezy in under six degrees.

Arteezy Of the 592 players on the graph, only 6 had no path to Arteezy. 224 players had the most frequent Arteezy number of 3, and the entire population had an average Arteezy number of 3.22 (you can’t make this stuff up!).

The travellers

Most Connected Some players really get around, and unsurprisingly they tend to be the ones who’ve been around the longest. The table below shows the number of teammates the top travellers have had. Every one of the top connected players has battled alongside at least two other people on that list, with the exception of Hao and hFn, who are both isolated from the rest of the group.

Player Number of Teammates
SexyBamboe 38
SingSing 37
BuLba 35
Black^ 34
DeMoN 33
7ckngMad 33
ComeWithMe 30
VANSKOR 29
Hao 28
ArtStyle 28
G 28
hFn 28

The loners

Some players have very few connections, perhaps just one line connecting them to the rest of the graph. Teams should have five players, so this isn’t technically possible. Looking further into it, this is due to either their teammates not having wiki pages, or crawling errors (for instance the team Newbee Young is sometimes denoted as Newbee Y., which causes issues when looking for all their players). It’s a shame I couldn’t capture everybody in the data, at some point I’ll have to go back and try and make some improvements to my process.

Truly global scale

Most Connected It’s crazy to me just how international a game Dota is. Tournaments are constantly categorised into regions, and we tend to think of games based on which servers we play on, or by encompassing descriptors of our teammates such as Russian, American, Chinese, etc. It’s so easy to forget just how much diversity there is amongst the millions of regular players, let alone the professional scene.

I recorded 53 different countries that spawned a pro player, ranging from Switzerland to Serbia to Albania to New Zealand, it seems as if every corner of the map has some representation (OK not quite, but it’s still impressive!). It certainly made it hard to colour code the graph with such a variety of nationalities, and with a fairly even distribution across each nationality at that (with the exception of China, who lay claim to almost 200 players).

A team for every occasion

Most Connected The Liquipedia page on notable teams, both active and disbanded, lists 273 organisations. I used those team pages to get my list of Dota players, then looked at the individual player’s pages to get a complete list of their playing history. This yielded a far larger number of teams, 721 to be exact. There are probably a few duplicates and some teams that don’t really qualify in the larger number, but it’s safe to say the real value is somewhere in that range.

The ability for anybody to set up a team and play, or rename your team at any time, has obviously directly contributed to a much higher number of teams than what you might find in conventional sports. However, some organisations have stood the test of time and have consistently put forward squads year after year, of which Evil Geniuses leads the charge for most players, and is the only US team in the top ten.

Final thoughts

It’s pretty fun to dive in and see just how intertwined the professional Dota scene is, and that the six degrees of separation rule I mentioned at the start does seem to hold (in fact I’m sure for some players there are even shorter paths than the ones I calculated). It’s unfortunate that the quality of the data available means some links and stats are missed out. If there is a better resource I could use other than the wiki I’d love to know about it. Regardless, as a general insight into the shape of the professional scene, this project was a lot of fun to do.

Boats, Boxes and HTML5

Left/Right arrows move boat.
Spacebar 'jumps' the boat.
R key refills the boat with boxes/rocks.

In the 14 months since I last posted here Flash has recessed evermore into the ground. It's been a long time since I used Haxe, and given its capacity to compile to seemingly every language, there seemed little point reverting to OpenFL, the Flash API in Haxe framework. I decided to try out Flambe, another high level 2D game engine for Haxe with a focus on simplicity that compiles to HTML5, Android + iOS (with Adobe AIR), and the ever hard to get rid of Flash. Of course the biggest selling point is that it is not based off of the the Flash API, and coupled with a well designed entity-component system it is probably the easiest to learn games framework I've used, certainly the least tedious.

Flambe works easily with Nape, a Haxe physics engine that's a thousand times nicer to use than Box2D, if less powerful, and so a few hours into learning the demo above was born. Fast WebGL rendering, great asset management, speedy compile times; Flambe really is a step up from my experience with OpenFL. I'm looking forward to playing about with it more, it really is an impressive engine.

Flocking Simulation

Spacebar toggles flocking on/off.
R resets the demo.
D toggled the debug lines.

This a simulation of flocking behaviour based on the Boids simulation created by Craig Reynolds. Flocking adheres to three simple rules:

  • Separation: avoid close neighbours
  • Cohesion: steer towards average position of neighbours
  • Alignment: steer towards average heading of neighbours.

The pink lines connecting the birds (or 'boids') in the demo represent neighbour association, i.e. being within a certain radius of each other, and therefore 'flocking'.
The applications of flocking behaviour range from the obvious use of simulating animals, to data visualisation, to homing missiles!

Maze Generation Using Randomized Kruskal's Algorithm

I previously posted a maze generator using depth-first search and backtracking. This implementation however uses a randomized version of Kruskal's Algorithm (Minimum Spanning Tree Algorithm). The Wikipedia description of the algorithm does a far better job summarising it than I ever could:

  1. Create a list of all walls, and create a set for each cell, each containing just that one cell.
  2. For each wall, in some random order:
    1. If the cells divided by this wall belong to distinct sets:
      1. Remove the current wall.
      2. Join the sets of the formerly divided cells.

For my implementation I stored a list of the edges (walls) between each cell and DisjointSets data structure to keep track of which cells are traversable. Simply, DisjointSets keeps track of a fixed number of disjoint sets (sets that do not overlap). Here initially each cell is a disjoint set. The sets can be unioned together as they need to be merged, i.e when a wall is destroyed between two sets of cells. As described above, I select random edges from my list to remove provided removing that edge will join two disjoint parts of the maze together until my DisjointSets contains a single set containing every cell. I assume the start and end points to be in the top-left and bottom-right positions of the maze respectively, but this is arbitrary as any cell can be reached from any other cell via some route. Below is the source code for my algorithm and DisjointSets data structure. Either generate() or animate() can be called depending on whether you want the drawing delay as the algorithm runs.

Fisher-Yates Shuffle

Fisher-Yates Shuffle is a simple algorithm for shuffling a finite set. The above demo shows the algorithm in action, exchanging the position of the last and a random element from a subset that decrements in size by one until the set is empty.

The source code for the demo above is a bit lengthy as it involves some visual aids and tweening, so below is a simplified version of the algorithm for shuffling a set of integers: