-
-
Notifications
You must be signed in to change notification settings - Fork 0
/
limited_machine.ts
103 lines (99 loc) · 2.66 KB
/
limited_machine.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
// Copyright 2022-2024 NeTT. All rights reserved. MIT license.
/**
* Data fed to the constructor.
* The `result` property holds the result that will be returned after rolling.
* `chance` is the weight of the result.
*/
export interface GachaChoice<T> {
result: T;
chance: number;
}
/**
* Data transformed by the constructor, fed to the binary search function.
* The `result` property holds the result that will be returned after rolling.
* `cumulativeChance` is used to make it fit for binary search.
*/
export interface ComputedGachaData<T> {
result: T;
cumulativeChance: number;
}
/**
* Gacha system for rolling n distinct items
* from the weighted collection.
*/
export class LimitedGachaMachine<T> {
#items: ComputedGachaData<T>[];
constructor(items: GachaChoice<T>[]) {
this.#items = new Array(items.length);
this.#configItems(items);
}
set items(items: GachaChoice<T>[]) {
this.#items = new Array(items.length);
this.#configItems(items);
}
/** Setup items for rolling. */
#configItems(items: GachaChoice<T>[]) {
let i = 0;
let cumulativeChance = 0;
while (i < items.length) {
cumulativeChance += items[i].chance;
this.#items[i] = {
result: items[i].result,
cumulativeChance: cumulativeChance,
};
i += 1;
}
}
/**
* Roll distinct items from the gacha machine.
* ```ts
* const machine = new GachaMachine(items);
* machine.get(11)
* ```
*
* However, rolling distinct items does not mutate the pool.
* The items rolled are only distinct within the `n` items.
*/
get(count: number): T[] {
if (count > this.#items.length) {
throw new RangeError(`count must be less than number of items in pool.`);
}
const result = new Array<T>(count);
let i = 0;
const data = this.#items.slice(0);
while (i < count) {
const res = rollWithBinarySearch(data);
result[i] = data[res].result;
data.splice(res, 1);
i += 1;
}
return result;
}
}
function rollWithBinarySearch<T>(
items: ComputedGachaData<T>[],
): number {
const totalChance = items[items.length - 1].cumulativeChance;
if (items.length === 1) return 0;
const rng = Math.random() * totalChance;
let lower = 0;
let max = items.length - 1;
let mid = (max + lower) >> 1;
while (
mid != 0 && lower <= max
) {
if (
(items[mid].cumulativeChance > rng &&
items[mid - 1].cumulativeChance < rng) ||
items[mid].cumulativeChance == rng
) return mid;
if (items[mid].cumulativeChance < rng) {
lower = mid + 1;
mid = (max + lower) >> 1;
} else {
max = mid - 1;
mid = (max + lower) >> 1;
}
}
return mid;
}