Find Adjacent Hexagon Tiles on Map Using X & Y Coordinates

Question

I've been searching hard to solve this one -- so I really must ask for help.

I've created a CSS based game map that overlays DIV's in the shape of Hexagon Tiles (like table top games). I'm trying to find which tiles are adjacent to the current active tile.

I've been able to generate the ID's of the map sequentially from top left to bottom right and assign coordinates to each of the tiles. From there I used the Pythagorean Theorem to calculate distance between the 2 X&Y Coords (this took me a while to figure out). Things are actually very close, but the problem is that because a hex tile map is essentially "staggered" (e.g. it's not a square grid and two adjacent tiles are not on the same exact horizontal line), when I calculate distance, a few tiles that are actually 2 steps away, math out to closer than a tile just adjacent.

I've put up a demo of what I built so you can see exactly what I'm talking about.

http://www.pitashi.com/map/index.php

If you click on any tile, it will refresh the page and put a flag on your "current location". Then each of the tiles displays the coordinates and the calculated distance from the current location. If you click around, you'll see that many of the tiles that don't border the current location are closer in distance.

CODE:

// load the map DIV tags (90 tiles)

if (isset($_GET['x'])) {
    $gl_map_x = $_GET['x'];
} else $gl_map_x = 0;

if (isset($_GET['y'])) {
    $gl_map_y = $_GET['y'];
} else $gl_map_y = 0;

if (isset($_GET['mapid'])) {
    $gl_map_id = $_GET['mapid'];
} else $gl_map_id = 42;                         

$i = 1;
$x = 0;
$y = 0;
while ($i <= 90) {
echo "<div class='hexagon hexagon" . $i . "' onclick=\"window.location=('index.php?mapid=". $i . "&x=" . $x . "&y=" . $y . "')\"><div class='hexagon-in1'>";
    echo "<div class='hexagon-in2'>";
        if ($i == $gl_map_id) { 
            echo "<img class='hexstar" . $i . "' src='images/map_star1.png' />";
        } 

        $distance = round(sqrt(pow($gl_map_x - $x, 2) + pow($gl_map_y - $y, 2)), 2);                                        
        echo "<div style='color:#ffffff; padding-left:48px; padding-top:30px;'>" . $x . ", " . $y . "<br />" . $distance . "</div>";
        //echo "<div style='color:#ffffff; font-weight:bold; padding-left:48px; padding-top:30px;'>" . $distance . "</div>";
        //echo "<div style='color:#ffffff; padding-left:48px; padding-top:30px;'>" . $i . "</div>";                                         

    echo "</div></div></div>";
    $i++;
    $x = $x + 63;
        if ($x > 756) { 
            $x = 63;
            $y = $y + 54;
        } elseif ($y == 432) {
            $x = $x + 63;
        }
}

?>  

---

I know there must be some additional math I need to use to compensate for the staggering of the tiles, but I'm way out of my pay grade on this one. But this functionality is essential to my little RPG game.

Any suggestions?

Answer 1

It's a bit difficult to explain without a sketch, but the solution is fairly simple, I think. The x coordinates of the hexagons are OK but half of the y coordinates need correcting. When I clicked on the link above, the marked hexagon had the coordinates x= 315, y=162. The y coordinate of all cells in this column need to be increased by 27. Thus instead of 162 the y coordinate should be 189. For the cell directly above, the y coord. should be changed from 108 to 135. Above that cell increase the y coord. from 54 to 81, and so on. This change needs to be made for every second column, i.e. for all the columns which have hexagons at exactly the same height as the one we've just been talking about. If you make this change, the Pythagoras calculation lets you test for the adjacent cells, because it will yield the distance between the centres of the hexagons. Hope that helps. Good luck with your game.

Answer 2

You can use the Euclidean distance in the XY plane.

The distance between two pounts P1(x1, y1) and P2(x2, y2) is given by:

sqrt( (y1-x1)^2 + (y2-x2)^2 )

If you don't care about the actual distance, but just about the closest points, you shouldn't take the square root, but rather use just:

(y1-x1)^2 + (y2-x2)^2

This is faster and more accurate as it's an integer expression (rather than floating point).

Answer 3

You're goin about it the wrong way, conceptualize the board as a series of columns running down the page.

{[0][0], NULL , [2][0]}
{ NULL ,[1][1],  NULL }
{[0][1], NULL , [2][1]}
{ NULL ,[1][2],  NULL }
{[0][2], NULL , [2][2]}
{ NULL ,[1][3],  NULL }
//The nulls are just to make it clearer feel free to optimize.

So clearly we have a starggered 2D array of spaces padded with NULLs to represent the staggering, if we wanted to get the sapces adjacent to [0][2], we would know they are

[0,1],[1,1],[2,1],[0,2],[2,2],[1,3]