Поиск пути в двухмерном пространстве: компонент AStar (action script 3.0)

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


Файл компонента можно найти здесь:
1) depositfiles.com/files/ptsxof3p9
2) ifolder.ru/14260428

СУТЬ ПОИСКА

Для успешного поиска, плоскость, по которой движется и ищет путь некая сущность, должна делиться на «плитки» (см. рисунок 1). Я, как правило, храню информацию о таком поле в двухмерном массиве объектов.

Рисунок 1 – Поле из «плиток» (закрашенные плитки это препятствия)

В каждом объекте, описывающем «плитку» (с этого момента давайте перейдем на термин «узел» вместо «плитки») в простейшем случае хранятся её координаты на экране и признак того, является ли эта плитка препятствием. Как правило, это булево выражение, где при значении true данный узел это препятствие, а при false — свободный для прохождения узел. При разработке компонента я придумал термин «карта препятствий», он будет полезен при объяснении работы компонента. Карта препятствий — это двухмерный массив, который хранит булевы выражения, характеризующие проходимость каждого узла (является ли узел препятствием или нет). На основании карты препятствий компонент осуществляет поиск пути.
Теперь давайте на простейшем примере создадим карту препятствий, после чего перейдем к изучению методов компонента. Допустим, мы хотим создать поле 5 на 7 и сделать некоторые клетки непроходимыми для этого делаем следующее:

1) Проинициализируем карту препятствий, задав каждому узлу значение false – свободный для прохождения узел

var obstacle_map:Array=[];
for (var i:int=0; i<5; i++) {
  obstacle_map[i]=[];
  for (var j:int=0; j<5; j++) {
    obstacle_map[i][j]=false;
  }
}

2) Теперь выберем некоторые узлы и сделаем их препятствиями, поменяв их значения на true.

obstacle_map[0][0]=true;
obstacle_map[1][1]=true;
obstacle_map[2][1]=true;
obstacle_map[2][3]=true;
obstacle_map[3][3]=true;
obstacle_map[4][3]=true;
obstacle_map[0][4]=true;

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

Рисунок 2 – Карта препятствий

Итак, карта препятствий создана, давайте теперь разберемся в методах компонента AStar.

СВОЙСТВА И МЕТОДЫ КОМПОНЕНТА – СТРОИМ ПУТЬ

Чтобы компонент работал, необходимо задать ему карту препятствий, но обо всем по порядку, сначала объявление и создание экземпляра данного компонента:

var a_star:AStar=new AStar();


Теперь нужно добавить к объекту a_star слушатель события a_star.ERROR:

a_star.addEventListener(a_star.ERROR,onError);


Как видно из названия события, данный слушатель предназначен для регистрации событий ошибок. В данном примере при возникновении события ошибки вызывается метод onError. Этот метод может выглядеть, например, так:

private function onError(e:Event):void{
  trace(a_star.lastError);
  }



Таким образом, мы всегда можем обратиться к тексту последней ошибки в объекте a_star, обратившись к его свойству lastError. Есть всего две ошибки – ошибка карты препятствий и ошибка поиска. На рисунке 3 представлен пример вывода в output ошибки карты препятствий. Любая ошибка в компоненте сопровождается описанием, с помощью которого легко понять, что именно послужило причиной ошибки.



Рисунок 3 – Пример текста ошибки

Далее необходимо задать карту препятствий:

a_star.setObstacleMap(obstacle_map);


ВНИМАНИЕ! Слушатель AStar.ERROR необходимо добавить сразу после создания объекта класса AStar, до задания карты препятствий. Поясню подробней, зачем это нужно. В данном компоненте корректность карты препятствий определяется в методе setObstacleMap и если здесь что-то неверно, то происходит событие ошибки и свойство lastError получает значение ошибки карты препятствий. Поэтому если слушатель добавлен после карты, то в результате выполнения программы вы получите другую ошибку – ошибку поиска и произойдет она только в тот момент, когда Вы попытаетесь осуществить поиск пути. В принципе, рано или поздно Вы найдете ошибку, т.к. ошибаться тут, в общем то, негде, однако, следуя простому правилу добавлять слушателя сразу после создания экземпляра класса AStar, Вы сэкономите себе немного времени.

