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

Question

[Артём]

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

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

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

Если ли какие-то уже известные алгоритмы, которые можно просто взять? Или же мне как-то существующий подгонять?

Answer 1

[Артём]

Я нашёл подходящий алгоритм для решения этой задачи: задача о ранце (knapsack problem)

Answer 2

[Юрий Ярош]

Вообще "де-факто" алгоритмом для нахождения коротких путей является A* (a star).
В вашем случае есть ещё задача о рюкзаке, в которой порядок слаживания предметов определён маршрутом. Если нет потребности куда-то дойти, то проще всего использовать алгоритм "волны" проверяя при этом количество очков и "энергии".
В любом случае задача сводится к контролируемому поиску в ширину.

Comments

[Артём]

Либо я не совсем понимаю, либо я недорассказал. Пути на уровне нет, есть всего 2 условия прохождения: набрать N количество очков и не уйти в минус по энергии.
Если бы были разные варианты путей/дорог до конца уровня, то тогда их можно собрать в граф и найти оптимальный, но в данном случае я как-то затрудняюсь.