Best Way to Store a Triangular/Hexagonal Grid in Python

Question

I'm making a game with hexagonal tiles, and have decided upon using a triangular/hexagonal grid. I found this question which helped me generate coordinates, and slightly modified the code to store all the coordinates as keys in a dictionary with values of either "." (floor) or "X" (wall,) and included a function that prints out a string representation of the map where each non-blank character represents a hexagonal tile. This is the new code:

deltas = [[1,0,-1],[0,1,-1],[-1,1,0],[-1,0,1],[0,-1,1],[1,-1,0]]
class HexGrid():
    def __init__(self, radius):
        self.radius = radius
        self.tiles = {(0, 0, 0): "X"}
        for r in range(radius):
            a = 0
            b = -r
            c = +r
            for j in range(6):
                num_of_hexas_in_edge = r
                for i in range(num_of_hexas_in_edge):
                    a = a+deltas[j][0]
                    b = b+deltas[j][1]
                    c = c+deltas[j][2]           
                    self.tiles[a,b,c] = "X"

    def show(self):
        l = []
        for y in range(20):
            l.append([])
            for x in range(60):
                l[y].append(".")
        for (a,b,c), tile in self.tiles.iteritems():
            l[self.radius-1-b][a-c+(2*(self.radius-1))] = self.tiles[a,b,c]
        mapString = ""
        for y in range(len(l)):
            for x in range(len(l[y])):
                mapString += l[y][x]
            mapString += "\n"
        print(mapString)

With this code, I can generate all the coordinates within the radius like so:

import hexgrid
hg = hexgrid.HexGrid(radius)

and access a coordinate like this:

hg.tiles[a,b,c]

This seems to work fine for now, but I'm sure there must be some disadvantages to storing the map this way. If there are any disadvantages, could you please point them out, and maybe present a better way to store the map? Thanks a lot for your time.

Answer 1

Using an array for storage may save you some CPU time, but the difference is probably neglible.

However, you missed a very simple way of managing such a map. Consider it to be rows and columns, just the cells have slightly different shapes.

+--+--+--+--+--+--+--+
 \/ \/ \/ \/ \/ \/ \/    Even row

  /\ /\ /\ /\ /\ /\ /\   Odd row
 +--+--+--+--+--+--+--+

Or for hexagons:

  __    __    __    __
 /  \__/  \__/  \__/  \__ Even row
 \__/  \__/ A\__/  \__/   Odd  row
 /  \__/ F\__/ B\__/  \__ Even row
 \__/  \__/ X\__/  \__/   Odd  row
 /  \__/ E\__/ C\__/  \__ Even row
 \__/  \__/ D\__/  \__/   Odd  row
 /  \__/  \__/  \__/  \__ Even row
 \__/  \__/  \__/  \__/   Odd  row

Then you can store the data just as a regular 2D array. Odd rows are offset .5 to the right, and you need to figure out the neighborship steps for X: above: A = (0,-2), up right: B = (1,-1), bottom right: C = (1,1), below: D = (0,2), bottom left: E = (0,1), top left: F = (0,-1)

If you are ok with wasting a bit of memory, you can also leave every other column empty, and the neighborship becomes a bit simpler: (0,-2), (1,-1), (1,-1), (0,-2), (-1,-1), (-1,1)

Answer 2

I made some research too, and found a far more simple way to do it. You do not have to get as complicated as you do! The table can be an simple array of array, without any special rules.

You want to use an hexagonal root coordonate system. See the theory here : https://en.wikipedia.org/wiki/Root_system . Also https://www.redblobgames.com/grids/hexagons/

The cell (0,0) is located in the centre of the structure, then it have six neighbours : as in the well known orthogonal table (1,0), (0,1), (-1,0), (0,-1) but also (1,1) , (-1-1). Others cell have similarly six neighbours, no need of modulo!

Here some Ascii art for beter understanding:

   _____       _____      ____      __
  / -2,2\_____/ 0,1 \____/2,0 \____/  \__ 
  \_____/-1,1 \_____/ 1,0\____/3,-1\__/   
  /-2,1 \_____/0,0  \____/2,-1\____/  \__     
  \_____/-1,0 \_____/1,-1\____/3,-2\__/   
  /-2,0 \_____/ 0,-1\____/2,-2\____/  \__ 
  \_____/     \_____/    \____/    \__/   

You can calculate the position of the center of each cell in the plane (and so in the screen) because it follows the rules of vectorial geometry. The vector have the coordinates that are in 60° instead of 90° : a=(0,1) but b=(0,87,0.5), simply multiply and add theses coordinates!

You may want to use the python library Hexy.