Performance of A* route

I'm new to the Swift language. I have a C# version of a simple A* route which is very fast. But I rewrote it with Swift, and the performance is very bad (3,4 seconds for a very simple road).

Could someone give me some suggestions? What I thought is that, the loop and compares logic spends most of the time.

Here is the entire project.When the app launches, the screen is covered with many white blocks. You could touch on it to switch color to red, blue, yellow etc. Red means blocks; blue means start point; yellow means destination point. We could simply set a point to blue and a yellow from lower left corner to upper right corner; once the yellow color is set, I will execute the route logic; you will see how slow it is.

import Foundation
import SpriteKit

public class RouteManager {
public init(column : Int, row : Int) {
var matrix = [[Bool]]()

for var r : Int = 0; r <= row; r++ {
var oneRow = [Bool]()
for var c : Int = 0; c <= column; c++ {
oneRow.append(false)
}

matrix.append(oneRow)
}

self.matrix = matrix
self.costCalc = SimpleCostCalc()
}

public required init (matrix : [[Bool]]) {
self.matrix = matrix
self.costCalc = SimpleCostCalc()
}

public var matrix : [[Bool]]
public var costCalc : CostCalcProtocal!;

public func route(start : PointInt, destination : PointInt) -> [PointInt]? {
let map = RectInt(x: 0, y: 0, width: matrix[0].count, height: matrix.count)
if(!map.contains(start) || !map.contains(destination)) {
return nil
}

let routeData = RouteData(rect: map, destination: destination)
let startNode = AStarNode(location: start, previousNode: nil, costG: 0, costH: 0)
routeData.openedNodes.append(startNode)

var currentNode = startNode
return routeCore(routeData, currentNode: currentNode)
}

func routeCore (routeData : RouteData, currentNode : AStarNode) -> [PointInt]? {

let start = NSDate()
for direction in routeData.directions {

if !routeData.rect.contains(nextLocation) {
continue
}

if matrix[nextLocation.y][nextLocation.x] {
continue
}

let costG = costCalc.getCostG(currentNode, direction: direction)
let costH = costCalc.getCostH(nextLocation, destination: routeData.destination)

if costH == 0 {
var result = [PointInt]()
result.append(routeData.destination)
result.insert(currentNode.location, atIndex: 0)

var tempNode = currentNode
while (tempNode.previousNode != nil) {
result.insert(tempNode.previousNode!.location, atIndex: 0)
tempNode = tempNode.previousNode!
}
return result
}

let existingNode = getNodeOnLocation(nextLocation, routeData: routeData)
if((existingNode?) != nil) {
if(existingNode!.costG > costG) {
existingNode!.previousNode = currentNode
existingNode!.costG = costG
}
}
else {
let newNode = AStarNode(location: nextLocation, previousNode: currentNode, costG: costG, costH: costH)
routeData.openedNodes.append(newNode)
}
}

let currentNodeIndex = indexOf(routeData.openedNodes, item: currentNode)
routeData.openedNodes.removeAtIndex(currentNodeIndex)
routeData.closedNodes.append(currentNode)

println(routeData.openedNodes.count)
let minimumCostNode = getMinimumCostNode(routeData)
if minimumCostNode == nil {
return nil
}
return routeCore(routeData, currentNode: minimumCostNode!)
}

func getMinimumCostNode(routeData : RouteData) -> AStarNode? {
var node : AStarNode? = nil
if(routeData.openedNodes.count != 0) {
for n in routeData.openedNodes {
if node == nil {
node = n
}
else if node?.costF > n.costF {
node = n
}
}
}

return node
}

func getNodeOnLocation (location:PointInt, routeData : RouteData) -> AStarNode? {
for node in routeData.openedNodes {
if node.location.x == location.x && node.location.y == location.y {
return node;
}
}

for node in routeData.closedNodes {
if node.location.x == location.x && node.location.y == location.y {
return node
}
}

return nil
}

func indexOf (items : [AStarNode], item : AStarNode) -> Int {
var result = -1
for var index = 0; index < items.count; index++ {
if items[index] === item {
result = index
break
}
}

return result
}
}

• That code uses quite a lot of types and methods which are not shown. That makes a review difficult. Also there is no closing brace for class RouteManager {, perhaps some code is missing? – Martin R Dec 9 '14 at 20:47
• getMinimumCostNode(routeData:) -> AStarNode? is also missing its closing brace. It's extraordinarily difficult to review code asking about time performance if we don't have a runnable version. – nhgrif Dec 9 '14 at 23:16
• Sorry. I missed the link. To use the TimeProfiler, open Xcode Instruments (from the top bar, Xcode -> Developer Tools -> Instruments). Once that opens, select time profiler. Launch your app, go back to time profiler, choose the process (your app name) and hit the red circle to start profiling. Then return to the app and get it to start doing the time consuming code. – nhgrif Dec 10 '14 at 2:53
• Time profiling recursion.... i.stack.imgur.com/ltPBu.png – nhgrif Dec 10 '14 at 3:22
• Please consider posting an answer to your own question describing the profiler results, your interpretation, and how you think the code can be improved. – 200_success Dec 10 '14 at 8:23

Without a clue as to what is actually running slow and without enough code to actually compile and time profile myself, the first thing that stands out to me is your nested loop in init.

Why don't we replace that nested loop with the following:

self.matrix = [[Bool]](count: row, repeatedValue:[Bool](count: column, repeatedValue: false))


We have a variable, costCalc, which is of type CostCalcProtocal! (it's spelled "protocol" by the way). But there are problems with this...

First of all, all of our init messages initialize it to SimpleCostCalc(). Why don't we just put this at the variable declaration?

public var costCalc: CostCalcProtocal! = SimpleCostCalc()


And we are we abbreviating so much? I've never once heard autocomplete complain about helping me make my code more readable:

public var costCalculator: CostCalculatorProtocol! = SimpleCostCalculator()


Much better.

But there's still problems here.

The question is, do we want to allow the user to set the cost calculator? This looks a bit like a protocol-delegate pattern, so perhaps we do. If this is what we want, using the forced unwrapped optional is bad. It allows the user to set this variable to nil and crash when you try to access it. For example:

let routeManager = RouteManager(column: 3, row: 4)
routeManager.costCalc = nil
let result = routeManager.routeCore(routeData: foo, currentNode: bar)


This will crash.

The explicitly unwrapped optional is saying this variable should never be nil... but the fact that it's an optional means it could be nil (and you can set it nil and nothing prevents that). And the fact that it's forced unwrapped instead of optionally unwrapped means you get a crash.

So, if we want to let the user set it, we have two options:

public var costCalculator: CostCalculatorProtocol = SimpleCostCalculator()

public weak var costCalculator: CostCalculatorProtocol? = SimpleCostCalculator()


The first option means non-optional. We will always have a valid costCalculator object.

The second option means optional. It could possible be nil, but because it's optional with the question mark, that's okay--we'll be checking it for nil every step of the way.

But there's also that word weak there. This may or may not be necessary.

If we're following a typical protocol-delegate pattern, this is almost certainly necessary. In most cases, a delegate has a reference to the object it is delegating. If the delegate has a strong reference to the delegated object, and the delegated object has a strong reference back to the delegate, we've created what's called a "retain-cycle". Neither object will ever be released by ARC--they'll be kept in memory forever.

Making the variable a weak, optional means that if the cost calculator has no other strong references to it, our reference to it will be nil-ed out as it deallocates (and if it was the only strong reference to us, we'll deallocate as well, appropriately).

• Woo, that's perfect. I will get it a try later and mark as answer when it's ready. It's really a good guide for me. – Howard Dec 10 '14 at 3:09