A* path finding with Dart

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

Last updated 2021-12-29.

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 an (old) 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

Make API more general

Hi, I was working on a color sort game in Flutter and tried to use this package to provide hints but didn't find the API very comfortable as it seems to be more based on a grid of actual locations and doesn't generalize well to abstract states.

Here's the core of my API:

@immutable
abstract class AStarState<T extends AStarState<T>> {
  /// A compact but unique string representation. Used for debug printing and avoiding duplicate states.
  String hash();

  /// Whether the algorithm should stop when it gets to this state. Could be a destination, win state, or simply a heuristic threshold.
  bool isGoal();

  /// Calculates the heuristic distance to the goal state.
  int calculateHeuristic();

  /// Gets states that are reachable from just one action from this state (eg, one move, one turn, one step)
  Iterable<T> getNeighbors();
}

Using these methods instead, I was able to get an API better suited to abstract planning rather than specifically path planning. Specifically, the requirement to iterate over all possible states (Graph.allNodes) in this package was prohibitively expensive and maybe not possible. Additionally, methods like Graph.getDistance(a, b) don't generalize well to, say, a game, where planning to get from one state to the next is the hard part and can't easily be calculated without re-running A*. Also, putting these methods directly on the state helped keep the API tight.

I'd be happy to submit a PR with this API and update docs/examples. If that's not wanted I can publish another package, but I wanted to avoid proliferating the ecosystem with more packages than needed, especially because this already has the name a_star.

The rest of the API

/// While this could be a simple "parent" field, it's left as a class so one can subclass it and annotate
/// how to get from one state to another. In physical pathfinding, this isn't as important, but in problem
/// solving, this is often the important part. 
class AStarTransition<T extends AStarState<T>> {
  final T parent;
  AStarTransition(this.parent);
}

@immutable
abstract class AStarState<T extends AStarState<T>> implements Comparable<T> {
  // -------------------- Fields --------------------

  final int depth;
  final AStarTransition<T>? transition;
  late final int heuristic;
  late final String hashed;
  AStarState({required this.transition, required this.depth}) {
    heuristic = calculateHeuristic();
    hashed = hash();
  }

  int get score => depth + heuristic;

  // -------------------- A* methods --------------------

  String hash();
  bool isGoal();
  int calculateHeuristic();
  Iterable<T> getNeighbors();

  Queue<AStarTransition<T>> reconstructPath() {
    final path = Queue<AStarTransition<T>>();
    var current = transition;
    while (current != null) {
      path.addFirst(current);
      current = current.parent.transition;
    }
    return path;
  }

  // -------------------- Common overrides --------------------

  @override
  int get hashCode => hashed.hashCode;

  @override
  bool operator ==(Object other) => other is AStarState<T> && other.hashed == hashed;

  @override
  String toString() => hashed;

  @override
  int compareTo(T other) => score.compareTo(other.score);
}

The updated A* function

T? aStar<T extends AStarState<T>>(T start, {bool verbose = false, int limit = 1000}) {
  // A* states _do_ implement [Comparable], but if this comparison function isn't provided,
  // that is checked at runtime for every element, which slows things down.
  // See https://pub.dev/documentation/collection/latest/collection/PriorityQueue/PriorityQueue.html
  final open = PriorityQueue<T>((a, b) => a.compareTo(b))..add(start);
  final opened = <T>{start};
  final closed = <T>{};
  var count = 0;
  
  while (open.isNotEmpty) {
    final node = open.removeFirst();
    if (verbose) print("[$count] Exploring: ${node.hashed}");  // ignore: avoid_print
    opened.remove(node);
    closed.add(node);
    if (node.isGoal()) {
      return node;
    }
    for (final neighbor in node.getNeighbors()) {
      if (count++ >= limit) {
        if (verbose) print("ABORT: Hit A* limit");  // ignore: avoid_print
        return null;
      }
      if (closed.contains(neighbor)) continue;
      if (opened.contains(neighbor)) continue;
      if (verbose) print("[$count]   Got: ${neighbor.hashed}");  // ignore: avoid_print
      open.add(neighbor);
      opened.add(neighbor);
    }
  }
  return null;
}

sethladd / dart-a-star Goto Github PK

dart-a-star's Introduction

A* path finding with Dart

Example

Reporting bugs

Contributors

dart-a-star's People

Contributors

Stargazers

Watchers

Forkers

dart-a-star's Issues

Recommend Projects

Recommend Topics

Recommend Org