Finding adjacent neighbors on a hexagonal grid

Question

EDIT: Wrapped the example map in a code block so the formatting is correct.

Ok, I'm trying to write an extremely simple A* algorithm over a hexagonal grid. I understand, and can do the A* portion. In fact, my A* works for square grids. What I can't wrap my brain around is finding neighbors with hexagons. Here's the layout for the heagonal grid

0101     0301
    0201      0401
0102     0302
    0202      0402

etc, etc

So, what I need help with is writing a Hexagon class that, given it's hex coordinates, can generate a list of neighbors. It needs to be able to generate neighbors which would 'fall off' the grid (like 0000 or 2101 in a 20x20 grid) because that's how my A* tracks across multiple maps laid side-by-side. So something that would work with this code snippet:

planet = Hex('0214') print(planet.neighbors()) ['Hex 0213', 'Hex 0215', 'Hex 0115', 'Hex 0315', 'Hex 0116', 'Hex 0316']

I have provided an answer to this same question found here: http://stackoverflow.com/a/15524441/2135355 — Ed Rowlett-Barbu, Mar 20 '13 at 13:10

score 9 · Accepted Answer · answered Jul 12 '11 at 08:22

9

It depends on how you define the coordinates of your hex tiles.

Let's see.

  ,   ,   ,   ,
 / \ / \ / \ / \
| A1| A2| A3| A4|
 \ / \ / \ / \ /
  | B1| B2| B3|
 / \ / \ / \ / \
| C1| C2| C3| C4|
 \ / \ / \ / \ /
  '   '   '   '

In this case, neighbor definition is different for even and odd rows.

For a cell (X,Y) where Y is even, the neighbors are: (X,Y-1),(X+1,Y-1),(X-1,Y),(X+1,Y),(X,Y+1),(X+1,Y+1)

For a cell (X,Y) where Y is odd, the neighbors are: (X-1,Y-1),(X,Y-1),(X-1,Y),(X+1,Y),(X-1,Y+1),(X,Y+1)

answered Jul 12 '11 at 08:22

G B

2,951
2
28
50

Ok, I think I'm following. This one has really been driving me crazy, and I've been mulling it over for quite some time. Can you take a look at my pretty-formatted example? – Jonathanb Jul 12 '11 at 08:35
I see, it's very similar, my tiles are "vertical" and yours are "horizontal", just exchange X with Y, and think columns instead of rows. – G B Jul 12 '11 at 08:51
Thank you. I'm under the weather right now, but as soon as I actually get the code written up, I'll post it as a comment underneath this answer in case other people need similar help. I just couldn't get past the conceptual barrier.... – Jonathanb Jul 14 '11 at 04:58
Too big to fit in a commment, so I've posted it as an answer below. Thanks again for your help! – Jonathanb Jul 17 '11 at 04:07
@GB: I think you have got Y == even and Y == odd mixed up. Can you check? – Manoj Govindan Mar 30 '12 at 10:45
I've checked again, and it looks ok. Example: B2 => Y is even (starting from 1, not from 0). – G B May 29 '13 at 11:29

score 2 · Answer 2 · answered Jul 17 '11 at 04:10

Per my comment above, here is the code I implemented. Anybody with suggestions to help me clean it up, I'd welcome the feedback.

class Hexagon():
"""Implements a class of hexagon from a hex map which is vertically tiled.
This hexagon is able to return a list of it's neighbors. It does not care 
if the neighbors are hexes which actually exist on the map or not, the map is
responsible for determining that."""

def __init__(self,grid_number):
    self.name = grid_number
    self.x = int(grid_number[0:2])
    self.y = int(grid_number[2:4])

def neighbors(self):
    ret_list = []
    if self.x % 2 == 0:
        temp_list = [[self.x,self.y-1],
              [self.x-1,self.y],  [self.x+1,self.y],
              [self.x-1,self.y+1],[self.x+1,self.y+1],
                    [self.x,self.y+1]]
        for i in temp_list:
            ret_list.append(format(i[0],'02d') + format(i[1],'02d'))

    elif self.x % 2 == 1:
        temp_list = [[self.x,self.y-1],
              [self.x-1,self.y-1],[self.x+1,self.y-1],
              [self.x-1,self.y],[self.x+1,self.y],
                    [self.x,self.y+1]]
        for i in temp_list:
            ret_list.append(format(i[0],'02d') + format(i[1],'02d'))

    return ret_list

def main():
    hex1 = Hexagon('0201')
    hex2 = Hexagon('0302')
    if hex1.neighbors() == ['0200','0101','0301','0102','0302','0202']:
        print("Works for even columns.")
    else:
        print("Failed for even columns.")
        print(hex1.neighbors())

    if hex2.neighbors() == ['0301','0201','0401','0202','0402','0303']:
        print("Works for odd columns.")
    else:
        print("Failed for odd columns.")
        print(hex2.neighbors())

if __name__ == '__main__':
    main()

Finding adjacent neighbors on a hexagonal grid

2 Answers2

Linked