Calculating distance using hex coordinate system
m...@nowhere.edu
I've created a hex grid bitmap, and have assigned each hex a
coordinate exactly as portrayed on this page,
http://www.gamedev.net/reference/articles/article1800.asp and am now
trying to nail down the algorithm to determine the distance between
any two hexes when the coordinates are known.
it seems like it should be easy, but damn if I just can't reason it
out!
Any suggestions would be appreciated. I am coding in c#.net but I
should be able to translate from almost any programming language, so
don't let that be a barrier to you in posting. =)
Thanx
Christopher Dearlove
writes
>Any suggestions would be appreciated. I am coding in c#.net but I
>should be able to translate from almost any programming language, so
>don't let that be a barrier to you in posting. =)
As I recall - I had a non-games reason for it once - if the shortest
path
from the centre of one hex to another is m hexes along one row, then
n hexes along another (so that most games measure the distance as
m+n) then the actual distance is
sqrt(m^2 + mn + n^2) or sqrt([m+n]^2 - mn)
assuming the distance from the centre of one hex to the next is 1
(otherwise multiply by it).
It was a few years ago, and I haven't checked it today. But I'm
reasonably confident of it.
(This comes up in ideal cellular radio systems. This maps to
reusing m^2 + mn + n^2 frequencies, and only some numbers
work: 1, 3, 4, 7, 9, ...)
--
Christopher Dearlove
Nick Wedd
>
>I've created a hex grid bitmap, and have assigned each hex a
>coordinate exactly as portrayed on this page,
>http://www.gamedev.net/reference/articles/article1800.asp and am now
>trying to nail down the algorithm to determine the distance between
>any two hexes when the coordinates are known.
What kind of distance do you want to calculate? The two most likely
possibilities are
1.) The hex equivalent of "Manhattan distance", i.e. the number of
"king's moves" it takes to get from one hex to another
2.) The Euclidean distance between the centres of two hexes
Nick
>it seems like it should be easy, but damn if I just can't reason it
>out!
>
>Any suggestions would be appreciated. I am coding in c#.net but I
>should be able to translate from almost any programming language, so
>don't let that be a barrier to you in posting. =)
>
>Thanx
--
Nick Wedd ni...@maproom.co.uk
Christopher Dearlove
<ni...@maproom.co.uk> writes
>What kind of distance do you want to calculate? The two most likely
>possibilities are
>1.) The hex equivalent of "Manhattan distance", i.e. the number of
>"king's moves" it takes to get from one hex to another
>2.) The Euclidean distance between the centres of two hexes
In terms of my answer, 1) is m+n, 2) is (I believe, note caveats) given
by the formula I gave. [And the background I gave probably tells you
what you could Google for - there's probably a Wikipedia article
covering it, I haven't checked.]
--
Christopher Dearlove
m...@nowhere.edu
wrote:
>In message <cihme3tl3b7knouni...@4ax.com>, m...@nowhere.edu
>writes
>>Howdy all,
>>
>>I've created a hex grid bitmap, and have assigned each hex a
>>coordinate exactly as portrayed on this page,
>>http://www.gamedev.net/reference/articles/article1800.asp and am now
>>trying to nail down the algorithm to determine the distance between
>>any two hexes when the coordinates are known.
>
>What kind of distance do you want to calculate? The two most likely
>possibilities are
>1.) The hex equivalent of "Manhattan distance", i.e. the number of
>"king's moves" it takes to get from one hex to another
>2.) The Euclidean distance between the centres of two hexes
>
>Nick
>
Distance as measured in the smallest number of hexes that would have
to be crossed to get from the first hex to the second.
Torben Ægidius Mogensen
> Howdy all,
>
> I've created a hex grid bitmap, and have assigned each hex a
> coordinate exactly as portrayed on this page,
> http://www.gamedev.net/reference/articles/article1800.asp and am now
> trying to nail down the algorithm to determine the distance between
> any two hexes when the coordinates are known.
I prefer a numbering where both x and y correspond to straight lines
of hexes, i.e., letting x increase (with constant y) by going right
and y increase (with constant x) by going 60 degrees down from right
(assuming (0,0) is top left corner).
This way, if you move in one of the three "natural" directions, you
either have constant x, constant y or constant (x+y).
That makes calculation of distances etc. easier, as you don't have to
sepcial-case on odd and even rows.
I assume you know the hex coordinates and want to find the distance in
number of hexes while moving across edges.
If you had used the alternative numbering I described above, the
distance is calculated as follows:
mydistance((x1,y1), (x2,y2))
= if x1>x2 then mydistance((x2,y2), (x1,y1))
else if y2>=y1 then x2-x1 + y2-y1
else max(x2-x1, y1-y2)
With the numbering shown on the webpage you sited, you can calculate
distance as follows:
yourdistance((x1,y1),(x2,y2))
= mydistance((x1 - y1 `div` 2,y1), (x2 - y2 `div` 2,y2))
I.e., convert to the simpler coordinate system and calculate distance
in that. You convert by subtracting half the y coordinate (rounded
down) from the x coordinate.
Torben
Stefano MAC:GREGOR
> I've created a hex grid bitmap, and have assigned each hex a
> coordinate exactly as portrayed on this page,
> http://www.gamedev.net/reference/articles/article1800.asp and am now
> trying to nail down the algorithm to determine the distance between
> any two hexes when the coordinates are known.
I worked this out a few decades ago, and I believe my answer was even
published in some gaming magazine - one of SPI's, as I recall.
To make it easier, I had non-staggering coördinates, so that with
coördinates of [x,y], all hexes with the same value of "y" were in the
same horizontal row, and all with the same value of "x" were in the
same diagonal row.
[0,0] [0,1] [0,2] [0,3] [0,4] [0,5]
[1,1] [1,2} [1,3] [1,4] [1,5] [1,6]
[2,1] [2,2] [2,3] [2,4] [2,5] [2,6]
[3,2] [3,3] [3,4] [3,5] [3,6] [3,7]
[4,2] [4,3] [4,4] [4,5] [4,6] [4,7]
[5,3] [5,4] [5,5] [5,6] [5,7] [5,6]
Now to calculate the hex-distance between two hexes, calculate the
difference between their x-coördinates, the difference between their y-
coördinates, and the difference between these two differences; take
the absolute value of each of these three numbers, and the distance is
the largest of these three values.
So -- for the distrance from [5,5] to [3,6], x = -2, y = 1, and the
difference between the two deltas is 3. The greatest of 2, 1, and 3
is three, and Bob's your uncle.
--
Steve
299,792,358 m/s -- it's not just a good idea; it's the LAW!