Algorithm for creating cells in a spiral on a hexagonal field

Question

Help me find an algorithm for creating cells in a spiral on a hexagonal field.

Look at the image:

Let's imagine a dimensionless 2d array. X axis - blue line, Y - horizontal, spiral - red.

I need to add cells from the center point x0y0 to point N in a spiral

Please tell me a way to solve the problem. Thanks!

Answer 1

I would suggest changing the cells numbered so that X stays the same when you go down and to the right (or up and to the left). Then a simple algorithm should work, such as the following:

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 } 

This generates points as follows:

After the conversion we get:

Answer 2

(circles have a diameter of 1)

Here is the function to get position i :

  void getHexPosition( int i, ref double x, ref double y ) { if ( i == 0 ) { x = y = 0; return; } int layer = (int) Math.Round( Math.Sqrt( i/3.0 ) ); int firstIdxInLayer = 3*layer*(layer-1) + 1; int side = (i - firstIdxInLayer) / layer; // note: this is integer division int idx = (i - firstIdxInLayer) % layer; x = layer * Math.Cos( (side - 1) * Math.PI/3 ) + (idx + 1) * Math.Cos( (side + 1) * Math.PI/3 ); y = -layer * Math.Sin( (side - 1) * Math.PI/3 ) - (idx + 1) * Math.Sin( (side + 1) * Math.PI/3 ); } 

Scaling the result on Math.Sqrt(.75) gives

If you are interested in distorted coordinates, as in Shura’s answer:

  int[] h = { 1, 1, 0, -1, -1, 0, 1, 1, 0 }; void getHexSkewedPosition( int i, ref int hx, ref int hy ) { if ( i == 0 ) { hx = hy = 0; return; } int layer = (int) Math.Round( Math.Sqrt( i/3.0 ) ); int firstIdxInLayer = 3*layer*(layer-1) + 1; int side = (i - firstIdxInLayer) / layer; int idx = (i - firstIdxInLayer) % layer; hx = layer*h[side+0] + (idx+1) * h[side+2]; hy = layer*h[side+1] + (idx+1) * h[side+3]; } void getHexPosition( int i, ref double hx, ref double hy ) { int x = 0, y = 0; getHexSkewedPosition( i, ref x, ref y ); hx = x - y * .5; hy = y * Math.Sqrt( .75 ); } 

Answer 3

Imagine that you had a normal grid with squares instead of hexagons, create a spiral using this grid, then draw it by moving, say, every odd y on the left by m pixels, which will give you this effect.

Answer 4

You can select hexes one at a time using the appropriate rating function to select the best of the six not yet selected adjacent hexes, so that the hexadecimal selected in the previous round. I think the evaluation function that works is to select the one closest to (0,0) (enhances the choice of hexes in one “shell” at a time), breaking the bonds, choosing the closest to (1,0) (forces the consistent spiral direction in a new shell). The distance in the hexadecimal grid can be calculated 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 5

You could do this by simulating directions. If your directions are "0 points up", then an increment of 1 when moving clockwise should be as follows:

  Pick a center 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

Answer 6

Well, I had the same problem, and the suggestions here do not solve the problem, because it was stated that I thought I would add my solution ...

 private void generateMap(int size) { // size is number of rings not counting center so array length is... mapHexs = new Hex[(size*2)+1,(size*2)+1]; // offsets to traverse (sw,w,nw,ne,e,se) from a tile int[,] offsetsOdd = new int[,] {{-1,-1},{-1,0},{-1,1},{0,1},{1,0},{0,-1}}; int[,] offsetsEven = new int[,] {{0,-1},{-1,0},{0,1},{1,1},{1,0},{1,-1}}; //start in the center int posX = size; int posY = size; // each ring for (int ring = 1; ring <= size; ring++) { // at the start of a ring step out one posX++; // each side for(int side = 0; side < 6; side++) { // tiles per side for(int idx = 0; idx < ring; idx++) { // odd or even line if(posY % 2 == 0) { posX += offsetsEven[side,0]; posY += offsetsEven[side,1]; } else { posX += offsetsOdd[side,0]; posY += offsetsOdd[side,1]; } mapHexs[posX,posY] = new Hex(); } } } } 

Answer 7

I liked @shura's approach to solving the problem, but could not get this exact algorithm to work. In addition, I use a 2x1 hexagonal spacing (where cells x are spaced 2 apart and each other element x is hidden).

Here is what I got (albeit in JavaScript):

  //Hexagon spiral algorithm, modified from for(var n=1; n<=rings; ++n) { x+=2; add(x, y); for(var i=0; i<n-1; ++i) add(++x,++y); // move down right. Note N-1 for(var i=0; i<n; ++i) add(--x,++y); // move down left for(var i=0; i<n; ++i) { x-=2; add(x, y); } // move left for(var i=0; i<n; ++i) add(--x,--y); // move up left for(var i=0; i<n; ++i) add(++x, --y); // move up right for(var i=0; i<n; ++i) { x+=2; add(x, y); } // move right }