New iPhone puzzle game

Magnetic Block Puzzle is now available on the App Store for a small amount.

It's a departure from my two previous games, Reversi and Merelles, which were both abstract strategy games. Magnetic Block Puzzle is, as the name implies, a puzzle game. The aim of each of the 110 puzzles is to join the coloured blocks, which are special magnets that stick to other blocks of the same colour, by tilting the puzzle to make the blocks move.

The process of building this game, from inception to completion, went something like this:

I started out this project by building the underlying model of the blocks and the board, including the logic to shift the blocks around. This was done in a test-driven manner, which helped to drive out the model and behaviour correctly and to identify edge and corner cases early. Towards the end of this process, I discovered a similar puzzle game on clickmazes.com and contacted them to ensure I wouldn't be violating a copyright. They were happy for me to proceed and gave me permission to use two of their puzzles too.

The next step was to build a solver and a puzzle builder application on top of the model, to allow me to design and test puzzle layouts. This was done as an iPhone application and many puzzles were designed on my iPhone whilst I was riding on the tube :)

Once enough puzzles had been designed, I tailored the solver to determine various things about each puzzle such as the number of solutions, the number of moves in the best solution, the number of useful positions in the solution tree (positions from which the puzzle can be solved), the number of dead-end positions (positions from which the puzzle cannot be solved), and so on. This proved to be quite CPU-intensive on the more complex puzzles, so it was compiled and run on my Mac rather than on the iPhone. These values were then used to assess the relative difficulty of each puzzle.

So, every puzzle included in the game was designed by hand, but assessed and verified by code.

Finally I wrote the actual application, including in it the 110 puzzles that had been selected for the final application, in a local SQLite database. Like the solver and the puzzle builder, the actual game was built on top of the model built initially.

I started this application in early December 2008 and finished it in late April 2009 - nearly five months of much of my free time went into building it. I am happy with the end product and hope that those who purchase it enjoy playing it as much as I enjoyed creating it. It's available on the App Store now.

More responsive sliders on the iPhone

One of the best things about the iPhone is you can have thin fingers or fat fingers, and pressing buttons and using controls on the touch screen is still quite easy. On old-school touch screen devices (WinMob phones in particular spring to mind), one had to be very precise as the first location touched on the screen immediately triggered a touch event, which is why a stylus was almost always necessary. The iPhone takes a slightly different approach, where a touch that consists of many points on the screen (as would occur with a finger) is converted into a co-ordinate through some sort of averaging of all the points. In general this works really well. However, using this approach still requires the controls on the screen be sufficiently large that a user will be able to put a finger over it, with the average falling comfortably on the control. From my experiments, I believe a control needs to have a touch area of at least 32x32 pixels.

Unfortunately, some of the standard controls suffer from having a touch area that is too small and subsequently difficult to press. In particular, when creating an info type UIButton with the Interface Builder the dimensions and bounding rect are set to 18x19, which is too small. This can be fixed by changing the bounding rect through code, but not in the interface builder.

I recently ran into a similar issue with a slider control.

When creating a UISlider with the Interface Builder, it is given a fixed height of 23 pixels, which is too low. More troubling is the thumb control in the slider, whose size is not exposed, but is around 20x20 and is too small for the slider to be comfortably moved. I found with a horizontal slider slid all the way to the left or all the way to the right, it would be difficult to move the thumb control off the edge with my finger - and I have fingers that are relatively slender. The bounding rect of the slider and the touchable area of the thumb control are as follows:

Unfortunately, simply changing the bounding rect on the control was not a solution in this case as it simply makes the slider bigger and does not change the touchable area of the thumb control. I tried all sorts of workarounds to make the slider more responsive and eventually settled on extending the UISlider control and overriding some behaviour with the following two-pronged approach (the code follows at the bottom of the post):

1. 
   Override the pointInside method to make points slightly outside of the control still appear to be inside the control (without changing the size of the actual slider). I decided to extend the touchable area by 10 pixels on either side of the control and 8 pixels above and below it.
   
2. 
   Override the beginTrackingWithTouch method, which determines whether the user has clicked on the thumb control, to start tracking. This requires determining where the thumb control is based on the current value, then determining if the user's touch was close enough to it for tracking to begin. I effectively increased the thumb control size to 40x40.
   

The new effective bounding rect of the slider and the touchable area of the thumb control are now as follows:

To use the code below, use the Interface Builder to drop a slider on the screen and then change its class from UISlider to MySlider. It only supports horizontal sliders, the beginTrackingWithTouch method would need to be changed or extended to use it with vertical sliders.

Granted this is a hack, but until Apple sorts out this issue, I'll continue to resort to this sort of thing. I'm surprised it hasn't been sorted out already. I've seen forum posts from people having this problem with the info button, but none as yet with sliders. Am I the only one that sees this as an issue?

MySlider.h:

#import <UIKit/UIKit.h>

@interface MySlider : UISlider {
}

MySlider.m:

#import "MySlider.h"

#define THUMB_SIZE 10
#define EFFECTIVE_THUMB_SIZE 20

@implementation MySlider

