Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 48
Опа. Спасибо, как раз актуально
а описание алгоритма будет?
blitzetc.blitzmax.ru/index.php/Алгоритм_A*_для_новичков вот на русском языке (перевод)
Демка хорошая.
Эх, выложить чтоли свой собственный эффективный нестандартный Field-Of-View на хексагональной сетке :)
а что вы имеете в виду под fov? интересно посмотреть…
Область видимости из заданного хекса. У меня алгоритм не просто видно/не видно. Каждому хексу присваивается какое-то значение, для заданного шестиугольника и для всех в определенном радиусе вычисляется минимум суммы значений по всем проходящим лучам. Вместо суммы можно брать и максимум. Таким образом, можно строить сложные условия на видимость.
Выложите)
AI в Dragon Age очень похоже бегает. Особенно первая треть характерная. Наверное, там тоже хексы.
алгоритм волны (А*) применим к любой абстрактной сетке. главное условие: путь от клетки к клетке должен был равным. а как визуально это представить — дело второе.
A* и волновой — это не одно и то же.
Обидно, рисовал карту, потом нажал глянуть, что такое «60» и все стерлось((
Было бы еще очень хорошо, если в демку добавить отображение «веса» пути
Уперся в ту же фигню в своём решении на JavaScript. Если относительно далеко на карте приказать двигаться объекту — будет неприятный лаг. А если выбрано несколько объектов — так вообще ппц:
Сразу заметно, что автор плохо изучил вопрос:
«В сети мной было найдено большое количество описаний алгоритма на примере квадратной сетки и некоторое количество реализаций, но ни одного упоминания о шестиугольной сетке»
— Алгоритм А* одинаково работает на всех видах графов, т.е. ему абсолютно всё равно какого вида ячейки и сколько у них связей. Внимательно изучите теорию.
«работа с шестиугольной сеткой (нахождение соседей по координатам ячейки, нахождение координат центра и углов ячейки по её координатам и т.д.)»
— Так никто не делает, так как более оптимально изначально статически задать параметры игрового поля, а не динамически вычислять каждый раз. Я понимаю, что лень писать много строк кода, но производительность системы из-за этого снижается.
По поводу двух координат:
— Я понимаю, что визуально проще представить сетку в двух осях, но обрабатывать такую конструкцию тяжелее. Практически во всех нормальных решениях, которые я встречал используют порядковое обозначение ячеек.
«В сети мной было найдено большое количество описаний алгоритма на примере квадратной сетки и некоторое количество реализаций, но ни одного упоминания о шестиугольной сетке»
— Алгоритм А* одинаково работает на всех видах графов, т.е. ему абсолютно всё равно какого вида ячейки и сколько у них связей. Внимательно изучите теорию.
«работа с шестиугольной сеткой (нахождение соседей по координатам ячейки, нахождение координат центра и углов ячейки по её координатам и т.д.)»
— Так никто не делает, так как более оптимально изначально статически задать параметры игрового поля, а не динамически вычислять каждый раз. Я понимаю, что лень писать много строк кода, но производительность системы из-за этого снижается.
По поводу двух координат:
— Я понимаю, что визуально проще представить сетку в двух осях, но обрабатывать такую конструкцию тяжелее. Практически во всех нормальных решениях, которые я встречал используют порядковое обозначение ячеек.
«работа с шестиугольной сеткой (нахождение соседей по координатам ячейки, нахождение координат центра и углов ячейки по её координатам и т.д.)» — это всего лишь несколько арифметических действий. не думаю, что было бы быстрее всё это посчитать заранее и потом вытаскивать из массива.
«порядковое обозначение ячеек» — это ещё сложней, так как для разной размерности карты и порядковые номера, например, соседей будут другие. опять же придётся их вычислять по какому-нибудь алгоритму. или я не правильно вас понял?
«порядковое обозначение ячеек» — это ещё сложней, так как для разной размерности карты и порядковые номера, например, соседей будут другие. опять же придётся их вычислять по какому-нибудь алгоритму. или я не правильно вас понял?
Вы меня не поняли.
Вычислять связи ячеек вообще не надо. Игровое поле статично, т.е. порядок связей между ячейками не меняется. Поэтому самый простой и оптимальный вариант это дать обозначение ячеек порядковыми числами (одной «координатой») и изначально задать одномерный массив связей ячеек. Работает это быстрее, чем ваш вариант.
Посмотрите, как это реализовано в других проектах.
Вычислять связи ячеек вообще не надо. Игровое поле статично, т.е. порядок связей между ячейками не меняется. Поэтому самый простой и оптимальный вариант это дать обозначение ячеек порядковыми числами (одной «координатой») и изначально задать одномерный массив связей ячеек. Работает это быстрее, чем ваш вариант.
Посмотрите, как это реализовано в других проектах.
но как производить поиск пути в такой системе координат? и всё равно не вижу, чем это будет быстрее.
покажите примеры проектов с такой системой координат. интересно посмотреть.
покажите примеры проектов с такой системой координат. интересно посмотреть.
Вы предлагаете в каждой из ячеек хранить ссылку на её соседа?
Да, в каждой ячейке хранить ссылку на соседа.
Можно даже указывать направление на соседа, если будет анимация поворота.
Конечно, получается очень большая структура данных, которую очень долго прописывать, но в реальных системах работают именно так. Дело в том, что в реальных проектах данный алгоритм выполняется как и на клиенте, так и на сервере очень много раз и вычисление каждый раз связей между ячейками даёт неплохую нагрузку. Поэтому никто эти связи не вычисляет, их задают изначально.
Можно даже указывать направление на соседа, если будет анимация поворота.
Конечно, получается очень большая структура данных, которую очень долго прописывать, но в реальных системах работают именно так. Дело в том, что в реальных проектах данный алгоритм выполняется как и на клиенте, так и на сервере очень много раз и вычисление каждый раз связей между ячейками даёт неплохую нагрузку. Поэтому никто эти связи не вычисляет, их задают изначально.
Ну хорошо. Вы действительно считаете, что (допустим в квадратной сетке) тяжело отнять единицу и получить элемент по индексу в массиве?
Я думаю, речь о том, что самое быстрое решение — это когда координата ячейки хранится как одно целое, для заданной карты смещения до соседних клеток известны, а значит можно получить эти значения путем одного сложения. Ну и еще это можно хранить в массиве(хотя в AS3 лучше будет сделать 6 копий кода, потому как массивы больно медленные).
Демка замечательная — сразу потянуло карту рисовать, с горными озерами и болотистыми дельтами рек :)
С А*, имхо, еще интересно поступиться оптимальностью пути и поиграться с эвристикой ради скорости, например, корректировать эвристику на N шагов вперед, предсказывая длину пути в зависимости от распределения уже пройденных вершин с различными весами и сложностью — что, вроде как, и делают во всяких D* и далее.
С А*, имхо, еще интересно поступиться оптимальностью пути и поиграться с эвристикой ради скорости, например, корректировать эвристику на N шагов вперед, предсказывая длину пути в зависимости от распределения уже пройденных вершин с различными весами и сложностью — что, вроде как, и делают во всяких D* и далее.
Шикарная статья! Спасибо за пару идей!
Не понял о каком рисовании карты идет речь, пока не сделал браузер на весь экран.
Стандартно на моем ноуте 1366*768 не видно низа (
А так интересно )
Стандартно на моем ноуте 1366*768 не видно низа (
А так интересно )
Комментарий чисто по коду —
вместо
var result:Object=new Object();
result['status']=-1;
и
var _path:Array=new Array();
рекомендуется адобом так:
var result:Object = {};
result.status = -1;
var _path:Array=[];
или так:
var result:Object = { status: 0, path: null}
А вообще, использовать generic-объекты не есть хорошая практика (FlexPMD помечает как некритическую лажу), лучше использовать Value Object класс. Тем более, что path у вас в последствии может быть также не просто массивом, а классом со своими служебными методами.
вместо
var result:Object=new Object();
result['status']=-1;
и
var _path:Array=new Array();
рекомендуется адобом так:
var result:Object = {};
result.status = -1;
var _path:Array=[];
или так:
var result:Object = { status: 0, path: null}
А вообще, использовать generic-объекты не есть хорошая практика (FlexPMD помечает как некритическую лажу), лучше использовать Value Object класс. Тем более, что path у вас в последствии может быть также не просто массивом, а классом со своими служебными методами.
Хотелось бы в статьях читать описание алгоритма и/решения (с кусками кода), а так выходит инструкция как пользоватся Вашим трудом.
Спасибо, полезно конечно, но немного интересней было бы если бы Вы описали то, как Вы решали, какие сложности с реализацией A* встретелись в случае гексагональной сетки и какие возможные оптимизации могут быть (или Вы сделали).
Просто иначе это скорее подойдет в какой-то блог именно про ActionScript, а не по алгоритмам в целом.
Спасибо, полезно конечно, но немного интересней было бы если бы Вы описали то, как Вы решали, какие сложности с реализацией A* встретелись в случае гексагональной сетки и какие возможные оптимизации могут быть (или Вы сделали).
Просто иначе это скорее подойдет в какой-то блог именно про ActionScript, а не по алгоритмам в целом.
«Ни одного упоминания о шестиугольной сетке»
Вот тут полно алгоритмов на сетке:
www-cs-students.stanford.edu/~amitp/gameprog.html#hex
Вот тут полно алгоритмов на сетке:
www-cs-students.stanford.edu/~amitp/gameprog.html#hex
я это видел, но это не совсем то, что нужно.
Круто! Вспомнился настольный battletech :')
Как-то тоже пришлось сделать поиск пути на гексагонах. В результате выбрал A*, но писал на PHP.
А есть пример с препятствиями?
А есть пример с препятствиями?
а есть на с++? нужно очень срочно
Спасибо! Отличная работа.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Поиск пути в гексагональной сетке (AS3)