Поиск пути A*.
Запись от ZackMercury размещена 27.06.2017 в 21:31
Вступление.
Давайте поговорим о дискретной математике. Если вы впервые слышите это словосочетание, то, скорее всего, вы испугались, но здесь нет ничего сложного.
А* - это алгоритм, который ищет путь от одной точки до другой. Давайте представим, что мы смотрим на карту шоссе, где точки - города.

Цифры на шоссе - это длина дороги, или то, что мы будем считать за "стоимость" пути.
В дискретной математике, это называется графом, и выглядит примерно вот так, за исключением того, что, как правило, пункты обозначаются буквами:

Постановка задачи.
Наша задача здесь - найти путь с найменьшей стоимостью из одного любого пункта в другой.
Анализ определения.
Давайте взглянем на определение А* в Википедии:
Цитата:
Поиск A* (произносится «А звезда» или «А стар», от англ. A star) — в информатике и математике, алгоритм поиска по первому наилучшему совпадению на графе, который находит маршрут с наименьшей стоимостью от одной вершины (начальной) к другой (целевой, конечной).
О чём это мы?
Давайте взглянем на граф и подумаем, как мы сами определяем самое короткое расстояние.

Нет! Тоесть, это плохой пример графа, ведь расстояния здесь не соответствуют граням.
Давайте поищу что-нибудь более подходящее...
Хорошо, давайте возьмём вот такой пример:

Пусть нам нужно попасть из b в d, и тут мы сразу определяем на глаз, что путь bcd короче пути bacd.
Как мы это делаем? Ну, на самом деле тут 2 способа мыслить, первый - в пути bacd больше букв, чем в пути bcd. Но всегда ли верно то, что такой путь будет короче? Что, если мы попробуем добраться из а в d по пути aed вместо abcd?

Ну и второй способ думать об этом - это то, что наши глаза сначала ищут пункты, по путям, которые смотрят в сторону цели, и только потом, не найдя пути по прямой, они ищут обходные. Наконец, приведя к этой мысли, я признаюсь, что именно так и работает алгоритм A*.
Он двигается в сторону цели, по пути считая стоимость пути из начальной в эту точку, суммируя эту стоимость с предполагаемой стоимостью до пути(тоесть, расстоянием до целевой точки), и проверяет соседей. Наконец, найдя соседа, сумма стоимости пути в данную точку + оценка пути до конечной является минимальной, она переходит в него, попутно добавляя остальных в очередь, которая нужна при условии, что данный путь является тупиком. Только убедившись, что данный путь тупиковый, алгоритм возвращается назад и берёт следующего наиболее оптимального соседа. Расстояние до конечной точки как правило определяется с помощью эвклидового расстояния.

Демонстрация работы.


