Data structure for Settlers of Catan map? [duplicate]

Question

A while back someone asked me if I knew of a nice way to encode the information for the game Settlers of Catan. This would require storing a hexagonal grid in a way where each hex can have data associated with it. More importantly, though, I would need some way of efficiently looking up vertices and edges on the sides of these hexagons, since that's where all the action is.

My question is this: is there a good, simple data structure for storing a hexagonal grid while allowing for fast lookup of hexagons, edges between hexagons, and vertices at the intersections of hexagons? I know that general structures like a winged-edge or quad-edge could do this, but that seems like massive overkill.

Answer 1

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.

Answer 2

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).

Answer 3

If you look at a cube from a 45 degree angle (with a corner facing you), you'll see that its silhouette is a hexagon. We can get a lot of mileage by treating hexagons as two-dimensional projections of cubes for algorithmic purposes.

For more information on the hexagon-as-cube approach, check out Amit's post. It is the definitive answer on implementing hexagonal grids in games.

Answer 4

Since it's a two-dimensional structure, we can always do with just two dimensions, which in this case are not at 90° but 60° to each other. However, distance calculations (in terms of hexes traversed) are a bit more tricky in that setting.

Another idea would be to store positions as triplets (x,y,z) along the three axes a hexagon naturally has, and where needed normalize one of the coordinates to 0.

Lots of wargames use hexagonal structures, but trying to look at the implementation of something like Vassal and VASL for ideas might be a bit of overkill.

Answer 5

Here's an alternative to the top voted answer because we found a lot of bugs in that implementation while implementing our own AI for Settlers of Catan. By the way, a lot of resources can be found on the hexagonal grid structure here: http://www.redblobgames.com/grids/hexagons/

