veloren_rtsim/data/

quest.rs

use common::{
    resources::Time,
    rtsim::{Actor, ItemResource, QuestId, SiteId},
};
use hashbrown::{HashMap, HashSet};
use itertools::Either;
use serde::{Deserialize, Serialize};
use std::{
    num::NonZeroU32,
    sync::atomic::{AtomicU8, AtomicU64, Ordering},
};
use vek::Vec2;

/// The easiest way to think about quests is as a virtual Jira board (or,
/// perhaps, a community jobs noticeboard).
///
/// This type represents the board. In effect, it is a big database of active
/// and resolved quests. Quests are not, by themselves, 'active' participants in
/// the world. They are informal contracts, and it is up to the NPCs and players
/// that interact with them to drive them forward.
///
/// Quests that are resolved or that have been active for some time without
/// activity may be garbage-collected, although the exact mechanism for this has
/// not yet been defined.
#[derive(Default, Serialize, Deserialize)]
pub struct Quests {
    /// Because quests can be created in a multi-threaded context, we use an
    /// atomic counter to generate IDs for them. Quest insertion happens at
    /// the end of each tick. This is guarded by a utility function, so
    /// unregistered quests *shouldn't* be visible to the rest of the code.
    id_counter: AtomicU64,
    quests: HashMap<QuestId, Quest>,
    #[serde(skip)]
    related_quests: HashMap<Actor, HashSet<QuestId>>,
}

impl Clone for Quests {
    fn clone(&self) -> Self {
        Self {
            // This isn't strictly kosher in a multi-threaded context, but we assume that clones
            // only happen on the main thread when we don't care about synchronisation
            id_counter: AtomicU64::new(self.id_counter.load(Ordering::SeqCst)),
            quests: self.quests.clone(),
            // Bit of a hack: we assume that cloning only happens for the sake of persistence, and
            // we don't persisted the related quests cache
            related_quests: HashMap::default(),
        }
    }
}

impl Quests {
    /// Register a new quest ID. It can be defined later with
    /// [`Quests::create`].
    ///
    /// Critically, this function works in a shared + concurrent context, which
    /// allows us to run it in parallel within the NPC AI code.
    pub fn register(&self) -> QuestId { QuestId(self.id_counter.fetch_add(1, Ordering::Relaxed)) }

    /// Create a quest with the given ID.
    ///
    /// This ID should be generated by [`Quests::register`] and used only once
    /// to create a quest.
    pub fn create(&mut self, id: QuestId, quest: Quest) {
        // Update quest lookup table
        quest.for_related_actors(|actor| {
            self.related_quests.entry(actor).or_default().insert(id);
        });
        self.quests.entry(id).or_insert(quest);
    }

    pub fn get(&self, id: QuestId) -> Option<&Quest> { self.quests.get(&id) }

    pub fn related_to(&self, actor: impl Into<Actor>) -> impl Iterator<Item = QuestId> + '_ {
        match self.related_quests.get(&actor.into()) {
            Some(quests) => Either::Left(
                quests.iter()
                // Don't consider resolved quests to be related
                .filter(|id| self.get(**id).is_some_and(|q| q.resolution().is_none()))
                .copied(),
            ),
            None => Either::Right(core::iter::empty()),
        }
    }

    /// Find all of the actors that are related to another actor via a quest
    pub fn related_actors(
        &self,
        actor: impl Into<Actor>,
    ) -> impl ExactSizeIterator<Item = Actor> + '_ {
        let actor = actor.into();
        let mut related = HashSet::new();
        for quest_id in self.related_to(actor) {
            if let Some(quest) = self.quests.get(&quest_id)
                // resolved quests aren't relevant
                && quest.resolution().is_none()
            {
                quest.for_related_actors(|a| {
                    if a != actor {
                        related.insert(a);
                    }
                });
            }
        }
        related.into_iter()
    }

    pub(super) fn prepare(&mut self) {
        // Populate quest lookup table
        for (quest_id, quest) in &self.quests {
            quest.for_related_actors(|actor| {
                self.related_quests
                    .entry(actor)
                    .or_default()
                    .insert(*quest_id);
            });
        }
    }
}

#[derive(Clone, Serialize, Deserialize)]
pub struct Quest {
    /// The actor responsible for arbitrating over the quest.
    ///
    /// Quests can only be resolved by their designated arbiter. The arbiter is
    /// defined when the quest is created, and the arbiter receives the
    /// quest deposit (see [`Quests::resolve`]).
    ///
    /// In the future, this can be extended to include factions, multiple
    /// actors, or even some system in the world (such as a noticeboard
    /// system, so that players can assign one-another quests).
    pub arbiter: Actor,

