
Recent Posts
Recent Comments
Archives
 July 2016
 June 2016
 May 2016
 January 2016
 June 2015
 May 2015
 April 2015
 January 2015
 May 2014
 April 2014
 March 2014
 February 2014
 January 2014
 March 2013
 December 2012
 November 2012
 August 2011
 July 2011
 May 2011
 February 2011
 May 2010
 April 2010
 November 2009
 September 2009
 May 2009
 April 2009
 March 2009
 February 2009
 January 2009
 December 2008
 October 2008
 September 2008
 August 2008
 July 2008
 June 2008
 May 2008
 April 2008
 March 2008
 February 2008
 January 2008
 December 2007
 November 2007
 October 2007
More MisInformation from the Media
This is why I don’t believe anything I hear on the news.
Posted in Self Defense
Leave a comment
Road buckle
Fascinating to watch the way people respond to this hump in the freeway. Some fly over it, some go around, a few slow down.
I watched about three minutes of it.
Posted in General
Leave a comment
Defending our Constitutional Rights.
https://www.youtube.com/watch?v=DNDcd1Fe5lg
Posted in Politics
Leave a comment
Airport minimums landing
https://www.youtube.com/watch?v=jXUpnhj_mtc
Posted in Aerospace
Leave a comment
B1 landing without nose landing gear
Cool video of a B1 landing at Edwards AFB with failed landing gear. Great landing job.
A* Algorithm in Swift
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 subclassed 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)
}