Code in Python:

    class Board:
      # Layout is just a double list of Tiles, some will be None
      def __init__(self, layout=None):
        self.numRows = len(layout)
        self.numCols = len(layout[0])
        self.hexagons = [[None for x in xrange(self.numCols)] for x in xrange(self.numRows)] 
        self.edges = [[None for x in xrange(self.numCols*2+2)] for x in xrange(self.numRows*2+2)] 
        self.vertices = [[None for x in xrange(self.numCols*2+2)] for x in xrange(self.numRows*2+2)] 
        for row in self.hexagons:
          for hexagon in row:
            if hexagon == None: continue
            edgeLocations = self.getEdgeLocations(hexagon)
            vertexLocations = self.getVertexLocations(hexagon)
            for xLoc,yLoc in edgeLocations:
              if self.edges[xLoc][yLoc] == None:
                self.edges[xLoc][yLoc] = Edge(xLoc,yLoc)
            for xLoc,yLoc in vertexLocations:
              if self.vertices[xLoc][yLoc] == None:
                self.vertices[xLoc][yLoc] = Vertex(xLoc,yLoc)

      def getNeighborHexes(self, hex):
        neighbors = []
        x = hex.X
        y = hex.Y
        offset = 1
        if x % 2 != 0:
          offset = -1

        if (y+1) < len(self.hexagons[x]):
          hexOne = self.hexagons[x][y+1]
          if hexOne != None: neighbors.append(hexOne)
        if y > 0:
          hexTwo = self.hexagons[x][y-1]
          if hexTwo != None: neighbors.append(hexTwo)
        if (x+1) < len(self.hexagons):
          hexThree = self.hexagons[x+1][y]
          if hexThree != None: neighbors.append(hexThree)
        if x > 0:
          hexFour = self.hexagons[x-1][y]
          if hexFour != None: neighbors.append(hexFour)
        if (y+offset) >= 0 and (y+offset) < len(self.hexagons[x]):
          if (x+1) < len(self.hexagons):
            hexFive = self.hexagons[x+1][y+offset]
            if hexFive != None: neighbors.append(hexFive)
          if x > 0:
            hexSix = self.hexagons[x-1][y+offset]
            if hexSix != None: neighbors.append(hexSix)
        return neighbors

      def getNeighborVertices(self, vertex):
        neighbors = []
        x = vertex.X
        y = vertex.Y
        offset = -1
        if x % 2 == y % 2: offset = 1
        # Logic from thinking that this is saying getEdgesOfVertex
        # and then for each edge getVertexEnds, taking out the three that are ==vertex
        if (y+1) < len(self.vertices[0]):
          vertexOne = self.vertices[x][y+1]
          if vertexOne != None: neighbors.append(vertexOne)
        if y > 0:
          vertexTwo = self.vertices[x][y-1]
          if vertexTwo != None: neighbors.append(vertexTwo)
        if (x+offset) >= 0 and (x+offset) < len(self.vertices):
          vertexThree = self.vertices[x+offset][y]
          if vertexThree != None: neighbors.append(vertexThree)
        return neighbors

      # used to initially create vertices
      def getVertexLocations(self, hex):
        vertexLocations = []
        x = hex.X
        y = hex.Y
        offset = x % 2
        offset = 0-offset
        vertexLocations.append((x, 2*y+offset))
        vertexLocations.append((x, 2*y+1+offset))
        vertexLocations.append((x, 2*y+2+offset))
        vertexLocations.append((x+1, 2*y+offset))
        vertexLocations.append((x+1, 2*y+1+offset))
        vertexLocations.append((x+1, 2*y+2+offset))
        return vertexLocations

      # used to initially create edges
      def getEdgeLocations(self, hex):
        edgeLocations = []
        x = hex.X
        y = hex.Y
        offset = x % 2
        offset = 0-offset
        edgeLocations.append((2*x,2*y+offset))
        edgeLocations.append((2*x,2*y+1+offset))
        edgeLocations.append((2*x+1,2*y+offset))
        edgeLocations.append((2*x+1,2*y+2+offset))
        edgeLocations.append((2*x+2,2*y+offset))
        edgeLocations.append((2*x+2,2*y+1+offset))
        return edgeLocations

      def getVertices(self, hex):
        hexVertices = []
        x = hex.X
        y = hex.Y
        offset = x % 2
        offset = 0-offset
        hexVertices.append(self.vertices[x][2*y+offset]) # top vertex
        hexVertices.append(self.vertices[x][2*y+1+offset]) # left top vertex
        hexVertices.append(self.vertices[x][2*y+2+offset]) # left bottom vertex
        hexVertices.append(self.vertices[x+1][2*y+offset]) # right top vertex
        hexVertices.append(self.vertices[x+1][2*y+1+offset]) # right bottom vertex
        hexVertices.append(self.vertices[x+1][2*y+2+offset]) # bottom vertex
        return hexVertices

      def getEdges(self, hex):
        hexEdges = []
        x = hex.X
        y = hex.Y
        offset = x % 2
        offset = 0-offset
        hexEdges.append(self.edges[2*x][2*y+offset])
        hexEdges.append(self.edges[2*x][2*y+1+offset])
        hexEdges.append(self.edges[2*x+1][2*y+offset])
        hexEdges.append(self.edges[2*x+1][2*y+2+offset])
        hexEdges.append(self.edges[2*x+2][2*y+offset])
        hexEdges.append(self.edges[2*x+2][2*y+1+offset])
        return hexEdges

      # returns (start, end) tuple
      def getVertexEnds(self, edge):
        x = edge.X
        y = edge.Y
        vertexOne = self.vertices[(x-1)/2][y]
        vertexTwo = self.vertices[(x+1)/2][y]
        if x%2 == 0:
          vertexOne = self.vertices[x/2][y]
          vertexTwo = self.vertices[x/2][y+1]
        return (vertexOne, vertexTwo)

      def getEdgesOfVertex(self, vertex):
        vertexEdges = []
        x = vertex.X
        y = vertex.Y
        offset = -1
        if x % 2 == y % 2: offset = 1
        edgeOne = self.edges[x*2][y-1]
        edgeTwo = self.edges[x*2][y]
        edgeThree = self.edges[x*2+offset][y]
        if edgeOne != None: vertexEdges.append(edgeOne)
        if edgeTwo != None: vertexEdges.append(edgeTwo)
        if edgeThree != None: vertexEdges.append(edgeThree)
        return vertexEdges

      # tested
      def getHexes(self, vertex):
        vertexHexes = []
        x = vertex.X
        y = vertex.Y
        xOffset = x % 2
        yOffset = y % 2

        if x < len(self.hexagons) and y/2 < len(self.hexagons[x]):
          hexOne = self.hexagons[x][y/2]
          if hexOne != None: vertexHexes.append(hexOne)

        weirdX = x
        if (xOffset+yOffset) == 1: weirdX = x-1
        weirdY = y/2 
        if yOffset == 1: weirdY += 1
        else: weirdY -= 1
        if weirdX >= 0 and weirdX < len(self.hexagons) and weirdY >= 0 and weirdY < len(self.hexagons):
          hexTwo = self.hexagons[weirdX][weirdY]
          if hexTwo != None: vertexHexes.append(hexTwo)

        if x > 0 and x < len(self.hexagons) and y/2 < len(self.hexagons[x]):
          hexThree = self.hexagons[x-1][y/2]
          if hexThree != None: vertexHexes.append(hexThree)

        return vertexHexes