A JVM (Scala / Java) implementation of A* (A Star), parametric in the possible states and transitions.

Standard implementations of A* are defined on a 2D map with a fixed set of commands for navigation. In contrast, this implementation is fully parametric (unaware) of the used "map"-structure and "commands". To guide the search algorithm the Engine (or JEngine for Java respectively) interface has to be implemented, repeated here for convenience:

trait Engine[State, Command] {
  // State related
  def valid(self: State): Boolean
  def bisimilar(self: State, other: State): Boolean
  def hash(self: State): Int
  def transition(state: State, cmd: Command): State

  // Available commands
  def commands: List[Command]

  // Heuristics
  def distance(fst: State, other: State): Double
}

The common A* algorithm can be recovered, by instantiating State = (Int, Int) and Command with the desired set of commands, whose behaviour is implemented in transition. The map structure then will be implemented by validity of positions in valid. Usually bisimilar = equals and hash = hashCode. However, also more complex equalities can be implemented like symmetry of rotations.

This project is hosted on sonatype and synchronized to Maven Central. You can use sbt or maven to add parametrized A* to your dependencies.

In build.sbt:

resolvers ++= Seq(
  Resolver.sonatypeRepo("releases"),
  Resolver.sonatypeRepo("snapshots")
)

libraryDependencies += "de.b-studios" %% "parametric-a-star" % "0.1"

In pom.xml:

<dependencies>
    <dependency>
      <groupId>de.b-studios</groupId>
      <artifactId>parametric-a-star_2.11</artifactId>
      <version>0.1</version>
    </dependency>
</dependencies>

For example usages see for instance this Scala file or this Java file.