As an exercise in learning, I set out to develop the A* algorithm, described here, in Swift. Swift is a strongly typed, dynamic programming language developed by Apple, and available on Linux and all Apple operating systems. It is an open source project managed by swift.org.

My AStar project is also an open source project on my GitHub account available here (including source, unit tests and Xcode project files).

The A* algorithm is an enhancement of Dijkstra’s algorithm for pathfinding and graph traversal, in that it uses heuristics to help finding the best path. In my implementation, I created three classes: Node, Path and SearchManager.

## Node

A Node describes a node on the graph or map. It has a reference to the previous Node, an array of Paths that originate at that Node, along with the cost to travel from the start Node to reach that Node, and the assumed cost from start to end passing through that Node. The total distance includes the actual distance from the start, and the heuristic to the end.

In most cases, a user of this implementation will need to subclass Node to provide application specific details of a Node. One of those is to implement an appropriate heuristic. This algorithm sets the heuristic to 0, meaning it is not used, so it acts like Dijkstra’s algorithm.

//

// Node.swift

// AStar

//

// Created by John Ahrens on 5/22/16.

// Copyright © 2016 John Ahrens. All rights reserved.

//

import Foundation

/**

* Node represents a point on a path. It is an end point that has one or more paths connected to it. Start and End are

* nodes, as are any points that you may pass through in between.

*

* In a real application, this class will need to be sub-classed to provide the means of handling application unique

* features of the Node. One such feature is the means of calculating the heuristic cost to get to the end point.

*/

class Node

{

var paths:Array<Path>? /// Paths define the connections between two nodes

var cameFrom: Node? /// The last Node accessed before arriving at this Node.

var gScore: Double/// The distance from start to this Node

var fScore: Double/// The distance from start to end, passing through this node

var heuristic: Double/// This value defaults to 0, but should be overridden by a child class to do something interesting

init()

{

self.paths = Array<Path>()

self.cameFrom = nil

self.gScore = DBL_MAX

self.fScore = DBL_MAX

self.heuristic = 0.0

}

init(withPaths paths:Array<Path>)

{

self.paths = paths

self.cameFrom = nil

self.gScore = DBL_MAX

self.fScore = DBL_MAX

self.heuristic = 0.0

}

}

## Path

A Path contains two nodes that are adjacent by virtue of our being able to travel from one to another directly without passing through any other Nodes. The other element of the Path is the cost of going between the two Nodes. Note that if you can go both directions between the Nodes, you need to create two Paths, one having the Nodes reversed from the other Node.

//

// Path.swift

// AStar

//

// Created by John Ahrens on 5/22/16.

// Copyright © 2016 John Ahrens. All rights reserved.

//

import Foundation

/**

* A path exists between two points. Both Nodes are listed here as node1 and node2

*/

class Path

{

var node1: Node? /// Starting Node for a path

var node2: Node? /// Ending Node for the path

var cost: Double/// The cost of traversing from node1 to node2

init()

{

node1 = nil

node2 = nil

cost = 0.0

}

init(withNode1 node1:Node, node2:Node, cost:Double)

{

self.node1 = node1

self.node2 = node2

self.cost = cost

}

}

## SearchManager

//

// SearchManager.swift

// AStar

//

// Created by John Ahrens on 5/22/16.

// Copyright © 2016 John Ahrens. All rights reserved.

//

import Foundation

/**

* SearchManager is a controller object in the Model/View/Controller sense of things. It does the work of finding the

* path to the end point.

*/

class SearchManager

