How do I represent a hextile/hex grid in memory?

Representing a Hextile/Hex Grid in Memory

Explore various data structures and algorithms for efficiently storing and manipulating hexagonal grids in computer memory, crucial for game development and simulations.

Hexagonal grids, or hex grids, are a popular choice in strategy games, simulations, and geographic information systems due to their unique properties, such as equidistant neighbors. Unlike square grids, working with hex grids can be less intuitive because of their non-orthogonal coordinate systems. This article delves into the fundamental ways to represent a hex grid in memory, covering coordinate systems, storage methods, and common operations.

Hexagonal Coordinate Systems

Before discussing memory representation, it's essential to understand the different coordinate systems used for hex grids. The most common systems are Axial, Cube, and Offset coordinates. Each offers unique advantages for specific operations.

Comparison of Hexagonal Coordinate Systems

Memory Storage Strategies

The choice of memory storage depends heavily on the grid's characteristics: whether it's regular or irregular, sparse or dense, and static or dynamic. Common strategies include 2D arrays (for offset coordinates), hash maps, and custom graph structures.

2D Array Representation (Offset Coordinates)

For regular, dense hex grids, a 2D array can be used by mapping offset coordinates directly. This is straightforward but requires careful handling of the 'jagged' or 'staggered' nature of hex rows/columns.

class HexGrid:
    def __init__(self, width, height):
        self.grid = [[None for _ in range(width)] for _ in range(height)]

    def get_hex(self, col, row):
        if 0 <= col < len(self.grid[0]) and 0 <= row < len(self.grid):
            return self.grid[row][col]
        return None

    def set_hex(self, col, row, value):
        if 0 <= col < len(self.grid[0]) and 0 <= row < len(self.grid):
            self.grid[row][col] = value

# Example usage:
grid = HexGrid(10, 10)
grid.set_hex(5, 3, 'Forest')
print(grid.get_hex(5, 3))

Basic 2D array representation for an offset hex grid.

Hash Map Representation (Axial/Cube Coordinates)

For sparse or irregular hex grids, where many cells might be empty or the grid boundary is non-rectangular, a hash map (or dictionary) is often more efficient. The hex coordinates (e.g., axial (q, r) or cube (x, y, z)) serve as keys.

class Hex:
    def __init__(self, q, r, data=None):
        self.q = q
        self.r = r
        self.data = data

    def __hash__(self):
        return hash((self.q, self.r))

    def __eq__(self, other):
        return isinstance(other, Hex) and self.q == other.q and self.r == other.r

class HexGridMap:
    def __init__(self):
        self.cells = {}

    def add_hex(self, hex_obj):
        self.cells[(hex_obj.q, hex_obj.r)] = hex_obj

    def get_hex(self, q, r):
        return self.cells.get((q, r))

# Example usage:
grid_map = HexGridMap()
grid_map.add_hex(Hex(0, 0, 'Start'))
grid_map.add_hex(Hex(1, -1, 'Mountain'))
print(grid_map.get_hex(0, 0).data)

Using a dictionary (hash map) to store hexes by their axial coordinates.

Neighbor Finding and Conversions

A crucial aspect of hex grid manipulation is finding neighboring cells and converting between coordinate systems. These operations are fundamental for pathfinding, area-of-effect calculations, and rendering.

Neighbor Finding (Cube Coordinates)

Finding neighbors is particularly elegant with Cube coordinates. Each of the six neighbors can be found by adding a specific 'direction vector' to the current cell's coordinates.

const CUBE_DIRECTIONS = [
    { x: 1, y: -1, z: 0 }, { x: 1, y: 0, z: -1 }, { x: 0, y: 1, z: -1 },
    { x: -1, y: 1, z: 0 }, { x: -1, y: 0, z: 1 }, { x: 0, y: -1, z: 1 }
];

function getCubeNeighbor(hex, directionIndex) {
    const dir = CUBE_DIRECTIONS[directionIndex];
    return { x: hex.x + dir.x, y: hex.y + dir.y, z: hex.z + dir.z };
}

// Example: get a neighbor of hex {x:0, y:0, z:0}
// console.log(getCubeNeighbor({x:0, y:0, z:0}, 0)); // {x:1, y:-1, z:0}

Function to get a neighbor using cube coordinates.

Axial to Offset Conversion

Converting between coordinate systems is often necessary, especially when using a 2D array for storage (offset) but performing calculations with axial or cube coordinates.

Tab 1

{ "language": "python", "title": "Python (Even-Q Offset)", "content": "def axial_to_offset_even_q(q, r): col = q row = r + (q + (q & 1)) // 2 return col, row" }

Tab 2

{ "language": "javascript", "title": "JavaScript (Even-Q Offset)", "content": "function axialToOffsetEvenQ(q, r) { const col = q; const row = r + (q + (q & 1)) / 2; return { col, row }; }" }