пятница, 21 мая 2010 г.

Поиск пути (pathfinding)

Представляю вашему вниманию очередной вольный перевод главы из книги AdvancED ActionScript 3.0 Animation, автор Keith Peters.

На этот раз речь пойдет о поиске пути между двумя произвольными точками.
Вот кое-что из того чему мы сегодня научимся

[SWF]http://coolisee.com/wordpress/wp-content/uploads/2010/05/21/pathfinding/Game.swf, 600, 600[/SWF]
Кликайте по узлам сетки, чтобы персонаж нашел к ним путь




Поиск пути (pathfinding).

Вы находитесь в точке А и вам нужно пройти в точку В. Как вам до нее добраться? Эта тема очень хорошо изучена разработчиками игр и то, что я здесь изложу, не является чем-то новым, но даст самые основы этой темы и приличную реализацию алгоритма поиска пути на языке ActionScript 3.0.

Основы поиска пути.

Поиск пути часто применяется к плиточному (основанному на плитках) миру. Даже когда мы имеем дело с игрой или миром не основанному на плитках, мы его все равно рассматриваем с точки зрения поиска пути как сетку. Таким образом, результатом поиска пути является набор плиток, которые представляют собой непрерывный путь от начальной плитки к конечной. Сложность увеличивается, когда вы делаете некоторые из этих плиток непроходимыми. Персонаж в игре, когда сталкивается с непроходимыми плитками, вынужден их обойти. Если эти непроходимые плитки формируют препятствие между начальной и конечной плиткой, то поиск пути может дать ответ как обойти это препятствие и достичь цели.

Путь с препятствиями
Рис 1. – Путь с препятствиями



Поиск пути также подразумевает, что вы ищете для своего персонажа «лучший» путь. Во многих реализациях «лучший» путь – это самый короткий путь, т.е. путь, составленный из наименьшего количества плиток. Но здесь мы будем использовать такое понятие как «стоимость» пути. Путешествие от одной плитки к другой стоит определенных усилий. Конечно, дистанция это существенная часть стоимости (стоимость пересечения двух плиток больше, чем стоимость пересечения одной), но могут быть и другие затраты при пересечении плиток. В некоторых играх, например, путь через болото или горы может быть самым коротким, но и одновременно самым трудным, т.к. пересекать болота и горы трудней, чем двигаться по дороге. Т.е. кратчайший путь может иметь большую стоимость, чем более длинный путь.


А* (А со звездой)

Если вы интересовались вопросом поиска пути, то несомненно сталкивались с А* - алгоритмом поиска лучшего пути между двумя точками. Этот алгоритм своего рода стандарт, используемый почти в каждой игре, которая использует поиск пути. При правильной реализации этот алгоритм гарантированно найдет путь «лучший» в том понимании, которое закладывает разработчик. Поэтому часто считают вопрос поиска пути закрытым и алгоритм А* - ответом на этот вопрос.
Одна из сильных сторон А* - это скорее очень общий алгоритм, чем точная формула. Фактически, одна из частей А* - эвристика (рабочая гипотеза, предположение), которая сама является подалгоритмом, используемым в одной из частей всего процесса. Эта эвристика не определяет полностью А* и использование нескольких эвристик дает различные результаты в зависимости от требований разработчика. Фактически любая часть алгоритма А* может быть настроена в зависимости от требований языка или приложения.


А* основы

А* выбирает стартовую плитку, посещает каждую соседнюю плитку и присваивает ей стоимость. Процесс повторяется для плитки с меньшей стоимостью, которая теперь выступает в роли стартовой. Продолжая этот процесс, мы достигнем конечной плитки и можем вернуться назад к стартовой плитки для определения лучшего пути между ними.


А* алгоритм

Большинство объяснений работы А* начинается с представления псевдокода алгоритма и продолжается показом простых рисунков, иллюстрирующих процесс поиска. Это, кажется, хорошо работает, поэтому мы сделаем также. Для начала давайте определимся с терминами.

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

- стоимость: это характеристика каждого узла, которая определяет затраты на перемещение через этот узел. Узлы с меньшей стоимостью более предпочтительны, чем узлы с большей. Стоимость состоит из двух частей: стоимости перемещения от стартового узла до текущего и стоимости перемещения от текущего узла до конечного. Элементы стоимости обычно обозначаются как f, g, h как описано далее.

- f: полная стоимость f=g+h.

- g: стоимость перемещения от стартового узла до текущего узла. Может быть вычислена точно, т.к. путь от стартового узла до текущего мы знаем.

- h: предполагаемая стоимость перемещения от текущего узла до конечного. Предположение и есть эвристика. Стоимость является предполагаемой потому, что мы не знаем точного пути.

- эвристика: функция, которая производит оценку стоимости перемещения из текущего узла к конечному.

- открытый список: список узлов, которые были посещены и которым была присвоена стоимость. Узел с самой низкой стоимостью будет использован в следующей итерации поиска.

- закрытый список: список узлов, соседи которых были все посещены.

- родительский узел: когда узел использован в итерации поиска и каждый его соседний узел проверен, то этот узел назначается для соседних узлов как родительский. Когда вы достигаете конечного узла, то по цепочке родительских узлов вы можете добраться до начального узла. Поскольку родительские узлы были узлами с наименьшей стоимостью в открытом списке, то вы гарантированно получаете лучший путь.

Теперь посмотрим на работу алгоритма:

1. Добавляем стартовый узел в открытый список.
2. Цикл поиска:
а. Находим узел в открытом списке с наименьшей стоимостью. Это узел будет текущим.
b. Если текущий узел является конечным, то мы у цели. Переходим к шагу 4.
c. Исследуем каждый из соседних узлов. Для каждого из них:
- если это непроходимый узел или уже содержится в открытом или закрытом списке, то пропускаем его и переходим к следующему узлу.
- определяем его стоимость.
- устанавливаем текущий узел (т.е. узел соседа которого мы сейчас проверяем) в качестве его родителя.
- добавляем его в открытый список.
d. Добавляем текущий узел в закрытый список.
3. Повторяем шаг 2 с обновленным открытым списком.
4. Мы нашли конечный узел. Создадим список узлов пути и добавим к нему конечный узел.
5. Добавим родительский узел конечного в список пути.
6. Добавим родительский узел этого узла в список пути. Повторим этот шаг до тех пор, пока не достигнем стартового узла. Теперь наш список содержит лучший путь от начального узла до конечного.

