In this tutorial we’ll create a scene with a simulation of the classic Towers of Hanoi problem. We’ll create an animated solution for the problem and provide UI controls to interactively modify the number of disks. The final result will look like this:
For a basic introduction to SceneKit have a look at Part 1
For more details on primitives have a look at Part 2
Here’s a SceneKit starter project with an empty scene to help you follow along with this tutorial. For starters, we’ll be adding code to the HanoiScene.swift
file.
The towers of hanoi problem consists of three pegs, and a number of disks of decreasing sizes which can be placed onto any peg. The puzzle starts with the disks in a stack in ascending order of size on the leftmost peg.
Disks can be moved from one peg to another but each move has to obey the following rules:
- You can only move one disk at a time
- You can only move the topmost disk
- You can’t place a disk above another disk of smaller size
The goal of the game is to get all the disks to the rightmost peg.
First let’s set up the scene and we’ll worry about an algorithm for solving the problem later.
Creating the board
To start off we’ll create a board with 3 pegs. The board will be made out of a rounded box and 3 cylinders.
We’ll have to think the layout through a bit before creating the board so that the disks fit on it nicely.
We’ll define the size of the board in terms of the radius of the disks we’ll place on it. We’ll want the pegs to have a distance of 2 times the radius of the disks between them and also we’ll want to add some padding so there’s some empty space on the edges of the board.
The total width of the board will be 6 * diskRadius + padding.
The length of the board will be 2 * diskRadius + padding.
We’ll arbitrarily set the height of the board to be 0.2
Here’s a visual illustration of the board seen from above:
To keep things organized, we’ll have separate methods for creating each component.
We’ll be adding properties to hold the sizes of the different elements in our scene.
This helps us keep things organized and is of real use if we want to tweak the sizes of elements later on.
We’ll define the radius of the disk to be 1.0 and we’ll determine the size of the other elements based on that.
The createBoard
method creates the base of our game board and adds it to the scene. This should be familiar code to you if you followed the previous tutorials.
First define the following properties at the top of the class:
class HanoiScene {
...
let diskRadius = 1.0
var boardWidth:CGFloat = 0.0
var boardLength:CGFloat = 0.0
let boardPadding:CGFloat = 0.8
let boardHeight:CGFloat = 0.2
...
}
Then add this method to create the board:
class HanoiScene {
...
func createBoard() {
boardWidth = diskRadius * 6.0 + boardPadding
boardLength = diskRadius * 2.0 + boardPadding
let boardColor = UIColor.brownColor()
let boardGeometry = SCNBox(width: boardWidth, height: boardHeight, length: boardLength, chamferRadius: 0.1)
boardGeometry.firstMaterial?.diffuse.contents = UIColor.brownColor()
let boardNode = SCNNode(geometry: boardGeometry)
rootNode.addChildNode(boardNode)
}
...
}
Creating the pegs
We’ll use cylinders to models the pegs on the board.
We’ll want to adjust the height of the pegs depending on the number of disks we have. More precisely if we have N disks than we’ll want the pegs to have height (N + 1) times the height of the disks.
We’ll have to define the diskHeight
and the numberOfDisks
properties. For starters we’ll set numberOfDisks to be equal to 4 and diskHeight to be equal to 0.2.
We’ll arbitrarily define the radius of the pegs as 0.1 and we’ll use a variable to keep track of the pegs total height for later use. To keep track of the nodes for later use we’ll also define an array of SCNNodes
to hold the peg nodes.
Add the following code to the top of the class:
class HanoiScene {
...
var numberOfDisks = 4
let diskHeight:CGFloat = 0.2
var pegHeight:CGFloat = 0.0
let pegRadius:CGFloat = 0.1
var pegs: [SCNNode] = []
...
}
To position the pegs on the board remember that the position of geometries is in terms of the center of the geometry so we’ll have to shift the pegs upwards so that they’re positioned is exactly above the board.
The board is also positioned in terms of its center so the total amount we have to move the pegs upword is pegHeight / 2 + boardHeight / 2
as illustrated below:
The first peg will be positioned at -boardWidth / 2 + boardPadding / 2 + diskRadius
as illustrated below:
Subsequent pegs will be offset by 2 * diskRadius in the x coordinate.
We’ll create the pegs in a loop where we increase the x coordinates by 2 * diskRadius at each iteration. Also we’ll add each peg to our pegs array for later usage.
class HanoiScene {
...
func createPegs() {
// Create the 3 Pegs on the board
pegHeight = CGFloat(numberOfDisks + 1) * diskHeight
var x:Float = Float(-boardWidth / 2.0 + boardPadding / 2.0 + diskRadius)
for i in 0..<3 {
let cylinder = SCNCylinder(radius: pegRadius, height: pegHeight)
let cylinderNode = SCNNode(geometry: cylinder)
cylinder.firstMaterial?.diffuse.contents = UIColor.brownColor()
cylinderNode.position.x = x
cylinderNode.position.y = Float(pegHeight / 2.0 + boardHeight / 2.0)
rootNode.addChildNode(cylinderNode)
pegs.append(cylinderNode)
x += Float(diskRadius * 2)
}
}
...
}
The scene should look like this now:
Placing the disks on the pegs
Tubes are perfect for modeling the disks. Again we have to keep in mind that disks are positioned in terms of their center so the first disk will have y coordinate boardHeight / 2.0 + diskHeight / 2.0
.
Now that we have the pegs placed on the board we can easily find the x position of the disks by referencing the x position of the pegs.
We’ll use a loop again to create the disks, increasing the y coordinate by the disk height to stack disk on top of each other and decreasing the radius at each iteration.
We’ll color the disks with a hue that ranges from 0 to 1 based on the index. Also we’ll add each disk to our disks array for later usage.
class HanoiScene {
...
var disks: [SCNNode] = []
...
func createDisks() {
var firstPeg = pegs[0]
var y:Float = Float(boardHeight / 2.0 + diskHeight / 2.0)
var radius:CGFloat = diskRadius
for i in 0..<numberOfDisks {
let tube = SCNTube(innerRadius: pegRadius, outerRadius: radius, height: diskHeight)
let hue = CGFloat(i) / CGFloat(numberOfDisks)
let color = UIColor(hue: hue, saturation: 1.0, brightness: 1.0, alpha: 1.0)
tube.firstMaterial?.diffuse.contents = color
let tubeNode = SCNNode(geometry: tube)
tubeNode.position.x = firstPeg.position.x
tubeNode.position.y = y
rootNode.addChildNode(tubeNode)
disks.append(tubeNode)
y += Float(diskHeight)
radius -= 0.1
}
}
...
}
Don’t forget to call the methods to create the geometry from the init method or your scene will be empty.
class HanoiScene {
...
override init() {
super.init()
createBoard()
createPegs()
createDisks()
}
...
}
Your scene should look like this now. Let’s look at an algorithm for towers of hanoi to get things moving.
Solving the towers of Hanoi problem
The towers of hanoi problem might seem daunting to solve at first. But you’ll soon see that it has a really easy and elegant solution.
Note: If you’re familiar with the solution feel free to skim this section.
Let’s start with the simplest possible case. How do we solve the problem for a single disk? This is of course trivial we just move the disk from the starting peg to the destination peg.
It’s almost as easy to do it with 2 disks:
- Step1: Move the small disk to the middle peg
- Step2: Move the large disk to the right peg
- Step3: Move the small disk to the right peg
Done!
Let’s look at the case with 3 disks. Notice that we can solve the problem in the following way:
- Step1: Solve the towers of hanoi problem for 2 disks but switch the destination with the intermediate peg
- Step2: Move the large disk from the start to the destination peg
- Step3: Solve the towers of hanoi problem for 2 disks starting from the intermediate peg and using the initial peg as an intermediate peg
This is a recursive solution to the problem, we break the problem into smaller instances of itself until we reach a trivial case that we solve.
Note that the case of 2 disks can be expressed by using the case with a single disk:
- Step1: Solve the towers of hanoi problem for 1 disk but switch the destination with the intermediate peg
- Step2: Move the large disk from the start to the destination peg
- Step3: Solve the towers of hanoi problem for 1 disks starting from the intermediate peg and using the initial peg as an intermediate peg
In code the solution will look like this:
func hanoi(numberOfDisks: Int, from: Int, using: Int, to: Int) {
if numberOfDisks == 1 {
move(from, to: to)
} else {
hanoi(numberOfDisks - 1, from: from, using: to, to: using)
move(from, to: to)
hanoi(numberOfDisks - 1, from: using, using: from, to: to)
}
}
Generating the moves
Create a new file called HanoiSolver.swift
. We’ll be using this for all the code needed to generate the moves.
We’ll need the following data to be able to animate the movement of the disks:
- the index of the disk to move
- the index of the peg we’re moving the disk to
- the number of disks on the peg we’re moving the disk to
struct HanoiMove {
var diskIndex: Int
var destinationDiskCount: Int
var destinationPegIndex: Int
init(diskIndex: Int,destinationPegIndex: Int,destinationDiskCount: Int) {
self.diskIndex = diskIndex
self.destinationDiskCount = destinationDiskCount
self.destinationPegIndex = destinationPegIndex
}
}
We’ll create a new class HanoiSolver
that will be used to generate the solution to our problem (an array of HanoiMoves). The class will contain the following properties:
- numberOfDisks – the number of disks in the problem
- leftPeg, middlePeg, rightPeg – arrays to keep track of the disks on each peg
- pegs an array used to easily access each peg given an peg index
- moves an array of HanoiMoves that will store our result
Initially all the disks will be placed on the left peg.
class HanoiSolver {
...
var numberOfDisks:Int
var leftPeg: [Int]
var middlePeg: [Int]
var rightPeg: [Int]
var pegs: [[Int]]
var moves: [HanoiMove]
init(numberOfDisks: Int) {
self.numberOfDisks = numberOfDisks
self.leftPeg = []
for i in 0..<numberOfDisks {
self.leftPeg.append(i)
}
self.middlePeg = []
self.rightPeg = []
self.pegs = [leftPeg, middlePeg, rightPeg]
self.moves = []
}
...
}
We’ll use the hanoi
method discussed above to generate moves by providing the from
and to
indices of the pegs who’s disk we want to move.
class HanoiSolver {
...
func hanoi(numberOfDisks: Int, from: Int, using: Int, to: Int) {
if numberOfDisks == 1 {
move(from, to: to)
} else {
hanoi(numberOfDisks - 1, from: from, using: to, to: using)
move(from, to: to)
hanoi(numberOfDisks - 1, from: using, using: from, to: to)
}
}
...
}
The move
method is used to create HanoiMoves
and update our arrays of disks. Notice that the update consists of popping a disk from the from
peg and pushing it to the to
peg.
class HanoiSolver {
...
func move(from: Int, to: Int) {
var disk = popDisk(from)
var diskIndex = disk
var destinationDiskCount = pegs[to].count
pushDisk(disk, peg: to)
let move = HanoiMove(diskIndex: diskIndex, destinationPegIndex: to, destinationDiskCount: destinationDiskCount)
moves.append(move)
}
...
}
The pushDisk
and popDisk
methods are shown below:
class HanoiSolver {
...
func popDisk(peg: Int) -> Int {
return pegs[peg].removeLast()
}
func pushDisk(disk: Int, peg: Int) {
pegs[peg].append(disk)
}
...
}
Finally we’ll add one more method that starts the computation of the moves.
class HanoiSolver {
...
func computeMoves() {
self.moves = []
hanoi(numberOfDisks, from: 0, using: 1, to: 2)
}
...
}
Animating the solution
Now that we can generate an array of moves it’s time to use them in SceneKit to create our animations.
Starting from a move we can now create an animation sequence that moves a disk from one peg to another peg.
First of all we’ll grab the node that stores the position of our disk from our disks array. Then we’ll grab the peg that we want to move the disk to.
We require 3 moves to get the disk to it’s final position:
- Move the disk above the current peg
- Move the disk sideways to the new peg
- Move the disk downwards
We’ll create three SCNActions and nest them in a sequence. Remember that the actions in a sequence run one after the other.
class HanoiScene {
...
func animationFromMove(move: HanoiMove) -> SCNAction {
var duration = 0.3
let node = disks[move.diskIndex]
let destination = pegs[move.destinationPegIndex]
// Move To Top
var topPosition = node.position
topPosition.y = Float(pegHeight + diskHeight * 4.0)
let moveUp = SCNAction.moveTo(topPosition, duration: duration)
// Move Sideways
var sidePosition = destination.position
sidePosition.y = topPosition.y
let moveSide = SCNAction.moveTo(sidePosition, duration: duration)
// Move To Bottom
var bottomPosition = sidePosition
bottomPosition.y = Float(boardHeight / 2.0 + diskHeight / 2.0) + Float(move.destinationDiskCount) * Float(diskHeight)
let moveDown = SCNAction.moveTo(bottomPosition,duration: duration)
let sequence = SCNAction.sequence([moveUp, moveSide, moveDown])
return sequence
}
...
}
To run an action we use the runAction
method on a node. SCNNode
provides several variations on the runAction
method, one of them is the runAction(action, completionHandler:() -> ()) method which takes an action and a block to run when the action has finished animating.
Here’s an example that hints at the solution to our problem:
We want to create an action from our first move and run it, once that action is completed we want to do the same thing for the second move and so on.
// Grab the first move and run it
let move = hanoiSolver.moves[0]
let node = disks[move.diskIndex]
let animation = animationFromMove(move)
node.runAction(animation, completionHandler: {
// Grab the second move and run it
let move = hanoiSolver.moves[1]
let node = disks[move.diskIndex]
let animation = animationFromMove(move)
node.runAction(animation, completionHandler: {
......
})
})
We want to execute this process until we don’t have any moves left. This can be easily implemented as a recursive method. We take an index that references the move we want to run as a parameter. We run the action that corresponds to the index. In the completion handler we call the method again if index + 1 is still within the bounds of our moves array.
class HanoiSolver {
...
func recursiveAnimation(index: Int) {
let move = hanoiSolver.moves[index]
let node = disks[move.diskIndex]
let animation = animationFromMove(move)
node.runAction(animation, completionHandler: {
if (index + 1 < self.hanoiSolver.moves.count) {
self.recursiveAnimation(index + 1)
}
})
}
...
}
To start our recursive animation we simply call:
recursiveAnimation(0)
Let’s add the steps of computing the moves and running the animation to a method playAnimation
that we’ll call at the end of our init method.
class HanoiScene {
...
func playAnimation() {
hanoiSolver.computeMoves()
recursiveAnimation(0)
}
...
}
Our init method will look like this now:
class HanoiSolver {
...
override init() {
super.init()
createBoard()
createPegs()
createDisks()
hanoiSolver = HanoiSolver(numberOfDisks: self.numberOfDisks)
playAnimation()
}
...
}
Running the project now will almost result in the animation shown at the top of the article.
You might run into issues of animations randomly stopping, this is caused by the fact that the scene is not set to playing
. To solve this call the play
method on scnView at the bottom of the viewDidLoad
method in the ViewController
class.
class ViewController {
...
func viewDidLoad() {
...
scnView.play(nil)
}
...
}
Normalizing the duration of the animation
Notice that the animation looks kinda weird right now. Sometimes the disks move faster sometimes slower. This happens because we use a fixed duration of 0.3
for all animations regardless of the distance the disk moved during the animation. To solve this problem we’ll compute the distance the disk moves during the animation and adjust the animation duration accordingly.
Determining the distance from a vector to another vector
To find the distance between 2 vectors in 3D we have to compute the length of the vector obtained by taking their difference.
class HanoiSolver {
...
func lengthOfVector(v: SCNVector3) -> Float {
return sqrt(pow(v.x,2.0) + pow(v.y,2.0) + pow(v.z,2.0))
}
func distanceBetweenVectors(v1 : SCNVector3, v2: SCNVector3) -> Float {
return lengthOfVector(SCNVector3(x: v1.x - v2.x, y: v1.y - v2.y, z: v1.z - v2.z))
}
...
}
For a more detailed explanation of computing distances have a look at the first part of this article.
To adjust the duration of the actions we’ll create a new method normalizedDuration
that takes the start and end position of the animation we want to adjust. We’ll define a reference length that we’ll use to adjust the duration of all other animations. The reference length we’ll use is the distance between the first and the last peg.
To compute the duration of an animation we’ll take the it’s ratio with the reference move and scale it by the duration we want the reference move to take, in our case 0.3
class HanoiSolver {
...
func normalizedDuration(startPosition: SCNVector3, endPosition: SCNVector3) -> Double {
let referenceLength = distanceBetweenVectors(pegs[0].position, v2: pegs[2].position)
let length = distanceBetweenVectors(startPosition, v2: endPosition)
return 0.3 * Double(length / referenceLength)
}
...
}
Here’s the updated animationFromMove
method with normalized duration for each action. We compute the normalized duration based on the position at the start and end of each action.
class HanoiSolver {
...
func animationFromMove(move: HanoiMove) -> SCNAction {
var duration = 0.0
let node = disks[move.diskIndex]
let destination = pegs[move.destinationPegIndex]
// Move To Top
var topPosition = node.position
topPosition.y = Float(pegHeight + diskHeight * 4.0)
duration = normalizedDuration(node.position, endPosition: topPosition)
let moveUp = SCNAction.moveTo(topPosition, duration: duration)
// Move Sideways
var sidePosition = destination.position
sidePosition.y = topPosition.y
duration = normalizedDuration(topPosition, endPosition: sidePosition)
let moveSide = SCNAction.moveTo(sidePosition, duration: duration)
// Move To Bottom
var bottomPosition = sidePosition
bottomPosition.y = Float(boardHeight / 2.0 + diskHeight / 2.0) + Float(move.destinationDiskCount) * Float(diskHeight)
duration = normalizedDuration(sidePosition, endPosition: bottomPosition)
let moveDown = SCNAction.moveTo(bottomPosition,duration: duration)
let sequence = SCNAction.sequence([moveUp, moveSide, moveDown])
return sequence
}
...
}
Adding UI controls
Currently the scene remains static after the animation has finished. Let’s add some UI Controls to give us the possibility of restarting the animation and changing the number of disks.
First of all we’ll have to be able to reset the scene. Add the following method to the HanoiScene class. This method will be called from our view controller when certain actions are triggered.
This method will update the number of disks. We have to recreate the pegs so that they have the correct height and we’ll also have to remove the disks and recreate them so their the correct number and on the correct peg.
class HanoiSolver {
...
func resetDisks(N: Int) {
self.numberOfDisks = N
for peg in pegs {
peg.removeFromParentNode()
}
pegs = []
createPegs()
for disk in disks {
disk.removeFromParentNode()
}
disks = []
createDisks()
}
}
...
Note: This is not the most efficient solution but it gets the job done and is easy to implement. A more efficient solution would update the pegs geometry and reuse the disks creating new disks only when necessary.
Remember that the view we’re using to present our 3D graphics is just a particular type of UIView
so we can add subviews to it and they’ll look and behave as expected.
Open the Main.storyboard
file and add the following components to the view.
- A UILabel with text “Number Of Disks:” white textColor
- another UILabel with text “4” and white textColor to it’s right
- a UIStepper with white tintColor below the labels
- a UIButton with white textColor and title “Restart” below the stepper
Your view should look like this
Select the stepper and set it’s minimum value to 2, maximum value to 8 and current value to 4
We’ll also have to connect the actions for the stepper and the button and add the label as an outlet.
To quickly connect outlets open the assistant editor. Hold control and drag the component you want to add below the class definition in the assistant editor.
To quickly connect actions open the assistant editor. Control click on the components whose action you want to add and drag from the right circle of the action you want to add below the class definition in the assistant editor.
Releasing the mouse will show the following popup where you can name the method and change the type of it’s argument.
Go ahead and add an outlet for the “4” label and actions for the stepper’s “Value Changed” action and the button’s “Touch Up Inside” action.
The top of your ViewController
class should look like this when you’re done:
class ViewController {
...
@IBOutlet weak var numberOfDisksLabel: UILabel!
@IBAction func numberOfDisksChanged(sender: UIStepper) {
}
@IBAction func didTapRestart(sender: AnyObject) {
}
...
}
In the numberOfDisksChanged
method we want to update our label with the steppers value and tell our scene to reset the disks to the steppers value and start playing the animation again.
class ViewController {
...
@IBAction func numberOfDisksChanged(sender: UIStepper) {
numberOfDisksLabel.text = "\(sender.value)"
scene.resetDisks(Int(sender.value))
scene.playAnimation()
}
...
}
In the didTapRestart
method we just want to reset the disks and restart the animation.
class ViewController {
...
@IBAction func didTapRestart(sender: AnyObject) {
scene.resetDisks(scene.numberOfDisks)
scene.playAnimation()
}
...
}
When running the app now, you’ll be able to adjust the number of disks in the simulation. You’ll also be able to restart the simulation whenever you like.
The screenshot below shows the simulation for 8 disks.
This concludes the series of Introduction to SceneKit. In the next series we’ll have a closer look at the way SceneKit represents geometry. I intend to cover custom meshes, rendering wireframes and procedurally generating terrain.
Stay tuned
Introduction To SceneKit – Part 2
Here’s an interesting and difficult challenge if you want to play with towers of hanoi some more:
Solve the towers of hanoi problem using 4 pegs in an optimal number of moves.
Thanks for Tut.
Would love to know how to handle touch events in the 3-D SceneKit. In other words, how to pick up if a specific SCNNode is touched/selected.
You can use this method to determine which nodes are hit. To get the touch events add gesture recognisers to your view or use touchesBegan, touchesMoved, etc.
Thanks. I struggle with Apple’s documentation though. After searching forums and fiddling, I got this to work:
———————————————————————–
@IBAction func tapped(g:UITapGestureRecognizer) {
let scnView = self.view as SCNView
let results = scnView.hitTest(g.locationInView(scnView), options: [SCNHitTestFirstFoundOnlyKey: true]) as [SCNHitTestResult]
if let result = results.first {
if result.node === self.scene.pegs[0] {
println(“Peg nr. 1 selected.”)
}
}
}
Awesome tutorial
I’m relatively new in iOS programming, and I would like to know how could I play with the disks, i mean, instead of animating the process, that I could move the disks from one peg to the other.
Thanks
disks[SCNNode] does not appear to be declared anywhere, although it appears in both the scene and the solver. What’s up?
Thanks for spotting the error. Disks is an array of nodes declared at the top of HanoiScene.(var disks: [SCNNode] = [])