Низкая производительность при реализации A * в игре Tower Defense

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

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

Это проблема реализации или 40х40 слишком много?

Редактировать:

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

• Все данные сохраняются в 2d массиве ячеек.
• Каждая ячейка содержит своего родителя в направлении пути (1-8 по часовой стрелке) и битовый кодированный массив ее дочерних элементов в пути (каждый бит представляет дочерний элемент).
• Поиск осуществляется по A * с оценкой евклидова расстояния.

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

Я предполагаю, что TD это «Tower Defense»

Я думаю, что 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|
 |---------|

и движение всегда к квадрату с более низким значением.

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

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

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

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

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

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

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