Как улучшить производительность моего A * path finder?

Так что в основном я закодировал A * pathfinder, который может найти пути через препятствия и двигаться с диагнозом. Я в основном реализовал псевдокод от http://www.policyalmanac.org/games/aStarTutorial.htm до реального кода, а также использовал метод двоичной кучи для добавления и удаления элементов из открытого списка.Как улучшить производительность моего A * path finder?

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

проблема в том, что она по-прежнему занимает около 1,5 млн. Наносекунд, что составляет около 0,0015 секунды.

Итак, вопрос заключается в том, что мой план состоит в том, чтобы сделать игру защиты башни, где каждый раз, когда я должен добавить карту башни, каждый раз нужно обновлять траекторию. Если бы у меня было около 50 мобов на карте, это означает, что для обновления всех путей для всего моба потребуется около .0015 * 50 = .075 секунд. Игра в основном тикает (все обновления игрового материала) каждые 1/60 секунды, что составляет 0,016 секунды, поэтому проблема в том, что для обновления путей требуется больше времени, чем требуется для галочки, что приведет к большому отставанию. Итак, как мне это сделать? Мне нужно найти лучший алгоритм для сортировки открытого списка или как-то разделить задачи поиска пути, чтобы каждый тик только X-число задач поиска пути, в отличие от всех из них.

источник

2013-02-27 GayLord

Ваш вопрос является слишком специфичен для уровня описания вы дали нам. –

Вместо поиска от каждого противника до контрольно-пропускного пункта, выходите наружу от контрольно-пропускного пункта к каждому врагу одновременно. Таким образом, вместо того, чтобы выполнять 50 поисков, вам нужно только сделать это.

Более конкретно, просто сделать поиска в ширину (или djikstra's, если ваш график взвешивается) от игрока наружу, пока не был достигнут каждый враг.

Вы могли бы изменить эту стратегию для работы с *, изменив эвристики EstimatedDistanceToEnd(ака h(x)) быть минимальная оценка для любого врага, но с большим количеством врагов, это может в конечном итоге медленнее, чем простой вариант , Для этого необходимо использовать эвристику consistent.

Кроме того, убедитесь, что используете correct tie-breaking criteria.

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

Если это еще слишком медленно, вы можете изучить D* lite для повторного использования информации между последующими поисками. Но я бы поставил деньги на то, что запуск одного поиска по ширине в несколько раз будет более чем достаточно быстрым.

(копируется из моего ответа на a similar question на игростроениях)

источник

2013-02-27 19:05:00

Является ли Djisktra или ширина первой быстрее, чем A * pathfinder? Я до сих пор не совсем понимаю ваши объяснения по поводу EstimatedDistanceToEnd, но мне очень интересно сначала попробовать djistra/widthth, если они приведут к значительному повышению производительности. Также я прочитал статью, которую вы предоставили, но не понимает, как ее можно использовать для навигации по нескольким целям (в моем случае - противникам). Я также искал оба алгоритма и не нашел никаких дружественных статей, которые я могу использовать для написания кода. Знаете ли вы о каких-либо статьях, таких как http://www.policyalmanac.org/games/aStarTutorial.htm – GayLord

Также будет ли поиск по ширине самым коротким путем? Я прочитал статью, и это кажется более простым, чем A *. Я просто не знаю, даст ли он мне кратчайший путь или нет. PLS ответить – GayLord

@GayLord: Да, это будет –

Вы считали алгоритм Флойда-Варшалла?

По существу, A * предназначен для поиска путей из одного источника в один или несколько пунктов назначения. Однако в защите башни (в зависимости от ваших правил, конечно) речь идет о нескольких источниках, перемещающихся по карте.

Так что для этого алгоритм Флойда кажется более оптимальным. Тем не менее, вы могли бы найти алгоритм поиска A * для групп вместо отдельных единиц, что должно оптимизировать ваши расчетные времена.

источник

2013-02-27 14:54:46 ryrich

-1 Floyd-Warshall предназначен для поиска кратчайших путей всех пар. Это будет ужасно ** неэффективно для игры в защиту башни. См. Мой ответ. –

Так что я парень, который изначально задал вопрос. Моя цель прямо сейчас - создать игру, такую как настольная защита башни. Вы можете добавить/удалить башни на карте, и враги изменят свой путь соответственно. Очевидно, я считаю, что делать это с A * будет очень медленным, потому что я планирую иметь на карте как минимум 50 объектов и каждый из них пересчитывает свой путь каждый раз, когда игрок добавляет/удаляет башню, потребуется много времени. Итак, какой алгоритм я должен использовать? До сих пор люди рекомендовали quadtree, d lite, djikstra, поиск точки прыжка, но на самом деле не могут найти никого дружелюбного пользователя на этих – GayLord

@ BlueRaja-DannyPflughoeft. Вы могли бы настроить его для приложения защиты башни. По существу, всякий раз, когда узел изменяется, он будет пересчитывать стоимость этого узла из окружающих плит и для каждого окружающего фрагмента, _if_ он изменился, алгоритм вызывается на них. Таким образом, нет необходимости в повторном расчете «игры». A * не будет оптимальным, так как обычно количество источников перевешивает количество плиток на доске, и вам нужно будет перезапустить алгоритм каждый раз, когда «что-то» изменилось ... – ryrich

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

источник

2013-02-27 16:06:41 themel

Как улучшить производительность моего A * path finder?

ответ

Смежные вопросы