a_star 0.3.0

  • README.md
  • CHANGELOG.md
  • Installing
  • Versions
  • 0

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.

See LICENSE file for license details.

See running example at http://sethladd.github.io/dart-a-star/deploy/

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).

Reporting bugs

Please file bugs at https://github.com/sethladd/dart-a-star/issues

Contributors

CHANGES

0.2.0

Use this package as a library

1. Depend on it

Add this to your package's pubspec.yaml file:


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';
  
Version Uploaded Documentation Archive
0.3.0 Nov 6, 2013 Go to the documentation of a_star 0.3.0 Download a_star 0.3.0 archive
0.2.0 Oct 14, 2013 Go to the documentation of a_star 0.2.0 Download a_star 0.2.0 archive
0.1.1 Oct 7, 2013 Go to the documentation of a_star 0.1.1 Download a_star 0.1.1 archive
0.1.0 Oct 7, 2013 Go to the documentation of a_star 0.1.0 Download a_star 0.1.0 archive
Popularity:
Describes how popular the package is relative to other packages. [more]
0
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]
0
Learn more about scoring.

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.

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: 'Tile.==' ('(Tile) → bool') isn't a valid override 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

Add SDK constraint in pubspec.yaml. (-50 points)

For information about setting SDK constraint, please see https://www.dartlang.org/tools/pub/pubspec#sdk-constraints.

Fix platform conflicts. (-20 points)

Error(s) prevent platform classification:

Error(s) in lib/a_star_2d.dart: 'Tile.==' ('(Tile) → bool') isn't a valid override of 'Object.==' ('(dynamic) → bool').

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.

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