274
9
func ﬁndPotentialCover(steps : Int, distance : CGFloat) -> [CGPoint] {
//

var coverPoints : [CGPoint] = []
//

steps

//

for coverPoint in 0..<steps {
//

let angle = Float(.pi * 2.0) * (Float(coverPoint) / Float(steps))
//

distance
）处的点
let potentialPoint = CGPoint(angleRadians: CGFloat(angle)) * distance
//

potentialPoint
）之间是否存在物体
if self.scene?.physicsWorld.body(alongRayStart: self.position,
end: potentialPoint) != nil {
//

//

coverPoints.append(potentialPoint)
}
}
//

return coverPoints
}

9.9

A*

A

275

A

A*

Swift

A*

//
CGPoint

//

extension CGPoint : Hashable {
public var hashValue : Int {
//
x
y

//

return self.x.hashValue << 32 ^ self.y.hashValue
}
//

//

public func distanceTo(_ other : CGPoint) -> CGFloat {
return (self - other).length
}
}
//

CGPoint

var points : [CGPoint]
//

points

//

var neighbors : [CGPoint : [CGPoint]]
//

points

//
“跃点”列表（邻近的点）
init (points:[CGPoint], maximumDistance: CGFloat) {
self.points = points
self.neighbors = [:]
//

for point in self.points {
//

self.neighbors[point] = []
//

for otherPoint in self.points {
//

point
if point == otherPoint {
276
9
continue
}
//

if point.distanceTo(otherPoint) <= maximumDistance {
self.neighbors[point]?.append(otherPoint)
}
}
}
}
//
points

func nearestPoint(to point : CGPoint) -> CGPoint {
var nearestPointSoFar : CGPoint = self.points[0]
var nearestDistanceSoFar = CGFloat.inﬁnity
for node in self.points {
let distance = node.distanceTo(point)
if distance < nearestDistanceSoFar {
nearestDistanceSoFar = distance
nearestPointSoFar = node
}
}
return nearestPointSoFar
}
func pathTo(start: CGPoint, end:CGPoint) -> [CGPoint]? {
//

g

//

var gScores : [CGPoint : CGFloat] = [:]
//

f

=g

+

//

//

var fScores : [CGPoint : CGFloat] = [:]
//
points

start
// end

let startPoint = self.nearestPoint(to: start)
let goalPoint = self.nearestPoint(to: end)
// closedNodes

var closedNodes = Set<CGPoint>()
// openNodes

// f

var openNodes = Set<CGPoint>()

277
//

openNodes.insert(startPoint)
// cameFromMap

//

//

var cameFromMap : [CGPoint : CGPoint] = [:]
//

while openNodes.count > 0 {
//

f

//

set

//

f

//

let currentNode = Array(openNodes).sorted{
(ﬁrst, second) -> Bool in
return fScores[ﬁrst, default: 0] < fScores[second, default: 0]
}.ﬁrst!
//

//

reconstructPath

//

cameFromMap

//

if currentNode == goalPoint {
var path : [CGPoint] = []
path += [start]
path += reconstructPath(cameFromMap: cameFromMap,
currentNode: currentNode)
path += [end]
return path
}
//

open

closed

openNodes.remove(currentNode)
closedNodes.insert(currentNode)
let nodeNeighbors = self.neighbors[currentNode] ?? []
//

for neighbor in nodeNeighbors {
//

//

let tentativeGScore =
(gScores[currentNode] ?? 0.0)
+ currentNode.distanceTo(neighbor)
let tentativeFScore = tentativeGScore
+ currentNode.distanceTo(goalPoint)
//

closed

278
9
//

//

if closedNodes.contains(neighbor)
&& tentativeFScore >=
(fScores[neighbor] ?? 0.0) {
continue
}
//

open

//

//

open
//

//

if openNodes.contains(neighbor)
|| tentativeFScore <
(fScores[neighbor] ?? CGFloat.inﬁnity) {
//

//

cameFromMap[neighbor] = currentNode
//

fScores[neighbor] = tentativeFScore
gScores[neighbor] = tentativeGScore
//

open

//

//

openNodes.insert(neighbor)
}
}
}
//

open

//

//

nil

//

return nil
}
//

cameFromMap

//

cameFromMap

//

cameFrom

func reconstructPath(cameFromMap: [CGPoint:CGPoint],
currentNode:CGPoint) -> [CGPoint] {
if let nextNode = cameFromMap[currentNode] {
return reconstructPath(cameFromMap: cameFromMap,
currentNode: nextNode) + [currentNode]
} else {
return [currentNode]

Get Swift游戏开发经典实例 now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.