dev1an/a-star

A* pathfinding library in Swift.

A-Star

Protocol oriented A* (A star) pathfinding algorithm implementation in Swift 5 (Playground included).

Add pathfinding to your graph just by implementing the 3 requirements of the Graph protocol.

Playground

• To use the playground: open AStar.xcodeproj
• Build the macOS framework (select the AStar macOS targer and press command + b)
• Click on Playground.playground

Swift Package Manager

You can now add this package to your project using SPM 🎉

Using Xcode

Xcode 11 has a new interface to include packages into your existing projects.

• Click File → Swift Packages → Add Package Dependency...
• Search for AStar and select this repository.
• Follow the on screen instructions

Manualy editing package file

To include it in your package manually, add the following dependency to your Package.swift file.

.package(url: "https://github.com/Dev1an/A-Star.git", .branch("master"))

Use import AStar to access the APIs.

a-star's Issues

The path found by findPath can vary from run to run, probably due to nodesAdjacent returning a Set rather than a NSOrderedSet.

I used A-Star to write a "Hitman Go" level solver:

https://jackpal.github.io/2022/04/29/A_Solver_for_Hitman_Go_Levels.html

A-Star worked well for me. Thanks for providing it!

However, I ran into an issue when writing unit tests: For many game levels, the path returned by findPath varies from run to run of the test. For example a diagonal path on a 2D grid might return North, East on one run, and East, North on the next run.

After thinking about it, I think the reason for this variation is that the GraphNode nodesAdjacent func returns a Set rather than a NSOrderedSet. Set doesn't guarantee an iteration order for its elements. So I think even though my app always inserts nodes into the set the same order, when A-Star iterates over the set of elements, it will iterate over them in random order.

It would be better (in terms of being able to reproduce results) if GraphNode nodesAdjacent either returned a NSOrderedSet, or even just a plain Array.

(I think I can work around the issue by slightly biasing my edge weights in a checkerboard pattern, but it seems like the problem will hit other users too, so you might want to fix it.)

Cant Run It

Hello Sorry, for saying this as an issue, but didn't know how tot talk to you, I don't know how to run and test your code, I have dowloaded it, open it on Xcode and click play, but it doesn't open anything(I have iOs experience, but never scene a Xcode project that builds to My Mac )

Playground does not compile in Xcode 11.5

☝️

Enhancement -

Just watched this
https://youtu.be/gGQ-vAmdAOI?t=171

was thinking of extending some of the classes to handle other use cases.

It isn’t clear what nodes the cost function will be called on...

So the doc comments on the cost don’t make it clear that it is only called on adjacent nodes (and I’m mostly guessing this is true). It is probably important to note because local costs can be easy to do exactly, but it can be much harder to do no -local costs!

So it would be nice if cost noted it only is passed adjacent nodes, and estimatedCost notes it can be asked to estimate a cost to any node.