Brad Howes 欢迎通过 GitHub Sponsors 对 AStar 提供支持。 如果您发现此 package 有用,请考虑支持它。
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。 因此,该算法选择了上面显示的路径。