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

Say I'm building a board game with a hextile grid, like Settlers of Catan:

Note that each vertex and edge may have an attribute (a road and settlement above).

How wou开发者_运维百科ld I make a data structure which represents this board? What are the patterns for accessing each tile's neighbors, edges and vertices?

Amit Patel has posted an amazing page on this topic. It's so comprehensive and wonderful that it needs to be the definitive answer to this question: Hexagonal Grids

Such a grid can be represented in a two-dimensional array:

If

   2
7     3
   1   
6     4
   5

is the number one with its neighbors in the hex grid, then you can put this into a 2D array like so:

2 3
7 1 4
  6 5

Obviously neighbor-ness is determined in this grid not only by being horizontally or vertically adjacent but also using one diagonal.

You can use a graph too, if you like to, though.

This article goes through how to set up a Isomeric/Hexagonal grid game. I recommend you have a look at the Forcing Isometric and Hexagonal Maps onto a Rectangular Grid section and the the movement section. Although it is different from what you are looking for it may help you formulate how to do what you want.

I've dealt a lot with hexes. In cases like this, you track each of the 6 points for the borders of the hex. This lets you draw it quite easily.

You would have a single array of objects that represent hexes. Each of these hex objects also has 6 "pointers" (or an index to another array) pointing to another array of "sides". Same thing for "vertices". Of course the vertices would have 3 pointers to the adjoining hexes, and the sides would have 2.

So, a hex may be something like: X, Y, Point(6), Vertices(6), Sides(6)

Then you have a Hex array, vertice array, and side array.

Then it is pretty simple to find the vertices/sides for a hex, or whatever.

When I say pointer it could just as easily be an integer pointing to the element in the vertice or side array or whatever. And of course arrays could be lists or whatever.

You could create a 2D array and then consider the valid positions as:

• On even-numbered rows (0,2,4,...): the odd numbered cells.
• On odd-numbered rows (1,3,5,...): the even numbered cells.

For each cell, its neighbors would be:

• Same column, 2 rows up
• Same column, 2 rows down
• 1 left + 1 up
• 1 left + 1 down
• 1 right + 1 up
• 1 right + 1 down

Illustration:

The x marks are hexes. x that are diagonal to each other are neighbors. | connects vertical neighbors.

   2
7     3
   1   
6     4
   5

You can also try to 'flat' rows of your map. For this example it would be:

  2
7 1 3
6 5 4

Its sometimes more useful to have rows in one row:P

I would suggest something like the following (I'll use Delphi-style declarations):

type
  THexEdge = record
    Hexes: array[1..2] of Integer; // Index of adjoining hexes.
    // Other edge stuff goes here.
  end;

  THexVertex = record
    Hexes: array[1..3] of Integer; // Index of adjoining hexes.
    // Other vertex stuff goes here.
  end;

  THex = record
    Edges: array[1..6] of Integer; // Index of edge.
    Vertices: array[1..6] of Integer; // Index of vertex.
    // Other hex stuff goes here.
  end;

var
  Edges: array of THexEdge;
  Vertices: array of THexVertex;
  HexMap: array of THex;

Each hex has six edges and six vertices. Each edge keeps track of its two adjoining hexes, and each vertex keeps track of its three adjoining hexes (hexes on the edges of the map will be a special case).

There are many things that you could do a different way of course. You could use pointers rather than arrays, you could use objects rather than records, and you could store your hexes in a two-dimensional array as other answerers have suggested.

Hopefully, that might give you some ideas about one way to approach it though.

We implemented a Settlers of Catan AI for a class project, and modified code from this answer (which was buggy) to create a Board with constant time random access to vertices and edges. It was a fun problem, but the board took a lot of time, so in case anyone is still looking for a simple implementation here is our Python code:

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

  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

I am sitting here "in my free time coding for fun" with hexes. And it goes like this... I will tell you what it looks like in words.

1. Hexagon: it has six neighbour hexagons. It can deliver the reference for each neighbouring hex tile. It can tell you what it consists of(water ,rock, dust). It can connect itself to others and vice versa. It can even automatically connect the others surrounding him to create a greater field and or making sure all fields can be adressed by its neighbours.
2. A building references up to three roads and three Hex Tiles. They can tell you which they are.
3. A road references two hexes and other roads when they are adressed by neighbouring tiles. They can tell which tiles that are and which roads or buildings they connect to.

This is just an idea how I would work on it.