Swift Package Index 的标志。Swift Package Index

追踪 Swift 6 严格并发检查在数据竞争安全性方面的采用情况。有多少个 Package 已为 Swift 6 做好准备

当使用 Xcode 项目时

当使用 Swift Package Manager 清单时

选择 package 版本

1.0.1

main


Swift 中的 A* 寻路库

Brad Howes 欢迎通过 GitHub Sponsors 对 AStar 提供支持。 如果您发现此 package 有用,请考虑支持它。




Swift Swift Badge SwiftPM compatible License Badge

AStar - Swift 中的 A* 算法库

AStar 库实现了经典的 A* 寻路算法。 它使用最小优先级队列来管理潜在路径,并按每条路径的已知成本和估计成本排序。 AStar 类将地图相关功能委托给 MapOracle 协议,以确定有效位置以及使用该位置的成本。 MapOracle 的示例可以在 AStarTests.swift 文件中找到。

AStar API 非常基础。 只有一个静态的 find 方法。 以下是其使用示例

let mapData = MapData(data: [
    [.🌊, .🌲, .🌲, .🌲, .🌲, .🌲, .🌲, .🌲],
    [.🌊, .🌲, .🌲, .🌲, .🌲, .🌲, .🌲, .🌲],
    [.🌲, .🌲, .🌲, .🌲, .🗻, .🌲, .🌲, .🌲],
    [.🌲, .🌲, .🗻, .🗻, .🗻, .🗻, .🗻, .🌲],
    [.🌲, .🌲, .🗻, .🌲, .🌲, .🗻, .🌊, .🌊],
    [.🌲, .🌲, .🗻, .🌲, .🗻, .🌲, .🌲, .🌊],
    [.🌊, .🌲, .🗻, .🌲, .🌲, .🌲, .🗻, .🗻],
    [.🌊, .🌲, .🌲, .🌲, .🌲, .🌲, .🗻, .🌲]
])

let start = Coord2D(x: 4, y: 0)
let end = Coord2D(x: 4, y: 4)
func distanceToEnd(position: Coord2D) -> Int { abs(position.x - end.x) + abs(position.y - end.y) }
let path = AStar.find(mapOracle: mapOracle, considerDiagonalPaths: true,
                      heuristicCostCalulator: distancToEnd,
                      start: start, end: end)

你需要提供一个实现了 MapOracle 协议的东西,例如上面的 MapData。 你可以决定是否接受对角线路径,并提供一种估算从地图上的给定点移动到终点的成本的方法(启发式成本)。 起始点和终点完成 find 请求。

你会得到一个 Coord2D 值的可选数组。 如果是 nil,则表示没有找到任何路径。 否则,该数组将包含找到的路径的地图坐标,从 start 开始,到 end 结束。

这是地图以及找到的路径的可视化表示。 起始位置显示为红旗 (🚩),结束位置显示为方格旗 (🏁)。 这两个点之间的路径包含一个冒险者 (🏃)。

let image = mapData.asString(path: path!)
print(image)
🌊🌲🌲🌲🚩🌲🌲🌲
🌊🌲🌲🌲🌲🏃🌲🌲
🌲🌲🌲🌲🗻🌲🏃🌲
🌲🌲🗻🗻🗻🗻🗻🏃
🌲🌲🗻🌲🏁🗻🏃🌊
🌲🌲🗻🌲🗻🏃🌲🌊
🌊🌲🗻🌲🌲🌲🗻🗻
🌊🌲🌲🌲🌲🌲🗻🌲

该地图包含三种不同的地形元素,每种地形元素都有自己的进入正方形的成本

  • 🌲 树 (1)
  • 🌊 水 (2)
  • 🗻 巨石 (∞)

该算法在最小化遍历地形元素的成本的同时,试图保持到目标的最短路径。 为了进行比较,这是当限制为不使用对角线移动时,该算法找到的结果

🌊🌲🌲🌲🚩🌲🌲🌲
🌊🌲🌲🏃🏃🌲🌲🌲
🌲🏃🏃🏃🗻🌲🌲🌲
🌲🏃🗻🗻🗻🗻🗻🌲
🌲🏃🗻🏃🏁🗻🌊🌊
🌲🏃🗻🏃🗻🌲🌲🌊
🌊🏃🗻🏃🌲🌲🗻🗻
🌊🏃🏃🏃🌲🌲🗻🌲

右边还有另一条也是 16 步的路径,但它经过两个 🌊 位置,这使得旅程的总成本增加了 2。 因此,该算法选择了上面显示的路径。