What is the easiest way to move towards and along the edge on a hex grid?

Question

I have a hexagonal grid with variable radius. My entity can move exactly two hexes per turn.

How should I calculate next step towards border and afterwards travelling clockwise around map?

Preferred movement at the boundary

Character should stay at the border while moving counter-clockwise every turn.

Example movement at the middle

Character should move 1 or 2 hexes towards edge every turn.

I can't figure out simple math to do this.

Edit:

This is how I did movement at the boundary:

  var x = pos.x;
  var y = pos.y;
  var z = -pos.x-pos.y;
  var dx =  0;
  var dy =  0;

  if      (x == -radius && z >   1) {          dy =  2; }
  else if (x == -radius && z ==  1) { dx =  1; dy =  1; }
  else if (y ==  radius && x <  -1) { dx =  2           }
  else if (y ==  radius && x == -1) { dx =  2; dy = -1; }
  else if (z == -radius && y >   1) { dx =  2; dy = -2; }
  else if (z == -radius && y ==  1) { dx =  1; dy = -2; }
  else if (x ==  radius && z <  -1) {          dy = -2; }
  else if (x ==  radius && z == -1) { dx = -1; dy = -1; }
  else if (y == -radius && x >   1) { dx = -2;          }
  else if (y == -radius && x ==  1) { dx = -2; dy =  1; }
  else if (z ==  radius && y <  -1) { dx = -2; dy =  2; }
  else if (z ==  radius && y == -1) { dx = -1; dy =  2; }

Any ideas how should I clean this up?

Shortest path to boundary is probably easiest to calculate from x, y and z.

Answer 1

I think it'll be easier to solve this if you move one step at a time instead of one-or-two. For each location on the map there's a single direction to move in. Let's calculate that direction.

First observation: if you're using the 3-valued “cube” coordinates, the largest coordinate tells you which of the six “wedges” you're in. Here's a diagram showing the colors:

Code like this should do it:

var axes = [cube.x, -cube.z, cube.y,
           -cube.x, cube.z, -cube.y];
var direction = 0;
for (var i = 0; i < 6; i++) {
    if (axes[i] >= axes[direction]) { 
        direction = i; 
    }
}
if (direction == 5 && axes[0] == axes[5]) { 
    direction = 0; // special case :(
}

Second observation: once you know which wedge you're in, you can decide how to move relative to that wedge direction:

1. If you're not at the edge of the map, you want to move towards the edge, and the wedge tells you which way to go. To be fancier, you can alternate left and right steps.
2. If you are at the edge of the map, you can take the direction you were moving towards the edge and rotate it left. This will then take you along the edge.

You can use code like this:

var length = Cube_length(cube);
var isBorder = (length == N);
var next = Cube_neighbor(cube, (direction + (isBorder? 2 : length % 2))%6);

Following these two rules you'll get something like this:

I've also written this up here.

Answer 2

I would do it in two 1-cell steps instead of a single 2-cell step, it’s a lot easier to implement.

Using your coding style, here would be my first try:

var dx = 0, dy = 0;

for (var i = 0, x = pos.x, y = pos.y; i < 2; ++i, x += dx, y += dy)
{
    var z = x + y;

    // If point is on the edge, move along the edge
    if (x != 0 
          && y == -radius) { --dx; }
    else if (x ==  radius) {       --dy; }
    else if (z ==  radius) { ++dx; --dy; }
    else if (y ==  radius) { ++dx; }
    else if (x == -radius) {       ++dy; }
    else if (z == -radius) { --dx; ++dy; }
    // Otherwise move towards the edge
    else if (x > 0 && z <= 0) {       --dy; }
    else if (z > 0 && y <= 0) { ++dx; --dy; }
    else if (y > 0 && x >= 0) { ++dx; }
    else if (x < 0 && z >= 0) {       ++dy; }
    else if (z < 0 && y >= 0) { --dx; ++dy; }
    else if (y < 0 && x <= 0) { --dx; }
    // Exactly at the centre — just choose a random direction
    else { ++dx; }
}

Answer 3

not a mathematician here but you could divide this problem in 4 distinct sections, like the quarters of a circle. Then, by checking which direction is closer to the edge, move along that path. ex: (2,-1) the (+,-) sing informs us that it`s located in the top right quadrant. then, we know that the edgemost closest hex is 3,-1 but you can deduce by using the max x value at y=0 or the max y value at x=0 and then substract your current position to see where the closest edge lies. then, we can see that there's some very easy rules to follow the edge counter clockwise if taken into quarter cases.

for example: Case 1(top right) if you're on the edge (x cannot go higher) move up along the y axis. if y cannot get higher, lower x until you reach (0, max y) which would be the top most coordinate and from there, move into quadrant 4 (-,-).

just my 2 cents, as i said, not a mathematician.