algorithm graph-theory graph-traversal metapost

Algorithm to traverse edges of a hex grid between two points

Background

Looking to trace a path between two points on a hexagonal grid while following the nearest edge.

Problem

Determining the algorithm to constrain the all iterations after the first one to the edge.

Code

Given:

vac -- The X coordinate of the starting vertex.
var -- The Y coordinate of the starting vertex.
vbc -- The X coordinate of the ending vertex.
vbr -- The Y coordinate of the ending vertex.
offset_ac -- The X grid offset for the starting central point.
offset_ar -- The Y grid offset for the starting central point.

We can compute:

theta -- The angle of the line, in degrees, between the starting and ending points.
vangle -- The nearest vertex to the line (based on angle).
vc -- The X coordinate of the first vertex, offset from the center.
vr -- Ditto for the Y coordinate.

% Compute the direction towards the first segment (to vertex of an edge).
theta := degrees( atantwo( vac, var, vbc, vbr ) );
vangle := round( theta / 60 ) * 60 * pi / 180;

% Calculate the position of the first vertex, offset from the center.
vc := offset_ac + cos( vangle );
vr := offset_ar + sin( vangle );

% Draw a line from the starting point to the ending point.
draw (offset_ac, offset_ar) -- (vc, vr)
  withcolor colour_node;

% Draw a circle at the ending coordinate.
draw (vc, vr)
  withcolor colour_node
  withpen pencircle
  scaled vertex_sm;

Output

The current output resembles:

The desired output resembles:

Question

What algorithm can walk the graph between the starting and ending points while the path is constrained to the edges?

Finding the first vertex was simple enough. Conceptually, the given code seems like it could be iterated over with the correct "shifting" of the starting point's offset to the vertex. However, after such a "shift" would the new angles be incorrect by something like a half-width and half-height? And even then, how would you keep the next iteration constrained as depicted in the second diagram?

Solution

There may be a more efficient algorithm, but this one accomplishes the task.

Calculate the direction from the starting point to the first vertex, in degrees.
```
vi = round( degrees( atan2( Point A, Point B ) ) / 60 )
```
Calculate the angle for the derived vertex.
```
vangle = vi * 60 * pi / 180
```

Calculate the position of the first vertex.

vc = Point A's x + cos( vangle )
vr = Point A's y + sin( vangle )

Determine the next vertex based on the smallest angle of the three possible next vertices with respect to the line of Point A to Point B.
```
start = if vi mod 2 == 1 then -1 else 2
nearest = infinity
```
Loop over the three possible vertices.
```
for k = start step 2 until 3 do
```

Determine the angle between Point B and a candidate vertex.

kangle = k * 60 * pi / 180
nc = vc + cos( kangle )
nr = vr + sin( kangle )

Determine the distance between Point B and the candidate vertex.
```
d = distance( Point B, Point(nc, nr) )
```
If the distance is smaller than any distance found so far, record the vertex and change up the three candidate three vertices (by increasing the selected vertex index):
```
if d < nearest then
  nearest = d
  sc = nc
  sr = nr
  vi = k + 1
end
```
Repeat from step 4 until the distance is less than or equal to 1.

Cherry-picked result from this algorithm, with additional modifications:

Another result: