Медленная работа над реализацией A * в игре защиты башни

Я делаю игру Tower Defense во Flash без предопределенного пути.

Хотя моя сетка 40x40 (малая?), A * борется при перерасчете каждый раз. Поэтому я сделал свою собственную модификацию, чтобы облегчить пересчет, а количество затронутых клеток упало примерно до 900 (при изменении возле корня). Он все еще замерзает за очень короткое, но обнаружимое количество времени, когда размещается новая башня.

Является ли это проблемой реализации, или слишком много 40x40?

Изменить:

Структура моего кода:

  • Все данные сохраняются в 2d массиве ячеек.
  • Каждая ячейка содержит своего родителя в направлении пути (1-8 по часовой стрелке) и побитокодированного массива его дочерних элементов в пути (каждый бит представляет собой дочерний элемент).
  • Поиск выполняется с помощью A * с оценкой эвклидовости.
9 голосов | спросил Dani 28 J000000Wednesday10 2010, 08:20:19

5 ответов


4

Я не могу комментировать, но первый профиль в Flex, все остальное - гипотеза.

ответил Jonathan Fischoff 28 J000000Wednesday10 2010, 08:26:56
13

Я предполагаю, что TD - это «Защита башни»

Я думаю, что A * для этого немного за борт.

В начале игры наводнение заполняет зону игры из точек выхода, чтобы создать карту движения:

 |---------|
 |5|4|3|3|3|
 |5|4|3|2|2|
->5|4|3|2|1->
 |5|4|3|2|2|
 |5|4|3|3|3|
 |---------|

, и движение всегда соответствует квадрату с меньшим значением.

Когда игрок размещает башню, обновляйте каждый из восьми смежных квадратов: для каждого квадрата установите его значение движения на одно больше, чем самое низкое смежное значение. Если значение изменится, повторите процесс, центрированный на обновленном квадрате. Затем, чтобы проверить, что маршрут до выхода не заблокирован, убедитесь, что все квадраты смежны с квадратом меньшего значения.

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

Более простой подход заключается в повторном заполнении заливки.

ответил Skizz 28 J000000Wednesday10 2010, 17:46:26
2

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

ответил Kaj 28 J000000Wednesday10 2010, 19:46:55
0

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

ответил Iain 28 J000000Wednesday10 2010, 14:25:14
0

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

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

ответил jhocking 26 PMpTue, 26 Apr 2011 20:05:33 +040005Tuesday 2011, 20:05:33

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132