Как рассчитать «нужды» NPC в числовом виде на основе его требований и инвентаря?

Question

[Владимир]

Допустим есть:
1. Мир в котором 1 тик - 1 "час".
2. NPC у которого есть HP и возраст, которому необходимо "потреблять" 1 юнит еды раз в 8 тиков и 1 юнит воды раз в 2 тика.
3. Без принятия еды HP у NPC будет падать на 5% за тик, а без воды - 10% за тик.
4. Инвентарь NPC с определённым запасом еды, воды и денег и максимальным количеством предметов. (не бездонный)
5. Работа на которой NPC тратит время и зарабатывает деньги.
6. Торговец, который расположен далеко от NPC и продаёт еду и воду.
7. Чтобы купить у торговца "что-то" необходимо потратить "время" на дойти и деньги.

Если постоянно тусить у торговца, чтобы не помереть, то денеги закончатся.
Если постоянно работать, то закончатся еда/вода.
Если бегать к торговцу и покупать только по 1 юниту продуктов -> вермя будет потрачено на дорогу , а не на работу => денег меньше -> закончатся еда/вода.

Какой подход/логика/алгоритм необходимо использовать для максимизации заработка/возраста NPC в этом мире?

Думаю уже существует какой-нить подход для подсчёта "нужды" в числовом виде для каждого из требований.
В зависимости от размера/порогов "нужд" определяются приоритеты задач:
1. Продолжать работать
2. Пойти к торговцу
2.1 Купить Х юнитов еды в зависимости от размера "нужды" еды.
2.2 Купить Х юнитов воды в зависимости от размера "нужды" воды.

Подскажите, как подойти к этой задаче?

Answer 1

[CBET_TbMbI]

> Без принятия еды HP у NPC будет падать на 5% за тик, а без воды - 10% за тик.

С таким условием он будет бессмертным. Если только не считать с округлением в меньшую сторону.

По самой задаче я бы копал немного в сторону психологии, а не математики. То есть имулировал человека, а не идеальноно робота.
1. Человек не хочет, чтобы его здоровье опускалось ниже 50% (цифры для примера, меняй на свой вкус).
2. Значит он должен выйти с работы заранее (насколько заранее, думаю, понятно, как посчитать).
3. Если инвентарь заполнится добычей, он сразу идёт её продавать.
4. Еды он купит столько, чтобы ему хватило на 2 дороги и минимум на столько дней работы, за сколько он заработает на эту самую еду (2 * Рас_на_дор + Х_дней_работы * расх_на_день_работы < цена_еды_на_Х_дней_работы+дни_дороги).
5. Если еды из п4 получается меньше 50% рюкзака, то он докупает его до 50%. (цифру нужно уточнить в зависимости от других параметров)

Заранее посчитать идеальные цифры весьма трудно (это не будет одним уравнением). Проще даже написать код и перебрать все варианты, выбирая оптимум.

Answer 2

[Rsa97]

Работать, потребляя еду и воду, пока запаса сытости не останется только на поход к торговцу и обратно.
Сходить к торговцу, закупить на все деньги еду.
Вернуться, начать всё сначала.

Comments

[Владимир]

А есть более обобщённый подход?
Например, список необходимостей NPC динамический и может меняться в зависимости от "работы"/состояния NPC и/или мира... напр. при болезни NPC добавляется требование "лекарства".

[Василий Банников]

Работать, потребляя еду и воду, пока запаса сытости не останется только на поход к торговцу и обратно.
Сходить к торговцу, закупить на все деньги еду.

А вот это уже задача оптимизации на то, как купить максимальное "время жизни" с учётом ограничений по инвентарю и деньгам.
+ не забываем про переменную HP, ведь можно немного голодным поработать.

при болезни NPC добавляется требование "лекарства".

По той же логике.

Нужно создать некую матмодель этого и посмотреть, как у него будет меняться время жизни в зависимости от решений.
Задача очень похоже на задачу об оптимизации (в момент закупки) и ещё квадратное уравнение нужно решить, чтобы определить, когда идти к продавцу, чтобы купить еду на грани голодной смерти.

Чем больше таких параметров, тем сложнее будет посчитать

Answer 3

[rPman]

В общем случае это задача комбинаторики, по простому оптимальный вариант можно найти перебором (что само собой не оптимально по затратам процессора/памяти).

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

Почти наверняка это будет функция с какими то граничными условиями и коэффициентами... твоя задача подобрать эти значения таким образом чтобы например максимизировать время его жизни (или у тебя там другие целевые критерии). Обычно пишут оценочную функцию, так же на основе состояния, которую и максимизируют. Например собирай оценку счастья NPC на основе событий в его жизни, как часто испытывает сытость, как долго живет, с каким количеством других сущностей он контактировал, умножаешь каждый параметр на коэффициент, складываешь и полученную функцию максимизируешь. Есть алгоритмы многомерной (по многим параметрам) оптимизации минимизации (если тебе нужно максимизировать f(x) а алгоритм умеет только минимизировать, то работай с 1/(f(x)+1)). Эти алгоритмы хороши если параметров мало и функция имеет мало ловушек (локальных минимумов).

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

Строишь свой мир, строишь для всего мира качественную оценку (например сумма всех параметров счастья всех NPC), затем всем NPC задаешь на старте случайные параметры, запускаешь его на существование до смерти всех или лимита времени, меняешь параметры, повторяешь...

Comments

[Владимир]

Те для определения параметров NPC использовать нейронку для поиска "оптимума", а на начальной стадии рандомные значения?!

Я бы для такого подхода использовал бы rtES-HyperNEAT.

Answer 4

[Сергей П]

Есть персонаж с неким состоянием. Хорошо представить состояние как неизменное. Есть некий конечный автомат, который на вход принимает действие, а на выходе даёт новое состояние. Бездействие - это тоже действие. Поведение персонажа в прошлом - это журнал действий. Теперь нужно выбрать стратегию поведение персонажа на будущее. Обычно это делается с помощью деревьев решений. То есть у персонажа есть в каждый тик выбор из набора допустимых действий. Некоторые будут вести к нежелательным последствиям вроде смерти, такие ветки можно обрубать, а некоторые ещё позволят пожить какое-то время. Если дерево получается сильно ветвящееся, то можно ввести норма-функцию, которая будет давать эмпирическую оценку состояния. Персонаж должен выбрать путь в дереве допустимых решений с наименьшими рисками. Правильно понимаю. что помимо действий на судьбу персонажа влияет внешний Пуассоновский поток рандомных событий?
Вот поэтому выбирается тот путь в дереве, который даёт максимальный запас живучести по каждому состоянию из всей цепочки прогнозируемого жизненного пути персонажа.
При возникновении любого внешнего события дерево придётся очистить и перестроить заново. Можно кешировать его отдельные ветки по состоянию. Помним, что состояние у нас имеет смысл сделать иммутабельным (неизменным), тогда его можно использовать как простой бинарный хеш-ключ в кэше. Это может сэкономить много вычислительных ресурсов и памяти при сильно ветвящихся деревьях.

Описаный подход позволил бы применять и нейросети и генетические алгоритмы и логические каркасные правила на том же прологе для оптимизации поиска пути в дереве решений. Можно, зная вероятности разных событий или накопив со временем статистику в прогнозы добавлять и события, тогда персонаж сможет целенаправленно учитывать риски или "надеяться" на позитивные случайные события.

Звучит как игра, которую кто-то "джва года ждал"=)