Lately I’ve been getting back to work on an Android game that I began not too long ago.  The original purpose of the project was to get to know the Android platform through hands on experience and what better way to do that than to jump right in and design a game.  I’ve always loved playing all sorts of strategy games, so naturally I decided to create a simple turn based game that allows players to move and engage other units on a map.  Due to my goals with regard to actual game dynamics a hex grid made more sense than a regular square grid.

Advantages of the hex grid include:
•    Constant distance between the centers of adjacent cells
•    Uniform edge sharing between neighbors
•    Simplified unit movement
•    Looks cool

Implementation of the hex grid started with a few choices and involved some interesting geometry algorithms and approaches.

What type of coordinates should be used?
There are many options for coordinate systems – typical cartesian coordinates, 2 dimensional coordinates in the x,y planes where the y plane is set diagonally or coordinates in 3 dimensions (x,y,z) – to name a few.  For “simplicity” I chose to use a standard cartesian plane and a 2D array to represent the hex grid.  This results in a zig-zag pattern in one of the planes due to the offset of the hex grid.  Depending on whether the grid is offset in the horizontal direction versus the vertical direction a neighboring cell may or may not be in the same row or column.

Converting pixel coordinates to hex coordinates and vice versa
Two algorithms stood out for the type of coordinate system that I chose.  Both require that the hex grid be overlaid by a square grid however one seemed a bit more elegant than the other.  In the first algorithm an overlay of the square grid resulted in two shapes that needed to be evaluated.  The second used an offset grid that created a single shape.  This resulted in the need to only implement a single calculation so I went with that instead.

Calculating sight and movement range options
Movement range was fairly trivial in that you just have to select the hexes that radiate from the location of the unit out to the distance of the movement range. It is a requirement for my game that the units face a particular direction and do not have 360 degrees of vision so I had to implement an algorithm to generate a cone of sight.

How do you calculate line of sight?
I believe that line of site will be the most challenging moving forward.  I’ve already implemented a cone of sight but that doesn’t take into account any obstacles that obscure a unit’s view.  This algorithm here is great (and has a really cool demo) but I’d like to create something that is a little simpler.  The algorithm has to take into account obstacles at any distance and orientation to determine what other hexes are visible from a given point.  When I figure it out I’ll post my solution!