Войти
ПрограммированиеФорумИгровая логика и ИИ

Принцип работы алгоритма поиска пути Астар (A*). (Комментарии к статье) (3 стр)

Страницы: 1 2 3 4 5 6 Следующая »
#30
14:13, 26 фев 2004

Ok, что тъ имееш ввиду говоря 'LOD' - какой LOD, чего - пространства, оценочной функции..?

#31
14:31, 26 фев 2004

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

#32
18:20, 26 фев 2004

Cupper
Ну раз так, то имплементация етого имхо будет одна и та-же как для А*, так и для волнъ. Вот только такое трудно делать, где ландшафт с весами по тайлам...

#33
18:30, 26 фев 2004

Zemedelec
Прочти, что я написал.
Список Closed - абстракция, единственное предназначение которой - определение факта повторной обработки узла. То есть проверка "IN CLOSED" в абстрактном описании алгоритма в AI Wisdom - это проверка на то, что узел уже обрабатывался и у него есть какой-то назначенный вес. В зависимости от этого, мы либо обращаем внимание на этот "старый вес", либо нет. Всё.
Для грида реализация такой проверки списком - маразм. Гораздо эффективнее сделать эту проверку либо флагами в самих узлах, либо инициализацией весов узлов неким запредельным значением.

Cupper
Psych
Zemedelec дал ссылку на неплохую книгу.
Подумайте ещё раз. Если эвристика - расстояние до цели или вес до цели, то на каждом шаге алгоритма будет взят узел, находящийся ближе всех к цели. В итоге получаем прямую линию. Наиболее распространённая эвристика - сумма веса узла и расстояния до цели (то есть в плоском случае сумма расстояний до старта и до финиша). В таком случае, если на прямой встретится зона с весом равным стоимости обхода по единицам, то будет рассмотрен обход.

#34
19:04, 26 фев 2004

had
ИМХО - флаги вместо closed листа это маразм. Тем более что можно использовать хэш (и никаких листов). Но не будем об этом спорить.

#35
20:51, 26 фев 2004

had
Для грида реализация такой проверки списком - маразм...
Ето мне извесно.

Cupper
ИМХО - флаги вместо closed листа это маразм. Тем более что можно использовать хэш (и никаких листов). Но не будем об этом спорить.
Если принадлежность к Open/Closed спискам реализированна флагами в гриде, то тогда проверка и доступ к етим нодам будет O(1), что никакой хеш или bin_heap не побьет. Конечно надо все протестить в конкретной ситуации, так как memory footprint у етого метода больше намного.

#36
12:13, 27 фев 2004

Zemedelec
Так флаги потом чистить надо.
Давайте все кто хочет поспорить лучше в приват, ко мне в аську: 116151665 или по мылу

#37
12:43, 27 фев 2004

Cupper
Нет, если людей несколько - только в форуме.

Флаги надо чистить, да, но ето делается только для прямоугольника в котором искали, т.е. не на всей карте. А иначе - очень спорно, будет ли ето медленее, чем поиск в хешах и вся возня по поддержке более умнъх структур.

#38
13:03, 27 фев 2004

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

#39
13:05, 27 фев 2004

Zemedelec
Скорее всего для поиска на небольшие расстояния можно обойтись и флагами.
А вот если идти через полкарты и она большая, лучше наверное пользоваться хэшем.

#40
13:34, 27 фев 2004

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

#41
13:54, 27 фев 2004

had
все хорошо, но
Битовый массив мне лично не подходит, так как у меня присутствует динамическое добавление и удаление подслоев карты путей.
далее как мне оценить до поиска пути количество нод в пути, чтобы сравнить его с количеством всех нод?
У меня нет ни малейшего желания чистить всю карту если юниту приспичило пройтись на пять метров.

PS:
когда я говорил что для поиска пути на небольшие расстояния быстрее флаги, я подразумевал что можно легко обозначить прямоугольник или прямоугольники для очистки этих флагов.

#42
13:56, 27 фев 2004

Cupper
Идти через полкартъ надо йерархическим поиском и ничем другим.

had
Можно скажем битовъй массив с флагами + индексом на нод, а лучше - только индекс на нод, в самом ноде флаги. Индекс - 16 битов.

#43
14:11, 27 фев 2004

Zemedelec
Иерархический поиск применим только если карту можно разделить на условные зоны/локации. А так не всегда получается. Или я не прав?

Использовать битовый массив имеет смысл только если он действительно битовый, иначе может получиться большой кусок памяти для очистки.

Сегодня завтра попробую сравнить битовые массивы против хэша.

#44
14:20, 28 фев 2004

had
Zemedelec
Результаты сравнения значится такие: использование битовых массивов оказалось быстрее, прирост скорости по сравнению с хэш-вариантом составил 10-18 % в зависимости от размеров и сложности карты и дальности поиска пути.
Спасибо за идею.
edit:
цифры верны для конкретного проекта, так как считалось время всего поиска. Прирост скорости самого алгоритма должен быть немного больше.

Страницы: 1 2 3 4 5 6 Следующая »
ПрограммированиеФорумИгровая логика и ИИ

Тема в архиве.