veloren_common/comp/skillset/
mod.rs

1use crate::{
2    assets::{AssetExt, Ron},
3    comp::{item::tool::ToolKind, skills::Skill},
4};
5use core::borrow::{Borrow, BorrowMut};
6use hashbrown::HashMap;
7use lazy_static::lazy_static;
8use serde::{Deserialize, Serialize};
9use sha2::{Digest, Sha256};
10use specs::{Component, DerefFlaggedStorage};
11use std::{collections::BTreeSet, hash::Hash};
12use tracing::{trace, warn};
13
14pub mod skills;
15
16#[cfg(test)] mod test;
17
18pub struct SkillGroupDef {
19    pub skills: BTreeSet<Skill>,
20    pub total_skill_point_cost: u16,
21}
22
23lazy_static! {
24    // Determines the skills that comprise each skill group.
25    //
26    // This data is used to determine which of a player's skill groups a
27    // particular skill should be added to when a skill unlock is requested.
28    pub static ref SKILL_GROUP_DEFS: HashMap<SkillGroupKind, SkillGroupDef> = {
29        // BTreeSet is used here to ensure that skills are ordered. This is important
30        // to ensure that the hash created from it is consistent so that we don't
31        // needlessly force a respec when loading skills from persistence.
32        let map: HashMap<SkillGroupKind, BTreeSet<Skill>> = Ron::load_expect_cloned(
33            "common.skill_trees.skills_skill-groups_manifest",
34        ).into_inner();
35        map.iter().map(|(sgk, skills)|
36            (*sgk, SkillGroupDef { skills: skills.clone(),
37                total_skill_point_cost: skills
38                    .iter()
39                    .map(|skill| {
40                        let max_level = skill.max_level();
41                        (1..=max_level)
42                            .map(|level| skill.skill_cost(level))
43                            .sum::<u16>()
44                    })
45                    .sum()
46            })
47        )
48        .collect()
49    };
50    // Creates a hashmap for the reverse lookup of skill groups from a skill
51    pub static ref SKILL_GROUP_LOOKUP: HashMap<Skill, SkillGroupKind> = {
52        let map: HashMap<SkillGroupKind, BTreeSet<Skill>> = Ron::load_expect_cloned(
53            "common.skill_trees.skills_skill-groups_manifest",
54        ).into_inner();
55        map.iter().flat_map(|(sgk, skills)| skills.iter().map(move |s| (*s, *sgk))).collect()
56    };
57    // Loads the maximum level that a skill can obtain
58    pub static ref SKILL_MAX_LEVEL: HashMap<Skill, u16> = {
59        Ron::load_expect_cloned(
60            "common.skill_trees.skill_max_levels",
61        ).into_inner()
62    };
63    /// Loads the prerequisite skills for each skill. It cannot currently detect
64    /// cyclic dependencies, so if you modify the prerequisite map ensure that there
65    /// are no cycles of prerequisites.
66    pub static ref SKILL_PREREQUISITES: HashMap<Skill, SkillPrerequisite> = {
67        Ron::load_expect_cloned(
68            "common.skill_trees.skill_prerequisites",
69        ).into_inner()
70    };
71    pub static ref SKILL_GROUP_HASHES: HashMap<SkillGroupKind, Vec<u8>> = {
72        let map: HashMap<SkillGroupKind, BTreeSet<Skill>> = Ron::load_expect_cloned(
73            "common.skill_trees.skills_skill-groups_manifest",
74        ).into_inner();
75        let mut hashes = HashMap::new();
76        for (skill_group_kind, skills) in map.iter() {
77            let mut hasher = Sha256::new();
78            let json_input: Vec<_> = skills.iter().map(|skill| (*skill, skill.max_level())).collect();
79            let hash_input = serde_json::to_string(&json_input).unwrap_or_default();
80            hasher.update(hash_input.as_bytes());
81            let hash_result = hasher.finalize();
82            hashes.insert(*skill_group_kind, hash_result.iter().copied().collect());
83        }
84        hashes
85    };
86}
87
88#[derive(Clone, Copy, Debug, Hash, PartialEq, Eq, Serialize, Deserialize, Ord, PartialOrd)]
89pub enum SkillGroupKind {
90    General,
91    Weapon(ToolKind),
92}
93
94impl SkillGroupKind {
95    /// Gets the cost in experience of earning a skill point
96    /// Changing this is forward compatible with persistence and will
97    /// automatically force a respec for skill group kinds that are affected.
98    pub fn skill_point_cost(self, level: u16) -> u32 {
99        use std::f32::consts::E;
100        match self {
101            Self::Weapon(ToolKind::Sword | ToolKind::Axe | ToolKind::Hammer) => {
102                let level = level as f32;
103                ((400.0 * (level / (level + 20.0)).powi(2) + 5.0 * E.powf(0.025 * level))
104                    .min(u32::MAX as f32) as u32)
105                    .saturating_mul(25)
106            },
107            _ => {
108                const EXP_INCREMENT: f32 = 10.0;
109                const STARTING_EXP: f32 = 70.0;
110                const EXP_CEILING: f32 = 1000.0;
111                const SCALING_FACTOR: f32 = 0.125;
112                (EXP_INCREMENT
113                    * (EXP_CEILING
114                        / EXP_INCREMENT
115                        / (1.0
116                            + E.powf(-SCALING_FACTOR * level as f32)
117                                * (EXP_CEILING / STARTING_EXP - 1.0)))
118                        .floor()) as u32
119            },
120        }
121    }
122
123    /// Gets the total amount of skill points that can be spent in a particular
124    /// skill group
125    pub fn total_skill_point_cost(self) -> u16 {
126        if let Some(SkillGroupDef {
127            total_skill_point_cost,
128            ..
129        }) = SKILL_GROUP_DEFS.get(&self)
130        {
131            *total_skill_point_cost
132        } else {
133            0
134        }
135    }
136}
137
138/// A group of skills that have been unlocked by a player. Each skill group has
139/// independent exp and skill points which are used to unlock skills in that
140/// skill group.
141#[derive(Clone, Debug, Eq, Hash, PartialEq, Serialize, Deserialize)]
142pub struct SkillGroup {
143    // Invariant should be maintained that this is the same kind as the key that the skill group is
144    // inserted into the skillset as.
145    pub skill_group_kind: SkillGroupKind,
146    // The invariant that (earned_exp >= available_exp) should not be violated
147    pub available_exp: u32,
148    pub earned_exp: u32,
149    // The invariant that (earned_sp >= available_sp) should not be violated
150    pub available_sp: u16,
151    pub earned_sp: u16,
152    // Used for persistence
153    pub ordered_skills: Vec<Skill>,
154}
155
156impl SkillGroup {
157    fn new(skill_group_kind: SkillGroupKind) -> SkillGroup {
158        SkillGroup {
159            skill_group_kind,
160            available_exp: 0,
161            earned_exp: 0,
162            available_sp: 0,
163            earned_sp: 0,
164            ordered_skills: Vec::new(),
165        }
166    }
167
168    /// Returns the amount of experience in a skill group that has been spent to
169    /// acquire skill points Relies on the invariant that (earned_exp >=
170    /// available_exp) to ensure function does not underflow
171    pub fn spent_exp(&self) -> u32 { self.earned_exp - self.available_exp }
172
173    /// Adds a skill point while subtracting the necessary amount of experience
174    fn earn_skill_point(&mut self) -> Result<(), SpRewardError> {
175        let sp_cost = self.skill_group_kind.skill_point_cost(self.earned_sp);
176        // If there is insufficient available exp, checked sub will fail as the result
177        // would be less than 0
178        let new_available_exp = self
179            .available_exp
180            .checked_sub(sp_cost)
181            .ok_or(SpRewardError::InsufficientExp)?;
182        let new_earned_sp = self
183            .earned_sp
184            .checked_add(1)
185            .ok_or(SpRewardError::Overflow)?;
186        let new_available_sp = self
187            .available_sp
188            .checked_add(1)
189            .ok_or(SpRewardError::Overflow)?;
190        self.available_exp = new_available_exp;
191        self.earned_sp = new_earned_sp;
192        self.available_sp = new_available_sp;
193        Ok(())
194    }
195
196    /// Also attempts to earn a skill point after adding experience. If a skill
197    /// point was earned, returns how many skill points the skill group now has
198    /// earned in total.
199    pub fn add_experience(&mut self, amount: u32) -> Option<u16> {
200        self.earned_exp = self.earned_exp.saturating_add(amount);
201        self.available_exp = self.available_exp.saturating_add(amount);
202
203        let mut return_val = None;
204        // Attempt to earn skill point
205        while self.earn_skill_point().is_ok() {
206            return_val = Some(self.earned_sp);
207        }
208        return_val
209    }
210}
211
212/// Contains all of a player's skill groups and skills. Provides methods for
213/// manipulating assigned skills and skill groups including unlocking skills,
214/// refunding skills etc.
215#[derive(Clone, Debug, Serialize, Deserialize, PartialEq, Eq)]
216pub struct SkillSet {
217    skill_groups: HashMap<SkillGroupKind, SkillGroup>,
218    skills: HashMap<Skill, u16>,
219}
220
221impl Component for SkillSet {
222    type Storage = DerefFlaggedStorage<Self, specs::VecStorage<Self>>;
223}
224
225impl Default for SkillSet {
226    /// Instantiate a new skill set with the default skill groups with no
227    /// unlocked skills in them - used when adding a skill set to a new
228    /// player
229    fn default() -> Self {
230        // Create an empty skillset
231        let mut skill_group = Self {
232            skill_groups: HashMap::new(),
233            skills: SkillSet::initial_skills(),
234        };
235
236        // Insert default skill groups
237        skill_group.unlock_skill_group(SkillGroupKind::General);
238        skill_group.unlock_skill_group(SkillGroupKind::Weapon(ToolKind::Pick));
239
240        skill_group
241    }
242}
243
244impl SkillSet {
245    pub fn initial_skills() -> HashMap<Skill, u16> {
246        let mut skills = HashMap::new();
247        skills.insert(Skill::UnlockGroup(SkillGroupKind::General), 1);
248        skills.insert(
249            Skill::UnlockGroup(SkillGroupKind::Weapon(ToolKind::Pick)),
250            1,
251        );
252        skills
253    }
254
255    /// NOTE: This does *not* return an error on failure, since we can partially
256    /// recover from some failures.  Instead, it returns the error in the
257    /// second return value; make sure to handle it if present!
258    pub fn load_from_database(
259        skill_groups: HashMap<SkillGroupKind, SkillGroup>,
260        mut all_skills: HashMap<SkillGroupKind, Result<Vec<Skill>, SkillsPersistenceError>>,
261    ) -> (Self, Option<SkillsPersistenceError>) {
262        let mut skillset = SkillSet {
263            skill_groups,
264            skills: SkillSet::initial_skills(),
265        };
266        let mut persistence_load_error = None;
267
268        // Loops while checking the all_skills hashmap. For as long as it can find an
269        // entry where the skill group kind is unlocked, insert the skills corresponding
270        // to that skill group kind. When no more skill group kinds can be found, break
271        // the loop.
272        while let Some(skill_group_kind) = all_skills
273            .keys()
274            .find(|kind| skillset.has_skill(Skill::UnlockGroup(**kind)))
275            .copied()
276        {
277            // Remove valid skill group kind from the hash map so that loop eventually
278            // terminates.
279            if let Some(skills_result) = all_skills.remove(&skill_group_kind) {
280                match skills_result {
281                    Ok(skills) => {
282                        let backup_skillset = skillset.clone();
283                        // Iterate over all skills and make sure that unlocking them is successful.
284                        // If any fail, fall back to skillset before
285                        // unlocking any to allow a full respec
286                        if !skills
287                            .iter()
288                            .all(|skill| skillset.unlock_skill(*skill).is_ok())
289                        {
290                            skillset = backup_skillset;
291                            // If unlocking failed, set persistence_load_error
292                            persistence_load_error =
293                                Some(SkillsPersistenceError::SkillsUnlockFailed)
294                        }
295                    },
296                    Err(persistence_error) => persistence_load_error = Some(persistence_error),
297                }
298            }
299        }
300
301        (skillset, persistence_load_error)
302    }
303
304    /// Check if a particular skill group is accessible for an entity, *if* it
305    /// exists.
306    fn skill_group_accessible_if_exists(&self, skill_group_kind: SkillGroupKind) -> bool {
307        self.has_skill(Skill::UnlockGroup(skill_group_kind))
308    }
309
310    /// Checks if a particular skill group is accessible for an entity
311    pub fn skill_group_accessible(&self, skill_group_kind: SkillGroupKind) -> bool {
312        self.skill_groups.contains_key(&skill_group_kind)
313            && self.skill_group_accessible_if_exists(skill_group_kind)
314    }
315
316    ///  Unlocks a skill group for a player. It starts with 0 exp and 0 skill
317    ///  points.
318    fn unlock_skill_group(&mut self, skill_group_kind: SkillGroupKind) {
319        if !self.skill_groups.contains_key(&skill_group_kind) {
320            self.skill_groups
321                .insert(skill_group_kind, SkillGroup::new(skill_group_kind));
322        }
323    }
324
325    /// Returns an iterator over skill groups
326    pub fn skill_groups(&self) -> impl Iterator<Item = &SkillGroup> { self.skill_groups.values() }
327
328    /// Returns a reference to a particular skill group in a skillset
329    fn skill_group(&self, skill_group: SkillGroupKind) -> Option<&SkillGroup> {
330        self.skill_groups.get(&skill_group)
331    }
332
333    /// Returns a mutable reference to a particular skill group in a skillset
334    /// Requires that skillset contains skill that unlocks the skill group
335    fn skill_group_mut(&mut self, skill_group: SkillGroupKind) -> Option<&mut SkillGroup> {
336        // In order to mutate skill group, we check that the prerequisite skill has been
337        // acquired, as this is one of the requirements for us to consider the skill
338        // group accessible.
339        let skill_group_accessible = self.skill_group_accessible(skill_group);
340        if skill_group_accessible {
341            self.skill_groups.get_mut(&skill_group)
342        } else {
343            None
344        }
345    }
346
347    /// Adds experience to the skill group within an entity's skill set, will
348    /// attempt to earn a skill point while doing so. If a skill point was
349    /// earned, returns the number of earned skill points in the skill group.
350    pub fn add_experience(&mut self, skill_group_kind: SkillGroupKind, amount: u32) -> Option<u16> {
351        if let Some(skill_group) = self.skill_group_mut(skill_group_kind) {
352            skill_group.add_experience(amount)
353        } else {
354            warn!("Tried to add experience to a skill group that player does not have");
355            None
356        }
357    }
358
359    /// Gets the available experience for a particular skill group
360    pub fn available_experience(&self, skill_group: SkillGroupKind) -> u32 {
361        self.skill_group(skill_group)
362            .map_or(0, |s_g| s_g.available_exp)
363    }
364
365    /// Checks how much experience is needed for the next skill point in a tree
366    pub fn skill_point_cost(&self, skill_group: SkillGroupKind) -> u32 {
367        if let Some(level) = self.skill_group(skill_group).map(|sg| sg.earned_sp) {
368            skill_group.skill_point_cost(level)
369        } else {
370            skill_group.skill_point_cost(0)
371        }
372    }
373
374    /// Adds skill points to a skill group as long as the player has that skill
375    /// group type.
376    pub fn add_skill_points(
377        &mut self,
378        skill_group_kind: SkillGroupKind,
379        number_of_skill_points: u16,
380    ) {
381        for _ in 0..number_of_skill_points {
382            let exp_needed = self.skill_point_cost(skill_group_kind);
383            self.add_experience(skill_group_kind, exp_needed);
384        }
385    }
386
387    /// Gets the available points for a particular skill group
388    pub fn available_sp(&self, skill_group: SkillGroupKind) -> u16 {
389        self.skill_group(skill_group)
390            .map_or(0, |s_g| s_g.available_sp)
391    }
392
393    /// Gets the total earned points for a particular skill group
394    pub fn earned_sp(&self, skill_group: SkillGroupKind) -> u16 {
395        self.skill_group(skill_group).map_or(0, |s_g| s_g.earned_sp)
396    }
397
398    /// Checks that the skill set contains all prerequisite skills of the
399    /// required level for a particular skill
400    pub fn prerequisites_met(&self, skill: Skill) -> bool {
401        match skill.prerequisite_skills() {
402            Some(SkillPrerequisite::All(skills)) => skills
403                .iter()
404                .all(|(s, l)| self.skill_level(*s).is_ok_and(|l_b| l_b >= *l)),
405            Some(SkillPrerequisite::Any(skills)) => skills
406                .iter()
407                .any(|(s, l)| self.skill_level(*s).is_ok_and(|l_b| l_b >= *l)),
408            None => true,
409        }
410    }
411
412    /// Gets skill point cost to purchase skill of next level
413    pub fn skill_cost(&self, skill: Skill) -> u16 {
414        let next_level = self.next_skill_level(skill);
415        skill.skill_cost(next_level)
416    }
417
418    /// Checks if player has sufficient skill points to purchase a skill
419    pub fn sufficient_skill_points(&self, skill: Skill) -> bool {
420        if let Some(skill_group_kind) = skill.skill_group_kind() {
421            if let Some(skill_group) = self.skill_group(skill_group_kind) {
422                let needed_sp = self.skill_cost(skill);
423                skill_group.available_sp >= needed_sp
424            } else {
425                false
426            }
427        } else {
428            false
429        }
430    }
431
432    /// Checks the next level of a skill
433    fn next_skill_level(&self, skill: Skill) -> u16 {
434        if let Ok(level) = self.skill_level(skill) {
435            // If already has skill, then level + 1
436            level + 1
437        } else {
438            // Otherwise the next level is the first level
439            1
440        }
441    }
442
443    /// Unlocks a skill for a player, assuming they have the relevant skill
444    /// group unlocked and available SP in that skill group.
445    ///
446    /// NOTE: Please don't use pathological or clever implementations of to_mut
447    /// here.
448    pub fn unlock_skill_cow<'a, B, C>(
449        this_: &'a mut B,
450        skill: Skill,
451        to_mut: impl FnOnce(&'a mut B) -> &'a mut C,
452    ) -> Result<(), SkillUnlockError>
453    where
454        B: Borrow<SkillSet>,
455        C: BorrowMut<SkillSet> + 'a,
456    {
457        if let Some(skill_group_kind) = skill.skill_group_kind() {
458            let this = (*this_).borrow();
459            let next_level = this.next_skill_level(skill);
460            let prerequisites_met = this.prerequisites_met(skill);
461            // Check that skill is not yet at max level
462            if !matches!(this.skills.get(&skill), Some(level) if *level == skill.max_level()) {
463                if let Some(skill_group) = this.skill_groups.get(&skill_group_kind)
464                    && this.skill_group_accessible_if_exists(skill_group_kind)
465                {
466                    if prerequisites_met {
467                        if let Some(new_available_sp) = skill_group
468                            .available_sp
469                            .checked_sub(skill.skill_cost(next_level))
470                        {
471                            // Perform all mutation inside this branch, to avoid triggering a copy
472                            // on write or flagged storage in cases where this matters.
473                            let this_ = to_mut(this_);
474                            let this = this_.borrow_mut();
475                            // NOTE: Verified to exist previously when we accessed
476                            // this.skill_groups (assuming a non-pathological implementation of
477                            // ToOwned).
478                            let skill_group = this.skill_groups.get_mut(&skill_group_kind).expect(
479                                "Verified to exist when we previously accessed this.skill_groups",
480                            );
481                            skill_group.available_sp = new_available_sp;
482                            skill_group.ordered_skills.push(skill);
483                            if let Skill::UnlockGroup(group) = skill {
484                                this.unlock_skill_group(group);
485                            }
486                            this.skills.insert(skill, next_level);
487                            Ok(())
488                        } else {
489                            trace!("Tried to unlock skill for skill group with insufficient SP");
490                            Err(SkillUnlockError::InsufficientSP)
491                        }
492                    } else {
493                        trace!("Tried to unlock skill without meeting prerequisite skills");
494                        Err(SkillUnlockError::MissingPrerequisites)
495                    }
496                } else {
497                    trace!("Tried to unlock skill for a skill group that player does not have");
498                    Err(SkillUnlockError::UnavailableSkillGroup)
499                }
500            } else {
501                trace!("Tried to unlock skill the player already has");
502                Err(SkillUnlockError::SkillAlreadyUnlocked)
503            }
504        } else {
505            warn!(
506                ?skill,
507                "Tried to unlock skill that does not exist in any skill group!"
508            );
509            Err(SkillUnlockError::NoParentSkillTree)
510        }
511    }
512
513    /// Convenience function for the case where you have mutable access to the
514    /// skill.
515    pub fn unlock_skill(&mut self, skill: Skill) -> Result<(), SkillUnlockError> {
516        Self::unlock_skill_cow(self, skill, |x| x)
517    }
518
519    /// Checks if the player has available SP to spend
520    pub fn has_available_sp(&self) -> bool {
521        self.skill_groups.iter().any(|(kind, sg)| {
522            sg.available_sp > 0
523            // Subtraction in bounds because of the invariant that available_sp <= earned_sp
524                && (sg.earned_sp - sg.available_sp) < kind.total_skill_point_cost()
525        })
526    }
527
528    /// Checks if the skill is at max level in a skill set
529    pub fn is_at_max_level(&self, skill: Skill) -> bool {
530        if let Ok(level) = self.skill_level(skill) {
531            level == skill.max_level()
532        } else {
533            false
534        }
535    }
536
537    /// Checks if skill set contains a skill
538    pub fn has_skill(&self, skill: Skill) -> bool { self.skills.contains_key(&skill) }
539
540    /// Returns the level of the skill
541    pub fn skill_level(&self, skill: Skill) -> Result<u16, SkillError> {
542        if let Some(level) = self.skills.get(&skill).copied() {
543            Ok(level)
544        } else {
545            Err(SkillError::MissingSkill)
546        }
547    }
548}
549
550#[derive(Debug)]
551pub enum SkillError {
552    MissingSkill,
553}
554
555#[derive(Debug)]
556pub enum SkillUnlockError {
557    InsufficientSP,
558    MissingPrerequisites,
559    UnavailableSkillGroup,
560    SkillAlreadyUnlocked,
561    NoParentSkillTree,
562}
563
564#[derive(Debug)]
565pub enum SpRewardError {
566    InsufficientExp,
567    UnavailableSkillGroup,
568    Overflow,
569}
570
571#[derive(Debug, PartialEq, Eq, Clone, Copy, Deserialize, Serialize)]
572pub enum SkillsPersistenceError {
573    HashMismatch,
574    DeserializationFailure,
575    SpentExpMismatch,
576    SkillsUnlockFailed,
577}
578
579#[derive(Debug, Clone, Deserialize, Serialize)]
580pub enum SkillPrerequisite {
581    All(HashMap<Skill, u16>),
582    Any(HashMap<Skill, u16>),
583}
veloren_common/comp/skillset/mod.rs

veloren_common/comp/skillset/
mod.rs
