I’ve been wanting to do a game with a hexagonal based map for a while now. Something where the world is persistent and changes in that world are meaningful. I mentioned this to a friend and pointed to a game called CyberStorm that had similar map mechanics. It’s a BattleTech clone written by Sierra back in the 90′s, which we both thoroughly enjoyed playing as a pencil & paper game. After some discussion we agreed to a collaboration. I’m not an expert and I’ve never looked into how to do hexagonal maps or what’s involved, so this will be a record of my journey into the unknown world of hexagonal mapping.
[Shiny Things]
As geeky as this is to admit, I really like the symmetry of hexagonal shapes. I do chainmaille as a hobby and several of my favourite weaves are 6-in-1 European and 12-in-2 Japanese.
12-in-2 Hexagonal Weave by Sara Richardson
(I’m also a big fan of Fieldstone, which are 3 parallel rings interlocked with a second set of 3 parallel rings with a dihedral angle of 90°).
Interestingly, the image demonstrates the relationship between hexagonal shapes and circles, and is called circle packing. A hexagon is the densest arrangement of equal sized circles on a 2-dimensional plane. Each cell is connected to other cells by links in increments of 60°. The above picture also foreshadows some additional features our hexagonal map will require, as represented by the purple rings. More on that in a moment.
[Hextille. Rhymes with style or steel?]
The first thing to define is what a grid is. In the context of a game, a grid generally represents a logical arrangement and subdivision of a playing field, and each individual location on a grid is known as a tile. Take, for example, a chessboard. The board itself is broken up into an 8×8 grid of individual tiles.
2D Chessboard (left); 3D Chessboard by Ji Lee (right)
A group of tiles is called a grid and a group of hexagonal tiles is called a hextille. I’m still unsure if it rhymes with “style” or “steel”, and it’s printed as both “hextille” and “hextile” on Wikipedia.
Even though they look different, the board on the left and the board on the right can be represented by the same data structure. Only the visualization of the data would need the additional information of height, which can be stored separately. From a programming perspective, this sort of grid can be easily represented by a 1- or 2-dimensional array, with the latter being more common.
Ok, so you could use an array to represent the grid. But, an array of what? For a grid as basic as chess or checkers, you might store what piece is present as an integer. That information is contained to a single tile, and it would be the equivalent of the larger chrome coloured rings above.
But what if you need to store more information? E.g., a maze where moving into some adjacent squares isn’t allowed, or there is some sort of cost associated with moving onto another tile. This sort of information would be akin to the purple rings in the chainmaille example above. The information is only relevant if there is an adjacent tile. We’ll need some sort of record that holds all the relevant information. In graph theory, that sort of record is called a node. Since we’re working with hexagonal shapes, naming it HexNode seems apt.
[Pointy Side Up]
If you are looking from above on a normal rectangular grid then each tile will have 4 adjacent neighbors (one every 90°) in the directions of left, right, down, and up. When dealing with a hextille, you end up being able to move in 6 directions (every 60°): upper-left, upper-right, lower-left, lower-right, and… well, now you have two options. You can either orient the map so you get up/down, or left/right (henceforth known as “pointy side up”). The orientation may not make much difference to an observer of the grid, as they are simply the same thing rotated 90°. However, it somewhat does matter internally because it may affect things like naming and the coordinate system.
Hextille with Left/Right (left); Hextille with Up/Down (right)
It may also matter depending on how you store each node. If you were using an array, the map with the pointy side up would make more logical sense, since it’s almost the equivalent of a rectangular array with every other row shifted by 1/2 of a unit. I’ve opted for the pointy side up version for a couple of reasons. One is because it reminds me of Q*Bert. The other is because of where (0,0) is.
[Where Am I?]
So far we know that hexagons have a close relationship to circles. So, if you needed to decide where the origin of a circle would be, what would be the logical choice? The center.
Hexagonal Coordinates from Overhead (left); Right-handed Cartesian Coordinate System (right)
The image on the left (original concept was from Juha-Mikko’s blog) places the origin in the center and shows the X- and Y-axis. Placing the origin in the center does several things to the implementation of the maps. The first is to make the maps definable by a radius. The second is the need to use an implementation that doesn’t mind negative coordinates. If you were using an array (or, specifically a jagged array), you would need to do some sort of translation from hextille coordinates to array coordinates. There’s actually an elegant solution for the negative array coordinates problem that doesn’t involve shooting yourself in the foot. Obviously using pascal (with its definable array subscript ranges) would be a solution, but I’m going to be writing this in C#. I’ll get to the actual implementation in the next post.
As for the axes, we’re using a right-handed coordinate system. The X value increases as you travel down and left. The Y value increases as you travel down and right. If we’re working with 3d points, the Z value would increase as you come towards the viewer. This is somewhat arbitrary and left up to personal preference.
[Plan For Today, Prepare For Tomorrow]
It is common knowledge that one should start small and work up. Well-designed software rarely congeals into existence after an evening of hacking it together. At this point I have a rough starting point with which to put something together and experiment with it. While hindsight is 20/20, I’m writing this without that luxury. So, I need to think ahead.
Here’s a list of items that I think I’ll need at some point in the future:
- Saving to disk (serialization)
- Flexible data nodes for future projects
- Path traversal including movement costs
- Gluing hextilles together
- Stacking hextilles on top of each other (layers)
- Higher resolution coordinates for movement within an individual cell
- The ability to iterate over each node
Of all those, only the last two are tricky. With all this in mind, I’ll cover implementation as I go along starting in the next post.
[Summary]
Chainmaille is shiny. Hexagons are a dense packing of circles. Rectangular packing of tiles is called a grid. Hexagonal packing of tiles is called a hextille. Only store needed info. Pointy side is up. Origin is in the middle. No need to use arrays. Think ahead.
[References]
http://en.wikipedia.org/wiki/Circle_packing
http://pleaseenjoy.com/project.php?cat=1&subcat=&pid=16
http://en.wikipedia.org/wiki/Hexagonal_tiling
http://www-cs-students.stanford.edu/~amitp/Articles/HexLOS.html
http://jmz.iki.fi/blog/programming/hexagonal_maps (Dead link at the time of this writing)
http://www.dev102.com/2008/11/10/10-ways-to-shoot-yourself-in-the-foot-part-a/
Recent Comments