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

10

Я делаю Tower Defense, и у меня есть базовая работа по поиску пути, но у меня есть проблема.

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

Так что мне нужен способ найти кратчайший путь, который, что более важно, имеет наименьшее количество башен на пути.

Как я могу это сделать?

algorithm path-finding tower-defense Дани
источник
1
разве это не будет обнаружением столкновения на вашем пути?
Prix
Поскольку блокирующие башни разрушаемы, на самом деле путь существует. Просто стоимость перемещения через них намного выше, чем движение по беспрепятственному пути. (См. Ответ от Coderanger ниже)
bummzack

Ответы:

21

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

coderanger
источник
хотел бы увидеть пример кода этой реализации, звучащий просто и
надежно
3
Алгоритм A * ( en.wikipedia.org/wiki/A * _search_algorithm) работает со стоимостью пути. Просто увеличьте стоимость сегментов, проходящих через башню. Затем ваши агенты попытаются избежать башен или, если «дешевле» атаковать башню, они нападут на нее. Идея алгоритма A * состоит в том, чтобы минимизировать стоимость, поэтому вы должны быть в состоянии достичь того, что вы хотите, просто изменив стоимость пути ...
bummzack
Это отличное решение, о котором я бы не подумал, спасибо!
Джокинг
Просто примечание: предоставление узлам башни огромных затрат на перемещение без увеличения оценки, используемой для алгоритма A *, когда путь явно заблокирован, будет означать, что ваши агенты проверят каждый узел на своей части препятствия, прежде чем принять решение об остановке. через точку. В зависимости от количества узлов и агентов это может сделать алгоритм чрезмерно медленным.
Мартин Сойка