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
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;

Image

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
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 :D 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 :D
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 :D 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!!! :D

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
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.