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 put together another iOS app in OCaml, one that interacts with you. It lets you solve the well known 5 x 5 sliding tile puzzle, or if you’re pressed for time it will use a heuristic search algorithm to solve the puzzle for you.
In the instructions below I show how to get the sources from Psellos and compile the app using Xcode. If you’ve 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.)
The most recent version of Slide24 is 1.0.5. I built and tested it under OS X 10.7 (Lion) using Xcode 4.3.2, the latest available at the time of writing. I would expect it to work with minimal changes using future Xcode releases also. A previous version 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. But if not, the goal is to shuffle up the 24 numbered tiles, then slide them around until they’re 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 buttons to show the solution.
There is always a solution for the shuffled position—the app generates only solvable ones. However, the current heuristic can’t always find a solution in a reasonable amount of time. The search space is very large, and the heuristic occasionally fails when there’s a time limit. If you move some tiles around or shuffle again it will be able to solve from the new position. It would be an interesting 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.
Since blocks-based animation is only supported in the most recent
versions of iOS, I chose 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. I’ve found that closures are especially powerful when you combine them with other functional language features, like partial application.
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 35% OCaml code, while Slide24 is around 55% OCaml code. For a realistic app such as Master Schnapsen/66 or Cassino, the ratio is much higher, and the amount of Objective C code even starts to become negligible. At Psellos we have a mostly fixed amount of Objective C, and write wrappers in OCaml. So the amount of Objective C is relatively small and independent of the size of the project.
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 4.3.2. These instructions should work for Xcode 4.2 and later.
You can download Xcode (for free) 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 3.10.2, with patches from others and from us (Psellos). You can download a binary, or build it from source yourself. See Compile OCaml for iOS for details.
Build Slide24 from Source
Download the sources for Slide24 1.0.5 from Psellos:
Now look in your Downloads folder (where your browser places downloaded
files). You should see a file named slide24-ios-1.0.5.zip. Your
browser may have opened it for you automatically. If not, double-click
on it. This creates the project folder, named slide24-ios-1.0.5. You
may want to move it out of the Downloads folder to a more convenient
place.
The project folder contains an Xcode project description for building
and running Slide24. Double-click on Slide24.xcodeproj to start up
Xcode. You can also open it from Xcode’s File -> Open menu.
Make sure Xcode is building the Slide24 target (not Slide24bin) and is building for an iOS device (not the iOS Simulator).
- Click at the left side of the Scheme selector at the left end of the toolbar. A menu drops down. Select Slide24 -> iOS Device. If a device is attached, the name of the device will appear instead of “iOS Device.”
The file Makefile.ios contains the instructions for building Slide24.
You may need to change some of the specific settings in this file. Make
sure you are in the Project Navigator, which shows the files of the
project. If necessary, click the triangle next to Slide24 to reveal
them. Click Makefile.ios in the left pane, and the file appears in
the center. You’ll see lines like this at the top of the file:
PLAT = /Applications/Xcode.app/Contents/Developer/Platforms/iPhoneOS.platform
SDK = /Developer/SDKs/iPhoneOS5.1.sdk
OCAMLDIR = /usr/local/ocamlxarm
Change PLAT to the location of your iPhoneOS platform folder, part of
the Xcode iPhone SDK. Change SDK to the iOS SDK you wish to use.
Probably you want to set it to the most recent SDK that you have
installed. Change OCAMLDIR to the location of your OCaml cross
compiler.
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 an A-shaped icon.
Click on Summary in the third pane. This brings up a few key settings for the target, including its bundle identifier.
Set the bundle identifier to an appropriate value for your development environment. In the supplied source, the initial value of the bundle identifier is
com.psellos.Slide24. If you’re using Automatic Device Provisioning, you probably don’t need to change the identifier. The wild-card profile will allow you to compile and run an app with any identifier.Now click on Build Settings in the third pane. This brings up a zillion settings for the Slide24 target, including code signing.
In the build settings, look at the Code Signing section. Make sure the Code Signing Identity is set to something reasonable for your development environment. For me it says: Currently matches ‘iPhone Developer: Jeffrey Scofield (XXX)’ in ‘iOS Team Provisioning Profile: *’. The Team Provisioning Profile is the one created for Automatic Device Provisioning; it’s a wild-card profile that matches every bundle identifier.
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 iPhone (or iPod Touch) 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.
If your device runs iOS 4.0 or later, you may see a warning like the following in the Xcode debugger console:
2012-05-26 11:58:00.548 Slide24[5180:707] Application windows are expected to have a root view controller at the end of application launch
This warning can be ignored. Slide24 is targeted for iOS 3.1 and later,
while the rootViewController property of windows wasn’t added until
iOS 4.0. Unfortunately, this warning is issued even when (as in this
case) it doesn’t necessarily make sense.
It might make an interesting project to retarget Slide24 for iOS 4.0, and to add support for the root view controller. I’ve done this myself, and I was able to do it by changing only the build settings and the nib file (no changes to the code). This works because Slide24 is so simple that the generic view controller (UIViewController) does everything that needs to be done. Since the last few iOS 3.X devices are fast disappearing, I’ll incorporate these changes into a future release of Slide24. Then the warning will go away.
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 controller, an instance of the class Slide24ctlr.t.
When you touch a button, Cocoa Touch calls a method in the Slide24ctlr
(inverse) wrapper class, which is translated directly into an OCaml
method call of the controller. The controller adjusts the positions and
appearance of the buttons through the UiButton wrapper instance, and
Cocoa Touch adjusts the display accordingly.
To keep things simple, the controller participates in the
UIApplicationDelegate protocol to receive notifications of changes in
the application state. This avoids having an extra class that would
just pass the notifications along to the controller anyway.
When you touch a tile button, the calculations for the new tile
positions are performed directly by the controller. When you touch the
Solve button, the controller passes off the calculations to be performed
by 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 startup of an iOS app is controlled by a nib file, generated by
Interface Builder. For Slide24, the file is Slide24.xib. This file
says to create the controller, and to make it the delegate for the
containing Slide24 app. It also contains descriptions of the Shuffle
and Solve buttons. The 24 numbered buttons, however, 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 Slide24.xib in the leftmost pane of the Project
Navigator, you’ll activate Interface Builder. You should see that the
nibfile is pretty simple. There are only a few interesting objects: the
main window, the Shuffle and Solve buttons, and the controller.
There is a connection to the controller from the delegate outlet of
the application (represented by File’s Owner). There are connections
from the controller to the window and the two buttons. Each button also
has an action that tells it to invoke an appropriate method of the
controller (shuffle' and solve', respectively).
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 -> unitThe 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 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 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 a compiler binary from Psellos, or build your own compiler 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.