Thursday, September 29, 2011

DDTe3 Hour 15 - 16 Hex Puzzle Game

My series of posts on the creation of Dozen Days of Tiles episode 3 (Puzzle Gallery) continues with the creation of the hex puzzle game. This builds on the theory and code from the last couple of posts so please read those first.

With the HexTile class complete, the next step is to actually display the puzzle. The display of a hex grid is a bit more complicated then displaying a regular tile grid. If you draw a rectangle on a piece of hex graph paper, you will notice that you will be clipping half a hex on each end. This means that the width of a hex-tile is equivalent to the width of the display divided by the half a hex more than the number of desired tiles in the row. The height of a hex -tile is even more confusing to calculate. Because the rows of hexes overlap, the height of a row is essentially less than the height of a tile. When determining the tile height, it is best to think of each row (except the last) being ¾ of the height of a tile.

figure 1 - Hex Clip

   var halfWidth = Math.floor(clip.width / (puzzle.puzzleWidth * 2 + 1));
   var quarterHeight = Math.floor(clip.height / (puzzle.puzzleHeight * 3 + 1));
   this.tileWidth = halfWidth * 2;
   this.tileHeight = quarterHeight * 4;

Laying out the tiles is pretty much the same as laying out a grid, except that every other row is offset by half a tile. Unlike the grid based games, the border is kind of important here as bits of the image are cut out by the irregular shape of the board. The border is drawn the same as it was in the original BasePuzzleView class except that the top and bottom extend a quarter of a tile into the board and the left and right borders extend half a tile into the board.

With the puzzle drawing properly, we now have the problem that the board is drawn in it’s solved state. Moving the hex tiles around is a bit trickier and I was about to write code to calculate the placement of a hex when I realized that I would be looping through them all anyway. By using the Puzzle value to determine which hex goes in which screen location, the update code was only marginally different from the original update code.

The final challenge, which I cheated on, is the click handling. Instead of properly determining which hex was clicked on, I assumed that most people are going to be clicking near the middle of a hex anyway so went with the much simpler bounding box. I may do proper checks later but for now the method is good enough.

With the click support added, creating the first puzzle was simply a matter of copying the original PicturePuzzle Class and changing BasePuzzleView to HexPuzzleView where necessary. With this done, the first hex based puzzle is done and it is time to start on the next one.

Friday, September 23, 2011

DDTe3 Hour 12 - 14 Hex Tile

This is a continuation of my series of articles on the creation of Dozen Days of Tiles episode 3. In this part, we continue developing the hex code by creating a hex-shaped image clipping tile.

As I don’t already have any existing classes for drawing masked shapes, a new class is going to need to be created for drawing the hex tile. This new class works very similarly to the existing ImageLayer class, but with a bit more drawing complexity. Overridding the ImageLayer class does not make sense as the drawing code is going to have to be replaced.

Clipping in the HTML5 canvas is a bit tricky. The important thing to remember about clipping is that you MUST save the state of the canvas before setting a clipping region and restore the state of the canvas once you are done. The canvas does not let you create a new clipping region larger than the existing region.  Each successive clip results in a ever-shrinking drawable region. I personally would have used a additive/subtractive model for building a clipping layer, but that is not what we currently have to work with.

Drawing the hex tile then consists of saving the canvas state, creating a hex path (outPath) for the tile, clipping the canvas using the path, drawing the tile as a rectangle, then restoring the canvas state. As I was doing all this drawing work anyway, I started thinking that perhaps I should combine the drawing of the hex with the drawing of the highlight/border.  Adding the setup/management methods of the TileBorder class to the HexTile class was simple as these classes for just set up variables. The hard part would be drawing them, and this was actually not overly difficult.

My first thought was to use a clipping approach as was done with the drawing of the image. This thought only lasted a few second as I quickly realized that instead of drawing a transparent rectangle over a clipping path, I could just draw a transparent color using the path. By creating the inner bounds of the border, I would also have the path needed for drawing the highlight color. With inner and outer hexes, it is possible to create the border path. As explained in the previous post, the border has to reverse the order of the inner path points as the winding order of the lines in the path determine the fill area. With the outer and inner hex path, this is very simple to do.

       for (var cntr = 0; cntr < 7; ++cntr) {
           this.borderPath[cntr] = this.outPath[cntr];
           this.borderPath[13-cntr] = this.inPath[cntr];
       }
       this.borderPath[14] = this.outPath[6];

The next step then is to create a hex view. That, along with the first hex game, is what we will be looking at next.

Thursday, September 15, 2011

DDTe3 Hours 11 Drawing Hexes

In order to manipulate hex-shaped images, masks are going to have to be used. In canvas parlance, clipping regions are the proper term. Clipping is one of the ugliest parts of the canvas API, as it uses a shrinking region logic. You have to save the canvas state before setting up the region, set up the region, do the clipping based drawing, then restore the state of the canvas.  Thankfully clipping is powerful enough to allow paths to be used to create a clipping region.  This means that if we can create a simple hex-drawing function, that hex can be used as a clipping shape for creating hex-shaped puzzle pieces.

Actually, instead of drawing a hex, creating an array of points is more useful, especially when it comes time to creating the border. The hex, when you look at it, really only has a small number of important numbers that need to be calculated. Figure 1 shows the special points that are needed to create the hex and listing 1 shows the function used for creating the array of points.


