3

Пишу Tower defence для всяких смарт.платформ. Встал вопрос с поиском пути для врага. Условия: территория 16х10, есть несколько точек входа и выхода для врагов. Не знаю какой алгоритм выбрать для поиска пути - волновой или А*. Реализация будет на C++.

Вторая часть вопроса - какие функции/классы должны присутствовать в данных алгоритмах?

1
  • 1
    Можно вообще обойтись без поиска пути если монстры бегают внутри ямы по фиксированной траектории, а башни можно строить только сверху. Дешево и сердито. В вашей же схеме при условии существования возможности продажи/уничтожения башен существует принципиальный баг позволяющий выиграть игру в 100% случаев заключающийся в том что можно победоносно управлять толпой монстров открывая/закрывая проходы как например в этом видео youtube.com/watch?v=j6TuHPBb56s и вся игра теряет смысл.
    – igumnov
    15 янв 2013 в 19:39

2 ответа 2

5

Если на С++ то лучше наверно А* (была бы Java, можно было бы поспороить о выч.затратах).

Соответственно можно добавить ранжирование выходов (например через СтоитмостьПути на участках прилегающих к выходу). Или как-то учитывать мощность оборонительных сооружений (где башни слабее, там ниже СтоимостьПути).

То есть Враги будут щемится во-первых к более интересному выходу (где больше жертв или очков, или как оно у вас придуманно), во-вторых по наиболее легкому пути (до каких-то пор даже бо более длинной (в расстоянии) дороге.

Конечно нужно добавить какой-то случайный коеффициент, чтоб не было "построил модную башню и теперь все враги ходят в обход нее" )) Ну и включать это на полную стоит на высоком уровне сложности (на простом можно все веса брать равными 1 - тогда будут ходить по кратчайшему, как после волнового).

Но в общем может быть забавно)


Ко второй части вопроса: Алгоритм поиска A*.

Плюс функции, которые переберают элементы "игрового мира" и на основании этого пересчитывают матрицу весов. Их лучше вешать на событие (чтоб веса пересчитывались только после изменения конфигурации игрового мира).

Собственно... сам поиск пути тоже можно вешать на событие. То есть при изменении игрового мира (постоили башню, изменилась ценность выхода) пересчитываем пути от каждого входа ко всем доступным выходам, и делаем матрицу с весовыми коеффициентами (тупо - добавили в матрицу 5 раз самый дешевый путь, и по одному разу все остальные и рандомно выбираем путь из матрицы для данного Входа при создании нового Врага).

5
  • Я не думаю, что нужно делать алгоритм выбора пути из возможных чересчур интеллектуальным. В конце-концов, в игрушки играют живые люди, а не программисты, и целью программы должно быть не "показать знание алгоритмики и сделать их всех", а "красиво проиграть юзеру, доставив как можно больше удовольствия от игры". Я бы просто увеличил вероятность прохода по более незащищённому пути, да и то только на финальных уровнях.
    – VladD
    21 дек 2012 в 12:37
  • 2
    Как раз по теме: bormor.livejournal.com/580497.html
    – VladD
    21 дек 2012 в 12:59
  • @VladD Не совсем согласен. Есть легкий уровень - расслабится (там мы не используем алгоритмы), есть сложный - для "задротов" - который практически не прощает ошибок. "Игровой баланс" обычно постигается в ходе тестирования: - Марьванна, я написал тетрис. - Молодец Вовочка! - Только у меня нету скриншота победы в отчете... - Да, я заметила. А почему? - Да выиграть не смог... З.Ы. За ссылку "по теме" - личное спасибо - супер!
    – SilverIce
    21 дек 2012 в 15:10
  • @SilverIce: Кстати, о том же тетрисе: вы наверное знаете, что программа может так бросать, чтобы пользователь гарантировано проиграл вне зависимости от скорости? (Надо бросать S и Z так, чтобы отношение их количеств стремилось к иррациональному числу.) Не видел ещё ни одной имплементации вживую. З.Ы.: пожалуйста! :)
    – VladD
    21 дек 2012 в 17:06
  • враги не будут проходить по башням, так что они будут искать кратчайший путь. А вот по поводу их генерации на рандомном пути - спасибо. 15 янв 2013 в 6:38
1

Задайте маршрут движения врагов точками, по точкам стройте сплайн, и двигайте врагов по сплайну.

1
  • совсем не вариант - путь может быть перегорожен. Да и не слишком уж игра навороченная, чтобы сплайны реализовывать 17 янв 2013 в 8:08

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.