Эта статья представляет собой описание компонента HexaPath, реализующего поиск пути по алгоритму А* в гексагональной сетке. В сети мной было найдено большое количество описаний алгоритма на примере квадратной сетки и некоторое количество реализаций, но ни одного упоминания о шестиугольной сетке. И я написал свою реализацию. Выкладываю исходники. Вдруг кому-нибудь понадобится это, а писать самому будет лень.
На самом деле это не один класс, а несколько:
По некоторым соображениям я выбрал такое расположение ячеек:
Сама сетка задаётся обычным двумерным массивом, в котором значениями ячеек являются «стоимость перехода» в эту ячейку. Если «стоимость перехода» больше или равна HexaGrid.MAX_AVAILABLE, то ячейка интерпретируется как непроходимая.
Работа с компонентом не представляет никакой сложности. Для начала необходимо иметь двумерный массив с заполненными «стоимостями перехода». Такой массив можно создать например так:
Это создаст массив, в каждой ячейке которой будет значение 1.
Заполнение ячеек «стоимостями» производится так:
Cкормим созданный массив классу HexaPath
Функция проанализирует массив и если всё нормально, вернёт true.
Теперь можно запрашивать путь:
структура переменной result такова:
result['status']=1, если путь просчитан успешно, -1 – если что-то произошло.
А произойти может такое:
Если result['status']=1, то в переменной result['path'] находится сформированный массив координат ячеек пути. В каждой ячейке массива переменная типа Object, у которой координаты ячейки находятся в свойстве coords. Сумбурно? Сейчас прокомментирую кодом:
и так далее.
Вот в сущности и всё. Реализация получилась довольно резвая.
Демку можно посмотреть здесь.
Исходники качаются отсюда.
Надеюсь, кому-нибудь мой труд пригодится…
UPD. ilyaplot переписал реализацию этого алгоритма на php. Скачать можно тут.
Описание компонента
На самом деле это не один класс, а несколько:
- NumberPoint.as – урезанный аналог класса Point
- PathList.as – реализация списка (открытого и закрытого). Что это такое смотри в описании алгоритма.
- HexaGrid.as – работа с шестиугольной сеткой (нахождение соседей по координатам ячейки, нахождение координат центра и углов ячейки по её координатам и т.д.)
- HexaPath.as – непосредственно сама реализация алгоритма.
По некоторым соображениям я выбрал такое расположение ячеек:
Сама сетка задаётся обычным двумерным массивом, в котором значениями ячеек являются «стоимость перехода» в эту ячейку. Если «стоимость перехода» больше или равна 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. Скачать можно тут.