Псевдокод из википедии
Цитата:
function A*(start, goal)
. // Набор вершин, уже пройденных
. closedSet := {}
.
. // Набор только известных вершин, ещё не пройденных
. // Изначально, известна только стартовая вершина
. openSet := {start}
. // Для каждой вершины, из какой вершины путь к ней будет самым эффективным.
. // Если вершина может быть достигнута из многих, cameFrom будет в конечном счёте хранить
. // самый эффективный предыдущий шаг.
. cameFrom := the empty map
. // Для каждой вершины, стоимость путешествия из начальной вершины в эту.
. gScore := map with default value of Infinity
.
. // Стоимость путешествия из стартовой в стартовую - 0.
. gScore[start] := 0
.
. // Для каждой вершины, общая стоимость путешествия из начальной вершины к цели
. // проходя через эту вершины. Это значение частично известное, частично эвристическое.
. fScore := map with default value of Infinity
.
. // Для начальной вершины, это значение полностью эвристическое.
. fScore[start] := heuristic_cost_estimate(start, goal)
.
. while openSet is not empty // пока открытый набор не пуст
. . current := the node in openSet having the lowest fScore[] value //текущая = вершина в открытом наборе с самым низким значением fScore
. . if current = goal //если текущая - целевая
. . . return reconstruct_path(cameFrom, current) //вернуть путь
. .
. . openSet.Remove(current) // Убрать текущую из открытого набора
. . closedSet.Add(current) // Добавить текущую в закрытый набор
. .
. . for each neighbor of current // Для каждого соседа текущей
. . . if neighbor in closedSet // если сосед находится в закрытом списке
. . . . continue // Игнорируем соседа, который уже просчитан
. . .
. . . if neighbor not in openSet // Открываем новую вершину
. . . . openSet.Add(neighbor)
. . .
. . . // Расстояние от стартовой вершины к соседу
. . . tentative_gScore := gScore[current] + dist_between(current, neighbor)
. . . if tentative_gScore >= gScore[neighbor]
. . . . continue // Это не лучший путь.
. . .
. . . // Этот путь - лучший на данный момент. Запишем его!
. . . cameFrom[neighbor] := current
. . . gScore[neighbor] := tentative_gScore
. . . fScore[neighbor] := gScore[neighbor] + heuristic_cost_estimate(neighbor, goal)
.
. return failure
.
function reconstruct_path(cameFrom, current)
. total_path := [current]
. while current in cameFrom.Keys:
. . current := cameFrom[current]
. . total_path.append(current)
. return total_path
. // Набор вершин, уже пройденных
. closedSet := {}
.
. // Набор только известных вершин, ещё не пройденных
. // Изначально, известна только стартовая вершина
. openSet := {start}
. // Для каждой вершины, из какой вершины путь к ней будет самым эффективным.
. // Если вершина может быть достигнута из многих, cameFrom будет в конечном счёте хранить
. // самый эффективный предыдущий шаг.
. cameFrom := the empty map
. // Для каждой вершины, стоимость путешествия из начальной вершины в эту.
. gScore := map with default value of Infinity
.
. // Стоимость путешествия из стартовой в стартовую - 0.
. gScore[start] := 0
.
. // Для каждой вершины, общая стоимость путешествия из начальной вершины к цели
. // проходя через эту вершины. Это значение частично известное, частично эвристическое.
. fScore := map with default value of Infinity
.
. // Для начальной вершины, это значение полностью эвристическое.
. fScore[start] := heuristic_cost_estimate(start, goal)
.
. while openSet is not empty // пока открытый набор не пуст
. . current := the node in openSet having the lowest fScore[] value //текущая = вершина в открытом наборе с самым низким значением fScore
. . if current = goal //если текущая - целевая
. . . return reconstruct_path(cameFrom, current) //вернуть путь
. .
. . openSet.Remove(current) // Убрать текущую из открытого набора
. . closedSet.Add(current) // Добавить текущую в закрытый набор
. .
. . for each neighbor of current // Для каждого соседа текущей
. . . if neighbor in closedSet // если сосед находится в закрытом списке
. . . . continue // Игнорируем соседа, который уже просчитан
. . .
. . . if neighbor not in openSet // Открываем новую вершину
. . . . openSet.Add(neighbor)
. . .
. . . // Расстояние от стартовой вершины к соседу
. . . tentative_gScore := gScore[current] + dist_between(current, neighbor)
. . . if tentative_gScore >= gScore[neighbor]
. . . . continue // Это не лучший путь.
. . .
. . . // Этот путь - лучший на данный момент. Запишем его!
. . . cameFrom[neighbor] := current
. . . gScore[neighbor] := tentative_gScore
. . . fScore[neighbor] := gScore[neighbor] + heuristic_cost_estimate(neighbor, goal)
.
. return failure
.
function reconstruct_path(cameFrom, current)
. total_path := [current]
. while current in cameFrom.Keys:
. . current := cameFrom[current]
. . total_path.append(current)
. return total_path
Начнём с построения графа. Здесь я не буду объяснять, какой код и что делает, я сфокусируюсь на конкретно алгоритме А*, поэтому, если вы новичок, и вам что-либо непонятно - не стесняйтесь спрашивать в комментариях. Если же вам непонятно всё - тогда купите себе книжку по AS3, например.
package com.zackmercury.test { import flash.display.Sprite; import flash.events.Event; /** * ... * @author ZackMercury */ public class Node extends Sprite { private var neighbours:Vector.<Node> = new Vector.<Node>(); public function Node() { super(); addEventListener(Event.ADDED_TO_STAGE, init); } public function connect(neighbour:Node):void { if (neighbours.indexOf(neighbour) < 0) //если в массиве ещё нет такого соседа, neighbours.push(neighbour);//добавить его в массив } private function draw():void { graphics.beginFill(0xFFAA22); graphics.drawCircle(0, 0, 5); } private function init(e:Event):void { draw(); } } } package com.zackmercury.test { import flash.display.Sprite; import flash.events.Event; import flash.events.MouseEvent; import flash.geom.Point; /** * ... * @author ZackMercury */ public class Main extends Sprite { public static const W:int = 640, H:int = 480; private var drawBegin:Node; private var drawEnd:Node; public function Main() { if (stage) init(); else addEventListener(Event.ADDED_TO_STAGE, init); } private function init(e:Event = null):void { removeEventListener(Event.ADDED_TO_STAGE, init); // entry point stage.addEventListener(MouseEvent.CLICK, onStageClick); } private function onStageClick(e:MouseEvent):void { if (e.target is Node) return; var n:Node = new Node(); addChild(n); n.x = e.stageX; n.y = e.stageY; n.addEventListener(MouseEvent.MOUSE_DOWN, onNodeDown); n.addEventListener(MouseEvent.MOUSE_UP, onNodeUp); } private function onNodeUp(e:MouseEvent):void { var n:Node = e.currentTarget as Node; drawEnd = n; graphics.lineStyle(2, 0); graphics.moveTo(drawBegin.x, drawBegin.y); graphics.lineTo(drawEnd.x, drawEnd.y); drawBegin.connect(drawEnd); drawEnd.connect(drawBegin); } private function onNodeDown(e:MouseEvent):void { var n:Node = e.currentTarget as Node; drawBegin = n; } } }
Добавим функционал выбора начала и конца пути, чтобы быть готовыми к поиску пути:
package com.zackmercury.test { import flash.display.Sprite; import flash.events.Event; /** * ... * @author ZackMercury */ public class Node extends Sprite { public static const BEGIN_NODE:int = 2; public static const END_NODE:int = 3; public static const CURRENT_NODE:int = 1; public static const IDLE_NODE:int = 0; private var neighbours:Vector.<Node> = new Vector.<Node>(); private var _role:int = IDLE_NODE; public function Node() { super(); addEventListener(Event.ADDED_TO_STAGE, init); } public function connect(neighbour:Node):void { if (neighbours.indexOf(neighbour) < 0) neighbours.push(neighbour); } private function draw():void { graphics.clear(); switch(_role) { case IDLE_NODE: graphics.beginFill(0xFFAA22); break; case BEGIN_NODE: graphics.beginFill(0x22FFAA); break; case CURRENT_NODE: graphics.beginFill(0x22FFAA); break; case END_NODE: graphics.beginFill(0xFF3322); break; } graphics.drawCircle(0, 0, 5); } private function init(e:Event):void { draw(); } public function get role():int { return _role; } public function set role(value:int):void { _role = value; draw(); } } } package com.zackmercury.test { import flash.display.Sprite; import flash.events.Event; import flash.events.MouseEvent; import flash.geom.Point; /** * ... * @author ZackMercury */ public class Main extends Sprite { public static const W:int = 640, H:int = 480; private var drawBegin:Node; private var drawEnd:Node; private var beginNode:Node; private var endNode:Node; public function Main() { if (stage) init(); else addEventListener(Event.ADDED_TO_STAGE, init); } private function init(e:Event = null):void { removeEventListener(Event.ADDED_TO_STAGE, init); // entry point stage.addEventListener(MouseEvent.CLICK, onStageClick); } private function onStageClick(e:MouseEvent):void { if (e.target is Node) return; var n:Node = new Node(); addChild(n); n.x = e.stageX; n.y = e.stageY; n.addEventListener(MouseEvent.MOUSE_DOWN, onNodeDown); n.addEventListener(MouseEvent.MOUSE_UP, onNodeUp); } private function onNodeUp(e:MouseEvent):void { var n:Node = e.currentTarget as Node; drawEnd = n; if (!drawBegin || (drawBegin == drawEnd)) return; graphics.lineStyle(2, 0); graphics.moveTo(drawBegin.x, drawBegin.y); graphics.lineTo(drawEnd.x, drawEnd.y); drawBegin.connect(drawEnd); drawEnd.connect(drawBegin); drawBegin = null; drawEnd = null; } private function onNodeDown(e:MouseEvent):void { var n:Node = e.currentTarget as Node; if (e.ctrlKey) { if (beginNode) beginNode.role = Node.IDLE_NODE; beginNode = n; n.role = Node.BEGIN_NODE; return; } else if (e.altKey) { if (endNode) endNode.role = Node.IDLE_NODE; endNode = n; n.role = Node.END_NODE; return; } drawBegin = n; } } }
Таким образом, теперь мы можем приступать к написанию алгоритма и смотреть на результат.
Хочу сразу объяснить, что такое fScore, а что такое gScore. gScore - это стоимость пройденного пути из начальной вершины в текущую. Тоесть, сумма всех пройденных расстояний. fScore - это gScore + расстояние от текущей вершины в конечную.
f(n) = g(n) + h(n);
f-full costg-cost to the current node /* who knows, what stands for G, let me know in the comments, please */
h-heuristic cost
И теперь показываю код, чтобы вы заметили, какие изменения были добавлены для работы алгоритма.
package com.zackmercury.test { import flash.display.Sprite; import flash.events.Event; /** * ... * @author ZackMercury */ public class Node extends Sprite { public static const BEGIN_NODE:int = 2; public static const END_NODE:int = 3; public static const PATH_NODE:int = 4; public static const CURRENT_NODE:int = 1; public static const IDLE_NODE:int = 0; public var neighbours:Vector.<Node> = new Vector.<Node>(); public var parentNode:Node; public var g:Number = Infinity; public var f:Number = Infinity; public var h:Number = Infinity; private var _role:int = IDLE_NODE; public function Node() { super(); addEventListener(Event.ADDED_TO_STAGE, init); } public function connect(neighbour:Node):void { if (neighbours.indexOf(neighbour) < 0) neighbours.push(neighbour); } private function draw():void { graphics.clear(); switch(_role) { case IDLE_NODE: graphics.beginFill(0xFFAA22); break; case BEGIN_NODE: graphics.beginFill(0x22FFAA); break; case CURRENT_NODE: graphics.beginFill(0x000000); break; case END_NODE: graphics.beginFill(0xFF3322); break; case PATH_NODE: graphics.beginFill(0x33FFFF); break; } graphics.drawCircle(0, 0, 5); } private function init(e:Event):void { draw(); } public function get role():int { return _role; } public function set role(value:int):void { _role = value; draw(); } override public function toString():String { return ("X:" + x + " Y:" + y + ", Role:" + _role); } } } package com.zackmercury.test { import com.bit101.components.Label; import com.bit101.components.PushButton; import flash.display.Sprite; import flash.events.Event; import flash.events.MouseEvent; import flash.geom.Point; import flash.utils.Dictionary; /** * ... * @author ZackMercury */ public class Main extends Sprite { public static const W:int = 640, H:int = 480; private var nodes:Vector.<Node> = new Vector.<Node>(); private var region:Sprite; private var drawBegin:Node; private var drawEnd:Node; private var beginNode:Node; private var endNode:Node; private var closedSet:Vector.<Node> = new Vector.<Node>(); private var openSet:Vector.<Node> = new Vector.<Node>(); private var output:Label; public function Main() { if (stage) init(); else addEventListener(Event.ADDED_TO_STAGE, init); } private function init(e:Event = null):void { removeEventListener(Event.ADDED_TO_STAGE, init); // entry point region = new Sprite(); region.graphics.beginFill(0xFFFFFF); region.graphics.drawRect(0, 0, W, H); addChild(region); var searchBtn:PushButton = new PushButton(this, W - 110, H - 25, "Search path", searchPath); output = new Label(this, 10, 10, ""); region.addEventListener(MouseEvent.CLICK, onRegionClick); } private function heuristicCost(node1:Node, node2:Node):Number { return Math.sqrt(Math.pow(node1.x - node2.x, 2) + Math.pow(node1.y - node2.y, 2)); } private function searchPath(e:MouseEvent = null):void { for (var i:int = 0; i < nodes.length; i ++) nodes[i].role = Node.IDLE_NODE; /*region.graphics.clear(); region.graphics.beginFill(0xFFFFFF); region.graphics.drawRect(0, 0, W, H);*/ if (!endNode || !beginNode) return; beginNode.role = Node.BEGIN_NODE; endNode.role = Node.END_NODE; // Добавляем в открытый набор начальную вершину openSet.push(beginNode); // Её пройденное расстояние = 0 beginNode.g = 0; // Её полная стоимость является полностью эврестической beginNode.f = beginNode.h = heuristicCost(beginNode, endNode); //Входим в цикл addEventListener(Event.ENTER_FRAME, update); } private function update(e:Event):void { // Пока в открытом наборе есть вершины if (openSet.length) { // Ищем вершину в openSet с минимальным значением fScore var current:Node = openSet[0]; for (var i:int = 0; i < openSet.length; i ++) if (openSet[i].f < current.f) { current = openSet[i]; } // Для наглядности будем показывать текущую ячейку. for (i = 0; i < nodes.length; i++) nodes[i].role = Node.IDLE_NODE; endNode.role = Node.END_NODE; beginNode.role = Node.BEGIN_NODE; current.role = Node.CURRENT_NODE; output.text = "current \n g: " + current.g + "\n h: " + current.h + "\n f: " + current.f + "\n" + current.toString(); // Убрать текущую точку из открытого набора openSet.splice(openSet.indexOf(current), 1); // Проходимся по соседям текущей for each(var neighbour:Node in current.neighbours) { // Если текущий сосед - цель, if (neighbour == endNode) { // Присваиваем соседу родителя neighbour.parentNode = current; // Трейсим и подсвечиваем путь highlightPath(neighbour); return; } // Если у соседа уже посчитан g, и он меньше текущего, пропускаем его if (current.g + heuristicCost(current, neighbour) >= neighbour.g) { continue; } // Устанавливаем соседу родителя neighbour.parentNode = current; // Считаем g, h, f: f(n) = g(n) + h(n); // Это известная часть стоимости, плюсуем стоимость путешествия к текущей с стоимостью путешествия из текущей в соседа neighbour.g = current.g + heuristicCost(current, neighbour); //g- // Эвристическая часть стоимости, просто расстояние от соседа до конечной точки neighbour.h = heuristicCost(neighbour, endNode); //h-heuristif // Считаем полную стоимость neighbour.f = neighbour.g + neighbour.h; //f-full // Если сосед не в закрытом наборе, и соседа нет в открытом if (!(closedSet.indexOf(neighbour) > -1) && (openSet.indexOf(neighbour) < 0)) { // Добавляем в открытый набор openSet.push(neighbour); } } // Добавить текущую точку в закрытый набор closedSet.push(current); } else { // Решения нет, чистим и сбрасываем всё clearEverything(); trace("No solution"); removeEventListener(Event.ENTER_FRAME, update); } } private function highlightPath(current:Node):void { var tp:Vector.<Node> = new Vector.<Node>(); tp.push(current); // Пока у текущей вершины есть родитель while (current.parentNode) { // Записываем путь tp.push(current.parentNode); // Выделяем путь current.role = Node.PATH_NODE; // Меняем текущую на отца текущей current = current.parentNode; } current.role = Node.PATH_NODE; //Чистим всё clearEverything(); removeEventListener(Event.ENTER_FRAME, update); } private function clearEverything():void { while (openSet.length) openSet.pop(); while (closedSet.length) closedSet.pop(); for (var i:int = 0; i < nodes.length; i ++) { nodes[i].g = nodes[i].h = nodes[i].f = Infinity; nodes[i].parentNode = null; } } private function onRegionClick(e:MouseEvent):void { if (e.target is Node) return; var n:Node = new Node(); addChild(n); nodes.push(n); n.x = e.stageX; n.y = e.stageY; n.addEventListener(MouseEvent.MOUSE_DOWN, onNodeDown); n.addEventListener(MouseEvent.MOUSE_UP, onNodeUp); e.updateAfterEvent(); } private function onNodeUp(e:MouseEvent):void { var n:Node = e.currentTarget as Node; drawEnd = n; if (!drawBegin || (drawBegin == drawEnd)) { drawBegin = null; drawEnd = null; return; } region.graphics.lineStyle(2, 0); region.graphics.moveTo(drawBegin.x, drawBegin.y); region.graphics.lineTo(drawEnd.x, drawEnd.y); drawBegin.connect(drawEnd); drawEnd.connect(drawBegin); drawBegin = null; drawEnd = null; e.updateAfterEvent(); } private function onNodeDown(e:MouseEvent):void { var n:Node = e.currentTarget as Node; if (e.ctrlKey) { if (beginNode) beginNode.role = Node.IDLE_NODE; beginNode = n; n.role = Node.BEGIN_NODE; return; } else if (e.altKey) { if (endNode) endNode.role = Node.IDLE_NODE; endNode = n; n.role = Node.END_NODE; return; } drawBegin = n; } } }
MinimalComps_0_9_10.rar
Всего комментариев 8
Комментарии
![]() ![]() |
|
А что за фонт используется во флэшке, сорри
![]() |
![]() ![]() |
|
Это стандартный шрифт для компонентов библиотеки MinimalComps, PF Ronda Seven.
|
|
Обновил(-а) ZackMercury 28.06.2017 в 14:08
|
![]() ![]() |
|
caseyryan, нужно нажать по уже поставленной точке с зажатой клавишей.
Окей, тогда будет вторая часть о реальном применении алгоритма на примере карты проходимости, однако позже. На самом деле, я хотел оставить это как есть, чтобы было больше понимания о том, как работает алгоритм и как его можно применить: ведь вершины можно расставлять где угодно, в том числе их можно расставлять в 3D. Исходник. |
|
Обновил(-а) ZackMercury 29.06.2017 в 09:00
|
![]() ![]() |
|
Где саморазвивающиеся нейронные сети-то!? Я жду!
|
![]() ![]() |
|
Не спешу, ещё множество интереснейших вещей, в которых я хотел бы разобраться прежде.
|
![]() ![]() |
|
ZackMercury, нет никакого смысла разбираться в чём-то ещё! Скорее пиши саморазвивающуюся нейронную сеть! И тогда она за сама разберётся во всём остальном за тебя!
|
![]() ![]() |
|
Ничем не могу помочь, остаётся вам либо подождать, либо следовать за любыми туториалами на тему в интернете(каких полно), и в намного более полном объёме, чем способен преподнести я, только начиная разбираться в теме. Например, вот этот хороший человек обещает выпустить детальный курс по нейросетям:
https://www.youtube.com/watch?v=ZEhwZhdk-zI У него на канале уже есть видео про нейросети. |
Последние записи от ZackMercury
- Вывод формулы для бесконечного цикла. (11.01.2019)
- Как заменить цикл на формулу. (10.01.2019)
- Конечные и бесконечные суммы, Ч. 1 (08.01.2019)
- Как легко запомнить тригонометрические функции (07.01.2019)
- Движение по треугольнику, квадрату, пентагону, хексагону, ... (05.01.2019)