• CHANGELOG.md
• Installing
• Versions
• 24

# A* path finding with Dart #

A simple A* algorithm implemented in Dart. An example of path finding.

Last updated 2013-11.

The original 2D algorithm was ported from this JavaScript example. No effort has been made to optimize it. A more generic A* algorithm was added in November 2013. That one is fairly optimized.

# Example #

There are two separate A* algorithms in this package. One of them, `aStar2D`, is specific to 2D grid maps. The usage can be as simple as:

``````import 'package:a_star/a_star_2d.dart';
main() {
String textMap = """
sooooooo
oxxxxxoo
oxxoxooo
oxoogxxx
""";
Maze maze = new Maze.parse(textMap);
Queue<Tile> solution = aStar2D(maze);
}
``````

The second algorithm is generic and works on any graph (e.g. 3D grids, mesh networks). The usage is best explained with an example (details below):

``````import 'package:a_star/a_star.dart';

class TerrainTile extends Object with Node {
// ...
}
class TerrainMap implements Graph<TerrainTile> {
// Must implement 4 methods.
Iterable<T> get allNodes => /* ... */
num getDistance(T a, T b) => /* ... */
num getHeuristicDistance(T a, T b) => /* ... */
Iterable<T> getNeighboursOf(T node) => /* ... */
}

main() {
var map = new TerrainMap();
var pathFinder = new AStar(map);
var start = /* ... */
var goal = /* ... */
pathFinder.findPath(start, goal)
.then((path) => print("The best path from \$start to \$goal is: \$path"));
}
``````

Explanation: Here, we have a `TerrainMap` of `TerrainTile` nodes. The only requirements are that `TerrainMap` implements `Graph` (4 methods) and `TerrainTile` is extended with the `Node` mixin (no additional work). Then, we can simply instantiate the A* algorithm by `new AStar(map)` and find paths between two nodes by calling the `findPath(start, goal)` method. Normally, we would only create the `AStar` instance once and then reuse it throughout our program. This saves performance.

You can also use `findPathSync(start, goal)` if you don't need to worry about blocking.

All the three classes (`AStar`, `Graph` and `Node`) are well documented in `lib/a_star.dart`. For a complete example, see the minimal unit tests or one of the two generalized benchmarks (`benchmark.dart` or `benchmark_generalized_2d`).

# CHANGES #

## Use this package as a library

### 1. Depend on it

``````
dependencies:
a_star: ^0.3.0

``````

### 2. Install it

You can install packages from the command line:

with pub:

``````
\$ pub get

``````

Alternatively, your editor might support `pub get`. Check the docs for your editor to learn more.

### 3. Import it

Now in your Dart code, you can use:

``````
import 'package:a_star/a_star.dart';
``````
0.3.0 Nov 6, 2013
0.2.0 Oct 14, 2013
0.1.1 Oct 7, 2013
0.1.0 Oct 7, 2013
 Popularity: Describes how popular the package is relative to other packages. [more] 48 Health: Code health derived from static analysis. [more] -- Maintenance: Reflects how tidy and up-to-date the package is. [more] -- Overall: Weighted score of the above. [more] 24

The package version is not analyzed, because it does not support Dart 2. Until this is resolved, the package will receive a health and maintenance score of 0.

#### Analysis issues and suggestions

Support Dart 2 in `pubspec.yaml`.

The SDK constraint in `pubspec.yaml` doesn't allow the Dart 2.0.0 release. For information about upgrading it to be Dart 2 compatible, please see https://www.dartlang.org/dart-2#migration.

#### Maintenance issues and suggestions

Make sure `dartdoc` successfully runs on your package's source files. (-10 points)

Dependencies were not resolved.