Как решить эту проблему игры

Question

У меня простая игровая проблема с использованием A *:

У нас есть несколько узлов в дереве, один узел содержит:

1. монстр с силой и его стихией
2. путь ссылки на другие узлы.
3. Плюс, который мы получаем после убийства этого монстра.

Есть пять элементов: металл, дерево, вода, огонь, земля.

Наш персонаж может убить монстра, только если показатель столкновения нашего элемента больше или равен монстру.

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

цель: найти кратчайший путь к конкретному узлу.

Мое решение: Я буду использовать A *:

эвристика: Дейкстра

find(mainCharacter,node,plusPoint) {
  // node here is the node has smallest f
  shortestWay[5] ways;
  foreach(element in elements) {
       mainCharacter->element += plusPoint;
       if (mainCharacter can beat the monster in node) {
           bestNode is node has the smallest f in node->neighbourNodes
           *ways[element] ++ << the steps, we plus point to the first element at very first path. it can be -1 if we can't go.
           find(mainCharacter,bestNode,node->plusPoint)
       }
}
Our goal will be the *ways[element] with the smallest step.

Мой вопрос:

Правильно ли и достаточно ли мое решение?

Есть ли лучшее решение для этой игры?

Спасибо в первую очередь:)

Answer 1

Я не уверен, что A * позволит вам сделать это.

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

Пример: Вы находитесь в узле A, который открывается в B и C. B открывается в E. E открывается в F, который открывается в G, который открывается в D. C открывается в D, который является вашим пунктом назначения.

B охраняется элементалом степени 2, а C - элементалом степени 4. Вы находитесь на уровне 3. У всех E, F и G есть элементалы степени 2.

Из A вы можете идти только к B и C. C слишком силен, поэтому вы идете к B. Вы можете продолжать ходить вокруг, чтобы выдать ABEFGD, или вы можете вернуться: ABAC D. (После того, как вы вынули B, C это больше не слишком мощный.)

Итак, в конечном итоге вы проведете много переоценок по любому алгоритму, который вам придет в голову. Это даже не ограничено O(n!) из-за возможного отслеживания назад.

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