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

Question

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

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

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

Answer 1

Самый эффективный способ, если вам не нужно много хранимого состояния, состоит в том, чтобы сделать то, что вы намекали: создать цепь Маркова. Связанным с каждым состоянием является массив вероятностей выхода в следующее состояние. Это дает вам полный контроль над процессом и довольно компактен. (Обратите внимание, что вы используете его, генерируя случайное число от 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), вы обнаружите, что по мере того, как вы получаете избыточные пусковые установки, вероятность получения большего будет снижаться. Но, в то же время, вы увеличите вероятность получения ракет. В принципе, у вас будет некоторый экспоненциально разлагающийся весовой коэффициент, который предвзят вас против пусковых установок, если вы недавно его использовали.

Answer 2

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

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

• событие А, относительная вероятность: 4
• событие В, относительная вероятность: 1
• событие С, относительная вероятность: 1
• событие D, относительная вероятность: 10

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

• вычесть 4 из X. Если X в настоящее время отрицательный, выберите событие A.
• else, вычесть 1 из X. Если X в настоящее время отрицательный, выберите событие B.
• else, вычесть 1 из X. Если X теперь отрицателен, выберите событие C.
• еще, Пику событие D.