Алгоритм поиска оптимального прохождения игрового уровня. Какой использовать?

Делаю небольшую игру. Изначально для прохождения уровня требовалось набрать N количество очков. Использовал алгоритм "нахождения сдачи" (извините, не знаю, как он на русском): находишь минимальное количество "монет" нужное для сдачи. В данном случае в роли монет здесь выступали какие-то игровые предметы. Например, чтобы набрать 100 очков и перейти на новый уровень, нужно найти 1 коробок спичек, который даёт 75 очков, и 1 топор, дающий 25 очков. На уровне есть еще другие элементы, которые дают разные очки. Суть в том, чтобы сделать уровень оптимальным по сложности.

В новой итерации решили каждому игровому предмету помимо очков еще дать энергию. Она может быть как отрицательной, так и положительной. Например, когда находишь спички, то получаешь 75 очков и 10 энергии, а топор даёт 25 очков и -10 энергии.

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

Если ли какие-то уже известные алгоритмы, которые можно просто взять? Или же мне как-то существующий подгонять?
  • Вопрос задан
  • 3373 просмотра
Решения вопроса 1
@alius Автор вопроса
Я нашёл подходящий алгоритм для решения этой задачи: задача о ранце (knapsack problem)
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
Вообще "де-факто" алгоритмом для нахождения коротких путей является A* (a star).
В вашем случае есть ещё задача о рюкзаке, в которой порядок слаживания предметов определён маршрутом. Если нет потребности куда-то дойти, то проще всего использовать алгоритм "волны" проверяя при этом количество очков и "энергии".
В любом случае задача сводится к контролируемому поиску в ширину.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы