Алгоритм AStar на Scala

Очень долго в последнее время работаю над созданием интерактивных диаграмм. Одна из задача в таких диаграммах — это правильная прорисовка соединений. Соединения должны обходить препятствия.

Решения всегда разные, но один из самых распространенных случаев — применение алгоритма AStar. Подробно я его описывать не буду. Ибо его описание есть на вики. А цель этой статьи описать более понятный и конкретный алгоритм работы для дальнейшей реализации на Scala.

Предусловия:

начальная позиция никогда не является препятствием

Алгоритм:

Проверка на возможность пути (если проверка не успешная то выходим)
1. Если начальная и конечная позиции равны, то возвращаем путь из одной вершины
2. Если конечная позиция является препятствием, то путь невозможен и поэтому выходим
В открытый список добавляется первая точка c вычисленными параметрами
Цикл, пока не достигнем целевой точки
1. Ищем в открытом списке (необработанный список) вершину с наименьшим значением эвристической функции F
2. Если не нашли то путь невозможен и поэтому выходим
3. Если нашли, то раскрываем эту вершину циклом по всем ее соседям:
  1. Проверяем является ли вершина препятствием. Если да, то переходим к следующей соседней
  2. Проверяем находится ли вершина в закрытом списке. Если да, то переходим к следующей соседней
  3. Вычисляем параметры вершины
  4. Если ее нет в открытом списке, то добавляем ее туда
4. Раскрытую вершину удаляем из открытого списка и добавляем в закрытый
Достигли целевой точки поэтому собираем путь (по параметру parent) и возвращаем его

Абстрактная реализация на Scala:

package sandbox

import scala.reflect.ClassTag

trait AStarNode {
  var g, h, f: Int = _
  var parent: AStarNode = _
  def isAStarObstacle: Boolean
}

trait HeuristicFunctionTrait[T <: AStarNode] {
  def getDistance(source: T, target: T): Int
  def getCost(source: T, target: T): Int
  def update(source: T, target: T, current: T, neighbour: T) {
    neighbour.g = if (neighbour == current) 0 else getCost(current, neighbour)
    neighbour.h = getDistance(neighbour, target)
    neighbour.f = current.g + current.h
    neighbour.parent = if (neighbour == current) null else current
  }
}

trait AStarField[T <: AStarNode] {

  def getSourceNode: T

  def getTargetNode: T

  def getHeuristic: HeuristicFunctionTrait[T]

  def foreachNeighbour(current: T)(f: T => Unit)

  def path[T: ClassTag]: Array[T] = findPath match {
    case Some(array) => converter(array)
    case None        => converter(Array[AStarNode]())
  }

  private def converter[T: ClassTag](array: Array[AStarNode]): Array[T] = array map (_.asInstanceOf[T])

  private def findPath: Option[Array[AStarNode]] = {
    val source = getSourceNode
    val target = getTargetNode

    if (source == target) return Some(Array(source)) else if (!target.isAStarObstacle) {

      import scala.collection.mutable.HashSet

      val open = new HashSet[T]()
      val close = new HashSet[T]()
      val heuristic = getHeuristic
      heuristic update (source, target, source, source)
      open += (source)
      var current = source
      while (current != target) {

        var nextNode: Option[T] = None
        for (openNode <- open) nextNode match {
          case Some(node) => if (openNode.f < nextNode.get.f) nextNode = Some(openNode)
          case None       => nextNode = Some(openNode)
        }

        nextNode match {
          case Some(node) => current = node
          case None       => return None
        }

        foreachNeighbour(current) { neighbour =>
          if (!(neighbour.isAStarObstacle || close.contains(neighbour))) {
            heuristic update (source, target, current, neighbour)
            if (!open.contains(neighbour)) open += (neighbour)
          }
        }

        open -= (current)
        close += (current)
      }
      return Some {
        def assemblyPath(node: AStarNode): Array[AStarNode] = if (node.parent == null) Array[AStarNode](node) else assemblyPath(node parent) ++ Array[AStarNode](node)
        assemblyPath(current)
      }
    }
    return None
  }

}

package sandbox

import scala.reflect.ClassTag

trait AStarNode {

var g, h, f: Int = _

var parent: AStarNode = _

def isAStarObstacle: Boolean

}