Мы рассмотрим этот алгоритм подробно очень скоро, а теперь посмотрим, как вычислить стоимость для отдельной плитки.


Вычисление стоимости

Как мы уже определили в терминах, стоимость g отдельного узла определяется как f = g+h, где g – стоимость перемещения до текущего узла, h – предполагаемая стоимость перемещения от текущего узла до конечного.

Первая часть формулы стоимости понятна: стоимость узлов, которые были пройдены от начального узла до текущего. Пока мы будем считать, что стоимость перемещения от узла к соседнему стоит 1.

Итак, начиная с начального узла и проверяя каждый из соседних узлов, мы назначаем каждому g=1. См рисунок 2.

Присваивание g из начального узла
Рисунок 2. – Присваивание g из начального узла



В следующей итерации, мы можем посчитать g следующего узла как сумму его g и стоимости перемещения к нему от начального узла. Другими словами, предположим, что текущий узел это один из узлов окружающих начальный узел. Его g будет равным 1. Когда мы смотрим на каждый из окружающих узлов, которые окружают узел с g=1, мы присваиваем им g=2, потому, что перемещение по узлу с g=1 и стоит эту самую 1. См рисунок 3.

Присваивание g из следующего узла
Рисунок 3. – Присваивание g из следующего узла



Однако в большинстве реализаций стоимости узлов, окружающие начальный узел не равны между собой. Если вы посмотрите на расстояние между двумя узлами в той же самой строке или колонке и сравните его с расстоянием между двумя узлами по диагонали, можно увидеть, что расстояние по диагонали больше и равно не 1, а 1,414 (квадратный корень из 2). См рисунок 4.

Стоимость узлов, соседствующих по диагонали выше
Рисунок 4. – Стоимость узлов, соседствующих по диагонали выше



Следующая составляющая стоимости – предполагаемая стоимость перемещения от выбранного узла до конечного. Эта составляющая делается с помощью эвристики (гипотезы или предположения), которая представляет собой формулу или алгоритм. Одна из самых простых эвристик в этом случае – определить расстояние между этими двумя узлами с помощью старой и доброй теоремы Пифагора. Дистанцию определим следующим образом:

dx = расстояние между колонками, в которых находятся узлы;
dy = расстояние между строками, в которых находятся узлы;
dist = sqrt(dx*dx + dy*dy) – расстояние между узлами;


Это расстояние и есть наша h из формулы полной стоимости f.


Визуализация алгоритма

Итак, начнем. Создадим сетку, начальный узел, конечный узел и непроходимые плитки. См рисунок 5.


Рисунок 5



Продолжая поиск, мы добавляем начальный узел в открытый список. Теперь мы должны просмотреть список для определения соседнего узла с наименьшей стоимостью. Но т.к. сейчас в списке только один узел, то мы пропускаем этот шаг.

Теперь мы проверяем каждый соседний узел и присваиваем ему стоимость. Мы начинаем вычисление g для каждого из них. Если узел находится в той же строке или колонке, что и начальный, то g будет равным 1, если узлы соседствуют по диагонали, то g = 1.4. См рисунок 6.

Присваиваем стоимость g
Рисунок 6. – Присваиваем стоимость g



Теперь определим значения h. Для этого используем прямолинейную эвристику, т.е. в качестве предполагаемого расстояния между узлами возьмем прямую линию между ними. Это расстояние будет выражаться в количестве узлов и находить его мы будем с помощью теоремы Пифагора.

Теперь, когда мы имеем обе составляющие полной стоимости, мы можем ее вычислить. См рисунок 7.

Полная стоимость для каждого узла
Рисунок 7. – Полная стоимость для каждого узла



Текущий узел может быть добавлен теперь к закрытому списку, а каждый из соседних узлов можно добавить в открытый список.
Теперь мы смотрим в открытый список и найдем узел с наименьшей стоимостью, который на сетке находится в координатах В5. Далее повторяем процесс. В этот раз некоторые из окружающих узлов уже посчитаны и находятся в открытом и закрытом списках, поэтому повторно считать их мы не будем. Определяем стоимость для оставшихся узлов. См рисунок 8.

Второй этап поиска пути
Рисунок 8. – Второй этап поиска пути



Теперь добавляем В5 в закрытый список, а все проверенные узлы в открытый. Снова выбираем узел из открытого списка с наименьшей стоимостью. В этот раз это узел С5. Определяем стоимость для каждого соседнего узла. См рисунок 9.

Третий этап поиска пути
Рисунок 9. – Третий этап поиска пути



Теперь. Заметим, что узлы D5 и D6 имеют одинаковую стоимость. Фактически это происходит из-за того, что мы округляем полученные значения до десятых, на самом деле они могут быть и не равны. Но случилось то, что случилось. Какой же узел выбрать? На самом деле нет никакой разницы. Очевидно, что путь будет короче, если перейти на D6, т.к. впереди стена и придется рано или поздно свернуть. Но эвристика не может видеть эту стену. Она только вычисляет расстояние. С ее точки зрения все узлы одинаковы.
Так или иначе, предположим, что мы бросили монетку и выбрали D5. Тогда смотрим на соседние узлы и не видим ни одного нового – они или непроходимые или находятся в закрытом и открытом списках. Нет проблем. Эта ситуация – шаг 2с нашего алгоритма. Если нет никаких подходящих соседних узлов, то мы переходим к шагу 3, добавим узел D5 к закрытому списку и проверим открытый список для поиска узла с наименьшей стоимостью. На сей раз выбор D6 бесспорен. Мы продолжаем выполнять алгоритм, проверяя соседей. См рисунок 10.

Продолжение поиска пути
Рисунок 10. – Продолжение поиска пути



Повторяя этот процесс снова и снова мы получим следующий результат

Цель достигнута
Рисунок 11. – Цель достигнута



Текущий узел G7. Когда мы начнем проверку соседних узлов, мы увидим среди них и конечный узел. Мы сделали это!
В каждой фазе поиска, когда мы проверяли новые узлы мы делали каждый текущий узел родительским. Таким образом, мы можем теперь вернуться по этим родительским узлам назад к стартовому. Реверсируем список и получим лучший путь.


А теперь в коде

Для того, чтобы начать писать код А* нам понадобятся некоторые структуры, чтобы представить сетку и отдельный узел.
Для начала класс сетки.

