Help with hex calculations

Module Design
1

In my latest version of the module for “Carrier Battles: Philippine Sea” I make some hex calculations that sometimes do not give the right result. Maybe somebody could advise me a better algorithm.

The situation is this: A Japanese is sent from an origin hex to a target hex some distance away. The target detects the raid when it is 0-5 hexes away from the target. I need to calculate the number of a hex lies the interception distance away from the target hex in a straight line. I have the distance between the origin and the target through the Range() function of attached counters.

I split the hex numbers into a) the first two digits, and b) the last two digits and treat the a and b parts separately. My algorithm goes like this: subtract target from origin, divide by distance, and multiply by Intercept Range, then round. My BeanShell code for the a part is this:

{((Math.abs(((RaidOrigin_a-RaidTarget_a)*100)/Distance*InterceptRange)+50)*((RaidOrigin_a-RaidTarget_a<0)?-1:1)/100)+RaidTarget_a}

The code for the b part is similar.

It works for most situations, but sometimes it gives a wrong result because the rounding of the a and b parts conspire to give a result that is off by one hex.

I can best illustrate this with an example.

Guam Raid
Guam Raid632×318 112 KB

Here the origin is Guam at 1605, the target is TF58 at 1410, and the interception range is 4, so the raid should be at 1506 or 1607, but it ended up at 1507 which is only 3 hexes away from the target.

.Perhaps there already exists a function that gives the straight path between two hexes so that one can count until the right hex is found for the raid?

We can ignore the situation where the interception is further away than the distance between origin and target because in that case the raid is placed in the origin hex.

2

I suspect you will need a more sophisticated solution. Gemini AI’s response is “cube coordinates”, which is the barrier that I’ve encountered before when looking into hex grid calculations for line of sight. Sorry that I lack the expertise and time to give you a more personal response, perhaps some one else can do better. Also, have you come across this site yet?

Gemini AI (caveat emptor):

The issue described in the post is a classic “grid rounding” error. The user is treating hex coordinates (the 4-digit strings like 1605) as standard Cartesian (X,Y) coordinates and applying linear interpolation to them independently. This fails in hex grids because the relationship between the horizontal and vertical axes is not square, and standard rounding on two separate axes often results in a “drift” to an adjacent hex that doesn’t actually lie on the straightest path.

To solve this for a Vassal module, the most robust approach is to convert the coordinates to Cubic Coordinates (x, y, z) where x + y + z = 0.

The Solution: Linear Interpolation (Lerp) in Cube Space

Instead of the user’s current BeanShell math, the algorithm should follow these steps:

  1. Convert to Cube Coordinates: Convert the Origin and Target hexes from Offset (the 4-digit Vassal format) to Cube.

  2. Linear Interpolation: Find the point that is exactly $N$ distance away from the Target toward the Origin.

  3. Cube Rounding: This is the most critical step. Since the “exact” point will have decimals (e.g., x=1.2, y=-3.4, z=2.2), you must round them back to the nearest integer such that the x+y+z=0 constraint remains true.

  4. Convert back to Offset: Convert the result back to the 4-digit string.

Recommended BeanShell/Vassal Implementation

Since the user asked if a function already exists to find a path, they should use the GridLocation and Map classes in Vassal’s API if they are comfortable with custom Java code. However, for a pure BeanShell solution within the module, they can use this logic:

1. Calculate the Ratio

The user wants a hex at a specific InterceptRange from the target. The “progress” along the line (from Target to Origin) is:

t = InterceptRange / Distance

2. The “Cube Lerp” Logic

For each axis (x, y, z), the coordinate of the intercept hex is:

Intercept_x = Target_x + (Origin_x - Target_x) * t

(And similarly for y and z).

3. The “Cube Rounding” Function

This is where the user’s current code fails. To fix it, they need to implement this rounding logic:

Java

rx = Math.round(Intercept_x)
ry = Math.round(Intercept_y)
rz = Math.round(Intercept_z)

x_diff = Math.abs(rx - Intercept_x)
y_diff = Math.abs(ry - Intercept_y)
z_diff = Math.abs(rz - Intercept_z)

