18
\$\begingroup\$

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?

\$\endgroup\$
24
\$\begingroup\$

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);
\$\endgroup\$
6
  • \$\begingroup\$ This should push me in the right direction. Thanks! \$\endgroup\$
    – Sidar
    Mar 18 '13 at 14:34
  • 2
    \$\begingroup\$ Note that the code sample will add duplicate points for the first five segments. However, it's a nice answer. \$\endgroup\$
    – House
    Mar 18 '13 at 14:38
  • \$\begingroup\$ @Byte56 Yeah I figured. But at least I see the connection between shifts in direction! \$\endgroup\$
    – Sidar
    Mar 18 '13 at 14:39
  • 2
    \$\begingroup\$ @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 ...? \$\endgroup\$
    – Liosan
    Mar 18 '13 at 15:10
  • \$\begingroup\$ 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. \$\endgroup\$
    – House
    Mar 18 '13 at 15:57
2
\$\begingroup\$

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

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .