Skip to content

Instantly share code, notes, and snippets.

@BigZaphod
Created November 24, 2015 17:33
Show Gist options
  • Save BigZaphod/51cc865cd8da226c6821 to your computer and use it in GitHub Desktop.
Save BigZaphod/51cc865cd8da226c6821 to your computer and use it in GitHub Desktop.
AStar pathfinding in Swift
// uses PriorityQueue from https://github.com/mauriciosantos/Buckets-Swift
protocol Pathfinding {
typealias Node: Hashable
func neighborsFor(node: Node) -> [Node]
func costFrom(from: Node, to: Node) -> Int
func heuristicFrom(from: Node, to: Node) -> Int
}
extension Pathfinding {
func findPathFrom(start: Node, to goal: Node) -> [Node]? {
var costSoFar = [start : 0]
var cameFrom = [Node : Node]()
var frontier = PriorityQueue([(node: start, priority: 0)]) {
return $0.priority < $1.priority
}
while let best = frontier.dequeue() {
let current = best.node
if current == goal {
var path = [goal]
for var node = goal; node != start; {
node = cameFrom[node]!
path.append(node)
}
return path.reverse()
}
for next in neighborsFor(current) {
let newCost = costSoFar[current]! + costFrom(current, to: next)
let oldCost = costSoFar[next]
if oldCost == nil || newCost < oldCost {
costSoFar[next] = newCost
frontier.enqueue((node: next, priority: newCost + heuristicFrom(goal, to: next)))
cameFrom[next] = current
}
}
}
return nil
}
}
@magonicolas
Copy link

magonicolas commented Jan 13, 2017

Hi there! I need to implement A* using nodes (Instead of a Gird Like on image 6-4 on https://developer.apple.com/library/content/documentation/General/Conceptual/GameplayKit_Guide/Pathfinding.html). You have an implementation example for iOS on this?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment