Очень долго в последнее время работаю над созданием интерактивных диаграмм. Одна из задача в таких диаграммах — это правильная прорисовка соединений. Соединения должны обходить препятствия.
Решения всегда разные, но один из самых распространенных случаев — применение алгоритма AStar. Подробно я его описывать не буду. Ибо его описание есть на вики. А цель этой статьи описать более понятный и конкретный алгоритм работы для дальнейшей реализации на Scala.
Предусловия:
- начальная позиция никогда не является препятствием
Алгоритм:
- Проверка на возможность пути (если проверка не успешная то выходим)
- Если начальная и конечная позиции равны, то возвращаем путь из одной вершины
- Если конечная позиция является препятствием, то путь невозможен и поэтому выходим
- В открытый список добавляется первая точка c вычисленными параметрами
- Цикл, пока не достигнем целевой точки
- Ищем в открытом списке (необработанный список) вершину с наименьшим значением эвристической функции F
- Если не нашли то путь невозможен и поэтому выходим
- Если нашли, то раскрываем эту вершину циклом по всем ее соседям:
- Проверяем является ли вершина препятствием. Если да, то переходим к следующей соседней
- Проверяем находится ли вершина в закрытом списке. Если да, то переходим к следующей соседней
- Вычисляем параметры вершины
- Если ее нет в открытом списке, то добавляем ее туда
- Раскрытую вершину удаляем из открытого списка и добавляем в закрытый
- Достигли целевой точки поэтому собираем путь (по параметру parent) и возвращаем его
Абстрактная реализация на Scala:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 |
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, в которой:
- Переопределен метод isAStarObstacle (возвращает true, если вершина является препятствием)
- Переопределить методы hashCode и euals таким образом, чтобы они зависели от координат вершины
- Реализовать класс поля на котором ищется путь с примесью ASTarField, в котором:
- Переопределить методы получения начальной и конечной вершины пути: getSourceNode и getTargetNode
- Переопределить метод получения эвристической функции — getHeuristic
- Переопределить метод итерации по соседним вершинам
Вот пример реализации для сетки, в которой вершины являются квадратными, а соседними вершинами считаются клетки по четырем сторонам:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 |
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 } } |
На последок, совсем ужатая версия AStar.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
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) } |
