• CHANGELOG.md
• Installing
• Versions
• 22

# 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

``````

with Flutter:

``````
\$ flutter packages get

``````

Alternatively, your editor might support `pub get` or `flutter packages 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] 0 Health: Code health derived from static analysis. [more] 75 Maintenance: Reflects how tidy and up-to-date the package is. [more] 0 Overall: Weighted score of the above. [more] 22

We analyzed this package on Oct 22, 2018, and provided a score, details, and suggestions below. Analysis was completed with status completed using:

• Dart: 2.0.0
• pana: 0.12.4

#### Platforms

Detected platforms: Flutter, web, other

No platform restriction found in primary library `package:a_star/a_star.dart`.

#### Health issues and suggestions

Fix `lib/a_star_2d.dart`. (-25.38 points)

Analysis of `lib/a_star_2d.dart` failed with 1 error, 1 hint:

line 94 col 3: Invalid override. The type of 'Tile.==' ('(Tile) → bool') isn't a subtype of 'Object.==' ('(dynamic) → bool').

line 125 col 10: The value of the local variable 'f' isn't used.

Format `lib/a_star.dart`.

Run `dartfmt` to format `lib/a_star.dart`.

#### Maintenance issues and suggestions

Running `dartdoc` failed. (-10 points)

Make sure `dartdoc` runs without any issues.

Package is too old. (-100 points)

The package was released more than two years ago.

Add SDK constraint in `pubspec.yaml`. (-5 points)

The description is too short. (-20 points)

Add more detail about the package, what it does and what is its target use case. Try to write at least 60 characters.

Maintain an example. (-10 points)

Create a short demo in the `example/` directory to show how to use this package. Common file name patterns include: `main.dart`, `example.dart` or you could also use `a_star.dart`.

#### Dependencies

Package Constraint Resolved Available
Dev dependencies
benchmark_harness any
browser any
unittest any