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.
[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 therejust 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:
- Distance between 2917 and 3117?
- Distance between 2917 and 3018?
- 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 therejust 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:
- Distance between 2917 and 3117?
- Distance between 2917 and 3018?
- 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
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 
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