Grid distance

How to calculate the distance in a hexagonal grid?

I tried to use a code found in internet but it does not work or, I’m making a mistake somewhere.
The original

int GetTileDistance(int aX1, int aY1, int aX2, int aY2) { int dx = aX2 - aX1; // signed deltas int dy = aY2 - aY1; int x = Mathf.Abs(dx); // absolute deltas int y = Mathf.Abs(dy); // special case if we start on an odd row or if we move into negative x direction if ((dx < 0)^((aY1&1)==1)) x = Mathf.Max(0, x - (y + 1) / 2); else x = Mathf.Max(0, x - (y) / 2); return x + y; }

passed to Xojo
(fromHex and toHex are strings like “3320”, “3522”

[code]Public Function CheckDistance(fromHex as string, toHex as string) as integer
var aX1, aY1, aX2,aY2 as integer

aX1 = fromHex.Right(2).ToInteger
aY1 = fromHex.Left(2).ToInteger

aX2 = tohex.Right(2).ToInteger
aY2 = tohex.Left(2).ToInteger

var dx as integer = aX2 - aX1
var dy as integer = aY2 - aY1
var x as integer = abs(dx)
var y as integer = abs(dy)

if (dx<0 or aY1 mod 2 <> 0) then
x = max(0, x-(y+1)/2)
else
x = Max(0, x-(y)/2)
end if

return x + y

End Function
[/code]

Nobody has an idea on what is wrong? or another approach?

Make us an example for testing. What is your result? And where is the problem?

“^” in C is not an OR operator but an XOR
see https://www.tutorialspoint.com/cprogramming/c_operators.htm

so your tests lines are not right.

It seems clear that the first two digits of fromHex and toHex refer to the column and the last two digits refer to the row, but what is meant by “distance” is not clear. When you refer to distance, are you referring to the distance from the centre of one hexagon to the centre of another one, or from a vertex (or edge) of one hexagon to a vertex (or edge) of another one, etc., and if so, which vertex (or edge)?

This looks like a hexagonal version of taxicab geometry.

Posted a text example
https://www.dropbox.com/s/qbkae746a8tth0s/Grid.zip?dl=0

[quote=485263:@Robert Weaver]It seems clear that the first two digits of fromHex and toHex refer to the column and the last two digits refer to the row, but what is meant by “distance” is not clear. When you refer to distance, are you referring to the distance from the centre of one hexagon to the centre of another one, or from a vertex (or edge) of one hexagon to a vertex (or edge) of another one, etc., and if so, which vertex (or edge)?

This looks like a hexagonal version of taxicab geometry.[/quote]
Distance in hexes

[quote=485267:@Enric Herrera]Posted a text example
https://www.dropbox.com/s/qbkae746a8tth0s/Grid.zip?dl=0[/quote]
There’s no text example there—just the same image file as in your first post and a Xojo project file.

“Distance in hexes” explains nothing. So tell us, for example, what is:

  1. Distance between 2917 and 3117?
  2. Distance between 2917 and 3018?
  3. Distance between 2917 and 2918?
if (dx<0 or  aY1 mod 2 <> 0) then

should be

if ((dx<0) xor  ((aY1 mod 2) <> 0)) then

[quote=485269:@Robert Weaver]There’s no text example there—just the same image file as in your first post and a Xojo project file.

“Distance in hexes” explains nothing. So tell us, for example, what is:

  1. Distance between 2917 and 3117?
  2. Distance between 2917 and 3018?
  3. Distance between 2917 and 2918?[/quote]
    The link is a .zip that contains the res.xojo_binary_project and the grid.png (I just downloaded myself )
    The distance should be:
    2917 and 3117 = 2
    2917 and 3118 = 2
    2917 and 2918 = 1
    2917 and 3019 = 2
    So, starting on an hexagon count hexes to reach the target.

I think the trouble comes from the different type of layout
"odd-r” horizontal layout
“even-r” horizontal layout
“odd-q” vertical layout
“even-q” vertical layout
I’m using “even-q” vertical layout, ( shoves odd columns down)

[quote=485271:@Jean-Yves Pochez]if (dx<0 or aY1 mod 2 <> 0) then
should be

if ((dx<0) xor  ((aY1 mod 2) <> 0)) then

I tried also, but not luck

// if dx<0  or aY1 mod 2 = 0 then
if ((dx<0)  Xor (aY1 mod 2 <> 0)) then
  x = Max(0, x - floor((y+1)/2))
else
  x = Max(0, x - floor(y/2))
end if

q

Thanks Robert, but in some cases, I think your code do not work.
Checking from 3320 to 3419 or to 3219 gives a range of 1 when it should be 2.

???[quote=485287:@Robert Livingston]q[/quote]

[code]Public Function CheckDistance(fromHex As String, toHex As String) As Integer
Var hexA, hexB As Integer
hexA = fromHex.Val
hexB = toHex.Val

Var colA, colB, rowA, rowB As Integer

colA = hexA \ 100
colB = hexB \ 100
rowA = hexA Mod 100
rowB = hexB Mod 100

Var jump As Integer = 0

Do

If colA = colB And rowA = rowB Then Return jump + 0
If colA = colB Then Return jump + Abs(rowA - rowB)
If rowA = rowB Then Return jump + Abs(colA - colB)
If colA Mod 2 = 0 And rowA = rowB + 1 Then Return jump + Abs(colA - colB)
If colA Mod 2 = 1 And rowA = rowB - 1 Then Return jump + Abs(colA - colB)

jump = jump + 1
If Abs(colA - colB) > Abs(rowA - rowB) Then
// change column
If colA < colB Then colA = colA + 1 Else colA = colA - 1
Else
// change row
If rowA < rowB Then rowA = rowA + 1 Else rowA = rowA - 1
End If

Loop[/code]

Well, its is a little better but still not completely work :frowning:

Thanks Robert, it works well only at 2 hexes distance. Has 2 fautls at 3 hexes ,and 6 fautls at 4, so exponentially will fail much more at more distance.
It’s a very complicated algorithm, I though it should be very common because is used a lot in games that use hexagons…

[code]Public Function CheckDistance(fromHex As String, toHex As String) As Integer
Var hexA, hexB As Integer
hexA = fromHex.Val
hexB = toHex.Val

Var colA, colB, rowA, rowB As Integer

colA = hexA \ 100
colB = hexB \ 100
rowA = hexA Mod 100
rowB = hexB Mod 100

Var jump As Integer = 0

Do

If colA = colB And rowA = rowB Then Return jump + 0
If colA = colB Then Return jump + Abs(rowA - rowB)
If rowA = rowB Then Return jump + Abs(colA - colB)
If colA Mod 2 = 0 And rowA = rowB + 1 Then Return jump + Abs(colA - colB)
If colA Mod 2 = 1 And rowA = rowB - 1 Then Return jump + Abs(colA - colB)

jump = jump + 1
If colA Mod 2 = 0 And rowA > rowB And colA > colB Then
rowA = rowA - 1
colA = colA - 1
Continue
End If
If colA Mod 2 = 0 And rowA > rowB And colA < colB Then
rowA = rowA - 1
colA = colA + 1
Continue
End If
If colA Mod 2 = 1 And rowA < rowB And colA < colB Then
rowA = rowA + 1
colA = colA + 1
Continue
End If
If colA Mod 2 = 1 And rowA < rowB And colA > colB Then
rowA = rowA + 1
colA = colA - 1
Continue
End If

If Abs(colA - colB) > Abs(rowA - rowB) Then
// change column
If colA < colB Then colA = colA + 1 Else colA = colA - 1
Else
// change row
If rowA < rowB Then rowA = rowA + 1 Else rowA = rowA - 1
End If

Loop[/code]

This does better

Oh Robert, the last code seems to work very fine. I really appreciate your time (and your wisdom), I spent two completed days trying to find a way to calculate this. Really, thank you.

The code is pretty fast as is. But it could be a little more efficient. I reversed the most logical approach in one segment. As originally posted:

If Abs(colA - colB) > Abs(rowA - rowB) Then // change column If colA < colB Then colA = colA + 1 Else colA = colA - 1 Else // change row If rowA < rowB Then rowA = rowA + 1 Else rowA = rowA - 1 End If

It makes more sense to do the below:

If Abs(colA - colB) > Abs(rowA - rowB) Then // change row If rowA < rowB Then rowA = rowA + 1 Else rowA = rowA - 1 Else // change column If colA < colB Then colA = colA + 1 Else colA = colA - 1 End If