package
{
/**
* Содержит двухмерный массив узлов, методы для управления им, начальным узлом, конечным узлом для поиска пути.
*/
public class Grid
{
private var _startNode:Node;
private var _endNode:Node;
private var _nodes:Array;
private var _numCols:int;
private var _numRows:int;

/**
* Конструктор.
*/
public function Grid(numCols:int, numRows:int)
{
_numCols = numCols;
_numRows = numRows;
_nodes = new Array();

for(var i:int = 0; i < _numCols; i++)
{
_nodes[i] = new Array();
for(var j:int = 0; j < _numRows; j++)
{
_nodes[i][j] = new Node(i, j);
}
}
}


////////////////////////////////////////
// открытые методы
////////////////////////////////////////

/**
* Возвращает узел с данными координатами.
* @param x координата х.
* @param y координата у.
*/
public function getNode(x:int, y:int):Node
{
return _nodes[x][y] as Node;
}

/**
* устанавливает узел с данными координатами в качестве конечного.
* @param x координата х.
* @param y координата у.
*/
public function setEndNode(x:int, y:int):void
{
_endNode = _nodes[x][y] as Node;
}

/**
* устанавливает узел с данными координатами в качестве начального.
* @param x координата х.
* @param y координата у.
*/
public function setStartNode(x:int, y:int):void
{
_startNode = _nodes[x][y] as Node;
}

/**
* устанавливает узел с данными координатами в качестве непроходимого/проходимого.
* @param x координата х.
* @param y координата у.
*/
public function setWalkable(x:int, y:int, value:Boolean):void
{
_nodes[x][y].walkable = value;
}



////////////////////////////////////////
// геттеры/сеттеры
////////////////////////////////////////

/**
* Возвращает конечный узел.
*/
public function get endNode():Node
{
return _endNode;
}

/**
* Возвращает количество колонок в сетке.
*/
public function get numCols():int
{
return _numCols;
}

/**
* Возвращает количество строк в сетке.
*/
public function get numRows():int
{
return _numRows;
}

/**
* Возвращает начальный узел.
*/
public function get startNode():Node
{
return _startNode;
}

}
}


В конструкторе мы задаем количество строк и колонок нашей сетки и создаем массив узлов. Также мы можем установить начальный и конечный узлы, определяя для этого их координаты, мы можем установить тот или иной узел проходимым или непроходимым. Наконец вы можете получить с помощью геттеров начальный узел, конечный узел и количество строк и колонок в сетке. Отметим, что класс Grid – это просто хранилище информации о сетке и не имеет визуального представления.
Теперь посмотрим на класс узла:

package
{
/**
* Представляет отдельный узел.
*/
public class Node
{
public var x:int;
public var y:int;
public var f:Number;
public var g:Number;
public var h:Number;
public var walkable:Boolean = true;
public var parent:Node;
public var costMultiplier:Number = 1.0;

public function Node(x:int, y:int)
{
this.x = x;
this.y = y;
}
}
}


Класс узла – это просто объект данных для хранения его характеристик. Он не имеет поведений, а только открытые свойства.
Следующее в чем мы нуждаемся – это класс, который и выполняет всю работу по поиску пути. Класс AStar:

package
{
public class AStar
{
private var _open:Array;
private var _closed:Array;
private var _grid:Grid;
private var _endNode:Node;
private var _startNode:Node;
private var _path:Array;
// private var _heuristic:Function = manhattan;
// private var _heuristic:Function = euclidian;
private var _heuristic:Function = diagonal;
private var _straightCost:Number = 1.0;
private var _diagCost:Number = Math.SQRT2;


public function AStar()
{
}

public function findPath(grid:Grid):Boolean
{
_grid = grid;
_open = new Array();
_closed = new Array();

_startNode = _grid.startNode;
_endNode = _grid.endNode;

_startNode.g = 0;
_startNode.h = _heuristic(_startNode);
_startNode.f = _startNode.g + _startNode.h;

return search();
}

public function search():Boolean
{
var node:Node = _startNode;
while(node != _endNode)
{
var startX:int = Math.max(0, node.x - 1);
var endX:int = Math.min(_grid.numCols - 1, node.x + 1);
var startY:int = Math.max(0, node.y - 1);
var endY:int = Math.min(_grid.numRows - 1, node.y + 1);

for(var i:int = startX; i <= endX; i++)
{
for(var j:int = startY; j <= endY; j++)
{
var test:Node = _grid.getNode(i, j);
if(test == node ||
!test.walkable ||
!_grid.getNode(node.x, test.y).walkable ||
!_grid.getNode(test.x, node.y).walkable)
{
continue;
}

var cost:Number = _straightCost;
if(!((node.x == test.x) || (node.y == test.y)))
{
cost = _diagCost;
}
var g:Number = node.g + cost * test.costMultiplier;
var h:Number = _heuristic(test);
var f:Number = g + h;
if(isOpen(test) || isClosed(test))
{
if(test.f > f)
{
test.f = f;
test.g = g;
test.h = h;
test.parent = node;
}
}
else
{
test.f = f;
test.g = g;
test.h = h;
test.parent = node;
_open.push(test);
}
}
}
_closed.push(node);
if(_open.length == 0)
{
trace("no path found");
return false
}
_open.sortOn("f", Array.NUMERIC);
node = _open.shift() as Node;
}
buildPath();
return true;
}

private function buildPath():void
{
_path = new Array();
var node:Node = _endNode;
_path.push(node);
while(node != _startNode)
{
node = node.parent;
_path.unshift(node);
}
}

public function get path():Array
{
return _path;
}

private function isOpen(node:Node):Boolean
{
for(var i:int = 0; i < _open.length; i++)
{
if(_open[i] == node)
{
return true;
}
}
return false;
}

private function isClosed(node:Node):Boolean
{
for(var i:int = 0; i < _closed.length; i++)
{
if(_closed[i] == node)
{
return true;
}
}
return false;
}

private function manhattan(node:Node):Number
{
return Math.abs(node.x - _endNode.x) * _straightCost + Math.abs(node.y + _endNode.y) * _straightCost;
}

private function euclidian(node:Node):Number
{
var dx:Number = node.x - _endNode.x;
var dy:Number = node.y - _endNode.y;
return Math.sqrt(dx * dx + dy * dy) * _straightCost;
}

private function diagonal(node:Node):Number
{
var dx:Number = Math.abs(node.x - _endNode.x);
var dy:Number = Math.abs(node.y - _endNode.y);
var diag:Number = Math.min(dx, dy);
var straight:Number = dx + dy;
return _diagCost * diag + _straightCost * (straight - 2 * diag);
}

public function get visited():Array
{
return _closed.concat(_open);
}
}
}


