# looking for a hexagon tiling module

#### Do you have a question? Post it now! No Registration Necessary.  Now with pictures!

•  Subject
• Author
• Posted on
I'd like a module to manipulate co-ordinates on an X,Y plane that
have an overlapping hexagon grid. Consider, for example, a game
that uses a hexagonal grid to move around. Chinese Checkers (star
halma) is one such game. You would want functions to turn a mouse
click into a hexagon tile id of some sort, and you'd want functions
to calculate how to draw the tiles if the side is S pixels, or
if you want to fit N tiles across on a M wide field.

I don't want to implement a game, I do want to be able to divide a
pixel plane into hexagons, calculate which pixels would be interior,
which pixels would be a border, know which hexagons are complete
and which are clipped. I don't want something that is tied to a
particular drawing system, because it probably won't be the one I
want to use.

Functions of that nature must be fairly common, but I'm not seeing
any on CPAN.

I've looked at

Math::Polygon -- handles single polygons, not tilings

Math::PlanePath -- handles many things, but not hexagonal tilings

Games::Maze::SVG::HexCells -- specifically tied to SVG objects

Gtk2::Hexgrid -- specifically tied to Gtk2 images

As an example, here's this bit of ASCII art I must have spent
all of five minutes on. The hexagonal tiles are numbered with
example coordinates. There is a image area superimposed upon
this grid with a border of : + and =. The upper left hand corner
is about one quarter of the 0,0 hex grid. Cell 1,2 is the upper-
most, leftmost full hexagon, cell 1,1 is the leftmost, upper-
most full hexagon. 12 characters right and 16 down from the +
in the image corner is the * in cell 3,2. 18 characters right
and 5 down from the + is the L on the border of 0,3 and 1,3.

___         ___         ___         ___
/   \       /   \       /   \       /   \
/     \     /     \     /     \     /     \
/  0,0  \___/  0,2  \___/  0,4  \___/  0,6  \_
\   +===/===\=======/===\=======/===\=======/=
\  :  /     \     /     \     /     \     /
\_:_/  0,1  \___/  0,3  \___/  0,5  \___/
/ : \       /   \       /   \       /   \
/  :  \     /     \     /     \     /     \
/  1,0  \___/  1,2  \_L_/  1,4  \___/  1,6  \_
\   :   /   \       /   \       /   \       /
\  :  /     \     /     \     /     \     /
\_:_/  1,1  \___/  1,3  \___/  1,5  \___/
/ : \       /   \       /   \       /   \
/  :  \     /     \     /     \     /     \
/  2,0  \___/  2,2  \___/  2,4  \___/  2,6  \_
\   :   /   \       /   \       /   \       /
\  :  /     \     /     \     /     \     /
\_:_/  2,1  \___/  2,3  \___/  2,5  \___/
/ : \       /   \       /   \       /   \
/  :  \     /  *  \     /     \     /     \
/  3,0  \___/  3,2  \___/  3,4  \___/  2,6  \_
\   :   /   \       /   \       /   \       /
\  :  /     \     /     \     /     \     /
\_:_/  3,1  \___/  3,3  \___/  3,5  \___/
/ : \       /   \       /   \       /   \

I want the functions to be able to work that stuff out.
Does it exist currently?

Elijah
------
and for bonus points the hexgrid should be able to have a different rotation

## Re: looking for a hexagon tiling module

OK,as a sometime game programmer...

A hex grid is conceptually the same as an overlapping set of rectangles - it
maps to the layout of the bricks in a wall for eg.

Maintain:

Each object as hex-grid-location and state (as complex as required.)
A lookup table of state renderings
(either all-possible or as generated and preserved.)
A pre-screen image one hex too big in each margin.

A lookup table of renderings for any set of seven can be xor-mapped to any
position.  This might involve pre-rendering stages too - awaiting, eg,
lighting modifications.

Snapshot the screen display from the pre-screen at the desired origin.
Most likely you'll have a trade-off between hardware blitting and software,
often both are implemented giving a first class display on capable hardware
and lower res on the rest.

A pure perl blitter is unlikely to be adequate on uncontrolled end-user
machines.

This is very much video game programmimg 101.

And rather hardware dependent so not the sort of stuff that I'd expect to
see on CPAN.

Cheerio,

--

## Re: looking for a hexagon tiling module

[...]

I took that as a challenge for a bit of weekend programming ;-)

It doesn't do everything you want (must leave some of the fun to you)
but it should get you started:

