Hearthstone Battlegrounds is a great game and I highly recommend you try it.

Whenever I use software, I get a feel for which buttons make network calls, which ones are expensive, and how the app is designed to hide the latency of the expensive calls.

When I play Battlgrounds, I am just in awe at how seamless the experience is.

In this blog post, I’m going to give a brief overview of how Battlegrounds works, outline how I think the blizzard infrastructure is set up behind the scenes, and then I’ll implement the minion pool logic in python.

You can find the source code shown in this blog post here.

Overview of Battlegrounds

A game of Battlegrounds starts with 8 players. Each player alternates between a Recruit Phase, where they buy minions from a shared minion pool to build an army, and a Combat Phase, where each player is paired against another and their minions battle. Minions and Players have a Tavern Tier Level, players are only offered minions to buy that are at or below their tavern tier.

The minion pool is initialized with a fixed number of each minions of each tier.

In the Recruit Phase players:

• Buy minions from Bob’s shop
• Sell minions back to Bob
• Refresh the shop, send back the minions currently in the shop for new ones
• Upgrade their Tavern Tier to be able to buy more powerful minions

The Recruit Phase is crazy, all 8 players are getting minions from Bob’s shop, throwing their minions back at bob, getting new ones.

I was really fascinated at how the Recruit Phase felt so seamless, despite there being 7 other players making similar actions against the shared pool of minions.

Request Flow

This is a brief sketch of what I expect Blizzard’s game infrastructure to roughly look like.

Given the performance of the game, I expect:

• TCP connections to be reused as much as possible.
• All 8 players to be routed to the same game servers
• Some kind of high availability to account for failures within a data center
• A shared data layer, like redis, to persist the game state

Python Implementations

Next I set out to implement the minion pool logic in Python.

Minion Pool – Array

My first implementation of a Minion Pool was a tiered list approach.

[
	[ All the Tier 1 Minions ],
	[ All the Tier 2 Minions ],
	[ All the Tier 3 Minions ],
	[ All the Tier 4 Minions ],
	[ All the Tier 5 Minions ],
	[ All the Tier 6 Minions ]
]

Returning minions to the pool here is easy.

def put_minion_back_in_pool(self,minion):
    tier = int(minion[0])
    if tier > 6 or tier < 1:
        raise Exception("Invalid Tier")

    self.pool[tier-1].append(minion)

I encoded the tier of a minion in the first byte of each minion’s data. So to put a minion back into the pool, I just append it to the end of the list that stores minions of that tier. There is no need to shuffle the minions after inserting.

Fetching minions is a little bit more involved:

def get_batch_of_minions(self,tavern_tier,batch_size):
    number_of_valid_minions = 0
    for i in range(tavern_tier-1):
        number_of_valid_minions+= len(self.pool[i])

I start by counting the number of minions at or below the tavern tier I’m selecting for.

    random_ints = [randint(0,number_of_valid_minions) for i in range(batch_size)]

    minions_to_return = []

Next, I generate a random int for each minion I need to return

    for rand_int in random_ints:
        current_tier = 0
        while rand_int > len(self.pool[current_tier]) - 1:
            rand_int = rand_int - len(self.pool[current_tier])
            current_tier = current_tier + 1

        selected_minion = self.pool[current_tier][rand_int]

        minions_to_return.append(selected_minion)

        self.pool[current_tier].remove(selected_minion)

    return minions_to_return

Then I index into the nested arrays, remove the selected minions, and return them.

Minion Pool – Set

I was very pleased with the results of the Array implementation. But I saw some potential issues with it:

• The complex data type might not mesh well with the data layer
• 😅 But honestly, I just wanted to do another implementation with another data structure

So I decided to implement the minion pool using a set. I didn’t expect this to be faster than the array, but I do know that redis has a native set implementation, so it might be a better fit there.

To initialize my set, I added minions one by one and appended a UUID to them.

set(
	minion_name+UUID,
	minion_name+UUID,
	minion_name+UUID,
	minion_name+UUID,
	...
)

Once again, adding a minion back is simple:

def put_minion_back_in_pool(self,minion):
    self.pool.add(minion)

Grabbing minions from the pool is also a simple implementation, I grab a minion, see if it is of the appropriate tavern tier, if it isn’t, I throw it back and try again.

def get_batch_of_minions(self,tavern_tier,batch_size):
    minions_to_return = []

    while len(minions_to_return) != batch_size:
        element = self.pool.pop()
        if int(element[0]) <= tavern_tier:
            minions_to_return.append(element)
        else:
            self.pool.add(element)

    return minions_to_return

Benchmark

For each implementation, I wrote 3 benchmarks:

• Buy a single batch of minions, then immediately sell them back
• Buy minions at each tier, then sell them back
• A full game test, where I simulate the buy/sell actions a player would make in a real game

Benchmark Tests – Minion Array

Benchmark Tests – Minion Set

Benchmark Summary

The Minion Array beat out the Minion Set by a wide margin in each category.

These results intuitively make a lot of sense.

The Minion Set implementation has a lot of inefficiencies in the getbatchofminions_ method. The set data sturcture isn’t really a natural fit for this problem, in fact it hurts us a lot, since everytime we insert a new item it has to verify that that item is unique, this work is all overhead.

The Minion Array on the other hand benefits from having constant time random access and append.

Other Factors

While I do think Blizzard did a great job making Battlegrounds very performant, I want to point out some factors that make my experience extra snappy.

• I have a pretty fast computer and internet connection, 570 Up / 455 Down.
• I live in Reston, VA, which is close to lots of major data centres. It is very likely that there is a blizzard data center or backbone entry point within 5 miles of my apartment.