Здесь у нас есть массивы для хранения открытого и закрытого списков, массив для хранения искомого пути, который представляет собой список узлов и свойства, которые определяют вид эвристики. Я их сделал несколько и подробно их мы рассмотрим позднее. Вы можете выбрать любую из них, комментируя остальные. Наконец есть свойства, хранящие значения стоимости для узлов находящихся в той же строке и колонке, что и текущий узел и для узлов располагающихся по диагонали.
Следующее это метод findPatch:

		public function findPath(grid:Grid):Boolean
{
_grid = grid;
_open = new Array();
_closed = new Array();

_startNode = _grid.startNode;
_endNode = _grid.endNode;

_startNode.g = 0;
_startNode.h = _heuristic(_startNode);
_startNode.f = _startNode.g + _startNode.h;

return search();
}


Этот метод инициализирует сетку, создает открытый и закрытый списки, запрашивает у сетки начальный и конечный узлы и сохраняет их в свойства. Он определяет стоимость для начального узла и запускает метод search(), который осуществляет поиск конечного узла и возвращает путь до него.

Давайте посмотрим, как метод определяет стоимость начального узла. Сначала устанавливаем значение g равным нулю т.к. g – это стоимость перемещения от начального узла к текущему. А т.к. сейчас это одно и тоже, то и стоимость равна нулю. Затем мы вызываем тот метод эвристики, который определили ранее для стартового узла, который вернет предполагаемую стоимость перемещения от начального узла к конечному. Это и есть h. Наконец мы складываем g и h и получаем f – полную стоимость для начального узла.

Следующее действие – это метод search().

		public function search():Boolean
{
var node:Node = _startNode;
while(node != _endNode)
{
var startX:int = Math.max(0, node.x - 1);
var endX:int = Math.min(_grid.numCols - 1, node.x + 1);
var startY:int = Math.max(0, node.y - 1);
var endY:int = Math.min(_grid.numRows - 1, node.y + 1);

for(var i:int = startX; i <= endX; i++)
{
for(var j:int = startY; j <= endY; j++)
{
var test:Node = _grid.getNode(i, j);
if(test == node ||
!test.walkable ||
!_grid.getNode(node.x, test.y).walkable ||
!_grid.getNode(test.x, node.y).walkable)
{
continue;
}

var cost:Number = _straightCost;
if(!((node.x == test.x) || (node.y == test.y)))
{
cost = _diagCost;
}
var g:Number = node.g + cost * test.costMultiplier;
var h:Number = _heuristic(test);
var f:Number = g + h;
if(isOpen(test) || isClosed(test))
{
if(test.f > f)
{
test.f = f;
test.g = g;
test.h = h;
test.parent = node;
}
}
else
{
test.f = f;
test.g = g;
test.h = h;
test.parent = node;
_open.push(test);
}
}
}
for(var o:int = 0; o < _open.length; o++)
{
}
_closed.push(node);
if(_open.length == 0)
{
trace("no path found");
return false
}
_open.sortOn("f", Array.NUMERIC);
node = _open.shift() as Node;
}
buildPath();
return true;
}


Начнем с определения переменной текущего узла, который сейчас будет начальным. Если текущей узел не является конечным, то выполняем блок while().
Первая вещь, которую мы сделаем в блоке while() это запуск двойного цикла для проверки всех узлов окружающих текущий узел. См рисунок 12

Значения индексов х, у для узлов, окружающих текущий узел
Рисунок 12. – Значения индексов х, у для узлов, окружающих текущий узел



Сначала мы получаем значения х и у для текущего узла и запускаем циклы для значений от х-1 до х+1 и для значений от у-1 до у+1 (помним о том, что значения х и у определяют не значение пикселей на экране, а значения строки и колонки, где находится текущий узел):

				var startX:int = Math.max(0, node.x - 1);
var endX:int = Math.min(_grid.numCols - 1, node.x + 1);
var startY:int = Math.max(0, node.y - 1);
var endY:int = Math.min(_grid.numRows - 1, node.y + 1);