package Math::HexGrid;

use warnings;
use strict;
use 5.010;
use POSIX qw(floor);

our \$VERSION = 0.001;

sub new {
my (\$class, \$s, \$h) = @_;

# \$s is the length of a side of a cell,
# \$h is the height of half a cell.
#    we can compute that from \$s or let the user specify it.
\$h = int(\$s * sqrt(3) / 2) unless defined \$h;
my \$self = { s => \$s, h => \$h };
bless \$self, \$class;
return \$self;
}

sub center_of_hex {
my (\$self, \$ind_x, \$ind_y) = @_;

my (\$s, \$h) = @{'s', 'h'};
my (\$px_x, \$px_y);

# That's simple. The horizontal differenc between the center of
# (0,0) and (0,2) is obviously 3 * \$s. (0,1) sits between them
# but is offset by \$h in the y axis.
if (\$ind_x % 2 == 0) {
\$px_x = \$ind_x * 3/2 * \$s;
\$px_y = \$ind_y * 2 * \$h;
} else {
\$px_x = \$ind_x * 3/2 * \$s;
\$px_y = (\$ind_y * 2 + 1) * \$h;
}
return (\$px_x, \$px_y);
}

sub hex_from_coord {
my (\$self, \$px_x, \$px_y) = @_;

my (\$s, \$h) = @{'s', 'h'};

# Not quite as simple, but if you squint a bit
# you can see that the pattern repeats every
# 3 * \$s horizontally and every 2 * \$h vertically.
# so we split the plane into rectangles of this size
my \$seg_x = floor(\$px_x / (3 * \$s));
my \$seg_y = floor(\$px_y / (2 * \$h));
my \$rel_x = \$px_x - \$seg_x * 3 * \$s;
my \$rel_y = \$px_y - \$seg_y * 2 * \$h;

my (\$ind_x, \$ind_y);

# and then we split those rectangles into vertical stripes
# again.
# Everything between +/- 0.5 \$s horizontally from the center of a
# cell belongs to that cell.
# but between that the cells overlap and we have to check on which
# side of the diagonals the pixel is.
given (\$rel_x) {
when (\$_ < 0.5 * \$s) {
\$ind_x = \$seg_x * 2;
\$ind_y = \$seg_y + (\$rel_y >= \$h);
}
when (\$_ < 1 * \$s) {
my \$r_x = (\$_ - \$s / 2) / (\$s / 2);
my \$r_y = abs((\$rel_y - \$h) / \$h);
if (\$r_y < \$r_x) {
\$ind_x = \$seg_x * 2 + 1;
\$ind_y = \$seg_y;
} else {
\$ind_x = \$seg_x * 2;
\$ind_y = \$seg_y + (\$rel_y >= \$h);
}
}
when (\$_ < 2 * \$s) {
\$ind_x = \$seg_x * 2 + 1;
\$ind_y = \$seg_y;
}
when (\$_ < 2.5 * \$s) {
my \$r_x = (2.5 * \$s - \$_) / (\$s / 2);
my \$r_y = abs((\$rel_y - \$h) / \$h);
if (\$r_y < \$r_x) {
\$ind_x = \$seg_x * 2 + 1;
\$ind_y = \$seg_y;
} else {
\$ind_x = \$seg_x * 2 + 2;
\$ind_y = \$seg_y + (\$rel_y >= \$h);
}
}
when (\$_ < 3 * \$s) {
\$ind_x = \$seg_x * 2 + 2;
\$ind_y = \$seg_y + (\$rel_y >= \$h);
}
}
return (\$ind_x, \$ind_y);

}

1;

hp

PS: I did see Derek's posting just before posting this, but afaics he
concentrates on rendering graphics while my code does just geometry, no
graphics at all (although I've also written a small test script to
create a PNG with hex-tiles).

--
_  | Peter J. Holzer    | Deprecating human carelessness and
|_|_) | Sysadmin WSR       | ignorance has no successful track record.
| |   | hjp@hjp.at         |
__/   | http://www.hjp.at/ |  -- Bill Code on asrg@irtf.org

## Re: looking for a hexagon tiling module

I've actually done the basic math to generate this using Cairo:

http://mvdwege.wordpress.com/2011/07/07/math-for-fun /

I still have to work out the rest of the code to really generate maps,
and my final usage scenario is different from yours, but hopefully it's
useful.

Regards,

Mart

--
"We will need a longer wall when the revolution comes."
--- AJS, quoting an uncertain source.