if (x_diff > y_diff && x_diff > z_diff) {
    rx = -ry - rz
} else if (y_diff > z_diff) {
    ry = -rx - rz
} else {
    rz = -rx - ry
}

Why the user’s current code failed

The user’s example (Origin 1605, Target 1410, Range 4) failed because they were doing:

((Origin_a - Target_a) / Distance) * InterceptRange

This treats the hexes like they are on a square grid. On a staggered hex grid (like the one in Carrier Battles), every other column is offset vertically. Simple division doesn’t account for the “zigzag” movement required to move diagonally in a hex coordinate system.

By switching to Cube Coordinates, the “distance” between any two adjacent hexes is always 1, and “straight lines” are mathematically consistent, which eliminates the +1/-1 hex error they are seeing.

3

Wow! Gemini certainly seems to have analysed my problem correctly. But unfortunately, Gemini doesn’t tell how to get from hex numbers to cubic coordinates. And frankly, I don’t know the relationship between hexagons and cubes, so I’ll just have to accept that it is right.

As Gemini suspects, I am not comfortable with constructing custom Java code for Vassal, but it seems like I should take a look.

As it stands, my current code gives the correct hexes for most positions. In fact, so much that after having noticed the problem once, I had difficulty recreating it. But once I had found the situation I used as an example, all intercept distances larger than 2 cause an error.

In order to give the players a fine module that works for everything else, I might calculate the distance of the raid to the target, and print a warning message to the playerif it is not correct! Then I could issue a correction later,

4

I have found an algorithm to convert hex numbers to cube coordinates and back. This is going to involve a lot of time consuming math, so I have to consider how to implement this best (without going into custom Java code).

But I’ll give it a shot.

5

For hex-grid calculations it can be beneficial to do a transformation to different coordinates. In particular the so-called cube coordinates can be quite beneficial.

If you have the location (x,y) where x is the column number, and y the row number, then the cube coordinates q, r, s are given by

  • q = x
  • r = y - (x + o * (x % 2) / 2)
  • s = -q - r

where % is the modulo operator (x % 2 is 0 for x even, 1 for x odd), the division above is a truncating (integer) division (3/2 = 1, f.ex.), and o is an offset (0 or 1) depending on whether rows are high or low in even columns.

Distance between L1=(q1,r1,s1) and L2=(q2,r2,s2)

|L1 L2| = (|q1 - q2| + |r1 - r2| + |s1-s2_|) / 2

This means that distances calculated in the column or diagonal directions (straight lines) are fairly straight forward.

For more on different hexagonal coordinate systems, see this excellent page.

Incidently, Vassal uses cube coordinates internally.

Also note, that the the calculations above are entirely integer calculations, which means there’s no rounding error problems.

I recreate these coordinates in my module The Battle of Agincourt. There, I need to know, given a units facing

  • whether the unit is attacked from the rear or flanks.
  • what the range to another unit is when calculaing archery penalties,
  • and, as far as I remember, a few other things.

Suppose you have configured your grid to have locations of the format XXYY where XX is the zero-padded column, and YY is the zero-padded row. Then you can do something like

Define similar properties for other locations - say Target to have those in the cube coordinates. Then you can calculate distances like

  • Calculated Property
    • name: DistanceToTarget
    • expression: {(Math.abs(TargetQ-LocationQ)+Math.abs(TargetR-LocationR)+Math.abs(TargetS-LocationS))/2}

Because the calculations of row and column numbers uses Integer.parseInt, everything will be done as integer calculations with no rounding errors (possibly overflow - but very unlikely).

Hope that can be of some help.

Yours,
Christian

6

This is absolutely splendid, thanks! I had already found the page from Redblob Games, and I was preparing to use those methods, but your post gives the algorithm in a ready-to-type-in form!

I have been busy splitting my code into a fourth action counter (as discussed in my other thread about execution speed), so that the added calculations will not slow the code down.

7

I have implemented the cube conversion, and after some initial difficulties, it now works beautifully. My difficulty was mainly in realising that my hex columns were increasing when going to the right, whereas the redblobgames hexes were decreasing.