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
104
105
106
107
108
109
110
111

use crate::{
    astar::{astar, Path, SearchInfo},
    BSPNode, BSPTree, NodeIndex, NodePayload, PortalIter,
};
use glam::Vec2;
use rand::Rng;

use crate::{Face, Portals};

/// Contains the graph and edges necessary for path finding
#[derive(Default)]
#[cfg_attr(feature = "serialize", derive(serde::Serialize, serde::Deserialize))]
pub struct NavigationContext {
    tree: Option<BSPTree>,
    portals: Portals,
}

impl NavigationContext {
    /// Creates a new navigation context
    pub fn new(faces: impl IntoIterator<Item = Face>) -> Self {
        let tree = BSPTree::new(faces.into_iter());
        let mut portals = Portals::new();
        if let Some(tree) = tree.as_ref() {
            portals.generate(&tree);
        }

        Self { tree, portals }
    }

    /// Creates a new navigation context.
    /// Shuffles the input which usually reduces the depth of the final tree.
    pub fn new_shuffle(faces: impl IntoIterator<Item = Face>, rng: &mut impl Rng) -> Self {
        let tree = BSPTree::new_shuffle(faces.into_iter(), rng);
        let mut portals = Portals::new();
        if let Some(tree) = tree.as_ref() {
            portals.generate(&tree);
        }

        Self { tree, portals }
    }
    pub fn node(&self, index: NodeIndex) -> Option<&BSPNode> {
        self.tree.as_ref()?.node(index)
    }

    /// Locate a position in the tree.
    /// Return None if there are no faces in the scene
    pub fn locate(&self, point: Vec2) -> Option<NodePayload> {
        match &self.tree {
            Some(tree) => Some(tree.locate(point)),
            None => None,
        }
    }

    /// Get a reference to the navigation context's tree.
    pub fn tree(&self) -> Option<&BSPTree> {
        self.tree.as_ref()
    }

    /// Get a reference to the navigation context's portals.
    pub fn portals(&self) -> &Portals {
        &self.portals
    }

    /// Get the portals associated to a node
    pub fn get(&self, index: NodeIndex) -> PortalIter {
        self.portals.get(index)
    }

    /// Find a path from `start` to `end`
    /// Returns None if no path was found.
    /// If there are no faces in the scene, a straight path will be returned.
    pub fn find_path(
        &self,
        start: Vec2,
        end: Vec2,
        heuristic: impl Fn(Vec2, Vec2) -> f32,
        info: SearchInfo,
    ) -> Option<Path> {
        match &self.tree {
            Some(tree) => astar(
                &tree,
                &self.portals,
                start,
                end,
                heuristic,
                info,
                Path::new(),
            ),
            None => Some(Path::euclidian(start, end)),
        }
    }

    /// Find a path from `start` to `end`
    /// Returns None if no path was found.
    /// If there are no faces in the scene, a straight path will be returned.
    /// Uses an already allocated path to fill and will attempt to only update
    /// parts of the path
    pub fn find_path_inc(
        &self,
        start: Vec2,
        end: Vec2,
        heuristic: impl Fn(Vec2, Vec2) -> f32,
        info: SearchInfo,
        path: Path,
    ) -> Option<Path> {
        match &self.tree {
            Some(tree) => astar(&tree, &self.portals, start, end, heuristic, info, path),
            None => Some(Path::euclidian(start, end)),
        }
    }
}