Slide24: Sliding Tile Puzzle for iOS

Posted by Jeffrey

Note: This is an archived version of the Slide24 page, for those interested in earlier versions. The most recent version is at Slide24: Sliding Tile Puzzle Webapp.

I’ve just revamped my OCaml implementation of the 5 x 5 sliding tile puzzle for iOS. It lets you shuffle and solve the puzzle, or if you’re pressed for time it will use a heuristic search algorithm to solve the puzzle for you.

On this page I show how to get the sources from Psellos and compile and run the app using Xcode. If you’re registered as an Apple developer, you can run it on your iOS device. (If you’re not, you can still run OCaml apps in the iOS Simulator. See Gamut: Explore Colors in iOS Simulator for a simple example app packaged for the iOS Simulator.)

This most recent version of Slide24 is 2.0.2. I built and tested it under iOS 8.3 using Xcode 6.3.1, the latest available at the time of writing. I would expect it to work with minimal changes using future Xcode releases also. Previous versions of Slide24, for earlier versions of OS X and Xcode, can be found in the OCaml Programming Archives.

Most likely you’re familiar with the puzzle in the screenshots. If not: you first slide the 24 tiles around to shuffle them up. Then the goal is to put them back in numeric order. The app, called Slide24, has a button (at the lower left in the screenshots) for shuffling the tiles. Each tile is itself a button. When you touch a tile, it moves itself toward the empty spot. If the tile isn’t adjacent to the empty spot, the tiles in between move as well. If a tile isn’t on the same row or column as the empty spot, you can’t move it—just as with the physical puzzle.

There’s also a button at the lower right that solves the puzzle. It runs a specialized version of the A* heuristic search algorithm to find a solution, then animates the tiles to show the solution.

There is always a solution for the shuffled position—the app generates only solvable ones. However, the heuristic can’t always find a solution. The search space is very large, and the heuristic occasionally fails because I impose a time limit (to preserve battery life and to keep things interesting). If you move some tiles around or shuffle again it will be able to solve from the new position. It would be a good project to improve the heuristic so that it finds a solution more often.

Overview

My first OCaml iOS app, Portland, shows how to compile, link, and package an OCaml iOS app. However, the app itself doesn’t do anything very interesting. The Slide24 app, while still pretty simple, has more of the feel of a real app.

• It has real GUI components.

• It uses the Cocoa Touch animation facility to make the interface lively.

• It performs some non-trivial computation.

To keep things simple, Slide24 is built entirely from one GUI element: the button. However, Cocoa Touch buttons are quite complex. The OCaml and Objective C wrapper code shows how to wrap a class that has many ways to control its appearance and behavior.

There are two forms of the Cocoa Touch animation facility. The most recent form is based on Objective C “blocks,” a simple implementation of first-class functions (also known as closures). Like many other programming languages these days, Objective C is adopting powerful structures like closures from functional languages.

For now I’ve chosen to use the previous animation interface, which uses pairs of begin/end method calls to encapsulate animations. They are available through wrappers for the UIView class. In the future it would be interesting to build an interface to blocks-based animation using OCaml closures in place of Objective C blocks.

While the Portland app does no interesting computation, Slide24 does at least a little bit: it solves the puzzle using a heuristic search. As a result, the amount of OCaml code compared to Objective C code in Slide24 is a bit higher than in Portland. Depending on how you count, Portland is around 43% OCaml code, while Slide24 is around 56% OCaml code.

I’ll discuss a few more interesting points in detail after I describe how to build and run the app.

Preliminaries

Before starting, make sure you have installed Apple’s Xcode and iOS SDK. As I write this, the current version is Xcode 6.3.1. You can download Xcode from the Mac App Store. See Apple’s Xcode page for more details.

You also need an OCaml-to-iOS cross compiler. I use a modified version of OCaml 4.01.0, with patches from us (Psellos). You can download a binary, or build it from source yourself. See Compile OCaml for iOS for details.

Get Slide24 Sources

Choose a place to work (an empty directory would be good).

$ cd <good place to work>

Download the sources for Slide24 2.0.2 from Psellos:

$ curl -O -s http://psellos.com/pub/slide24/slide24-ios-2.0.2.tgz
$ ls -l slide24-ios-2.0.2.tgz
-rw-r--r-- 1 psellos staff 113928 May 17 10:18 slide24-ios-2.0.2.tgz

To save typing, you can download it directly from this link:

