Thanks to this post: Hexagonal tiles and finding their adjacent neighbours, I'm able to collect adjacent tiles to a given tile. But I'm pretty much stuck on an algorithm that gives me only a "ring" of tiles specified by an offset. The algorithm given in that Stack Overflow post doesn't exactly care about the order in which it collects the tiles.

I know that with every offset 6 tiles are added.

  • Offset 1 gives you 6 tiles (the first adjacent tiles).
  • Offset 2 gives you 12.
  • Offset 3 gives you 18, etc.

There is a constant growth of 6 with each offset. So I assume there should be a rule which adapts to these offsets. I can't exactly figure this one out. Anyone?

up vote 21 down vote accepted

A hexagonal ring with the radius of N consists of 6 straight lines, each with length N - see my extremely crude example below :) For N=2:

enter image description here

The arrows cover 2 hexes each.

I assume you have some functions which give you the neighbouring tile in a specific direction, like north(), southeast() etc. So your algorithm, in pseudocode, should be something like this:

var point = startingPoint.north(N)
for i = 0..N-1:
    result.add(point)
    point = point.southeast(1);
for i = 0..N-1:
    result.add(point)
    point = point.south(1);
for i = 0..N-1:
    result.add(point)
    point = point.southwest(1);
for i = 0..N-1:
    result.add(point)
    point = point.northwest(1);
for i = 0..N-1:
    result.add(point)
    point = point.north(1);
for i = 0..N-1:
    result.add(point)
    point = point.northeast(1);

Note that this should work also for edge cases N=1, returning 6 tiles, and N=0 returning an empty set.

I know the code isn't perfect :) There is some redundancy here. In my projects using regularly tiled maps (hexagonal or otherwise) I usually have an enum "Direction", which allows me to do this more smoothly:

var point = startingPoint.inDir(N, Direction.North)
var dir = Direction.SouthEast.
for d = 0..Direction.count():
    for i = 0..N-1:
        result.add(point)
        point = point.inDir(1, dir);
    dir = nextDirection(dir);
  • This should push me in the right direction. Thanks! – Sidar Mar 18 '13 at 14:34
  • 2
    Note that the code sample will add duplicate points for the first five segments. However, it's a nice answer. – MichaelHouse Mar 18 '13 at 14:38
  • @Byte56 Yeah I figured. But at least I see the connection between shifts in direction! – Sidar Mar 18 '13 at 14:39
  • 1
    @Byte56 Really? Hm. I tried to avoid that one... 0..N-1 gives 0..1 for N=2, so that's i=0 and i=1, which is 2 values. 2 values from each times 6 directions is 12 tiles, as it should be ...? – Liosan Mar 18 '13 at 15:10
  • Nope. You're right. Since each loop is adding a point from the last loop I was off by one for the loops, my mistake. It's a clever algorithm. – MichaelHouse Mar 18 '13 at 15:57

I have found this article to be a very good reference for hexagonal grid algorithms, and its section on "Distances" provides a method for determining the number of steps between two tiles. If you convert your axial coordinates (x-y) into cube coordinates (x-y-z), the distance is always equal to the largest of the coordinate offsets between the two tiles, or max(|dx|, |dy|, |dz|).

An exhaustive search of the whole grid for tiles at the desired distance is \$O(n^2)\$ with the grid dimensions, but it is a simple implementation that works well for small grids.

enter image description here

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.