Calculating distance between hexagons on a grid

PHP programming forum. Ask questions or help people concerning PHP code. Don't understand a function? Need help implementing a class? Don't understand a class? Here is where to ask. Remember to do your homework!

Moderator: General Moderators

Post Reply
ivargu77
Forum Newbie
Posts: 7
Joined: Wed Dec 07, 2011 9:27 am

Calculating distance between hexagons on a grid

Post 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 997 times
Best regards, Ivar
ivargu77
Forum Newbie
Posts: 7
Joined: Wed Dec 07, 2011 9:27 am

Re: Calculating distance between hexagons on a grid

Post 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;
}
maxx99
Forum Contributor
Posts: 142
Joined: Mon Nov 21, 2011 3:40 am

Re: Calculating distance between hexagons on a grid

Post 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
ivargu77
Forum Newbie
Posts: 7
Joined: Wed Dec 07, 2011 9:27 am

Re: Calculating distance between hexagons on a grid

Post 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
maxx99
Forum Contributor
Posts: 142
Joined: Mon Nov 21, 2011 3:40 am

Re: Calculating distance between hexagons on a grid

Post 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
maxx99
Forum Contributor
Posts: 142
Joined: Mon Nov 21, 2011 3:40 am

Re: Calculating distance between hexagons on a grid

Post 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
ivargu77
Forum Newbie
Posts: 7
Joined: Wed Dec 07, 2011 9:27 am

Re: Calculating distance between hexagons on a grid

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

}
maxx99
Forum Contributor
Posts: 142
Joined: Mon Nov 21, 2011 3:40 am

Re: Calculating distance between hexagons on a grid

Post by maxx99 »

Great!!! :D
ivargu77
Forum Newbie
Posts: 7
Joined: Wed Dec 07, 2011 9:27 am

Re: Calculating distance between hexagons on a grid

Post 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
maxx99
Forum Contributor
Posts: 142
Joined: Mon Nov 21, 2011 3:40 am

Re: Calculating distance between hexagons on a grid

Post by maxx99 »

Just to be clear by visibility you mean this?
Attachments
hex_vis.png
hex_vis.png (25.28 KiB) Viewed 937 times
ivargu77
Forum Newbie
Posts: 7
Joined: Wed Dec 07, 2011 9:27 am

Re: Calculating distance between hexagons on a grid

Post by ivargu77 »

Correct, that is exactly what I mean
maxx99
Forum Contributor
Posts: 142
Joined: Mon Nov 21, 2011 3:40 am

Re: Calculating distance between hexagons on a grid

Post by maxx99 »

And is 1,1 in line with 5,1 ?
ivargu77
Forum Newbie
Posts: 7
Joined: Wed Dec 07, 2011 9:27 am

Re: Calculating distance between hexagons on a grid

Post by ivargu77 »

Ah, no. More in line with this:
hexgrid-los.jpg
hexgrid-los.jpg (13.87 KiB) Viewed 932 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
maxx99
Forum Contributor
Posts: 142
Joined: Mon Nov 21, 2011 3:40 am

Re: Calculating distance between hexagons on a grid

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