• Slide24 2.0.2

Unpack and Check Particulars

$ tar -xf slide24-ios-2.0.2.tgz
$ cd slide24-ios-2.0.2
$ ls -1
Slide24
Slide24.xcodeproj

Most of the work of building Slide24 is done by Slide24/Makefile. You may need to change some of the specific settings near the beginning:

IOSREV = 8.3
IOSMINREV = 7.1

HIDEOUT = /Applications/Xcode.app/Contents/Developer
TOOLDIR = $(HIDEOUT)/Toolchains/XcodeDefault.xctoolchain/usr/bin
PLT = $(HIDEOUT)/Platforms/iPhoneOS.platform
SDK = /Developer/SDKs/iPhoneOS$(IOSREV).sdk
OCAMLDIR = /usr/local/ocamlxarm/v7

IOSREV is the revision of the iOS SDK that you wish to use. I’ve been testing with the iOS 8.3 SDK. IOSMINREV is the earliest iOS revision that you want the app to run on, called the “Deployment Target” in Xcode. In my experience it’s not necessary to support very old versions of iOS, as Apple issues frequent reminders to upgrade.

If your Xcode is installed in a nonstandard location, change HIDEOUT to the Developer directory inside your Xcode application. OCAMLDIR is the location of your OCaml cross compiler.

Open Xcode and Change Project Parameters

To open Xcode, you can use the following command:

$ open Slide24.xcodeproj

This starts Xcode and opens Slide24 as an Xcode project. You can also open the project from Xcode’s File -> Open menu, or double click on Slide24.xcodeproj in the Finder.

Make sure Xcode is building the Slide24 target (not Slide24bin) and is building for an iOS device (not an iOS Simulator).

• Click the left side of the scheme selector at the left end of the toolbar. From the menu select Slide24.
• Then click a little bit to the right and select your iOS device from the top section.

Next make sure code signing is configured properly. This is hard to describe, but not so hard to do.

• Under the Navigate menu, select Reveal in Project Navigator. This should show the project as a whole and its two targets near the top of the second pane.

• Click on Slide24, the target. It’s the last listed item in the second pane, with a miniature app icon. (You don’t want Slide24, the project, which is at the top.)

• Click on Build Settings in the third pane. This brings up a zillion settings for the Slide24 target.

• In the build settings, look at the Code Signing section. Make sure the Code Signing Identity and Provisioning Profile are set to something reasonable for your development environment. For me the code signing identity says “iOS Developer” and the provisioning profile says “Automatic”.

Build and Run

You can now build the app. If you have an iOS device attached, you can build and run it.

• To build, click on the Product -> Build menu item.

• To build and run, click on the Product -> Run menu item.

If things go right, you’ll see an app running on your iOS device that looks like the screenshots above. It’s actually quite entertaining, especially the shuffle animation and the automated solving. Or at least, I like them.

Updates for iOS 8

There were four major parts of the iOS 8 update.

Automatic Reference Counting The Objective C wrappers are compiled with ARC enabled. To make this work, you need a way to represent the fact that an Objective C object is referenced from the OCaml world. I represent this by a global table g_objc_to_ocaml, defined in wrap.m. It holds Objective C objects that are referenced from OCaml, and as a side benefit it maps from an Objective C object (a pointer) to the OCaml object that represents it.

View Controllers Recent iOS apps are based more on subclasses of UIViewController than on views. This is tricky because it’s not feasible (at least not yet) to create an OCaml subclass of an Objective C class. I handle this by creating a UIViewController subclass named Slide24ViewController that delegates all its interesting methods to an object in the OCaml world. The OCaml class of the delegate is Slide24ViewControllerD.t, described below.

Storyboards Recent iOS apps use storyboards and automatic layout. Once you have a design that supports view controllers, these are not difficult changes for a simple app like Slide24.

Flexible Geometry The number of different screen sizes of iOS devices has increased dramatically since a few years ago, so it’s no longer reasonable to do layout by counting pixels. I kept the same tile images and adjusted the layout to keep them centered on a screen of any size. I suspect it would be better to use larger tile images for larger screens, something to try later.

Theory of Operation

Slide24 essentially follows the MVC paradigm. The model is a small data structure—an int array—representing the current configuration of the tiles. The view is the grid of square buttons plus the two extra Shuffle and Solve buttons—all instances of UiButton. These are coordinated by the view controller delegate, an instance of the class Slide24ViewControllerD.t. Let’s call this instance “the controller.” The controller is created as specified in the storyboard file Main.storyboard.

