Swiftpack.co - bradhowes/astar as Swift Package

Swiftpack.co is a collection of thousands of indexed Swift packages. Search packages.
bradhowes/astar
A* path finding library in Swift
.package(url: "https://github.com/bradhowes/astar.git", from: "1.0.1")

Swift Swift Badge SwiftPM compatible License Badge

AStar - an A* Library in Swift

The AStar library implements the classic A* path-finding algorithm. It uses a min priority queue for managing potential paths, ordered by each path's known and estimated cost. The AStar class delegates map-related functionality to a MapOracle protocol to determine valid positions as well as the cost of using a position. Example of a MapOracle can be found in the AStarTests.swift file.

The AStar API is very basic. There is just the static find method. Here is an example of it being used:

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)

You supply something that implements the MapOracle protocol like the MapData above. You decide if diagonal paths are acceptable, and provide a way to estimate the cost of moving from a given point on the map to the end point (the heuristic cost). The start and end points complete the find request.

You get back an optional array of Coord2D values. If nil then there was no path to be found. Otherwise, the array will have the map coordinates of the path that was found, starting at start and ending with end.

Here is the visual representation of the map with the found path. The starting position appears as a red flag (🚩) and the end position is a checkered flag (🏁). The path in between these two points contains an adventurer (πŸƒ).

let image = mapData.asString(path: path!)
print(image)
🌊🌲🌲🌲🚩🌲🌲🌲
πŸŒŠπŸŒ²πŸŒ²πŸŒ²πŸŒ²πŸƒπŸŒ²πŸŒ²
πŸŒ²πŸŒ²πŸŒ²πŸŒ²πŸ—»πŸŒ²πŸƒπŸŒ²
πŸŒ²πŸŒ²πŸ—»πŸ—»πŸ—»πŸ—»πŸ—»πŸƒ
πŸŒ²πŸŒ²πŸ—»πŸŒ²πŸπŸ—»πŸƒπŸŒŠ
πŸŒ²πŸŒ²πŸ—»πŸŒ²πŸ—»πŸƒπŸŒ²πŸŒŠ
πŸŒŠπŸŒ²πŸ—»πŸŒ²πŸŒ²πŸŒ²πŸ—»πŸ—»
πŸŒŠπŸŒ²πŸŒ²πŸŒ²πŸŒ²πŸŒ²πŸ—»πŸŒ²

The map contains three different terrain elements, each with their own cost for travelling into their square:

  • 🌲 tree (1)
  • 🌊 water (2)
  • πŸ—» boulder (∞)

The algorithm minimizes the cost of traveling over terrain elements while at the same time trying to keep to the shortest path to the goal. For comparison, here is what the algorithm found when constrained to not use diagonal moves:

🌊🌲🌲🌲🚩🌲🌲🌲
πŸŒŠπŸŒ²πŸŒ²πŸƒπŸƒπŸŒ²πŸŒ²πŸŒ²
πŸŒ²πŸƒπŸƒπŸƒπŸ—»πŸŒ²πŸŒ²πŸŒ²
πŸŒ²πŸƒπŸ—»πŸ—»πŸ—»πŸ—»πŸ—»πŸŒ²
πŸŒ²πŸƒπŸ—»πŸƒπŸπŸ—»πŸŒŠπŸŒŠ
πŸŒ²πŸƒπŸ—»πŸƒπŸ—»πŸŒ²πŸŒ²πŸŒŠ
πŸŒŠπŸƒπŸ—»πŸƒπŸŒ²πŸŒ²πŸ—»πŸ—»
πŸŒŠπŸƒπŸƒπŸƒπŸŒ²πŸŒ²πŸ—»πŸŒ²

There is another path to the right that is also 16 moves, but it goes over two 🌊 positions which increases the total cost of the trip by 2. Thus the algorithm chose the one shown above.

GitHub

link
Stars: 1
Last commit: 4 weeks ago

Ad: Job Offers

iOS Software Engineer @ Perry Street Software
Perry Street Software is Jack’d and SCRUFF. We are two of the world’s largest gay, bi, trans and queer social dating apps on iOS and Android. Our brands reach more than 20 million members worldwide so members can connect, meet and express themselves on a platform that prioritizes privacy and security. We invest heavily into SwiftUI and using Swift Packages to modularize the codebase.

Submit a free job ad (while I'm testing this). The analytics numbers for this website are here.

Swiftpack is being maintained by Petr Pavlik | @ptrpavlik | @swiftpackco | API | Analytics