figure 1


function buildHexPath(rect, pathlist)
{
   var path = pathlist;
   // make sure path list of points contains proper number of points
   if (path == null)
       path = new Array();
   while (path.length < 7)
       path.push(new BGLayers.Point());
   while (path.length > 7)
       path.pop();
 
  var halfx = rect.x + rect.width / 2;
   var x2 = rect.x + rect.width;
   var y1a = rect.y + rect.height / 4;
   var y1b = rect.y + 3 * rect.height / 4;
   var y2 = rect.y + rect.height;

   path[0].x = rect.x;
   path[0].y = y1a;
   path[1].x = halfx;
   path[1].y = rect.y;
   path[2].x = x2;
   path[2].y = y1a;
   path[3].x = x2;
   path[3].y = y1b;
   path[4].x = halfx;
   path[4].y = y2;
   path[5].x = rect.x;
   path[5].y = y1b;
   path[6].x = rect.x;
   path[6].y = y1a;
   return path;
}

The hex can now be drawn, but to create a border we need a pair of hexes. My first attempt to create a border hex was to create an inner hex and an outer hex and join the two together. This did not work as expected. If you look at figure 2, the first hex is the normal hex. The second hex is suppose to be the border. My immediate reaction was that the fill method didn’t support complex polygons. This isn’t that surprising of a limitation so I quickly wrote my plan B implementation.

figure 2

The third hex in this figure was created by drawing each segment of the hex separately. This was done in a similar way to the first attempt at creating a border. A outer hex and an inner hex are created and then the points are looped through and combined to create six separate polygons.

function drawHexBorder(ctx, rect, pct)
{
   var outpath = buildHexPath(rect, null);
   var wadj = rect.width * pct;
   var hadj = rect.height * pct;
   var inpath = buildHexPath(new BGLayers.Rectangle(rect.x+wadj, rect.y+hadj, rect.width - wadj-wadj, rect.height - hadj-hadj),null);
   for(var cntr = 0; cntr < 6; ++cntr) {
       ctx.beginPath();
       ctx.moveTo(outpath[cntr].x,outpath[cntr].y);
       ctx.lineTo(outpath[cntr+1].x,outpath[cntr+1].y);
       ctx.lineTo(inpath[cntr+1].x,inpath[cntr+1].y);
       ctx.lineTo(inpath[cntr].x,inpath[cntr].y);
       ctx.lineTo(outpath[cntr].x,outpath[cntr].y);
       ctx.closePath();
       ctx.fill();
   }
}

Once this was done I decided to spend a little bit of time researching how the cavas fill was suppose to work as I was positive that I had seen some drawings that had holes in it. After a few minutes of research (about the same amount of time it took me to write plan-b) I finally stumbled upon the winding rule for filling. It appears that the direction of the edge lines are used as part of determining of the points that are filled. While I have played with a number of fill algorithms, I have never actually implemented a winding algorithm but it does mean that by reversing the order of the points in the inner hexagon, the fill should work properly. This would allow the drawing of the border as a single drawing operation which should be more efficient.

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.

Thursday, September 1, 2011

DDTe3 Hour 10 - Spin Puzzle

The spin puzzle is similar to the twist puzzle except that the tiles surrounding the tile clicked on are the ones that move counterclockwise. As with the previous puzzle, this one was very quick to implement. In fact, this game was finished in under half an hour!

The spinning mechanism is very similar to the twist mechanism but more so. To make it easer to get my coordinates straight, I took a piece of paper and created a 3x3 grid and wrote the offsets in the grid as the following table demonstrates.

-1,-10,-11,-1
-1,0* 1,0
-1,10,11,1

Instead of the 4 way swap that was implemented for the twist puzzle, this game will use a 8 way swap.

PuzzleGallery.SpinPuzzleGame.prototype.performTwist = function(p)
{
   var temp = this.puzzle.getPuzzlePiece(p.x-1, p.y-1);
   this.puzzle.setPuzzlePiece(p.x-1, p.y-1, this.puzzle.getPuzzlePiece(p.x, p.y-1));
   this.puzzle.setPuzzlePiece(p.x, p.y-1, this.puzzle.getPuzzlePiece(p.x+1, p.y-1));
   this.puzzle.setPuzzlePiece(p.x+1, p.y-1, this.puzzle.getPuzzlePiece(p.x+1, p.y));
   this.puzzle.setPuzzlePiece(p.x+1, p.y, this.puzzle.getPuzzlePiece(p.x+1, p.y+1));
   this.puzzle.setPuzzlePiece(p.x+1, p.y+1, this.puzzle.getPuzzlePiece(p.x, p.y+1));
   this.puzzle.setPuzzlePiece(p.x, p.y+1, this.puzzle.getPuzzlePiece(p.x-1, p.y+1));
   this.puzzle.setPuzzlePiece(p.x-1, p.y+1, this.puzzle.getPuzzlePiece(p.x-1, p.y));
   this.puzzle.setPuzzlePiece(p.x-1, p.y, temp);
   this.view.update();   
}

Finally, the click had to make sure the position clicked on can spin and the scrambling method had to be adjusted to insure the coordinates are valid. With those simple changes, another game has been completed. My next game in this challenge will be a bit more complex as it will not only require a new view class be created, but also a new coordinate system though surprisingly the BasePuzzleModel will remain unchanged!