{

var closedSet: Array<Node> /// Set of nodes already evaluated

var openSet: Array<Node> /// Set of nodes still to be evaluated. Initially only the starting point

var start: Node

var end: Node

### init

The SearchManager class is the controller of all the action, where all the magic happens. After creating all the Nodes and Paths and assigning the Paths to the appropriate Nodes, initialize a SearchManager with the start and end Nodes. The start Node should have the gScore set to zero, since the cost of going from start to start is 0.

init(withStart start: Node, end: Node)

{

closedSet = Array<Node>()

openSet = Array<Node>(arrayLiteral: start)

self.start = start

self.end = end

}

Note that after initialization, the openSet (known Nodes that have not yet been analyzed) contains only the start Node, and the closedSet (known Nodes that have already been analyzed) is empty.

### findPath

After initialization, call the findPath method and evaluate the response. It returns true if it finds a path from start to end, and returns false if no path is available.

- While the openSet is not empty
- Remove the last Node of the openSet as the current Node
- if the current Node is the end Node
- return true, you’ve found the optimal path

- add the current Node to the closedSet
- for each Path in the current Node
- Take the node2 Node as the next Node
- if the next Node is part of the closedSet
- go on, it’s already been evaluated

- compute the cost from the start Node to the next Node
- if the next Node is not part of the openSet
- add the next Node to the openSet, you’ve found a new Node

- otherwise if the cost is greater than or equal to the gScore of the next Node
- go on, it is not a good path

- At this point, you’ve found a candidate for a Node on the optimal path, add it

- If you run out of Nodes and have not reached the end Node, return false

func findPath() -> Bool

{

var current = Node()

start.fScore = start.heuristic

while (0 < openSet.count)

{

current = openSet.popLast()!

if current === end

{

returntrue

}

closedSet.append(current)

for path in current.paths!

{

let nextNode = path.node2

ifclosedSet.contains({$0 === nextNode})

{

// This node has already been evaluated.

continue

}

let cost = current.gScore + path.cost

if !openSet.contains({$0 === nextNode})

{

// Found a new node

openSet.append(nextNode!)

}

elseif cost >= nextNode!.gScore

{

// not a good node

continue

}

// The current best node, add it.

nextNode!.cameFrom = current

nextNode!.gScore = current.gScore + path.cost

nextNode!.fScore = (nextNode?.gScore)! + (nextNode?.heuristic)!

openSet.sortInPlace {

$0.fScore > $1.fScore

}

}

}

returnfalse

}

### recreatePath

After getting a successful path, recreate the path through all the nodes by backtracking from the end Node, through the cameFrom members to the start Node, then returning an Array of Nodes in order. This method uses recursion to accomplish that task.

func recreatePath(fromNode: Node) -> Array<Node>

{

var pathToEnd: Array<Node> = []

if fromNode !== start

{

pathToEnd = recreatePath(fromNode.cameFrom!)

}

pathToEnd.append(fromNode)

return pathToEnd

}

}

## Tests

The framework includes a set of UnitTests. I am using only one here as an example of how I anticipate using the framework.

- Initialize the start Node and set the gScore to 0 (cost of going from start to start)
- Create Node adjacent to start Node
- Create Path from start Node to adjacent Node
- Add Path to start Node
- Create Path from adjacent Node to start Node
- add Path to adjacent Node
- Create next Node adjacent to start Node
- Repeat steps 3 through 6 for Node created in step 7
- Create end Node
- Repeat steps 3 through 6 for step 2 Node and end Node
- Repeat steps 3 through 6 for step 7 Node and end Node
- Initialize SearchManager with start and end Nodes
- call searchManager.findPath()
- If it returns true call searchManager.recreatePath()

/**

* Tests the case with two possible paths. The shortest first leg leads to the shortest path.

* Diagram looks like: Start*—+A

* \ \

* B+—*End

*/

func testTwoPathsTwoIntermediateNodesShortestFirstLegShortestPath() {

let start = Node()

start.gScore = 0.0

let nodeA = Node()

let startPathA = Path(withNode1: start, node2: nodeA, cost: 1.0)

start.paths?.append(startPathA)

let pathAStart = Path(withNode1: nodeA, node2: start, cost: 1.0)

nodeA.paths?.append(pathAStart)

let nodeB = Node()

let startPathB = Path(withNode1: start, node2: nodeB, cost: 1.5)

start.paths?.append(startPathB)

let pathBStart = Path(withNode1: nodeB, node2: start, cost: 1.5)

nodeB.paths?.append(pathBStart)

let end = Node()

let pathAEnd = Path(withNode1: nodeA, node2: end, cost: 1.5)

nodeA.paths?.append(pathAEnd)

let endPathA = Path(withNode1: end, node2: nodeA, cost: 1.5)

end.paths?.append(endPathA)

let pathBEnd = Path(withNode1: nodeB, node2: end, cost: 1.5)

nodeB.paths?.append(pathBEnd)

let endPathB = Path(withNode1: end, node2: nodeB, cost: 1.5)

end.paths?.append(endPathB)

let searchManager = SearchManager(withStart: start, end: end)

XCTAssertTrue(searchManager.findPath())

let totalPath = searchManager.recreatePath(end)

XCTAssertEqual(3, totalPath.count)

XCTAssertTrue(totalPath[0] === start)

XCTAssertTrue(totalPath[1] === nodeA)

XCTAssertTrue(totalPath[2] === end)

}