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. =)
In message <cihme3tl3b7knounivjrfhksoi6shn4...@4ax.com>, m...@nowhere.edu 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, ...)
In message <cihme3tl3b7knounivjrfhksoi6shn4...@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
>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. =)
In message <fSGV$asVO+6GF...@maproom.demon.co.uk>, Nick Wedd <n...@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.]
>In message <cihme3tl3b7knounivjrfhksoi6shn4...@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.
>>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. =)
> 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:
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.
> 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.
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!
>> 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:
>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.
