weighted_selection.ts

/**
 * Data transformed by the constructor, fed to the binary search function.
 * The `result` property holds the result that will be returned after rolling.
 * `chance` is the weight of the result.
 * `cumulativeChance` is used to make it fit for binary search. Something like an arithmetic progression.
 */
export interface ComputedGachaData<ItemType> {
  result: ItemType;
  chance: number;
  cumulativeChance: number;
}

/**
 * Roll one item from a pool using binary search. Requires special transformation.
 * @param items List of items to roll from, each having a `result` and `cumulativeChance`.
 * @param totalChance Total weight of the pool.
 * @returns An item from the pool.
 */
function rollWithBinarySearch<ItemType>(
  items: ComputedGachaData<ItemType>[],
  totalChance?: number,
): ItemType {
  if (!totalChance) totalChance = items[items.length - 1].cumulativeChance;
  if (items.length === 1) return items[0].result;
  const rng = Math.random() * totalChance;
  let lower = 0;
  let max = items.length - 1;
  let mid = Math.floor((max + lower) / 2);
  while (
    mid != 0 && lower <= max
  ) {
    if (
      (items[mid].cumulativeChance > rng &&
        items[mid - 1].cumulativeChance < rng) ||
      items[mid].cumulativeChance == rng
    ) return items[mid].result;
    if (items[mid].cumulativeChance < rng) {
      lower = mid + 1;
      mid = Math.floor((max + lower) / 2);
    } else {
      max = mid - 1;
      mid = Math.floor((max + lower) / 2);
    }
  }
  return items[mid].result;
}
/**
 * Roll one item from a pool using linear search. Simple and great for smaller pools.
 * @param items List of items to roll from, each having a `result` and `chance`.
 * @param totalChance Total weight of the pool.
 * @returns An item from the pool.
 */
function rollWithLinearSearch<ItemType>(
  choices: ComputedGachaData<ItemType>[],
  totalChance = 0,
): ItemType {
  let total = totalChance;
  let i = 0;
  if (totalChance === 0) {
    while (i < choices.length) {
      total += choices[i].chance;
      i += 1;
    }
  }
  const result = Math.random() * total;
  let going = 0.0;
  i = 0;
  while (i < choices.length) {
    going += choices[i].chance;
    if (result < going) {
      return choices[i].result;
    }
    i += 1;
  }
  return choices[Math.floor(Math.random() * choices.length)].result;
}