Make API more general

[Levi-Lesches]

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

```dart /// 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> { final T parent; AStarTransition(this.parent); } @immutable abstract class AStarState> implements Comparable { // -------------------- Fields -------------------- final int depth; final AStarTransition? 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 getNeighbors(); Queue> reconstructPath() { final path = Queue>(); 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 && other.hashed == hashed; @override String toString() => hashed; @override int compareTo(T other) => score.compareTo(other.score); } ```

The updated A* function

```dart T? aStar>(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((a, b) => a.compareTo(b))..add(start); final opened = {start}; final closed = {}; 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; } ```

[Levi-Lesches]

Closed in #11!