Hashsets to Bitsets— optimizing hexagonal coordinate retrieval

TL;DR:

• Any HashSet where you can find a 1:1 function from possible inputs to numbers 0..n, can be converted to a BitSet, which is ~10x faster
• Likewise, any HashMap with such a function on the keys, can be converted to array access, with similar results
• We provide an example of such a function for hexagonal tile positions, which is 5x faster than the common implementation

In Unciv, a huge part of AI ‘next turn’ calculations is unit movement. ~25% of total “next turn” latency is a single function — getMovementToTilesAtPosition.

Of that, profiling shows the expensive parts are HashSet/HashMap accesses. As we know and love(?), hashmap access is an expensive action — it’s only inexpensive compared to other, much worse things.

So, the Big Idea is: since that entire function is surrounding a focal point — the position of the unit, instead of a generic hashmap/hashset, we can use relative distances to derive positions (0..n) and turn them into array/enumset-like accesses.

The coordinate system

In our coordinate system, X and Y correspond to the 10 o’clock and 2 o’clock directions, respectively:

All maps are centered on 0,0. What we need, therefore, is a function where the center tile maps to 0, places 1–6 are the 6 neighbors, 7–18 are ring 2, etc — that way, the max index of a map is roughly equal to the number of tiles in the map, similar to this spiral from RebBlobGames:

Kudos Amit Patel for all his fantastic work on hexagonal coordinates!

Determining which ring we’re in is simple — if both X and Y are the same sign, it’s max(abs(x),abs(y)), and if not, it’s abs(x-y).

What remains, therefore, is: given a hex position in ring X, how do we determine 1:1 its position within the ring?

In-ring index of a tile

A simple way, and the way suggested by redblobgames, is to simply iterate over all the tiles in a ring until we find our tile — so the in-ring index is dependent on our iteration cycle. This is also hex-spiral.

However, given what we know about the structure of the coordinates, we can make a function ~5x faster.

There are only 6 edges to a ring. If we mark the nth ring as ring, then

• Top right edge is y=ring,
• Top left edge is x=ring,
• Bottom right edge is x=-ring,
• Bottom left edge is y=-ring,
• Left edge is (x-y)=ring,
• Right edge is (y-x)=ring.

Therefore we can check which edge a tile is in, and for each such edge — we know how many tiles are in it, and we can check it by either x or y!

Since we know how many are in each edge, we also know the start index of this edge, compared to the start of the ring.

In code:

val positionInRing = when (ring) {
    y -> 0 /* start index*/ + x /*variable*/    // contains `ring+1` elements
    x -> ring + 1 /* start index */ + y /*variable*/ // contains `ring` elements - 1 already taken by x=y=ring above
    -x -> 2 * ring + 1 /* start index */ -y /*variable*/ // contains `ring+1` elements
    -y -> 3 * ring + 2 /*start index*/ -x /*variable*/ // contains `ring` elements - 1 already taken by -x=-y=ring above
    x-y -> 4 * ring + 2 /* start index */ +x-1 /*variable*/ // contains `ring-1` elements. -1 because x=0 is already taken by ring=-y above
    y-x -> 5 * ring + 1 /* start index */ +y-1 /*variable*/ // contains `ring-1` elements. -1 because y=0 is already taken by ring=-x above
    else -> throw Exception("How???")
}

So the entire function is:

fun getZeroBasedIndex(x: Int, y: Int): Int {
    if (x == 0 && y == 0) return 0
    val ring = getDistance(0, 0, x, y)
    val ringStart = 1 + 6 * ring * (ring - 1) / 2 // 1 for the center tile, then 6 for each ring

    // total number of elements in the ring is 6 * ring

    // We divide the ring into its 6 edges, each of which can be determined by an equality comparison
    // Each edge has a start index, a variable from 0 to the number of elements in that edge
    val positionInRing = when (ring) {
        y -> 0 /* start index*/ + x /*variable*/    // contains `ring+1` elements
        x -> ring + 1 /* start index */ + y /*variable*/ // contains `ring` elements - 1 already taken by x=y=ring above
        -x -> 2 * ring + 1 /* start index */ -y /*variable*/ // contains `ring+1` elements
        -y -> 3 * ring + 2 /*start index*/ -x /*variable*/ // contains `ring` elements - 1 already taken by -x=-y=ring above
        x-y -> 4 * ring + 2 /* start index */ +x-1 /*variable*/ // contains `ring-1` elements. -1 because x=0 is already taken by ring=-y above
        y-x -> 5 * ring + 1 /* start index */ +y-1 /*variable*/ // contains `ring-1` elements. -1 because y=0 is already taken by ring=-x above
        else -> throw Exception("How???")
    }
    return ringStart + positionInRing
}

We can test this by iterating over all tiles in a distance, and ensuring they A. fit within the index space we expect, and B. do not overlap:

@Test
fun testZeroBasedIndex(){
    val seenCoordsMapping = hashSetOf<Int>()
    for (ring in 1..100) {
        val coords = HexMath.getVectorsAtDistance(Vector2.Zero, ring, 100, false)
        val ringStartCoordinate = 1 + 6 * ring * (ring - 1) / 2
        for (coord in coords) {
            val mapping = HexMath.getZeroBasedIndex(coord.x.toInt(), coord.y.toInt())
            Assert.assertFalse("Duplicate coords found: $coord", seenCoordsMapping.contains(mapping))
            Assert.assertTrue("Coords $coord should be in ring $ring, actual mapping $mapping", mapping in ringStartCoordinate .. (ringStartCoordinate + 6 * ring - 1))

            seenCoordsMapping.add(mapping)
        }
    }
}

Testing this against the naive iteration implementation (included for completeness), for n=0 to 100, we found our function roughly 5x faster — since it requires no in-edge iteration, this is more pronounced on further rings.

Putting it to use

With our new function in hand, we can convert the Hashset to a Bitset! In order to properly test the performance difference, I had them live side-by-side in the code so profiling would catch them both.

Initially, I ran getZeroBasedIndex every time I would have used HashSet.get and HashSet.set — but since the tiles have consistent positions, we can instead precalculate these values for a minor cost and reuse them throughout!

The results were a 10x speedup in hash access, leading to a total gain of 7.4% in ‘next turn’ latency — and for a game that’s as hyper-optimized as this, that’s a lot!

The Tradeoff

Nothing is without cost. In this case, each tile had to include an extra Int field for the precalculated zero-index; In-memory, we store an extra N bits, where N is roughly the number of tiles. But these costs are entirely worth the gain.