    /// A machine-intelligible description of the quest and its completion
    /// conditions.
    ///
    /// We try to avoid being prescriptive about what form quests can take
    pub kind: QuestKind,

    /// The time before which the quest should be completed to be considered
    /// successful.
    pub timeout: Option<Time>,

    outcome: QuestOutcome,

    /// The only aspect of the quest that mutates over time. Resolving quests is
    /// monotonic: once resolved, they cannot be unresolved (to avoid the
    /// deposit being paid back twice, for example).
    res: QuestRes,
}

impl Quest {
    /// Create a new escort quest that requires an escorter to travel with an
    /// escortee to a destination.
    ///
    /// The escortee is considered to be the quest arbiter.
    pub fn escort(escortee: Actor, escorter: Actor, to: SiteId) -> Self {
        Self {
            arbiter: escortee,
            kind: QuestKind::Escort {
                escortee,
                escorter,
                to,
            },
            timeout: None,
            outcome: QuestOutcome::default(),
            res: QuestRes(AtomicU8::new(0)),
        }
    }

    /// Create a new slay quest that requires the slayer to kill a target.
    pub fn slay(arbiter: Actor, target: Actor, slayer: Actor) -> Self {
        Self {
            arbiter,
            kind: QuestKind::Slay { target, slayer },
            timeout: None,
            outcome: QuestOutcome::default(),
            res: QuestRes(AtomicU8::new(0)),
        }
    }

    /// Create a new courier quest that requires an individual to deliver an
    /// item to another individual. The arbiter is the individual that is
    /// expecting to receive the package, and the source is the individual
    /// that created the quest opportunity. The messenger is the individual
    /// making the journey with the package in hand.
    pub fn courier(arbiter: Actor, instance: CourierQuestInstance) -> Self {
        Self {
            arbiter,
            kind: QuestKind::Courier { instance },
            timeout: None,
            outcome: QuestOutcome::default(),
            res: QuestRes(AtomicU8::new(0)),
        }
    }

    /// Deposit an item (usually for payment to whoever completes the quest) in
    /// the quest for safekeeping.
    ///
    /// Deposits are paid out to the arbiter when a quest is resolved. The
    /// arbiter usually passes the deposit on to the character that
    /// completed the quest, but this is not the concern of the quest system.
    pub fn with_deposit(mut self, item: ItemResource, amount: f32) -> Self {
        self.outcome.deposit = Some((item, amount));
        self
    }

    /// Add a timeout to the quest, beyond which the quest is considered to be
    /// failed.
    pub fn with_timeout(mut self, time: Time) -> Self {
        self.timeout = Some(time);
        self
    }

    /// Resolve a quest.
    ///
    /// Quest resolution is monotonic and so can only be done once: all future
    /// attempts will fail. If this is the first attempt at resolving (i.e:
    /// the function returns `Some(...)`), the deposit will be returned.
    ///
    /// Note that the result type of this function only indicates whether
    /// updating the resolution status of the quest was successful:
    /// `Some(...)` will still be returned if the quest was resolved by failure
    /// too.
    ///
    /// The `requester` parameter is a sanity test: you should pass the actor
    /// that originated the request to resolve, and the function will ensure
    /// that this matches the quest's designated arbiter.
    pub fn resolve(&self, requester: impl Into<Actor>, res: bool) -> Option<QuestOutcome> {
        if self.arbiter != requester.into() {
            // Actor that requested quest resolution did not match the designated arbiter,
            // resolution not permitted!
            None
        } else {
            self.res
                .0
                .compare_exchange(
                    0,
                    if res { 2 } else { 1 },
                    Ordering::Relaxed,
                    Ordering::Relaxed,
                )
                .ok()
                .map(|_| self.outcome.clone())
        }
    }

    pub fn resolution(&self) -> Option<bool> { self.res.get() }

    pub fn get_related_actors(&self) -> HashSet<Actor> {
        let mut related = HashSet::default();
        self.for_related_actors(|actor| {
            related.insert(actor);
        });
        related
    }

    fn for_related_actors(&self, mut f: impl FnMut(Actor)) {
        f(self.arbiter);
        match &self.kind {
            QuestKind::Escort {
                escortee,
                escorter,
                to: _,
            } => {
                f(*escortee);
                f(*escorter);
            },
            QuestKind::Slay { target, slayer } => {
                f(*target);
                f(*slayer);
            },
            QuestKind::Courier { instance } => {
                f(instance.source_actor);
                f(instance.messenger);
            },
        }
    }
}