for(var i:int = startX; i <= endX; i++)
{
for(var j:int = startY; j <= endY; j++)
{


Нам нужно убедиться в том, что мы не пытаемся получить доступ к плиткам, которые находятся за границами сетки. Для этого мы используем методы Math.min и Math.max и наши индексы никогда не будут меньше нуля или больше количества строк и колонок сетки.

Если проверяемый узел является текущим узлом или непроходимым мы должны его проигнорировать и двигаться дальше:

				var test:Node = _grid.getNode(i, j);
if(test == node || !test.walkable)continue;


Двигаясь дальше, мы получаем проверенный узел и нам нужно теперь определить его стоимость. Сначала мы определяем стоимость перемещения от начального узла до проверяемого (g). Для этого мы можем взять стоимость g текущего узла и прибавить к нему стоимость проверяемого узла. Если этот проверяемый узел лежит в той же строке или колонке, что и текущий, то его стоимость будет равна значению переменной _straightCost, если узлы располагаются по диагонали – то значению _diagCost. Теперь прибавляем это значение к общей стоимости g, находим значение эвристики для проверяемого узла и сложением эвристики h и стоимости g находим полную стоимость f:

				var cost:Number = _straightCost;
if(!((node.x == test.x) || (node.y == test.y)))
{
cost = _diagCost;
}
var g:Number = node.g + cost * test.costMultiplier;
var h:Number = _heuristic(test);
var f:Number = g + h;


Следующий шаг содержит небольшую хитрость, о которой мы еще не говорили. Ранее, я подразумевал, что если узел находиться в открытом или закрытом списке, то нам не нужно будет его проверять, т.к. он уже проверен. Однако стоимость этого проверенного узла может стать меньше в текущей проверке, чем стоимость в предыдущей проверке (например, если вы производили проверку для узла находящегося на диагонали по отношению к текущему узлу, а при перемещении этот же узел стал располагаться в той же колонке или строке по отношению к текущему узлу). Поэтому, даже если узел находиться в закрытом или открытом списке следует сравнить его текущую стоимость с предыдущим значением. Мы делаем это сравнивая значения f проверяемых узлов (это значение есть у него только в том случае, если он был проверен ранее) с значением f которое вычислили сейчас. Если предыдущее значение f больше, то мы присваиваем проверяемому узлу значения f, g, h которые вычислили сейчас. Мы также присваиваем текущий узел проверяемому в качестве родителя:

				if(isOpen(test) || isClosed(test))
{
if(test.f > f)
{
test.f = f;
test.g = g;
test.h = h;
test.parent = node;
}
}


Если проверяемый узел не содержится в открытом или закрытом списках мы также присваиваем значения f, g, h и родительский узел и добавляем проверяемый узел в открытый список:

				else
{
test.f = f;
test.g = g;
test.h = h;
test.parent = node;
_open.push(test);
}


Когда мы проверили все соседние узлы мы можем наш текущий узел спокойно занести в закрытый список:

_closed.push(node);


Теперь мы должны найти следующий текущий узел для продолжения процесса. Для этого мы проверим открытый список и найдем узел с наименьшей стоимостью. Но сначала проверим, есть ли в этом списке узлы, т.е. не пуст ли он.

				if(_open.length == 0)
{
trace("no path found");
return false
}


В этой реализации возвращается true если путь существует и false если пройти к конечному узлу невозможно. Это может быть проверено с помощью кода, который ищет путь.
Если узлы в открытом списке есть, то мы должны найти узел с наименьшей стоимостью. Мы можем сделать это с помощью сортировки массива по свойству узла f и помещением нужного элемента в начало массива:

				_open.sortOn("f", Array.NUMERIC);
node = _open.shift() as Node;


Это – конец текущей итерации. И теперь у нас есть новый текущий узел. И мы повторяем весь процесс снова.
Когда мы достигнем конечного узла, мы вызовем метод buildPatch() и вернем значение true. Посмотрим на этот метод:

		private function buildPath():void
{
_path = new Array();
var node:Node = _endNode;
_path.push(node);
while(node != _startNode)
{
node = node.parent;
_path.unshift(node);
}
}


Этот код создает для пути новый массив и добавляет в него конечный узел. Затем пока текущий узел не станет стартовым, мы добавляем в массив пути родителя текущего узла. И к моменту, когда текущий узел будет являться начальным, у нас уже будет тот самый лучший путь. Дело сделано! Нетерпеливые могут сразу перейти к шагу с использования А*, а с любознательными мы посмотрим на виды эвристики.

Итак посмотрим на разные виды эвристики.


Эвристики

Самое смешное в А* то, что он может дать вам оптимальный путь независимо от того, какая эвристика используется. И этих оптимальных путей может быть несколько, т.е. стоимость их будет одинакова, а сами пути будут содержать разные узлы. См рисунок 13. Здесь представлены пути с одинаковой стоимостью 4.8 (два диагональных перемещения стоимостью 1.4 и два горизонтальных стоимостью 1).

Три оптимальных пути между одними и теми же узлами
Рисунок 13. – Три оптимальных пути между одними и теми же узлами



Пока мы будем получать один из этих путей, наш путь будет правильным.
Таким образом, использование «лучшей» эвристики не значит, что она вернет кратчайший путь. Но некоторые эвристики работаю быстрее, чем другие. Наибольшее различие между ними это количество узлов проверяемых при поиске пути каждой эвристикой. Чем меньше этих узлов, тем быстрее вы получите требуемый путь, быстрее будет выполняться сортировка массивов и т.д.

Кроме того, некоторые эвристики создают путь, который кажется более прямым и коротким в наших глазах. Например, большинство людей могли бы сказать, что первый и второй пути на рисунке 13 короче, чем третий, хотя на самом деле они имеют одинаковую цену.

Здесь мы рассмотрим три вида эвристики (которые используются в нашем классе AStar).

эвристика Манхеттена, эвристика Эвклида и диагональная эвристика
Рисунок 14. – эвристика Манхеттена, эвристика Эвклида и диагональная эвристика



Начнем с так называемой эвристики Манхеттена, которая игнорирует любые диагональные перемещения и использует сумму строк и колонок между проверяемым и конечным узлами.

		private function manhattan(node:Node):Number
{
return Math.abs(node.x - _endNode.x) * _straightCost
+ Math.abs(node.y + _endNode.y) * _straightCost;
}


Здесь все достаточно просто, метод определяет количество строк и колонок между проверяемым и конечным узлами и складывает их.

Следующая эвристика – Эвклида. Использует теорему Пифагора, вычисляет длину прямой линии соединяющей проверяемый узел и конечный.

		private function euclidian(node:Node):Number
{
var dx:Number = node.x - _endNode.x;
var dy:Number = node.y - _endNode.y;
return Math.sqrt(dx * dx + dy * dy) * _straightCost;
}


Следующая – диагональная эвристика.

		private function diagonal(node:Node):Number
{
var dx:Number = Math.abs(node.x - _endNode.x);
var dy:Number = Math.abs(node.y - _endNode.y);
var diag:Number = Math.min(dx, dy);
var straight:Number = dx + dy;
return _diagCost * diag + _straightCost * (straight - 2 * diag);
}


Она выглядит сложней предыдущих, но и возвращает более точный результат.

Следующие три рисунка показывают результат применения этих трех алгоритмов, заметим, что все три алгоритма возвращают путь, состоящий из 25 диагональных перемещений и 23 горизонтальных. Во всех случаях стоимость пути составляет 58. Различие эвристик не в длине получаемого пути, а характере пути и количестве проверяемых узлов (которые на рисунках закрашены серым). Вы можете видеть, что эвристика Манхеттена (см рисунок 15) дает не совсем реалистичный путь и делает проверку очень большого количества узлов.

Применение метода Манхеттена
Рисунок 15. – Применение метода Манхеттена



Следующая эвристика – Эвклида (см рисунок 16), которая дает более реалистичный путь и делает меньше проверок узлов.

Результат применения эвристики Эвклида
Рисунок 16. – Результат применения эвристики Эвклида



Диагональная эвристика дает наиболее реалистичный путь и делает меньшее количество проверок узлов. См рисунок 17.

Результат применения диагональной эвристики
Рисунок 17. – Результат применения диагональной эвристики




Применение класса AStar

Когда вы будете реализовывать А* в своей игре или приложении, вы вероятно создадите плиточный мир с проходимыми и непроходимыми плитками. Начальной точкой будет плитка, в которой находится персонаж, а конечная точка может быть точкой, по которой пользователь кликнул мышью (плитка где находиться горшок с золотом, враг или любой другой объект). Сам путь, вероятно, не нужно будет визуализировать – он будет использоваться для перемещения персонажа. Для демонстрации я создал класс GridView:

package
{
import flash.display.Sprite;
import flash.events.MouseEvent;

/**
* Служит визуальным представление сетки
*/
public class GridView extends Sprite
{
private var _cellSize:int = 20;
private var _grid:Grid;

/**
* Конструктор.
*/
public function GridView(grid:Grid)
{
_grid = grid;
drawGrid();
findPath();
addEventListener(MouseEvent.CLICK, onGridClick);
}

/**
* Отрисовывает сетку и окрашивает узлы в соответсвующий цвет.
*/
public function drawGrid():void
{
graphics.clear();
for(var i:int = 0; i < _grid.numCols; i++)
{
for(var j:int = 0; j < _grid.numRows; j++)
{
var node:Node = _grid.getNode(i, j);
graphics.lineStyle(0);
graphics.beginFill(getColor(node));
graphics.drawRect(i * _cellSize, j * _cellSize, _cellSize, _cellSize);
}
}
}

/**
* Определяет цвет для узлов разного вида.
*/
private function getColor(node:Node):uint
{
if(!node.walkable) return 0;
if(node == _grid.startNode) return 0x666666;
if(node == _grid.endNode) return 0x666666;
return 0xffffff;
}

/**
* Слушатель события MouseEventClick. Делает узел, по которому кликнул пользователь непроходимым.
*/
private function onGridClick(event:MouseEvent):void
{
var xpos:int = Math.floor(event.localX / _cellSize);
var ypos:int = Math.floor(event.localY / _cellSize);

_grid.setWalkable(xpos, ypos, !_grid.getNode(xpos, ypos).walkable);
drawGrid();
findPath();
}

/**
* Создает экземпляр класса А* и использует его для поиска пути.
*/
private function findPath():void
{
var astar:AStar = new AStar();
if(astar.findPath(_grid))
{
showVisited(astar);
showPath(astar);
}
}

/**
* Подсвечивает все узлы, которые были проверены.
*/
private function showVisited(astar:AStar):void
{
var visited:Array = astar.visited;
for(var i:int = 0; i < visited.length; i++)
{
graphics.beginFill(0xcccccc);
graphics.drawRect(visited[i].x * _cellSize, visited[i].y * _cellSize, _cellSize, _cellSize);
graphics.endFill();
}
}

/**
* Подсвечивает путь.
*/
private function showPath(astar:AStar):void
{
var path:Array = astar.path;
for(var i:int = 0; i < path.length; i++)
{
graphics.lineStyle(0);
graphics.beginFill(0);
graphics.drawCircle(path[i].x * _cellSize + _cellSize / 2,
path[i].y * _cellSize + _cellSize / 2,
_cellSize / 3);
}
}
}
}


Конструктор класса GridView использует экземпляр класса Grid, который содержит список всех узлов. Метод drawGrid() проходит через все узлы и отрисовывает в каждом из них небольшой квадрат, размер которого соответствует размеру _cellSize. Цвет квадрата определяется методом getColor(), который возвращает черный цвет, если узел непроходимый, серый для начального и конечного узлов и белый для всех остальных.

Вызывается метод findPatch(), который создает экземпляр класса AStar и вызывает его метод findPatch(). Если путь найден, показываются узлы, которые были проверены и узлы, которые и представляют собой путь. Результат можно увидеть на рисунках 15, 16, 17.

Конечно, обнаружение пути без препятствий не интересно, поэтому мы добавляем слушателя onGridClick() события MouseEvent.CLICK. Это слушатель делает узел, по которому кликнул пользователь проходимым или непроходимым. Также этот слушатель заново отрисовывает сетку и заново находит новый путь.
Для того чтобы связать все вместе создадим класс Patchfinding:

package {
import flash.display.Sprite;
import flash.display.StageAlign;
import flash.display.StageScaleMode;
import flash.events.MouseEvent;

[SWF(backgroundColor=0xffffff)]
public class Pathfinding extends Sprite
{
private var _grid:Grid;
private var _gridView:GridView;


public function Pathfinding()
{
stage.align = StageAlign.TOP_LEFT;
stage.scaleMode = StageScaleMode.NO_SCALE;

_grid = new Grid(50, 30);
_grid.setStartNode(0, 2);
_grid.setEndNode(48, 27);

_gridView = new GridView(_grid);
_gridView.x = 20;
_gridView.y = 20;
addChild(_gridView);
}

}
}


Здесь мы создаем экземпляры классов Grid и GridView и связываем их. Вы можете задать различные начальные и конечные узлы; если ролик уже запущен, кликая по разным узлам вы можете задать их непроходимость и путь будет рассчитываться заново.


Рисунок 18.



Сам ролик:

[SWF]http://coolisee.com/wordpress/wp-content/uploads/2010/05/21/pathfinding/Pathfinding.swf, 600, 600[/SWF]




Улучшение пути: углы

У нас есть одна потенциальная проблема, о которой мы еще не говорили и с которой не сталкивались в примерах. Когда путь проходит рядом с углом препятствия, происходит перемещение между диагональными узлами, что может привести к ситуации, показанной на рисунке 19.

Прохождение пути через углы препятствий (трещины)
Рисунок 19. – Прохождение пути через углы препятствий (трещины)



Здесь путь проходит через трещины между препятствиями. Вы могли бы подумать, что создали для пути непреодолимое препятствие, но перемещение по диагонали для нашего пути вполне законно, хотя и выглядит в этом случае неправильно. Мы должны сделать так, чтобы путь не срезался вокруг непроходимых узлов, а проходил все узлы вокруг окончания препятствия. Для этого мы закроем соответствующий узел для перемещения. См рисунок 20.

Закрытый для перемещения узел
Рисунок 20. – Закрытый для перемещения узел



Черный круг здесь представляет текущий узел и серый квадрат – узел, который сейчас проверяется и которому должна быть определена стоимость. Место в методе search():

                                 for(var i:int = startX; i <= endX; i++)
{
for(var j:int = startY; j <= endY; j++)
{
var test:Node = _grid.getNode(i, j);
if(test == node ||!test.walkable) continue;


Здесь мы убеждаемся, что проверяемый узел не является текущим узлом и не является непроходимым. Если хоть одно из этих условий не выполняется, мы пропускаем этот узел и приступаем к проверке следующего узла. Здесь мы хотим добавить еще одно условие: мы пропустим этот узел, если он находится на окончании препятствия. Когда node и test находятся на одной диагонали как сейчас, два других узла должны быть проверены. Эти узлы будут иметь следующие координаты:

node.x, test.y
и
test.x, node.y

См рисунок 21


Рисунок 21



Таким образом, все, что мы должны сделать - это проверка на проходимость этих двух узлов. Если они непроходимы, мы пропускаем проверку узла и переходим к следующему:

				for(var i:int = startX; i <= endX; i++)
{
for(var j:int = startY; j <= endY; j++)
{
var test:Node = _grid.getNode(i, j);
if(test == node ||
!test.walkable ||
!_grid.getNode(node.x, test.y).walkable ||
!_grid.getNode(test.x, node.y).walkable)
{
continue;
}


Такая поправка дает нам следующий путь (см рисунок 22):


Рисунок 22



Теперь путь проходит вокруг окончаний препятствий – диагональных перемещений нет. Кроме того, если начальный или конечный узел находятся в таком замкнутом пространстве, как на рисунке 22, то путь не будет найден вообще.

Путь не может быть найден
Рисунок 23. – Путь не может быть найден




Использование AStar в игре

Предыдущий пример с классом GridView был предназначен для демонстрационных целей – можно было увидеть, как путь образовывается, какие узлы были проверены при этом, и что происходит с уже существующем путем, если устанавливать узлы, по которым он проходит непроходимыми.

В реальной ситуации, как правило, все наоборот – состояние проходимый/непроходимый для определенного узла не меняется, а вот положение начального и конечного узла пути меняется очень часто. Начальный узел – узел, где находится персонаж, а он обычно в процессе игры много перемещается; конечный узел – тот узел куда персонаж должен перейти, когда игрок щелкает по нему мышью. Давайте сделаем очень простую реализацию этого поведения:

package
{
import flash.display.Sprite;
import flash.display.StageAlign;
import flash.display.StageScaleMode;
import flash.events.Event;
import flash.events.MouseEvent;

public class Game extends Sprite
{
private var _cellSize:int = 20;
private var _grid:Grid;
private var _player:Sprite;
private var _index:int;
private var _path:Array;

public function Game()
{
stage.align = StageAlign.TOP_LEFT;
stage.scaleMode = StageScaleMode.NO_SCALE;

makePlayer();
makeGrid();
stage.addEventListener(MouseEvent.CLICK, onGridClick);
}

/**
* Создание игрока. Здесь это простой шарик.
*/
private function makePlayer():void
{
_player = new Sprite();
_player.graphics.beginFill(0xff0000);
_player.graphics.drawCircle(0, 0, 5);
_player.graphics.endFill();
_player.x = Math.random() * 600;
_player.y = Math.random() * 600;
addChild(_player);
}

/**
* Создание сетки с случайными препятствиями.
*/
private function makeGrid():void
{
_grid = new Grid(30, 30);
for(var i:int = 0; i < 200; i++)
{
_grid.setWalkable(Math.floor(Math.random() * 30),
Math.floor(Math.random() * 30),
false);
}
drawGrid();
}

/**
* Отрисовка сетки, заливка ячеек.
*/
private function drawGrid():void
{
graphics.clear();
for(var i:int = 0; i < _grid.numCols; i++)
{
for(var j:int = 0; j < _grid.numRows; j++)
{
var node:Node = _grid.getNode(i, j);
graphics.lineStyle(0);
graphics.beginFill(getColor(node));
graphics.drawRect(i * _cellSize, j * _cellSize, _cellSize, _cellSize);
}
}
}

/**
* Определение цвета ячейки.
*/
private function getColor(node:Node):uint
{
if(!node.walkable) return 0;
if(node == _grid.startNode) return 0xcccccc;
if(node == _grid.endNode) return 0xcccccc;
return 0xffffff;
}

/**
* Слушатель события MouseEvent.CLICK.
*/
private function onGridClick(event:MouseEvent):void
{
var xpos:int = Math.floor(mouseX / _cellSize);
var ypos:int = Math.floor(mouseY / _cellSize);
_grid.setEndNode(xpos, ypos);

xpos = Math.floor(_player.x / _cellSize);
ypos = Math.floor(_player.y / _cellSize);
_grid.setStartNode(xpos, ypos);

drawGrid();
findPath();
}

/**
* Создает экземпляр класса AStar и использует его для поиска пути.
*/
private function findPath():void
{
var astar:AStar = new AStar();
if(astar.findPath(_grid))
{
_path = astar.path;
_index = 0;
addEventListener(Event.ENTER_FRAME, onEnterFrame);
}
}

/**
* Находит следующий узел пути и перемещает игрока в этот узел.
*/
private function onEnterFrame(event:Event):void
{
var targetX:Number = _path[_index].x * _cellSize + _cellSize / 2;
var targetY:Number = _path[_index].y * _cellSize + _cellSize / 2;
var dx:Number = targetX - _player.x;
var dy:Number = targetY - _player.y;
var dist:Number = Math.sqrt(dx * dx + dy * dy);
if(dist < 1)
{
_index++;
if(_index >= _path.length)
{
removeEventListener(Event.ENTER_FRAME, onEnterFrame);
}
}
else
{
_player.x += dx * .5;
_player.y += dy * .5;
}
}
}
}


У этого класса есть много общего с классом GridView, но есть и несколько важных различий. В конструкторе мы создаем игрока, который представляет собой круг и размещаем его случайно на сцене. Также мы создаем сетку и делаем часть ее узлов непроходимыми.

Методы drawGrid() и getColor() по сути те же, что и в предыдущем примере.

Здесь мы слушаем событие MouseEvent.Click. Когда происходит клик по сетке мы устанавливаем в качестве начального узла тот узел, в котором находиться игрок и в качестве конечного – узел, по которому кликнули. Затем мы перерисовываем сетку, чтобы отобразить изменения и вызываем метод findPatch().
Метод findPatch() создает экземпляр класса AStar и использует его для поиска пути. Если он найден, то сохраняем его в переменную и устанавливаем свойство _index = 0, тем самым соотнося позицию игрока с первым узлом в массиве пути. Затем подписываемся на получение события Event.ENTER_FRAME и устанавливаем для него в качестве слушателя метод onEnterFrame().

Метода onEnterFrame() берет тот узел из массива пути, который определен значением _index, определяет расстояние между этим узлом и игроком и перемещает игрока в этот узел. Если используется последний узел в массиве пути, то мы отписываемся от получения события Event.ENTER_FRAME.

Итак, вот что у нас должно получится в итоге:

[SWF]http://coolisee.com/wordpress/wp-content/uploads/2010/05/21/pathfinding/Game.swf, 600, 600[/SWF]



Продвинутый ландшафт

Есть еще одно понятие, упоминаемое в самом начале, но еще не рассмотренное нами. Это – идея разной стоимости для непроходимых узлов. Не будем слишком углубляться в эту тему, а рассмотрим самые основы.

Например, узел грунтовой дороги имеет большую стоимость, чем узел дороги с асфальтным покрытием, а узел с болотом или горами имеет еще большую стоимость. Различная стоимость элементов ландшафта может быть реализована добавлением свойства дополнительной стоимости в класс Node, который будет выступать в роли множителя. Для пустого узла это значение будет равным 1.0, перемещение в горизонтальном или вертикальном направлении будет стоить как и прежде 1.0, а в диагональном – 1.414. Однако у узлов с плохой проходимостью этот множитель может быть равным 2.0, таким образом, их окончательная стоимость была бы 2 и 2.828 соответственно.
Это заставляет AStar избегать труднопроходимых узлов и отдавать предпочтение простым узлам, даже если они дают более длинный путь. В определенной ситуации стоимость пути через болото может оказаться меньшей, чем стоимость пути вокруг болота.

Для реализации этой идеи добавим новое свойство costMultiolier в класс Node:

package
{
/**
* Представляет отдельный узел.
*/
public class Node
{
public var x:int;
public var y:int;
public var f:Number;
public var g:Number;
public var h:Number;
public var walkable:Boolean = true;
public var parent:Node;
public var costMultiplier:Number = 1.0;

public function Node(x:int, y:int)
{
this.x = x;
this.y = y;
}
}
}


Теперь нам нужно изменить формулу определения полной стоимости в классе AStar. Было:

var g:Number = node.g + cost;


Стало:

var g:Number = node.g + cost * test.costMultiplier;


Теперь стоимость каждого узла откорректирована в соответствии с его свойством costMultiplier. На рисунке 24 я изменил класс GridView добавлением узлов с различными costMultiplier в случайном порядке. Кроме того я окрасил каждый узел ярче или темнее, в зависимости от его свойства costMultiplier. Белые узлы лучше проходимы для игрока, чем более темные. Все эти изменения можно найти в классе GridView2.as


Рисунок 24



Теперь, если вы сделаете часть узлов непроходимыми, то путь будет проходить через узлы с меньшей проходимостью. См рисунок 25.


Рисунок 25



[SWF]http://coolisee.com/wordpress/wp-content/uploads/2010/05/21/pathfinding/PathfindingWithGridView2.swf, 600, 600[/SWF]



На этом все. Исходники

12 комментариев:

  1. А как сделать, чтобы круг не двигался рывками? А шёл плавно по пути?

    ОтветитьУдалить
  2. вот может поможет, делал на скорую руку
    патч - это массив нодов, World.CELL_SIZE - это размер ячейки, position и velocity это векторы позиции и скорости соответственно
    if (_path != null && _index < _path.length)
    {

    var tx:int = _path[_index].x * World.CELL_SIZE;
    var tz:int = _path[_index].z * World.CELL_SIZE;

    if (tx < position.x)
    {
    velocity.x = - _maxSpeed;
    position.x += velocity.x*_maxSpeed;

    if (position.x < 0)
    {
    position.x  = 0
    }
    }
    else if (tx > position.x)
    {
    velocity.x = _maxSpeed;
    position.x += velocity.x*_maxSpeed;

    if (position.x > 384)
    {
    position.x  = 384
    }
    }

    if (tz < position.z)
    {
    velocity.z = - _maxSpeed;
    position.z += velocity.z*_maxSpeed;

    if (position.z < 0)
    {
    position.z  = 0
    }
    }
    else if (tz > position.z)
    {
    velocity.z =  _maxSpeed;
    position.z += velocity.z*_maxSpeed;

    if (position.z > 384)
    {
    position.z  = 384
    }
    }

    if (tz == position.z && tx == position.x)
    {
    _index++;

    if (_index >= _path.length)
    {
    _index = 0;
    _path = null;
    return;
    }
    }

    if (tz == position.z)
    {
    velocity.z =  0;
    }

    if (tx == position.x)
    {
    velocity.x =  0;
    }

    x = position.x;
    z = position.z;
    }

    ОтветитьУдалить
  3. Спасибо за отзыв. А куда это всё хозяйство вставлять? В обработчик onEnterFrame ?

    ОтветитьУдалить
  4. ну да, только придется его наверно немного адаптировать :)

    ОтветитьУдалить
  5. Я не совсем понимаю как этот код работает. откуда взялось position.z ? Его ж в роде не было в коде. Если не затруднит можете объяснить?

    ОтветитьУдалить
  6. да, этого не было в коде, потому что этот кусок вообще другой программы, но где я использовал этот поиск пути. position и velocity - это векторы определяющие позицию и координаты объекта. Про это можно посмотреть в переводе про steering behaviors (управление поведениями) Тут ничего сложного, если действительно есть необходимость, то вы разберетесь без проблем :)

    ОтветитьУдалить
  7. Всё я уж по своему решил проблему. Но всё равно спасибо за помощь ;)

    ОтветитьУдалить
  8. что это за быдлкод в файле astar
     




    088
    for(var o:int = 0; o < _open.length; o++)








    089
    {








    090
    }

    ОтветитьУдалить
  9. а вообще клёво, работает, спасибо большое

    ОтветитьУдалить
  10. for(varo:int= 0; o < _open.length; o++)






    089
    {






    090
    }













    Что это? Так и не понял.(

    ОтветитьУдалить