SR-71

Posted in Aerospace | Leave a comment

More Mis-Information 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

Brexit

The best article you’ll read on it. period.

Posted in Politics | Leave a comment

When we were decidedly less insane.

It never happened in my school, but it could have.

Posted in Self Defense | Leave a comment

The Truth about guns

In a simple graphic.

Posted in Self Defense | 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

B-1 landing without nose landing gear

Cool video of a B-1 landing at Edwards AFB with failed landing gear. Great landing job.

Posted in Aerospace | Tagged | Leave a comment

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

  1. Initialize the start Node and set the gScore to 0 (cost of going from start to start)
  2. Create Node adjacent to start Node 
  3. Create Path from start Node to adjacent Node
  4. Add Path to start Node
  5. Create Path from adjacent Node to start Node
  6. add Path to adjacent Node
  7. Create next Node adjacent to start Node
  8. Repeat steps 3 through 6 for Node created in step 7
  9. Create end Node
  10. Repeat steps 3 through 6 for step 2 Node and end Node
  11. Repeat steps 3 through 6 for step 7 Node and end Node
  12. Initialize SearchManager with start and end Nodes
  13. call searchManager.findPath()
  14. 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)

    }


Posted in Swift | Tagged , , | 5 Comments