astar

astar.scala

@tailrec
final def aStarSearch(queue: PriorityQueue[(State, List[Move])], explored: Set[State]): Option[List[Move]] =
  if (queue.length == 0) return None
  else {
    val (state, history) = queue.dequeue
    if (state == goalState) Some(history)
    else {
      if (!explored(state)) {
        val children = Move.availableStates(state, moves, history, explored)
        queue ++= children
        aStarSearch(queue, explored + state)
      } else
        aStarSearch(queue, explored)
    }
  }