trait HeuristicFunctionTrait[T <: AStarNode] {

def getDistance(source: T, target: T): Int

def getCost(source: T, target: T): Int

def update(source: T, target: T, current: T, neighbour: T) {

neighbour.g = if (neighbour == current) 0 else getCost(current, neighbour)

neighbour.h = getDistance(neighbour, target)

neighbour.f = current.g + current.h

neighbour.parent = if (neighbour == current) null else current

}

trait AStarField[T <: AStarNode] {

def getSourceNode: T

def getTargetNode: T

def getHeuristic: HeuristicFunctionTrait[T]

def foreachNeighbour(current: T)(f: T => Unit)

def path[T: ClassTag]: Array[T] = findPath match {

case Some(array) => converter(array)

case None => converter(Array[AStarNode]())

}

private def converter[T: ClassTag](array: Array[AStarNode]): Array[T] = array map (_.asInstanceOf[T])

private def findPath: Option[Array[AStarNode]] = {

val source = getSourceNode

val target = getTargetNode

if (source == target) return Some(Array(source)) else if (!target.isAStarObstacle) {

import scala.collection.mutable.HashSet

val open = new HashSet[T]()

val close = new HashSet[T]()

val heuristic = getHeuristic

heuristic update (source, target, source, source)

open += (source)

var current = source

while (current != target) {

var nextNode: Option[T] = None

for (openNode <- open) nextNode match {

case Some(node) => if (openNode.f < nextNode.get.f) nextNode = Some(openNode)

case None => nextNode = Some(openNode)

}

nextNode match {

case Some(node) => current = node

case None => return None

}

foreachNeighbour(current) { neighbour =>

if (!(neighbour.isAStarObstacle || close.contains(neighbour))) {

heuristic update (source, target, current, neighbour)

if (!open.contains(neighbour)) open += (neighbour)

}

open -= (current)

close += (current)

}

return Some {

def assemblyPath(node: AStarNode): Array[AStarNode] = if (node.parent == null) Array[AStarNode](node) else assemblyPath(node parent) ++ Array[AStarNode](node)

assemblyPath(current)

}

return None

}

Для конкретной реализации необходимо:

Реализовать класс вершины с примесью ASTarNode, в которой:
1. Переопределен метод isAStarObstacle (возвращает true, если вершина является препятствием)
2. Переопределить методы hashCode и euals таким образом, чтобы они зависели от координат вершины
Реализовать класс поля на котором ищется путь с примесью ASTarField, в котором:
1. Переопределить методы получения начальной и конечной вершины пути: getSourceNode и getTargetNode
2. Переопределить метод получения эвристической функции — getHeuristic
3. Переопределить метод итерации по соседним вершинам

Вот пример реализации для сетки, в которой вершины являются квадратными, а соседними вершинами считаются клетки по четырем сторонам:

package sandbox.t2

class QuadroNode extends AStarNode {

  var x: Int = _
  var y: Int = _

  var isObstacle = false

  var sides = Array.ofDim[QuadroNode](4)

  override def isAStarObstacle = isObstacle

  override def hashCode: Int = (x * y) ^ (x + y)

  override def equals(obj: Any): Boolean = obj match {
    case node: QuadroNode => node.x == x && node.y == y
    case _                => false
  }

  override def toString = if (isObstacle) "1" else "0"

}

class QuadroGrid(val grid: Array[Array[QuadroNode]]) extends AStarField[QuadroNode] {

  var sourceNode: QuadroNode = _

  var targetNode: QuadroNode = _

  override def toString: String = grid map (_ mkString) mkString "n"

  override def getSourceNode = sourceNode

  override def getTargetNode = targetNode

  override def getHeuristic = new HeuristicFunctionTrait[QuadroNode] {
    val LINE_COST = 10
    override def getCost(source: QuadroNode, target: QuadroNode): Int = source.g + LINE_COST
    override def getDistance(source: QuadroNode, target: QuadroNode) = ({ if (target.x > source.x) target.x - source.x else source.x - target.x } + { if (target.y > source.y) target.y - source.y else source.y - target.y }) * LINE_COST
  }

  override def foreachNeighbour(current: QuadroNode)(f: QuadroNode => Unit) = current.sides filter (_ != null) foreach f

}

object AStarQuadroTest {

  def main(args: Array[String]): Unit = {

    var source: QuadroNode = null

    var target: QuadroNode = null

    val parsedGrid: Array[Array[QuadroNode]] = ({
      "S00n" +
      "010n" +
      "01E"
    } toString) split ("n") map { line =>
      (line toCharArray) map { char =>
        val node = new QuadroNode
        if (char == '0' || char == 'S' || char == 'E') node.isObstacle = false else if (char == '1') node.isObstacle = true
        if (char == 'S') source = node else if (char == 'E') target = node
        node
      }
    }

    val grid = Array.ofDim[QuadroNode](parsedGrid(0) length, parsedGrid length)
    for (i <- 0 to grid.length - 1) {
      for (j <- 0 to grid(i).length - 1) {
        grid(i)(j) = parsedGrid(j)(i)
        grid(i)(j) = parsedGrid(j)(i)
      }
    }
    for (i <- 0 to grid.length - 1) {
      for (j <- 0 to grid(i).length - 1) {
        grid(i)(j).x = i
        grid(i)(j).y = j
      }
    }
    for (i <- 0 to grid.length - 1) {
      for (j <- 0 to grid(i).length - 1) {
        val node = grid(i)(j)
        if (i > 0) node.sides(0) = grid(i - 1)(j)
        if (j > 0) node.sides(1) = grid(i)(j - 1)
        if (i + 1 < grid.length) node.sides(2) = grid(i + 1)(j)
        if (j + 1 < grid(i).length) node.sides(3) = grid(i)(j + 1)
      }
    }
    val testGrid = new QuadroGrid(grid)
    testGrid.sourceNode = source
    testGrid.targetNode = target

    val path = testGrid.path
  }

}

package sandbox.t2

class QuadroNode extends AStarNode {

var x: Int = _

var y: Int = _

var isObstacle = false

var sides = Array.ofDim[QuadroNode](4)

override def isAStarObstacle = isObstacle

override def hashCode: Int = (x * y) ^ (x + y)

override def equals(obj: Any): Boolean = obj match {

case node: QuadroNode => node.x == x && node.y == y

case _ => false

}

override def toString = if (isObstacle) "1" else "0"

}

class QuadroGrid(val grid: Array[Array[QuadroNode]]) extends AStarField[QuadroNode] {

var sourceNode: QuadroNode = _

var targetNode: QuadroNode = _

override def toString: String = grid map (_ mkString) mkString "n"

override def getSourceNode = sourceNode

override def getTargetNode = targetNode

override def getHeuristic = new HeuristicFunctionTrait[QuadroNode] {

val LINE_COST = 10

override def getCost(source: QuadroNode, target: QuadroNode): Int = source.g + LINE_COST

override def getDistance(source: QuadroNode, target: QuadroNode) = ({ if (target.x > source.x) target.x - source.x else source.x - target.x } + { if (target.y > source.y) target.y - source.y else source.y - target.y }) * LINE_COST

}

override def foreachNeighbour(current: QuadroNode)(f: QuadroNode => Unit) = current.sides filter (_ != null) foreach f

}

object AStarQuadroTest {

def main(args: Array[String]): Unit = {

var source: QuadroNode = null

var target: QuadroNode = null

val parsedGrid: Array[Array[QuadroNode]] = ({

"S00n" +

"010n" +

"01E"

} toString) split ("n") map { line =>

(line toCharArray) map { char =>

val node = new QuadroNode

if (char == '0' || char == 'S' || char == 'E') node.isObstacle = false else if (char == '1') node.isObstacle = true

if (char == 'S') source = node else if (char == 'E') target = node

node

}

val grid = Array.ofDim[QuadroNode](parsedGrid(0) length, parsedGrid length)

for (i <- 0 to grid.length - 1) {

for (j <- 0 to grid(i).length - 1) {

grid(i)(j) = parsedGrid(j)(i)

}

for (i <- 0 to grid.length - 1) {

for (j <- 0 to grid(i).length - 1) {

grid(i)(j).x = i

grid(i)(j).y = j

}

for (i <- 0 to grid.length - 1) {

for (j <- 0 to grid(i).length - 1) {

val node = grid(i)(j)

if (i > 0) node.sides(0) = grid(i - 1)(j)

if (j > 0) node.sides(1) = grid(i)(j - 1)

if (i + 1 < grid.length) node.sides(2) = grid(i + 1)(j)

if (j + 1 < grid(i).length) node.sides(3) = grid(i)(j + 1)

}

val testGrid = new QuadroGrid(grid)

testGrid.sourceNode = source

testGrid.targetNode = target

val path = testGrid.path

}

На последок, совсем ужатая версия AStar.

package sandbox.astar.generic

import scala.reflect.ClassTag
import scala.collection.mutable.HashSet

trait AStarNode {
  var g, h, f: Int = _
  var parentAStar: AStarNode = _
  def isAStarObstacle: Boolean
}

trait HeuristicFunctionTrait[T <: AStarNode] {
  def getDistance(source: T, target: T): Int
  def getCost(source: T, target: T): Int
  final def update(source: T, target: T, current: T, neighbour: T) {
    neighbour.g = if (neighbour == current) 0 else getCost(current, neighbour)
    neighbour.h = getDistance(neighbour, target)
    neighbour.f = current.g + current.h
    neighbour.parentAStar = if (neighbour == current) null else current
  }
}

trait AStarField[T <: AStarNode] {

  var sourceNode, targetNode: T = _

  val heuristic: HeuristicFunctionTrait[T]

  def foreachNeighbour(current: T)(f: T => Unit)

  def path[T: ClassTag]: Array[T] = findPath match {
    case Some(array) => array map (_.asInstanceOf[T])
    case None        => Array[T]()
  }

  private def findPath: Option[Array[AStarNode]] = if (sourceNode == targetNode) return Some(Array(sourceNode)) else if (!targetNode.isAStarObstacle) {
    val open = new HashSet[T]()
    val close = new HashSet[T]()
    heuristic update (sourceNode, targetNode, sourceNode, sourceNode)
    open += (sourceNode)
    var current = sourceNode
    while (current != targetNode) if (open.size > 0) {

      current = open minBy (_.f)

      foreachNeighbour(current)(neighbour => if (!neighbour.isAStarObstacle && !close.contains(neighbour)) {
        heuristic update (sourceNode, targetNode, current, neighbour)
        if (!open.contains(neighbour)) open += (neighbour)
      })

      open -= (current)
      close += (current)

    } else return None

    return Some(assemblyPath(current))
  } else None

  private def assemblyPath(node: AStarNode): Array[AStarNode] = if (node.parentAStar == null) Array[AStarNode](node) else assemblyPath(node parentAStar) ++ Array[AStarNode](node)

}

package sandbox.astar.generic

import scala.reflect.ClassTag

import scala.collection.mutable.HashSet

trait AStarNode {

var g, h, f: Int = _

var parentAStar: AStarNode = _

def isAStarObstacle: Boolean

}

trait HeuristicFunctionTrait[T <: AStarNode] {

def getDistance(source: T, target: T): Int

def getCost(source: T, target: T): Int

final def update(source: T, target: T, current: T, neighbour: T) {

neighbour.g = if (neighbour == current) 0 else getCost(current, neighbour)

neighbour.h = getDistance(neighbour, target)

neighbour.f = current.g + current.h

neighbour.parentAStar = if (neighbour == current) null else current

}

trait AStarField[T <: AStarNode] {

var sourceNode, targetNode: T = _

val heuristic: HeuristicFunctionTrait[T]

def foreachNeighbour(current: T)(f: T => Unit)

def path[T: ClassTag]: Array[T] = findPath match {

case Some(array) => array map (_.asInstanceOf[T])

case None => Array[T]()

}

private def findPath: Option[Array[AStarNode]] = if (sourceNode == targetNode) return Some(Array(sourceNode)) else if (!targetNode.isAStarObstacle) {

val open = new HashSet[T]()

val close = new HashSet[T]()

heuristic update (sourceNode, targetNode, sourceNode, sourceNode)

open += (sourceNode)

var current = sourceNode

while (current != targetNode) if (open.size > 0) {

current = open minBy (_.f)

foreachNeighbour(current)(neighbour => if (!neighbour.isAStarObstacle && !close.contains(neighbour)) {

heuristic update (sourceNode, targetNode, current, neighbour)

if (!open.contains(neighbour)) open += (neighbour)

})

open -= (current)

close += (current)

} else return None

return Some(assemblyPath(current))

} else None

private def assemblyPath(node: AStarNode): Array[AStarNode] = if (node.parentAStar == null) Array[AStarNode](node) else assemblyPath(node parentAStar) ++ Array[AStarNode](node)

}

inaword

Блог о разработке и современных технологиях

Алгоритм AStar на Scala

Алгоритм AStar на Scala

Читайте также