Алгоритмы предвзятого нереста предметов - PullRequest
Новая
       18

Алгоритмы предвзятого нереста предметов

3 голосов
/ 10 августа 2010

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

Идея, которую я придумала, может состоять в том, чтобы создать массив N x N, который будет действовать в качестве таблицы поиска вероятностей (элемент, ранее созданный VS, для появления) Однако в этом процессе мне понадобится какой-нибудь способ генерации случайного числа с вероятностью, действующей как смещение. Я не уверен, что лучший способ сделать это. Вещи также становятся немного сложнее, когда инвентарь вступает в игру, поскольку ракеты не могут быть сгенерированы, если количество Y уже появилось. Я мог бы создать трехмерный массив и сохранить там инвентарный номер, но я не уверен, насколько эффективно будет продолжать обновлять таблицу поиска массива на основе инвентарного количества.

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

Ответы [ 2 ]

4 голосов
/ 10 августа 2010

Самый эффективный способ, если вам не нужно хранить много состояний, - это делать то, что вы намекнули: создать цепочку Маркова. С каждым состоянием связан массив вероятностей выхода в следующее состояние. Это дает вам полный контроль над процессом и является довольно компактным. (Обратите внимание, что вы используете его, генерируя случайное число от 0 до 1 и выполняя бинарный поиск по совокупным вероятностям.)

Альтернативный, нечеткий подход заключается в поддержании набора вероятностей и набора отклонений. Если у вас есть предвзятый термин, как 

launcher_bias = 0.8*launcher_bias + 0.2*(1.0 - (last_item == launcher))
rocket_bias = 0.8*rocket_bias + 0.2*(last_item == launcher)

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

3 голосов
/ 10 августа 2010

Однако в этом процессе мне понадобится какой-нибудь способ генерации случайного числа с вероятностью, действующей как смещение.Не уверен, что лучший способ сделать это?

Скажем, у вас есть 4 события

  • событие A, относительная вероятность: 4
  • событие B,относительная вероятность: 1
  • событие C, относительная вероятность: 1
  • событие D, относительная вероятность: 10

Сумма относительных вероятностей равна 16, поэтому сгенерируйтеслучайное число X в диапазоне [0,16).Четыре из этих чисел должны отображаться в A, одно в B и т. Д.

  • вычесть 4 из X .Если X теперь отрицательное, выберите событие A.
  • else, вычтите 1 из X .Если X теперь отрицательно, выберите событие B.
  • else, вычтите 1 из X .Если X теперь отрицательно, выберите событие C.
  • else, событие Dick D.
...