Pull to refresh

Поиск пути в гексагональной сетке (AS3)

Algorithms *
Sandbox
imageЭта статья представляет собой описание компонента HexaPath, реализующего поиск пути по алгоритму А* в гексагональной сетке. В сети мной было найдено большое количество описаний алгоритма на примере квадратной сетки и некоторое количество реализаций, но ни одного упоминания о шестиугольной сетке. И я написал свою реализацию. Выкладываю исходники. Вдруг кому-нибудь понадобится это, а писать самому будет лень.


Описание компонента


На самом деле это не один класс, а несколько:
  • NumberPoint.as – урезанный аналог класса Point
  • PathList.as – реализация списка (открытого и закрытого). Что это такое смотри в описании алгоритма.
  • HexaGrid.as – работа с шестиугольной сеткой (нахождение соседей по координатам ячейки, нахождение координат центра и углов ячейки по её координатам и т.д.)
  • HexaPath.as – непосредственно сама реализация алгоритма.


По некоторым соображениям я выбрал такое расположение ячеек:

image

Сама сетка задаётся обычным двумерным массивом, в котором значениями ячеек являются «стоимость перехода» в эту ячейку. Если «стоимость перехода» больше или равна HexaGrid.MAX_AVAILABLE, то ячейка интерпретируется как непроходимая.

Работа с компонентом не представляет никакой сложности. Для начала необходимо иметь двумерный массив с заполненными «стоимостями перехода». Такой массив можно создать например так:

HexaGrid.init(width, height);

Это создаст массив, в каждой ячейке которой будет значение 1.

Заполнение ячеек «стоимостями» производится так:

HexaGrid.grid[x][y]=value;

Cкормим созданный массив классу HexaPath

var res:Boolean=HexaPath.setMap(HexaGrid.grid);

Функция проанализирует массив и если всё нормально, вернёт true.
Теперь можно запрашивать путь:

var result:Object=HexaPath.createPath(source:Point, target:Point);

структура переменной result такова:
result['status']:int;
result['path']:Array;


result['status']=1, если путь просчитан успешно, -1 – если что-то произошло.
А произойти может такое:
  • координаты начала или конца выходят за пределы массива
  • координаты начала или конца находятся в непроходимых ячейках.

Если result['status']=1, то в переменной result['path'] находится сформированный массив координат ячеек пути. В каждой ячейке массива переменная типа Object, у которой координаты ячейки находятся в свойстве coords. Сумбурно? Сейчас прокомментирую кодом:

var result:Object=HexaPath.createPath(new Point(0, 0), new Point(5, 5));
var path:Array= result['path'];
var first_cell:Point=path[0]['coords'];

и так далее.

Вот в сущности и всё. Реализация получилась довольно резвая.
Демку можно посмотреть здесь.
Исходники качаются отсюда.

Надеюсь, кому-нибудь мой труд пригодится…

UPD. ilyaplot переписал реализацию этого алгоритма на php. Скачать можно тут.
Tags:
Hubs:
Total votes 96: ↑88 and ↓8 +80
Views 14K
Comments Comments 48