274
9
func findPotentialCover(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
}
}
struct NavigationGrid {
//
这个结构中存储了一个
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.infinity
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{
(first, second) -> Bool in
return fScores[first, default: 0] < fScores[second, default: 0]
}.first!
//
如果已经搜索到终点,那么表示搜索结束
//
调用
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.infinity) {
//
将邻近点标记到
//
路径中
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.