После этого следует добавить слушателя события Event.COMPLETE:

a_star.addEventListener(Event.COMPLETE,onComplete);

Метод onComplete разберем чуть позже, а перед этим остановится на установке свойства clippingType (устанавливать это свойство необязательно):

a_star.clippingType=<значение>

Это свойство может принимать одно из трех значений, их легко запомнить: a_star.F (от слова full), a_star.P (от слова prevent) и a_star.N (от слова none). По умолчанию свойство установлено в a_star.N и если Вы не зададите это свойство, то в принципе ничего страшного не случится. Чем же управляет данное свойство? Оно управляет тем, как огибаются препятствия и как собирается путь. Проще всего это пояснить графически. На рисунке 4 изображена наша созданная ранее карта препятствий и на ней отмечены буквой S (start) начало пути, а буквой f (finish) конец пути.



Рисунок 4 – Карта препятствий с отмеченными точками начала и конца пути

А теперь давайте посмотрим как будет построен путь при различных значениях свойства clippingType (см. рисунок 5)



посмотрим на рисунок 5.а – если clippingType=a_star.N то в результате будет построен кратчайший путь с учетом восьми направлений.
Теперь рассмотрим рисунок 5.б – здесь ситуация чуть интереснее, поэтому остановимся подробней. Вариант clippingType=a_star.P идеально подходит для перемещения персонажа игры. Ведь в противном случае ситуация следующая: не важно, какая у вас камера (обычный вид сверху, изометрия или вы используете одни из 3D движков) персонаж, передвигаясь по диагонали рядом с препятствием, будет перекрывать его. Иными словами, графическое представление игрока частично «залезает» на препятствие, чего быть не должно. Это наглядно показано на рисунке 6, где белый кружок это персонаж, а стрелка – направление его движения.



Рисунок 6 – Перекрытие препятствия персонажем

Но при установке clippingType=a_star.P на открытом пространстве (без препятствий) персонаж может двигаться по диагонали, но вблизи препятствий он обязательно будет их обходить. Таким образом, в данном случае путь не всегда кратчайший, но более реалистичный.

Рисунок 5.в показывает случай, который вряд ли будет часто использоваться – при clippingType=a_star.F мы получим кратчайший путь с учетом четырех направлений. Т.е. никаких диагональных перемещений.
Мы сделали почти все, кроме собственно получения самого пути. Поиск осуществляется очень просто, для этого есть метод:

AStar.findPath(_startx:int,_starty:int,_targetx:int,_targety:int):void

Например мы хотим построить путь от ячейки {0,1} в ячейку {6, 3}. Для этого вызовем метод findPath:

a_star.findPath(0,1,6,3);

Как только поиск будет закончен, произойдет событие Event.COMPLETE (помните, мы добавляли слушателя на него?), и тогда мы можем считать из объекта a_star путь. Давайте для примера запишем путь из a_star в переменную my_path:Array:

private function onComplete(e:Event):void{
    my_path=a_star.getPath();
}

Итак, мы получили массив, в котором содержится путь. Этот массив состоит из объектов вида { _x: <координата по горизонтали>, _y: <координата по вертикали>}. Чтобы точно всем было ясно, приведу как будет выглядеть путь для рисунка 5.а:

my_path=[
{_x:0,_y:1},
{_x:1,_y:0},
{_x:1,_y:2},
{_x:1,_y:3},
{_x:2,_y:4},
{_x:3,_y:5},
{_x:3,_y:6}
];

Вот и всё. Надеюсь Вам пригодится этот компонент, дорогой читатель.