Algorithm to traverse edges of a hex grid between two points

Question

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?

Are the coordinates always at the exact center of a hexagon? What is the length of a side of a hexagon? Are the hexagons always oriented such that they have a horizontal side? What do you mean "starting central point"? Is that the same as the "starting vertex"? Or is a vertex a hexagon? — trincot
– trincot, Commented Oct 13, 2022 at 7:16
The hexagons are all unit hexagons. The starting and ending coordinates are always centered, yes. The orientation is always horizontal. The starting vertex is the first vertex along the path, depicted as the small green dot in the first image. — Dave Jarvis
– Dave Jarvis, Commented Oct 13, 2022 at 15:39

Dave Jarvis · Accepted Answer · 2022-10-14 02:13:00Z

1

Given p0 is the starting point and p1 is the ending point then create a path as follows:

Add p0 to path.
Let p = p0.
Let h be hexagon at p.

Then repeat:

If h position is the same as p1 position then add p1 to path and stop.
Chose p from vertices h(i) i = {0, 1, 2, 3, 4, 5}, such that dot( h(i) - p0, p1 - p0 ) is maximal.
Add p to path.
Choose the nearest hexagon h from position p using the dot product of nearby hexagon centers and actual position p and direction of p1 - p.

edited Oct 14, 2022 at 2:13

Dave Jarvis

31.3k43 gold badges186 silver badges326 bronze badges

answered Oct 13, 2022 at 9:50

Spektre

52.3k12 gold badges125 silver badges413 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Dave Jarvis Over a year ago

I'm not sure this algorithm will work. Sometimes we need to stay at the current hexagon, so we can't always pick the nearest hexagon. Unless the set of nearby hexagons to choose from includes the current hexagon.

Dave Jarvis Over a year ago

Here's an image traversing the algorithm. When choosing the new hexagon, it appears as though a vertex will be skipped.

Dave Jarvis Over a year ago

I think there's an algorithm with fewer steps. For a given vertex p, treat p as the center of a new hexagon h. If p is odd, set p to the smallest angle of h relative to angle of p0 - p1 only for odd vertices of h; if even, use even. Repeat until the distance between p and p1 is one step away. Basically, we traverse the Y shape along a shifted hexagonal grid.

Dave Jarvis · Accepted Answer · 2022-10-18 07:07:25Z

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:

Collectives™ on Stack Overflow

Algorithm to traverse edges of a hex grid between two points

Background

Problem

Code

Output

Question

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

Background

Problem

Code

Output

Question

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related