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

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.

• Why is (1,0)’s destination (2,-2) instead of (1,-2) or (3,-2)? Why does (2,-1) go to (3,-3) instead of (2,-3)? The rules aren’t very clear to me. – sam hocevar Mar 13 '16 at 11:44
• That was just an example. Only rules are that character moves towards boundary if it can. And if it can't go further, then move counter-clockwise. – warbaque Mar 13 '16 at 11:49
• For example i.stack.imgur.com/42y0k.png would be also fine. – warbaque Mar 13 '16 at 11:55
• Some of this will be simpler if you treat your coordinates as an array of three numbers instead of separate x,y,z fields. Then you'll be able to choose an index into that array (and also a sign), and treat the x,y,z fields uniformly instead of repeating the code. – amitp Mar 13 '16 at 17:19
• Movement at the boundary is probably best done one step at a time, using the rotation function. In the visualization, put your mouse on the boundary and you'll see one coordinate is +/- radius; set the other two to -/+ radius and 0, and then use the rotate function to tell you which direction to go in. – amitp Mar 13 '16 at 17:28

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 == axes) {
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.

• It might also help OP to point out the invariant satisfied by cube coordinates: x + y + z == 0. Because of this invariant it is never necessary to store all three; the third can always be reconstructed from the other two. – Pieter Geerkens Mar 14 '16 at 3:16

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; }
}


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.

• also, why is your y axis reversed? it goes from top to bottom increasingly. – Alkarym Moro Mar 13 '16 at 12:14