veloren_common/
lottery.rs

1// Example for calculating a drop rate:
2//
3// On every roll an f32 between 0 and 1 is created.
4// For every loot table a total range is created by the sum of the individual
5// ranges per item.
6//
7// This range is the sum of all single ranges defined per item in a table.
8//                                                   // Individual Range
9// (3, "common.items.food.cheese"),                  // 0.0..3.0
10// (3, "common.items.food.apple"),                   // 3.0..6.0
11// (3, "common.items.food.mushroom"),                // 6.0..9.0
12// (1, "common.items.food.coconut"),                 // 9.0..10.0
13// (0.05, "common.items.food.apple_mushroom_curry"), // 10.0..10.05
14// (0.10, "common.items.food.apple_stick"),          // 10.05..10.15
15// (0.10, "common.items.food.mushroom_stick"),       // 10.15..10.25
16//
17// The f32 is multiplied by the max. value needed to drop an item in this
18// particular table. X = max. value needed = 10.15
19//
20// Example roll
21// [Random Value 0..1] * X = Number inside the table's total range
22// 0.45777 * X = 4.65
23// 4.65 is in the range of 3.0..6.0 => Apple drops
24//
25// Example drop chance calculation
26// Cheese drop rate = 3/X = 29.6%
27// Coconut drop rate = 1/X = 9.85%
28
29use std::{borrow::Cow, hash::Hash};
30
31use crate::{
32    assets::{AssetExt, BoxedError, FileAsset, load_ron},
33    comp::{Item, inventory::item},
34};
35use rand::prelude::*;
36use serde::{Deserialize, Serialize, de::DeserializeOwned};
37use tracing::warn;
38
39#[derive(Clone, Debug, PartialEq, Deserialize)]
40pub struct Lottery<T> {
41    items: Vec<(f32, T)>,
42    total: f32,
43}
44
45impl<T: DeserializeOwned + Send + Sync + 'static> FileAsset for Lottery<T> {
46    const EXTENSION: &'static str = "ron";
47
48    fn from_bytes(bytes: Cow<[u8]>) -> Result<Self, BoxedError> {
49        load_ron::<Vec<(f32, T)>>(&bytes).map(Vec::into)
50    }
51}
52
53impl<T> From<Vec<(f32, T)>> for Lottery<T> {
54    fn from(mut items: Vec<(f32, T)>) -> Lottery<T> {
55        let mut total = 0.0;
56
57        for (rate, _) in &mut items {
58            total += *rate;
59            *rate = total - *rate;
60        }
61
62        Self { items, total }
63    }
64}
65
66impl<T> Lottery<T> {
67    pub fn choose_seeded(&self, seed: u32) -> &T {
68        let x = ((seed % 65536) as f32 / 65536.0) * self.total;
69        &self.items[self
70            .items
71            .binary_search_by(|(y, _)| y.partial_cmp(&x).unwrap())
72            .unwrap_or_else(|i| i.saturating_sub(1))]
73        .1
74    }
75
76    pub fn choose(&self) -> &T { self.choose_seeded(rand::rng().random()) }
77
78    pub fn iter(&self) -> impl Iterator<Item = &(f32, T)> { self.items.iter() }
79
80    pub fn total(&self) -> f32 { self.total }
81}
82
83/// Try to distribute stacked items fairly between weighted participants.
84pub fn distribute_many<T: Copy + Eq + Hash, I>(
85    participants: impl IntoIterator<Item = (f32, T)>,
86    rng: &mut impl Rng,
87    items: &[I],
88    mut get_amount: impl FnMut(&I) -> u32,
89    mut exec_item: impl FnMut(&I, T, u32),
90) {
91    struct Participant<T> {
92        // weight / total
93        weight: f32,
94        sorted_weight: f32,
95        data: T,
96        recieved_count: u32,
97        current_recieved_count: u32,
98    }
99
100    impl<T> Participant<T> {
101        fn give(&mut self, amount: u32) {
102            self.current_recieved_count += amount;
103            self.recieved_count += amount;
104        }
105    }
106
107    // Nothing to distribute, we can return early.
108    if items.is_empty() {
109        return;
110    }
111
112    let mut total_weight = 0.0;
113
114    let mut participants = participants
115        .into_iter()
116        .map(|(weight, participant)| Participant {
117            weight,
118            sorted_weight: {
119                total_weight += weight;
120                total_weight - weight
121            },
122            data: participant,
123            recieved_count: 0,
124            current_recieved_count: 0,
125        })
126        .collect::<Vec<_>>();
127
128    let total_item_amount = items.iter().map(&mut get_amount).sum::<u32>();
129
130    let mut current_total_weight = total_weight;
131
132    for item in items.iter() {
133        let amount = get_amount(item);
134        let mut distributed = 0;
135
136        let Some(mut give) = participants
137            .iter()
138            .map(|participant| {
139                (total_item_amount as f32 * participant.weight / total_weight).ceil() as u32
140                    - participant.recieved_count
141            })
142            .min()
143        else {
144            tracing::error!("Tried to distribute items to no participants.");
145            return;
146        };
147
148        while distributed < amount {
149            // Can't give more than amount, and don't give more than the average between all
150            // to keep things well distributed.
151            let max_give = (amount / participants.len() as u32).clamp(1, amount - distributed);
152            give = give.clamp(1, max_give);
153            let x = rng.random_range(0.0..=current_total_weight);
154
155            let index = participants
156                .binary_search_by(|item| item.sorted_weight.partial_cmp(&x).unwrap())
157                .unwrap_or_else(|i| i.saturating_sub(1));
158
159            let participant_count = participants.len();
160
161            let Some(winner) = participants.get_mut(index) else {
162                tracing::error!("Tried to distribute items to no participants.");
163                return;
164            };
165
166            winner.give(give);
167            distributed += give;
168
169            // If a participant has received enough, remove it.
170            if participant_count > 1
171                && winner.recieved_count as f32 / total_item_amount as f32
172                    >= winner.weight / total_weight
173            {
174                current_total_weight = index
175                    .checked_sub(1)
176                    .and_then(|i| Some(participants.get(i)?.sorted_weight))
177                    .unwrap_or(0.0);
178                let winner = participants.swap_remove(index);
179                exec_item(item, winner.data, winner.current_recieved_count);
180
181                // Keep participant weights correct so that we can binary search it.
182                for participant in &mut participants[index..] {
183                    current_total_weight += participant.weight;
184                    participant.sorted_weight = current_total_weight - participant.weight;
185                }
186
187                // Update max item give amount.
188                give = participants
189                    .iter()
190                    .map(|participant| {
191                        (total_item_amount as f32 * participant.weight / total_weight).ceil() as u32
192                            - participant.recieved_count
193                    })
194                    .min()
195                    .unwrap_or(0);
196            } else {
197                give = give.min(
198                    (total_item_amount as f32 * winner.weight / total_weight).ceil() as u32
199                        - winner.recieved_count,
200                );
201            }
202        }
203        for participant in participants.iter_mut() {
204            if participant.current_recieved_count != 0 {
205                exec_item(item, participant.data, participant.current_recieved_count);
206                participant.current_recieved_count = 0;
207            }
208        }
209    }
210}
211
212#[derive(Clone, Debug, PartialEq, Deserialize, Serialize)]
213#[rustfmt::skip] // breaks doc comments
214#[derive(Default)]
215pub enum LootSpec<T: AsRef<str>> {
216    /// Asset specifier
217    Item(T),
218    /// Loot table
219    LootTable(T),
220    /// No loot given
221    #[default]
222    Nothing,
223    /// Random modular weapon that matches requested restrictions
224    ModularWeapon {
225        tool: item::tool::ToolKind,
226        material: item::Material,
227        hands: Option<item::tool::Hands>,
228    },
229    /// Random primary modular weapon component that matches requested
230    /// restrictions
231    ModularWeaponPrimaryComponent {
232        tool: item::tool::ToolKind,
233        material: item::Material,
234        hands: Option<item::tool::Hands>,
235    },
236    /// Dropping variable number of items at random from respective Category
237    ///
238    /// # Examples:
239    /// ```text
240    /// MultiDrop(Item("common.items.utility.coins"), 100, 250)
241    /// ```
242    /// Will drop 100-250 coins (250 coins is also possible).
243    /// ```text
244    /// MultiDrop(LootTable("common.loot_tables.food.prepared"), 1, 4)
245    /// ```
246    /// Will drop random item from food.prepared loot table one to four times.
247    /// Each time the dice is thrown again, so items might get duplicated or
248    /// not.
249    MultiDrop(Box<LootSpec<T>>, u32, u32),
250    /// Each category is evaluated, often used to have guaranteed quest item
251    /// and random reward.
252    ///
253    /// # Examples:
254    /// ```text
255    /// All([
256    ///     Item("common.items.keys.bone_key"),
257    ///     MultiDrop(
258    ///         Item("common.items.crafting_ing.mineral.gem.sapphire"),
259    ///         0, 1,
260    ///     ),
261    /// ])
262    /// ```
263    /// Will always drop bone key, 1-2 furs, and may drop or not drop one
264    /// sapphire.
265    ///
266    /// ```text
267    /// All([
268    ///     Item("common.items.armor.cultist.necklace"),
269    ///     MultiDrop(Item("common.items.armor.cultist.ring"), 2, 2),
270    /// ])
271    /// ```
272    /// Will always drop cultist necklace and two cultist rings.
273    All(Vec<LootSpec<T>>),
274    /// Like a `LootTable` but inline, most useful with `All([])`.
275    ///
276    /// # Examples:
277    /// ```text
278    /// All([
279    ///     Item("common.items.keys.terracotta_key_door"),
280    ///
281    ///     Lottery([
282    ///         // Weapons
283    ///         (3.0, LootTable("common.loot_tables.weapons.tier-5")),
284    ///         // Armor
285    ///         (3.0, LootTable("common.loot_tables.armor.tier-5")),
286    ///         // Misc
287    ///         (0.25, Item("common.items.tool.instruments.steeltonguedrum")),
288    ///     ]),
289    /// ])
290    /// ```
291    /// Will always drop a terracotta key, and ONE of items defined in a lottery:
292    /// * one random tier-5 weapon
293    /// * one random tier-5 armour piece
294    /// * Steeldrum
295    Lottery(Vec<(f32, LootSpec<T>)>),
296}
297
298impl<T: AsRef<str>> LootSpec<T> {
299    fn to_items_inner(
300        &self,
301        rng: &mut rand::rngs::ThreadRng,
302        amount: u32,
303        items: &mut Vec<(u32, Item)>,
304    ) {
305        let convert_item = |item: &T| {
306            Item::new_from_asset(item.as_ref()).map_or_else(
307                |e| {
308                    warn!(?e, "error while loading item: {}", item.as_ref());
309                    None
310                },
311                Some,
312            )
313        };
314        let mut push_item = |mut item: Item, count: u32| {
315            let count = item.amount().saturating_mul(count);
316            item.set_amount(1).expect("1 is always a valid amount.");
317            let hash = item.item_hash();
318            match items.binary_search_by_key(&hash, |(_, item)| item.item_hash()) {
319                Ok(i) => {
320                    // Since item hash can collide with other items, we search nearby items with the
321                    // same hash.
322                    // NOTE: The `ParitalEq` implementation for `Item` doesn't compare some data
323                    // like durability, or wether slots contain anything. Although since these are
324                    // Newly loaded items we don't care about comparing those for deduplication
325                    // here.
326                    let has_same_hash = |i: &usize| items[*i].1.item_hash() == hash;
327                    if let Some(i) = (i..items.len())
328                        .take_while(has_same_hash)
329                        .chain((0..i).rev().take_while(has_same_hash))
330                        .find(|i| items[*i].1 == item)
331                    {
332                        // We saturate at 4 billion items, could use u64 instead if this isn't
333                        // desirable.
334                        items[i].0 = items[i].0.saturating_add(count);
335                    } else {
336                        items.insert(i, (count, item));
337                    }
338                },
339                Err(i) => items.insert(i, (count, item)),
340            }
341        };
342
343        match self {
344            Self::Item(item) => {
345                if let Some(item) = convert_item(item) {
346                    push_item(item, amount);
347                }
348            },
349            Self::LootTable(table) => {
350                let loot_spec = Lottery::<LootSpec<String>>::load_expect(table.as_ref()).read();
351                for _ in 0..amount {
352                    loot_spec.choose().to_items_inner(rng, 1, items)
353                }
354            },
355            Self::Lottery(table) => {
356                let lottery = Lottery::from(
357                    table
358                        .iter()
359                        .map(|(weight, spec)| (*weight, spec))
360                        .collect::<Vec<_>>(),
361                );
362
363                for _ in 0..amount {
364                    lottery.choose().to_items_inner(rng, 1, items)
365                }
366            },
367            Self::Nothing => {},
368            Self::ModularWeapon {
369                tool,
370                material,
371                hands,
372            } => {
373                for _ in 0..amount {
374                    match item::modular::random_weapon(*tool, *material, *hands, rng) {
375                        Ok(item) => push_item(item, 1),
376                        Err(e) => {
377                            warn!(
378                                ?e,
379                                "error while creating modular weapon. Toolkind: {:?}, Material: \
380                                 {:?}, Hands: {:?}",
381                                tool,
382                                material,
383                                hands,
384                            );
385                        },
386                    }
387                }
388            },
389            Self::ModularWeaponPrimaryComponent {
390                tool,
391                material,
392                hands,
393            } => {
394                for _ in 0..amount {
395                    match item::modular::random_weapon(*tool, *material, *hands, rng) {
396                        Ok(item) => push_item(item, 1),
397                        Err(e) => {
398                            warn!(
399                                ?e,
400                                "error while creating modular weapon primary component. Toolkind: \
401                                 {:?}, Material: {:?}, Hands: {:?}",
402                                tool,
403                                material,
404                                hands,
405                            );
406                        },
407                    }
408                }
409            },
410            Self::MultiDrop(loot_spec, lower, upper) => {
411                let sub_amount = rng.random_range(*lower..=*upper);
412                // We saturate at 4 billion items, could use u64 instead if this isn't
413                // desirable.
414                loot_spec.to_items_inner(rng, sub_amount.saturating_mul(amount), items);
415            },
416            Self::All(loot_specs) => {
417                for loot_spec in loot_specs {
418                    loot_spec.to_items_inner(rng, amount, items);
419                }
420            },
421        }
422    }
423
424    pub fn to_items(&self) -> Option<Vec<(u32, Item)>> {
425        let mut items = Vec::new();
426        self.to_items_inner(&mut rand::rng(), 1, &mut items);
427
428        if !items.is_empty() {
429            items.sort_unstable_by_key(|(amount, _)| *amount);
430
431            Some(items)
432        } else {
433            None
434        }
435    }
436}
437
438#[cfg(test)]
439pub mod tests {
440    use std::borrow::Borrow;
441
442    use super::*;
443    use crate::{assets, comp::Item};
444    use assets::AssetExt;
445
446    #[cfg(test)]
447    pub fn validate_loot_spec(item: &LootSpec<String>) {
448        let mut rng = rand::rng();
449        match item {
450            LootSpec::Item(item) => {
451                Item::new_from_asset_expect(item);
452            },
453            LootSpec::LootTable(loot_table) => {
454                let loot_table = Lottery::<LootSpec<String>>::load_expect(loot_table).read();
455                validate_table_contents(&loot_table);
456            },
457            LootSpec::Nothing => {},
458            LootSpec::ModularWeapon {
459                tool,
460                material,
461                hands,
462            } => {
463                item::modular::random_weapon(*tool, *material, *hands, &mut rng).unwrap_or_else(
464                    |_| {
465                        panic!(
466                            "Failed to synthesize a modular {tool:?} made of {material:?} that \
467                             had a hand restriction of {hands:?}."
468                        )
469                    },
470                );
471            },
472            LootSpec::ModularWeaponPrimaryComponent {
473                tool,
474                material,
475                hands,
476            } => {
477                item::modular::random_weapon_primary_component(*tool, *material, *hands, &mut rng)
478                    .unwrap_or_else(|_| {
479                        panic!(
480                            "Failed to synthesize a modular weapon primary component: {tool:?} \
481                             made of {material:?} that had a hand restriction of {hands:?}."
482                        )
483                    });
484            },
485            LootSpec::MultiDrop(loot_spec, lower, upper) => {
486                assert!(
487                    upper >= lower,
488                    "Upper quantity must be at least the value of lower quantity. Upper value: \
489                     {}, low value: {}.",
490                    upper,
491                    lower
492                );
493                validate_loot_spec(loot_spec);
494            },
495            LootSpec::All(loot_specs) => {
496                for loot_spec in loot_specs {
497                    validate_loot_spec(loot_spec);
498                }
499            },
500            LootSpec::Lottery(table) => {
501                let lottery = Lottery::from(
502                    table
503                        .iter()
504                        .map(|(weight, spec)| (*weight, spec))
505                        .collect::<Vec<_>>(),
506                );
507
508                validate_table_contents(&lottery);
509            },
510        }
511    }
512
513    fn validate_table_contents<T: Borrow<LootSpec<String>>>(table: &Lottery<T>) {
514        for (_, item) in table.iter() {
515            validate_loot_spec(item.borrow());
516        }
517    }
518
519    #[test]
520    fn test_loot_tables() {
521        let loot_tables = assets::load_rec_dir::<Lottery<LootSpec<String>>>("common.loot_tables")
522            .expect("load loot_tables");
523        for loot_table in loot_tables.read().ids() {
524            let loot_table = Lottery::<LootSpec<String>>::load_expect(loot_table);
525            validate_table_contents(&loot_table.read());
526        }
527    }
528
529    #[test]
530    fn test_distribute_many() {
531        let mut rng = rand::rng();
532
533        // Known successful case
534        for _ in 0..10 {
535            distribute_many(
536                vec![(0.4f32, "a"), (0.4, "b"), (0.2, "c")],
537                &mut rng,
538                &[("item", 10)],
539                |(_, m)| *m,
540                |_item, winner, count| match winner {
541                    "a" | "b" => assert_eq!(count, 4),
542                    "c" => assert_eq!(count, 2),
543                    _ => unreachable!(),
544                },
545            );
546        }
547    }
548}