- (BOOL) pointInside:(CGPoint)point withEvent:(UIEvent*)event {
CGRect bounds = self.bounds;
bounds = CGRectInset(bounds, -10, -8);
return CGRectContainsPoint(bounds, point);
}

- (BOOL) beginTrackingWithTouch:(UITouch*)touch withEvent:(UIEvent*)event {
CGRect bounds = self.bounds;
float thumbPercent = (self.value - self.minimumValue) / (self.maximumValue - self.minimumValue);
float thumbPos = THUMB_SIZE + (thumbPercent * (bounds.size.width - (2 * THUMB_SIZE)));
CGPoint touchPoint = [touch locationInView:self];
return (touchPoint.x >= (thumbPos - EFFECTIVE_THUMB_SIZE) && touchPoint.x <= (thumbPos + EFFECTIVE_THUMB_SIZE));
}

@end

Merelles iPhone game released (finally)

I've been working on Merelles for the last 4 months and I'm pleased to say, I've finally finished it. It's available on the Apple App Store for a small amount.

Merelles is an abstract strategy game. It is also know as Mills, x Men's Morris (4, 6, 9 and 12 men variations) and by many other names.

Seeing as this is my technical blog (and the Apple NDA has been lifted), I feel compelled to provide some technical details. The app itself is written in Objective-C (of course) using TDD (of course!) driven by OCUnit.

The computer AI uses a negascout tree search to examine the game tree. The use of the negascout algorithm means that some pruning will occur on the game tree so that not every node needs to be examined, as long as the moves are ordered so that better moves are examined first!

Iterative deepening is applied on top of this, starting by searching one move ahead, then two, and so on. The moves that look to be good after a search are considered first when searching deeper. In addition, as the same board position can occur several times during a single tree search, moves that result in a really promising board position are classified as killer moves and examined before other moves if they occur again during the search. All this helps in obtaining an amazing prune rate of more than 90%

A question that is often asked is how do you determine if a board position is better than another board position? Unfortunately, it's a fuzzy answer. A set of heuristics is applied, which take into account things like how many pieces each player has in play, how mobile each player is (how many valid moves they have), how easily they can form a row of three pieces, and so on. The strength of the AI is determined largely by these heuristics.

There are 3 difficulty levels. For each level, the heuristics are mostly the same, with varying depths for the tree search and the maximum number of board positions that are considered. For the most complex game (the 12 men game):

• On easy, the AI only looks 2 moves ahead.
• On medium, the AI looks 2 to 4 moves ahead examining up to 3000 board positions.
• On difficult, the AI looks as many moves ahead as it can in examining up to 15000 board positions - in practice this is between 4 and 8 moves ahead, depending on the state of the game.

The resulting game play feels quite natural to me, with the AI coming up with some clever strategies, which in themselves have not been programmed into it, but rather are the result of the tree search and the heuristics. I've been astounded a few times at the way it has trapped me!

The primary challenge in writing this game was to balance the heuristics to set up board positions that would yield good results later in the game rather than just constantly pursue the capture of opponent pieces, which would result in rather one dimensional game play. On top of this, it was necessary to keep the calculations light and to optimise the code as much as possible so that the tree search would not take too long, remembering that it's running on a device with limited computational power. On difficult, the deepest tree searches take up to just over 4 seconds on the iPhone.

Unit testing iPhone applications

The OCUnit framework is bundled with a standard xcode installation, which is handy for getting up and running with unit tests and test-driven development (TDD). Somewhat annoyingly though it does not play nicely with the Cocoa Touch framework. So, how does one go about building iPhone applications using TDD? I'm sure there are several ways of achieving this, but I wanted to stick with OCUnit. After a bit of messing about this is how I do it.

Image from Bhavna Bahri's photostream.

The Cocoa Touch framework encourages the use of the model-view-controller (MVC) pattern. It's only the 'V' and 'C' bits however that need to extend Cocoa Touch objects (UIView and UIViewController); you're completely free to implement the 'M' bit as you see fit. So, the basic approach I take is to write the model classes against OCUnit tests compiled against the (Cocoa) Foundation library only, and to then use these same classes in my iPhone application, which is compiled against the Cocoa Touch framework. The Foundation library exists in both the Cocoa and Cocoa Touch frameworks and is (almost) identical, although the unit tests only run against the Cocoa version.

This setup involves creating two projects: a Foundation Tool project and a Cocoa Touch project, and to reference the model code (which lives in the Foundation Tool project) directly from the Cocoa Touch project. Rather than duplicating the files that comprise the model, they are just referenced from the Cocoa Touch project (which is achieved by dragging them from the finder into the Cocoa Touch project, making sure the 'Copy items into destination group's folder' option is not checked).

The files that comprise the model objects should import Foundation/Foundation.h whereas the files in the Cocoa Touch project should generally import UIKit/UIKit.h (which is a higher-level header file that ultimately includes Foundation/Foundation.h).

What this means is that unit tests only cover the model, not the controllers or the views - so domain logic should be in the model, with the controllers simply acting as conduits for responses from this logic. In other words, there should be as little domain logic as possible in the controllers (and obviously the views, but there should not be any logic in the views anyway!)