Page 1 of 1
Calculating distance between hexagons on a grid
Posted: Wed Dec 07, 2011 9:31 am
by ivargu77
Hi all.
I have been cracking my brain to try to make this work without any luck. Hopefully there is a helpful soul out there who has a solution for this.
I am trying to calculate the distance (in king's moves) between two hexagons on a grid, but am getting some offsetting errors where some hexes are one distance off. I know it has to do with how my axis are defined but I can't figure out how to solve this. Can anyone help?
This is how the coordinates (x,y) are defined in the data I have:

- hexgrid.jpg (13.93 KiB) Viewed 998 times
Best regards, Ivar
Re: Calculating distance between hexagons on a grid
Posted: Wed Dec 07, 2011 9:35 am
by ivargu77
Whoops forgot my non-perfect code. The function I am using looks like this, and works only partly, it gives errors which I believe relate to how the y-value zig-zags on the x-axis.
Code: Select all
function distance( $hex1, $hex2 ){
$disx = $hex2->x - $hex1->x;
$disy = $hex2->y - $hex1->y;
$absx = abs($disx);
$absy = abs($disy);
if( $absx == 0 ) $distance = $absy;
else{
$distance = max(Array($absx,$absy));
}
return $distance;
}
Re: Calculating distance between hexagons on a grid
Posted: Wed Dec 07, 2011 1:05 pm
by maxx99
Grid setup you've provided didn't work for me

it should do a trick for yours too with some adjustments
Code: Select all
$startx = 1;
$starty = 1;
$endx = 3;// always > $startx, switch places otherwise
$endy = 0;
if ($endy > $starty) $d = $endx-$startx+$endy-$starty;
else if($startx+$starty>$endx+$endy) $d = $starty-$endy;
else $d = $endx - $startx;
echo $d;

Re: Calculating distance between hexagons on a grid
Posted: Thu Dec 08, 2011 4:20 am
by ivargu77
Thanks alot for your reply maxx99. I appreciate it.
I can do the calculations based on a grid that is laid out the way yours is, but run into problems with mine due to the zig-zag-ing of the y-coordinate (See comparison below). I have been working to try to get a code similar to yours to work for my layout for quite awhile but am stumped. If anyone out there has an idea I would really appreciate any hints.
Comparison of grid layouts

- maxx99's on the left, mine on the right
Best regards from frozen Iceland,
Ivar
Re: Calculating distance between hexagons on a grid
Posted: Thu Dec 08, 2011 4:39 am
by maxx99
Hi Ivar,
I forgot to draw X,Y axes - which were the whole point

thanks. I have an idea in mind for your layout which I'll try it asap
Best regards
Re: Calculating distance between hexagons on a grid
Posted: Thu Dec 08, 2011 4:50 am
by maxx99
Hi

Check if that works out for you.
I've tried it walking right, like last time you'll need to switch points to make it walk right.
Sorry for "while" loop. It was easier for me

Notice first if, only in case when X coord is even you can step out of zig-zag and do X++ and Y++ in one step.
Code: Select all
$startx = 1;
$starty = 1;
$endx = 2;
$endy = 2;
$path = 0;
$limit = 0;
while(($startx != $endx && $starty != $endy) || $limit<50){
if($startx<$endx && $starty < $endy && $startx%2==0){
$startx++;
$starty++;
$path++;
}
else if($startx<$endx){
$startx++;
$path++;
}
else if($starty<$endy){
$starty++;
$path++;
}
$limit++;
}
echo 'For path: ' . ($path);
I've added $limit-er just in case

I've tested it with:
1,1 to 5,1
1,1 to 2,2
1,3 to 3,3
1,3 to 5,1
Re: Calculating distance between hexagons on a grid
Posted: Thu Dec 08, 2011 8:18 am
by ivargu77
Again thanks for your help maxx99. That did the trick

Following is my modified version of your code that I have tested in all directions and is working properly. I owe you one
Code: Select all
function distance( $hex1, $hex2 ){
// walk there version
if( $hex1->x <= $hex2->x ){
$startx = $hex1->x;
$starty = $hex1->y;
$endx = $hex2->x;
$endy = $hex2->y;
}
else{
$startx = $hex2->x;
$starty = $hex2->y;
$endx = $hex1->x;
$endy = $hex1->y;
}
echo "[initial: $startx, $starty - $endx, $endy]<br>";
$steps = 0;
$counter = 0;
$audit = null;
while( ($startx != $endx || $starty != $endy) && $counter < 10){
$counter++;
echo "[$startx , $starty] to ";
if( $startx == $endx ){
if( $endy < $starty){
$starty--;
$steps++;
}
else{
$starty++;
$steps++;
}
}
else if( $endy < $starty ){
//we're going ne
if( $startx %2 == 0 ){
//it's even
$startx++;
$steps++;
}
else{
//it's odd
$startx++;
$starty--;
$steps++;
}
}
else if( $endy > $starty ){
//we're going se
if( $startx %2 == 0 ){
//it's even
$startx++;
$starty++;
$steps++;
}
else{
//it's odd
$startx++;
$steps++;
}
}
else if( $endy == $starty ){
//we're at matching y
$startx++;
$steps++;
}
echo "[$startx , $starty] <br> ";
}
return $steps;
}
Re: Calculating distance between hexagons on a grid
Posted: Thu Dec 08, 2011 9:17 am
by maxx99
Great!!!

Re: Calculating distance between hexagons on a grid
Posted: Thu Dec 08, 2011 3:22 pm
by ivargu77
OK, now that problem has been solved, and I am able to properly calculate distances across the map. I am now looking at ways to determine line of sight, that is, what other hexagons a straight line from hex A to hex B would intersect.
I have seen a lot of references to Bresenham's line, but again fear I will have problems with the zig-zag nature of my coordinate layout. Is anyone out there who has an idea how I could accomplish this.
Regards, Ivar
Re: Calculating distance between hexagons on a grid
Posted: Fri Dec 09, 2011 2:06 am
by maxx99
Just to be clear by visibility you mean this?
Re: Calculating distance between hexagons on a grid
Posted: Fri Dec 09, 2011 3:23 am
by ivargu77
Correct, that is exactly what I mean
Re: Calculating distance between hexagons on a grid
Posted: Fri Dec 09, 2011 4:17 am
by maxx99
And is 1,1 in line with 5,1 ?
Re: Calculating distance between hexagons on a grid
Posted: Fri Dec 09, 2011 4:26 am
by ivargu77
Ah, no. More in line with this:

- hexgrid-los.jpg (13.87 KiB) Viewed 933 times
If I draw a straight line from 1,3 to 6,1, which hexagons does it intersect or come in contact with on the way there. I want to do this in order to be able to calculate whether something standing in 1,3 could see something standing in 6,1. To do that I need to know what hexagons the line of sight would cross in order to check if any of them might contain an obstacle that would block the view.
Hope this clarifies.
Regards again,
Ivar
Re: Calculating distance between hexagons on a grid
Posted: Fri Dec 09, 2011 7:35 am
by maxx99
Well, if you want to know which of the hex-es are standing in the way (in straight line), my idea would be to go full mathematic on it

Transform your grid to XY catrtesian coordinates (e.g. central points of every hex) then interpolate on start - end. Check distance between nearest (diagonal length of single hex) points to your linear function.