# 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

Noted.

Oh, I got started, but I started from a different angle than

I translated some C sharp code I found to create hexagons and
hexagon grids, but I'm not happy with that guy's inside-polygon
function.

Code I found:
http://www.codeproject.com/Articles/14948/Hexagonal-grid-for-games-and-other-projects-Part-1

(Note that I'm using floating point coordinates.)

# basic math

sub degtorad { my \$deg = shift; return (\$deg * \$pi / 180); }
sub round5p  { my \$num = shift; return sprintf('%0.5f', \$num); }

# Consider hexagon with side 's':
# a is distance between two parallel sides,
# b is distance between two opposite vertices.
#
#        __ b __
#       /       \
#    . :   ___. h:
#   /     /   \   \
#  |     /     \   r    a = 2*r        total height
#  a    /       \./     b = 2*h + s    total width
#  |    \       /
#  |     \     /
#   \.    \___/
#          . .
#           s
sub hfroms   { my \$s = shift; return (\$sin30 * \$s); }
sub rfroms   { my \$s = shift; return (\$cos30 * \$s); }
sub bfroms   { my \$s = shift; return (2 * hfroms(\$s) + \$s); }
sub bfromsh  { my \$s = shift; my \$h = shift; return (2 * \$h + \$s); }
sub afroms   { my \$s = shift; return (2 * rfroms(\$s)); }
sub afromr   { my \$r = shift; return (2 * \$r); }

# Two hexagon orientations:
#       0 ___ 1             0
#        /   \             ,'',
#       /     \        5 ,'    ', 1
#    5 /  flat \         |      |
#      \       / 2       |pointy|
#       \     /        4 ',    ,' 2
#        \___/             ',,'
#       4    3              3

sub pt_f_upperleft   { return 0; }
sub pt_p_top         { return 0; }
sub pt_f_upperright  { return 1; }
sub pt_p_upperright  { return 1; }
sub pt_f_middleright { return 2; }
sub pt_p_bottomright { return 2; }
sub pt_f_bottomright { return 3; }
sub pt_p_bottom      { return 3; }
sub pt_f_bottomleft  { return 4; }
sub pt_p_bottomleft  { return 4; }
sub pt_f_middleleft  { return 5; }
sub pt_p_upperleft   { return 5; }

# From a side length and a single starting point, work out where
# the other points are.

# HexagonalTest/HexagonalTest/Hexagonal/Hex.cs: Hex
sub calc_vertices {
my \$s = shift;    # length of side
my \$p0_x   = shift;    # x location of point #0
my \$p0_y   = shift;    # y location of point #0
my \$orient = shift;    # 'flat' or 'pointy'

my @points;

my \$h = hfroms(\$s);
my \$r = rfroms(\$s);

push(@points, [\$p0_x, \$p0_y]);            # point 0

if(defined(\$orient) and lc(\$orient) eq 'flat') {
# flat
push(@points, [(\$p0_x + \$s), \$p0_y]);        # point 1
push(@points, [(\$p0_x + \$s + \$h), (\$p0_y + \$r)]);    # point 2
push(@points, [(\$p0_x + \$s), (\$p0_y + 2 * \$r)]);    # point 3
push(@points, [\$p0_x, (\$p0_y + 2 * \$r)]);        # point 4
push(@points, [(\$p0_x - \$h), (\$p0_y + \$r)]);    # point 5
} else {
# pointy
push(@points, [(\$p0_x + \$r), (\$p0_y + \$h)]);    # point 1
push(@points, [(\$p0_x + \$r), (\$p0_y + \$s + \$h)]);    # point 2
push(@points, [\$p0_x, (\$p0_y + \$s + 2 * \$h)]);    # point 3
push(@points, [(\$p0_x - \$r), (\$p0_y + \$s + \$h)]);    # point 4
push(@points, [(\$p0_x - \$r), (\$p0_y + \$h)]);    # point 5
}

return @points;
} # end &calc_vertices

# HexagonalTest/HexagonalTest/Hexagonal/Board.cs: Initialize
sub hex_board {
my \$bs    = shift; # hash ref
my @hexes;

# TODO: allow pixelwidth and pixelheight, then set gridwidth and gridheight
if(!defined(\$\$bs))   { die "hex_board need gridwidth\n"; }
if(!defined(\$\$bs))  { die "hex_board need gridheight\n"; }

if(!defined(\$\$bs))        { die "hex_board need side\n"; }
if(!defined(\$\$bs))      { die "hex_board need orient\n"; }
if(!defined(\$\$bs))     { die "hex_board need xoffset\n"; }
if(!defined(\$\$bs))     { die "hex_board need yoffset\n"; }

my \$h = hfroms(\$\$bs);
my \$r = rfroms(\$\$bs);

my \$hexwidth;
my \$hexheight;
my \$isflat = undef;

if( \$\$bs eq 'flat' ) {
\$isflat = 1;

\$hexwidth  = \$\$bs + \$h;
\$hexheight = 2 * \$r;

\$\$bs  = \$\$bs  * \$hexwidth  + \$h;
\$\$bs = \$\$bs * \$hexheight + \$r;
} else {
\$hexwidth  = 2 * \$r;
\$hexheight = \$\$bs + \$h;

\$\$bs  = \$\$bs  * \$hexwidth  + \$r;
\$\$bs = \$\$bs * \$hexheight + \$h;
}

print STDERR "\$\$bs \$\$bs \$\$bs unit cells is
\$\$bs wide\n";
print STDERR "\$\$bs \$\$bs \$\$bs unit cells is
\$\$bs tall\n";
my %where = (
inTopRow => undef,
inBottomRow => undef,
inLeftColumn => undef,
inRightColumn => undef,
isTopLeft => undef,
isTopRight => undef,
isBotomLeft => undef,
isBottomRight => undef,
);

# i = y coord (rows), j = x coord (columns) of the hex tiles 2D plane
my \$i;
my \$j;
my \$ij_x;
my \$ij_y;
my \$refhex;

for (\$i = 0; \$i < \$\$bs ; \$i ++) {
if(\$i == 0) {
\$where = 1;
} else {
\$where = 0;
}

if(\$i == (\$\$bs - 1)) {
\$where = 1;
} else {
\$where = 0;
}

for (\$j = 0; \$j < \$\$bs ; \$j ++) {

# not sure why orig code set these first three
\$where = \$where = \$where =
\$where = \$where = \$where =  0;

if(\$j == 0) {
\$where = 1;
if(\$where) {
\$where = 1;
}

if(\$where) {
\$where = 1;
}
}

if(\$j == (\$\$bs - 1)) {
\$where = 1;
if(\$where) {
\$where = 1;
}

if(\$where) {
\$where = 1;
}
}

if(\$where) {
if(\$isflat) {
\$ij_x = \$h + \$\$bs;
\$ij_y =      \$\$bs;
} else {
# pointy
\$ij_x = \$r + \$\$bs;
\$ij_y =      \$\$bs;
}
} else {
# not top left

if(\$isflat) {
if(\$where) {
# calc from above
\$refhex = \$hexes[\$i - 1][\$j];
(\$ij_x, \$ij_y) = @;
} else {
# not left column

# calc from left, with staggered columns
\$refhex = \$hexes[\$i][\$j - 1];

if(\$j % 2) {
(\$ij_x, \$ij_y) = @;
} else {
(\$ij_x, \$ij_y) = @;
\$ij_x += \$h;
\$ij_y -= \$r;
}
}
} else {
# pointy
if(\$where) {
# calc from above, with staggered columns
\$refhex = \$hexes[\$i - 1][\$j];

if(\$i % 2) {
(\$ij_x, \$ij_y) = @;
} else {
(\$ij_x, \$ij_y) = @;
}
} else {
# not left column
# calc from left
\$refhex = \$hexes[\$i][\$j - 1];

(\$ij_x, \$ij_y) = @;
\$ij_x += \$r;
\$ij_y -= \$h;
}
}
}

push(@,
calc_vertices(\$\$bs, \$ij_x, \$ij_y, \$\$bs));
} # for j
} # for i

return @hexes;
} # end &hex_board

The InsidePolygon he has comes from
http://local.wasp.uwa.edu.au/~pbourke/geometry/insidepoly /
And is based on "Solution 1 (2D)" there. But the solution 3, for
convex polygons only, looks nicer to me. For one thing it distinguishes
inside, outside, and right on the edge.

My next directions after an inside polygon function will be finding
the center point of a cell (easy) and then finding the vertices of
a different sized cell on that same center point (not tough). That's
the direction I was going to head into for finding cell wall margins.

Elijah
------
the author of that hex code doesn't do very good ASCII art diagrams

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