When you touch a button, Cocoa Touch calls a method in the Slide24ViewControllerD (inverse) wrapper class, which is translated directly into an OCaml method call of the controller. The controller adjusts the model and calculates the new positions and appearances of the buttons. It applies them through the UiButton wrapper instance, and Cocoa Touch adjusts the display accordingly.

There is also an OCaml class named Slide24AppDelegate.t that participates in the UIApplicationDelegate protocol (through a wrapper) to receive notifications of changes in the application state. An instance of this class is created at startup, as specified in the main program main.m.

When you touch a tile button, the new model for the tile positions is determined directly by the controller. When you touch the Solve button, the controller invokes the Solve module, which guides the underlying heuristic search so that it finds the answer quickly enough to be fun to watch. The underlying search, in turn, is performed by the Astar module.

When the controller is displaying a solution to the puzzle, the model is expanded to include a list of future configurations along with the current one. A timer periodically calls the controller’s timerTick' method. It advances to the next configuration in the list, and displays it as usual.

The 24 numbered buttons are created dynamically at startup, mostly to avoid the tedium of specifying 24 nearly identical buttons with Interface Builder. The controller also creates the animation timer at startup and tells it to call the timerTick' method.

Interface Builder

If you click on Main.storyboard in the leftmost pane, you’ll activate Interface Builder to show the storyboard for Slide24. There are only five interesting objects: the view controller, the main view, the Shuffle and Solve buttons, and the view controller delegate (which we’re calling the controller).

The interesting connections are as follows. There’s a connection from the view controller’s delegate outlet to the controller. There are connections from the controller’s shuffle and solve outlets to the two buttons. Each button also has an action that tells it to invoke an appropriate method of the controller (doShuffle: or doSolve:).

UiButton Wrapper

One of the strengths of a language like OCaml is its formal type system, compared to the more ad hoc systems of languages in the C family. Where C makes exceptions in its typing rules to support things like operations on generic values, functional languages can capture the generic quality directly using parametric polymorphism. This gives a surprising combination of rigor and flexibility, one of the things that attracted me to OCaml in the first place.

As a small example of this, the wrapper for UIButton captures its subset of the Cocoa Touch design pretty faithfully, while using the extra rigor of the OCaml type system to catch errors that Objective C would miss. It’s not possible, for example, to use a touch event value where a button state is expected. In Objective C, these are both just unsigned integer values and can be freely interchanged or mixed.

Although its type system is unusual for an OO language (based on structure rather than naming), OCaml supports many of the usual OO idioms. For example, the following method is used to tell a button what to do when you touch it:

    method addTarget'action'forControlEvents' :
            #Wrappee.t -> string -> controlEvents -> unit

The type of the first parameter specifies that it can be any object that is (inversely) wrapped by an Objective C object. In essence, this is any object whose “real” implementation is in OCaml but that can be accessed from Objective C. This is, in fact, precisely the set of objects that make sense as targets of button touches.

The #Wrappee.t notation represents a light-weight kind of subtyping similar to a protocol in Objective C. This has proven to be quite handy in our larger projects at Psellos.

Heuristic Search

Another strength of OCaml is that its rigorous type system allows you to make changes to code while being pretty sure it still makes sense. This plasticity was, again, one of the things that attracted me to OCaml originally.

I wrote the heuristic search code over quite a short time, rewriting it many times as I discovered problems or thought of new approaches. I probably wrote at least 25 versions, but there were no delays caused by errors in the modifications. For me at least, a strong and flexible type system makes the language more plastic (rather than less), and helps focus on the problem I’m trying to solve.

It’s worth mentioning that the search is written in a functional style, which is my preferred way to write OCaml. It uses the Set and Map modules from the OCaml standard library (rather than imperative structures like hash tables). Even on a small device like the iPhone, the performance is excellent.

Discussion

As mentioned above, you can also run OCaml apps in the iOS Simulator. This is particularly easy, as it doesn’t require an iOS device or any code signing. You can download an OCamlt-to-iOS Simulator compiler binary from Psellos, or build your own from sources. See Compile OCaml for iOS Simulator for more information.

Many other resources, including more example apps for both iOS and the iOS Simulator, are listed on our OCaml Programming page.

If you have comments, questions, or corrections please leave them below, or email me at jeffsco@psellos.com.