Bagaimana cara merepresentasikan kisi hextile / hex dalam memori?

Katakanlah saya sedang membangun permainan papan dengan kisi yang kuat, seperti Settlers of Catan :

Perhatikan bahwa setiap simpul dan tepi mungkin memiliki atribut (jalan dan pemukiman di atasnya).

Bagaimana saya membuat struktur data yang mewakili papan ini? Apa pola untuk mengakses setiap tetangga, tepi, dan simpul ubin?

Amit Patel telah memposting halaman yang luar biasa tentang topik ini. Ini sangat komprehensif dan luar biasa sehingga perlu menjadi jawaban pasti untuk pertanyaan ini: Hexagonal Grids

Grid seperti itu dapat direpresentasikan dalam array dua dimensi:

Jika

   2
7     3
   1   
6     4
   5

adalah nomor satu dengan tetangganya di grid hex, maka Anda dapat memasukkannya ke dalam array 2D seperti:

2 3
7 1 4
  6 5

Jelasnya ketetanggaan ditentukan dalam grid ini tidak hanya dengan berdekatan secara horizontal atau vertikal tetapi juga menggunakan satu diagonal.

Anda juga dapat menggunakan grafik jika Anda mau.

Artikel ini membahas cara menyiapkan game kisi Isomer / Heksagonal. Saya menyarankan Anda untuk melihat Forcing Isometric and Hexagonal Maps onto a Rectangular Gridbagian dan bagian pergerakan. Meskipun berbeda dari apa yang Anda cari, ini dapat membantu Anda merumuskan bagaimana melakukan apa yang Anda inginkan.

Saya sudah banyak berurusan dengan kutukan. Dalam kasus seperti ini, Anda melacak masing-masing dari 6 titik untuk perbatasan hex. Ini memungkinkan Anda menggambarnya dengan cukup mudah.

Anda akan memiliki satu larik objek yang mewakili heksa. Masing-masing objek hex ini juga memiliki 6 "pointer" (atau indeks ke array lain) yang menunjuk ke array "sisi" lainnya. Hal yang sama untuk "simpul". Tentu saja simpul akan memiliki 3 penunjuk ke heks yang berdampingan, dan sisi akan memiliki 2.

Jadi, hex bisa berupa: X, Y, Point (6), Vertices (6), Sides (6)

Kemudian Anda memiliki array Hex, array vertice, dan array samping.

Maka sangat mudah untuk menemukan simpul / sisi untuk sebuah hex, atau apapun.

Ketika saya mengatakan pointer, itu bisa dengan mudah menjadi integer yang menunjuk ke elemen di simpul atau array samping atau apa pun. Dan tentu saja array bisa berupa daftar atau apapun.

   2
7     3
   1   
6     4
   5

Anda juga dapat mencoba untuk 'mendatar' baris peta Anda. Untuk contoh ini akan menjadi:

  2
7 1 3
6 5 4

Terkadang lebih berguna untuk memiliki baris dalam satu baris: P

Saya akan menyarankan sesuatu seperti berikut (saya akan menggunakan deklarasi gaya Delphi):

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;

Setiap hex memiliki enam sisi dan enam simpul. Setiap tepi melacak dua heks yang bersebelahan, dan setiap simpul melacak tiga heks yang berdampingan (heks di tepi peta akan menjadi kasus khusus).

Ada banyak hal yang dapat Anda lakukan dengan cara yang berbeda tentunya. Anda bisa menggunakan pointer daripada array, Anda bisa menggunakan objek daripada record, dan Anda bisa menyimpan hex Anda dalam array dua dimensi seperti yang disarankan oleh penjawab lain.

Mudah-mudahan, itu mungkin memberi Anda beberapa ide tentang satu cara untuk mendekatinya.

Kami mengimplementasikan Settler of Catan AI untuk proyek kelas, dan memodifikasi kode dari jawaban ini (yang merupakan bug) untuk membuat Board dengan akses acak waktu konstan ke simpul dan tepi. Itu adalah masalah yang menyenangkan, tetapi papannya membutuhkan banyak waktu, jadi jika ada yang masih mencari implementasi sederhana, berikut adalah kode Python kami:

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

Saya duduk di sini "di waktu luang saya, coding untuk bersenang-senang" dengan heksa. Dan bunyinya seperti ini ... Saya akan memberi tahu Anda seperti apa bentuknya dalam kata-kata.

1. Hexagon: memiliki enam hexagon tetangga. Ini dapat memberikan referensi untuk setiap ubin hex tetangga. Itu dapat memberi tahu Anda terdiri dari apa (air, batu, debu). Ia dapat menghubungkan dirinya sendiri dengan orang lain dan sebaliknya. Ia bahkan dapat secara otomatis menghubungkan orang lain di sekitarnya untuk membuat bidang yang lebih besar dan atau memastikan semua bidang dapat diatur oleh tetangganya.
2. Sebuah referensi bangunan hingga tiga jalan dan tiga Ubin Hex. Mereka dapat memberi tahu Anda siapa mereka.
3. Sebuah jalan mereferensikan dua heksa dan jalan lain jika ditempelkan oleh ubin tetangga. Mereka dapat mengetahui ubin mana dan jalan atau bangunan mana yang terhubung dengannya.

Ini hanyalah sebuah ide bagaimana saya akan mengerjakannya.

Anda dapat membuat larik 2D dan kemudian mempertimbangkan posisi yang valid sebagai:

• Pada baris genap (0,2,4, ...): sel bernomor ganjil.
• Pada baris ganjil (1,3,5, ...): sel bernomor genap.

Untuk setiap sel, tetangganya adalah:

• Kolom yang sama, 2 baris ke atas
• Kolom yang sama, 2 baris ke bawah
• 1 tersisa + 1 atas
• 1 kiri + 1 bawah
• 1 kanan + 1 atas
• 1 kanan + 1 bawah

Ilustrasi: Hex Grid

Tanda x adalah heksa. x yang diagonal satu sama lain adalah tetangga. | menghubungkan tetangga vertikal.