// 0 = unresolved, 1 = fail, 2.. = success
#[derive(Default, Serialize, Deserialize)]
struct QuestRes(AtomicU8);

impl QuestRes {
    fn get(&self) -> Option<bool> {
        match self.0.load(Ordering::Relaxed) {
            0 => None,
            1 => Some(false),
            _ => Some(true),
        }
    }
}

impl Clone for QuestRes {
    fn clone(&self) -> Self {
        // This isn't strictly kosher in a multi-threaded context, but we assume that
        // clones only happen on the main thread when we don't care about
        // synchronisation
        Self(AtomicU8::new(self.0.load(Ordering::Relaxed)))
    }
}

/// Produced on completion of a quest.
///
/// Can represent both success and failure outcomes, such as:
///
/// - The release of a payment deposit
/// - A change in reputation/goodwill
/// - The role of an NPC or playing changing (promotion!)
/// - etc.
#[derive(Clone, Default, Serialize, Deserialize)]
pub struct QuestOutcome {
    /// An item held in deposit.
    ///
    /// When the quest is resolved, it is returned to the arbiter (usually to
    /// then be passed to the quest completer, although not always).
    ///
    /// Deposits exist to avoid NPCs (or players) constantly needing to track
    /// 'earmarked' items in their inventories that correspond to payments.
    pub deposit: Option<(ItemResource, f32)>,
}

#[derive(Clone, Serialize, Deserialize)]
pub enum QuestKind {
    Escort {
        escortee: Actor,
        escorter: Actor,
        to: SiteId,
    },
    Slay {
        target: Actor,
        slayer: Actor,
    },
    Courier {
        instance: CourierQuestInstance,
    },
}

/// [`COURIER_QUEST_VARIANTS`] is worth looking at, as it contains all possible
/// quest permutations and can be extended.
#[derive(Debug, Copy, Clone, Serialize, Deserialize, PartialEq, PartialOrd, Eq, Ord, Hash)]
pub enum CourierQuest {
    /// Find an NPC and speak to them. No items are required.
    Message,
    /// Find an NPC and give them something.
    Deliver {
        payload: Payload,
        recipient: Recipient,
    },
}

/// For [`CourierQuest`].
#[derive(Debug, Copy, Clone, Serialize, Deserialize, PartialEq, PartialOrd, Eq, Ord, Hash)]
pub enum Recipient {
    Other,
    Giver,
}

/// For [`CourierQuest`].
#[derive(Debug, Copy, Clone, Serialize, Deserialize, PartialEq, PartialOrd, Eq, Ord, Hash)]
pub enum Payload {
    LegoomLeaf,
    GnarlingCarving,
}

impl CourierQuest {
    pub fn payload(self) -> Option<Payload> {
        match self {
            CourierQuest::Message => None,
            CourierQuest::Deliver { payload, .. } => Some(payload),
        }
    }

    pub fn delivers_to_giver(self) -> bool {
        matches!(self, CourierQuest::Deliver {
            recipient: Recipient::Giver,
            ..
        })
    }
}

/// Stack-allocated array of all of the possible courier quests that can be
/// rolled.
pub const COURIER_QUEST_VARIANTS: [CourierQuest; 5] = [
    // Add more here later!
    CourierQuest::Message,
    CourierQuest::Deliver {
        payload: Payload::GnarlingCarving,
        recipient: Recipient::Other,
    },
    CourierQuest::Deliver {
        payload: Payload::GnarlingCarving,
        recipient: Recipient::Giver,
    },
    CourierQuest::Deliver {
        payload: Payload::LegoomLeaf,
        recipient: Recipient::Other,
    },
    CourierQuest::Deliver {
        payload: Payload::LegoomLeaf,
        recipient: Recipient::Giver,
    },
];

/// Contains a completable courier quest.
#[derive(Clone, Copy, Debug, Serialize, Deserialize)]
pub struct CourierQuestInstance {
    pub kind: CourierQuest,
    pub spot: Option<Vec2<i32>>,
    /// The source site may or may not be useful in all situations, but we do
    /// want to keep it available in case we need to have dialogue that says
    /// something like "Wow, you came all the way from <site> to send me this?"
    pub source_site: Option<SiteId>,
    pub source_actor: Actor,
    /// This is `source_actor` for fetch quests.
    pub target_actor: Actor,
    /// Target actor's site, if available.
    pub target_site: Option<SiteId>,
    /// Usually this is the player.
    pub messenger: Actor,
    /// The distance to be traversed, calculated once at quest start.
    pub distance: NonZeroU32,
}