Оптимизация поиска пути A* для нескольких целей

Я хочу переместить некоторые юниты из одного места в другое. Когда я перемещаю 2 или 3 юнита, это не проблема, но когда я пытаюсь переместить 20 или 30, это занимает много времени... Как правило, юниты движутся почти по одному пути, поэтому мне не нужно считать это 20 раз... Я думал, что я нарежу путь от первого юнита, а потом просто "добавлю" пути для остальных юнитов (я имею в виду, что если мы назовем путь 1-го юнита P, это будет (Unit n -> P start) + P + (P end -> Unit n target) для юнита n)... Это отлично работает, но в некоторых случаях делает очень странные вещи, например, когда 2-й юнит находится рядом с целью, он должен перейти к 1-му запуск устройства, а затем обратно к цели ... Как я могу это оптимизировать? Может быть, это хорошая идея, чтобы разделить юнитов на группы, а затем перемещать группы? У меня нет лучших идей...

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


c++ optimization path-finding
person noisy cat    schedule 28.02.2012    source источник
comment
Почему вы хотите повторно использовать путь первого модуля?   -  person Beta    schedule 29.02.2012
comment
@Beata Потому что иначе мне пришлось бы вычислять это несколько раз, и это было бы немного иначе, чем первое...   -  person noisy cat    schedule 29.02.2012
comment
А? Если вы можете вычислить путь для первого элемента, почему бы не вычислить отдельный путь для каждого элемента? Почему они должны идти по стопам друг друга?   -  person Beta    schedule 29.02.2012
comment
@Beata, потому что поиск пути не очень быстрый и займет много времени :/. Я думаю, вам не нужна 20-секундная задержка для перемещения на 100 единиц, а?   -  person noisy cat    schedule 02.03.2012
comment
Насколько оптимален ваш алгоритм A*? Является ли он многоуровневым (т.е. сначала работает на макроуровне, а затем на микроуровне только через макропуть)? Если 100 единиц занимают 20 секунд, похоже, что у вас есть очень большой граф для поиска, что дает много места для этой оптимизации.   -  person Cory Nelson    schedule 26.11.2012
comment
Кроме того, как только вы оптимизируете эту часть, забавным упражнением будет избегать того, чтобы все юниты шли по одному и тому же пути. Это выглядит забавно, и если у ваших юнитов есть обнаружение столкновений, это создаст огромные засоры. Добавьте еще одно измерение — время — и сделайте так, чтобы каждый путь учитывал все остальные пути — оптимизируйте для максимальной пропускной способности, уравновешивая полосу пропускания и расстояние.   -  person Cory Nelson    schedule 26.11.2012

Ответы (3)


arrow_upward
3
arrow_downward

Перспективным решением является кеширование пути.

В частности, кратчайший путь P, состоящий из упорядоченной последовательности узлов от X_0 до X_n, содержит много полезной информации.

Самое главное, что для любого i >= 0 и i ‹ j ‹= n кратчайший путь от X_i до X_j является подпоследовательностью узлов пути P.

Это дает вам довольно много данных (на самом деле, n^2 фрагментов данных), которые вы потенциально можете повторно использовать.

Однако, если ваша карта не меняется, может быть более практичным предварительно вычислить все -пары кратчайшего пути. Это (чрезвычайно) простой в реализации алгоритм, но он занимает O(n^3) времени.

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

person sjdlgjsljg    schedule 01.03.2012

arrow_upward
3
arrow_downward

Я нашел следующее, чтобы помочь.

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

  2. Используйте группы. Рассматривайте группу юнитов как единое целое, назначьте одного из них лидером и найдите для него путь. Другие юниты могут просто следовать по стопам лидера, находя некоторый второстепенный путь к этим следам (таким образом, юниты также избегают препятствий на основном пути). Чтобы это сработало, подбирайте юниты, которые находятся рядом друг с другом, а пути от подчиненных к лидерам должны быть очень маленькими.

  3. Поменяйте точность на интерактивность. Не рассчитывайте все пути сразу, распределите их по времени. Используйте приоритетную очередь для юнитов, которым нужны пути, вытащите несколько, рассчитайте их пути. Вы даже можете установить ограничение по времени для своего кода поиска пути. Я сделал это в сочетании с группировкой и кэшированием путей, это изменение в моей реализации принесло мне наибольшие выгоды.

person Tim Finer    schedule 14.08.2012

arrow_upward
2
arrow_downward

Некоторые мысли:

  1. Начните поиск в общей точке всех поисков: целевой позиции.
  2. Используйте минимальное расстояние по всем единицам в качестве эвристики A *, это допустимая эвристика, которая приводит к оптимальным путям. Вычисления с большим количеством единиц могут быть несколько медленными, здесь вам, возможно, придется проделать некоторые трюки.
  3. Не перезапускайте поиск после нахождения первого юнита, просто продолжайте поиск, пока не найдете их все

Вам нужно инвертировать направления всех проверок «допустимого перемещения», потому что это обратный поиск, но в остальном он, вероятно, работает нормально. За исключением того, что планирование точных путей в начале движения юнитов делает слишком много работы, когда в этом даже нет необходимости, пока путь не выглядит ужасно глупым, игрок не будет возражать. И эти точные пути часто становятся недействительными, если вы считаете, что другие устройства блокируют пути.

person Patrick    schedule 28.02.2012