Algorithm for creating cells by spiral on the hexagonal field

Question

Help to find an algorithm for creating cells by spiral on the hexagonal field.

Look at the image:

Let's imagine an dimensionless 2d array. The X axis is the blue line, Y is horizontal, spiral is red.

I need to add cells from the central point x0y0 to point N by spiral

Tell me the way to solve the problem, please. Thank you!

Answer 1

Imagine you had a normal grid with squares instead of hexagons, create the spiral using that grid, then draw it by shifting say, every odd y to the left by m pixels, that'll give you that effect.

Answer 2

You can pick hexes one at a time by using an appropriate score function to select the best of the six not-yet-selected adjacent hexes to the hex selected the previous round. I think a score function that works is to pick the closest to (0,0) (forces selecting hexes in one "shell" at a time), breaking ties by choosing the closest to (1,0) (forces a consistent spiral direction in the new shell). Distance in the hex grid can be computed using the following function:

double grid_distance(int dx, int dy) {
  double real_dx = dx + y/2.0;
  double real_dy = dy * sqrt(3)/2.0;
  return sqrt(real_dx * real_dx + real_dy * real_dy);
}

Answer 3

I'd suggest changing the cells numbering sligtly, so that X remains the same when you go down and right (or up and left). Then simple algorithm like the following should work:

  int x=0, y=0;   
  add(x, y); // add the first cell
  int N=1 
  for( int N=1; <some condition>; ++N ) {
    for(int i=0; i<N; ++i) add(++x, y);  // move right
    for(int i=0; i<N-1; ++i) add(x, ++y); // move down right. Note N-1
    for(int i=0; i<N; ++i) add(--x, ++y); // move down left
    for(int i=0; i<N; ++i) add(--x, y); // move left
    for(int i=0; i<N; ++i) add(x, --y); // move up left
    for(int i=0; i<N; ++i) add(++x, --y); // move up right
  }

Answer 4

YOu could do it by simulating directions. If your directions are "0 points up", then increment by 1 as you go clock-wise, the following should do:

Pick a centre cell.
Pick the second cell (ideally in direction 0).
Set direction to 2.

While you have more cells to mark:
  if the cell in (direction+1)%6 is free:
    set direction = (direction+1)%6
  mark current cell as used
  go to cell in direction