Thursday, September 8, 2011

DDTe3 Hex theory

This article continues my series of articles on the creation of Dozen Days of Tiles episode 3. In this episode instead of creating a game in under 24 hours of development time, I am instead seeing how many games I can create in 24 hours. The previous articles covered the creation of the first four games in this episode. This article takes a look at hex grids and the theory used behind the next three games in this episode.

The fifth game in this game in a day (24 hours development time, not real time) is still not my rotation puzzle game. Instead, I am going to do a hex based version of the image puzzle.While this play mode may be original to the Blazing Games site, it is not the first time I have done this game. When I was playing around with the Android SDK, I developed this play mode. Instead of breaking the puzzle up into a grid, the puzzle is broken up into hexes on a hex map.

If you are into tabletop strategy or role-playing games, you are probably already familiar to hex maps. For these games, hex maps have a huge advantage over grids in that you do not have to deal with diagonals. This may not sound like a big deal, but moving diagonally lets you travel a bit more than 1.4 times further than if you travel horizontally or vertically. For image puzzles, it adds a bit more challenge to the puzzle as more thought is required to place the pieces.

Using a hex grid seems scary the first time you approach developing one, but as you look at it, things really are not that complicated. The first issue is how to represent the data. I originally solved this problem when I looked at an offset-tiled ceiling and immediately realized how the pattern was similar to that of a hex map. Figure 1 shows the two side by side.

figure 1
The nice thing about the offset map is that it is easy to represent the map by simply using a grid. Depending on the type of things you are planning on doing, there may be no issues at all. Where there is a problem is when you start adding things on top of the map and have to start moving them around and looking around the map. The x direction is fine, but any type of y manipulation is problematic as the grid shifts around. One solution to this problem is to properly align the y axis as shown in figure 2. Notice that there is a third axis, labeled Z. This is not really a separate axis as it’s value is dependent on the value of the X and Y axis so it can be easily calculated.

figure 2

This seems like a good idea but has the problem of having a skewed layout. Storing such a hex map means either having to have negative coordinates or having a lot of unused storage as the map size and positioning of things is adjusted to allow for a positive only layout. A better solution is to use the offset-grid format for storing the hex map but then convert to axis-aligned coordinates when doing any type of traversal of the grid. This translation can be done as follows:

hex_x = x - Math.floor(y/2);
hex_y = y;
hex_z = -hex_x - hex_y;

By having both the offset_tile coordinates for a logical grid-based storage and manipulation of the data as well as hex coordinates for navigating the hex-grid, the hex map becomes fairly easy to work with. The best part is that because the offset grid works the same as a normal grid, the BasePuzzleModel does not need to be changed in order to use it for hex-based puzzle games. What does need to be changed, however, is the BasePuzzleView. Before we can create the HexPuzzleView class, however, we will need to first figure out how to draw hexes. That, of course, will be next week.

No comments: