Performance of A* route

Question

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 {
            let nextLocation = currentNode.location.getAdjecentPoint(direction)

            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
    }
}

Answer 1

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).