Data structure for Settlers of Catan map?

A simple structure to store an hexagonal grid when you care only about hexagons, is a matrix, with an hexagon at (x,y) being a neighbor of hexagons at (x, y±1), (x±1,y), and (x±1,y+1) for even xs or (x±1,y-1) for odd xs. We can evolve this idea to allow fast lookup of edges and vertices.

You add two other matrices to this: one for edges, and another for vertices.

You consider an hexagon at (x,y) delimited by the vertices at positions (x,2y), (x,2y+1), (x,2y+2), (x+1,2y), (x+1,2y+1), and (x+1,2y+2), for even xs. For odd xs, add 1 to the y coordinate. The edges surrounding it are those at (2x,2y), (2x,2y+1), (2x+1, 2y), (2x+1,2y+2), (2x+2,2y), and (2x+2,2y+1), with an additional adjustment to y by adding one if x is odd.

This gives you constant time random access to edges and vertices given an hexagon (and you can work out the coordinate transformations to do the reverse lookup as well).

With some more simple formulas you can lookup edges from vertices, hexes from vertices, and other lookups you may need to play the game.

This way you can represent the board with nothing but arrays and do lookups with simple math to transform between "hexagon coordinates", "edge coordinates", and "vertex coordinates".

Because the board will not fit a (rectangular) matrix perfectly, you will need to fill a couple of cells with some "empty" or "invalid" value, to represent the couple of borderline cells that have mismatch the hexagonal shape of the board.

Asymptotically, this method uses memory linear on the number of hexes, and gives constant time for any lookup.

Here's some example C# code:

class Board
{
    public readonly Hex[,] Hexes = new Hex[10,10];
    public readonly Edge[,] Edges = new Edge[22,22];
    public readonly Vertex[,] Vertices = new Vertex[22,22];

    public Board()
    {
        for(int i = 0; i < 10; i++)
        for(int j = 0; j < 10; j++)
            Hexes[i,j] = new Hex { X = i, Y = j };
        for(int i = 0; i < 22; i++)
        for(int j = 0; j < 22; j++)
        {
            Edges[i,j] = new Edge { X = i, Y = j };
            Vertices[i,j] = new Vertex { X = i, Y = j };
        }
    }

    public IEnumerable<Hex> GetNeighbors(Hex hex)
    {
        var x = hex.X; var y = hex.Y;
        var offset = x % 2 == 0? +1 : -1;
        return new []
        {
            Hexes[x,y+1],
            Hexes[x,y-1],
            Hexes[x+1,y],
            Hexes[x-1,y],
            Hexes[x+1,y+offset],
            Hexes[x-1,y+offset],
        };
    }
    public IEnumerable<Vertex> GetVertices(Hex hex)
    {
        var x = hex.X; var y = hex.Y;
        var offset = x % 2;
        return new[]
        {
            Vertices[x,2*y+offset],
            Vertices[x,2*y+1+offset],
            Vertices[x,2*y+2+offset],
            Vertices[x+1,2*y+offset],
            Vertices[x+1,2*y+1+offset],
            Vertices[x+1,2*y+2+offset],
        };
    }
    public IEnumerable<Edge> GetEdges(Hex hex)
    {
        var x = hex.X; var y = hex.Y;
        var offset = x % 2;
        return new[]
        {
            Edges[2*x,2*y+offset],
            Edges[2*x,2*y+1+offset],
            Edges[2*x+1,2*y+offset],
            Edges[2*x+1,2*y+2+offset],
            Edges[2*x+2,2*y+offset],
            Edges[2*x+2,2*y+1+offset],
        };
    }
    public IEnumerable<Vertex> GetEnds(Edge edge)
    {
        var x = edge.X; var y = edge.Y;
        if(x % 2 == 0)
            return new[]
            {
                Vertices[x/2,y],
                Vertices[x/2,y+1],
            };
        else
            return new[]
            {
                Vertices[(x-1)/2,y],
                Vertices[(x+1)/2,y],
            };
    }
    public IEnumerable<Edge> GetEdges(Vertex vertex)
    {
        var x = vertex.X; var y = vertex.Y;
        return new []
        {
            Edges[x*2,y],
            Edges[x*2+1,y],
            Edges[x*2-1,y],
        };
    }
    public IEnumerable<Hex> GetHexes(Vertex vertex)
    {
        var x = vertex.X; var y = vertex.Y;
        var xoffset = x % 2;
        var yoffset = y % 2;
        return new[]
        {
            Hexes[x-1,(y+xoffset)/2-1],
            Hexes[x-(1-yoffset)*xoffset,(y-1)/2],
            Hexes[x,(y-xoffset)/2],
        };
    }
}

There is some memory inefficiency because a few cells are never used, but that shouldn't be a problem. The memory consumption remains under the same asymptotic bound.

One possibility is the "brick wall" technique, which uses a square grid with each row offset by half a square from the upper and lower rows. It's topologically the same as a hex grid, but easier to use in some ways.

You can always have hexagon and vertex data items, connected with pointers or references, but that might not meet your scaling requirements, and it's going to be harder to put them on a screen.

If I remember the rules correctly, it's very important to know which hexagons a vertex is on, and very important to know which vertices are adjacent to which, and most of the other relations are unimportant (aside from the hex sides that have ports or whatever you call those exchange things).