17012447928

Committed 16 Aug 2025 08:12PM UTC coverage: 38.85% (-12.3%) from 51.196%

Build # 17012447928

Build Type

Pull #3

github

Committed by

Xevion

Commit Message

chore: add cargo checks to pre-commit

Pull Request Pull Request #3: ECS Refactor

Run Details

161 of 1172 new or added lines in 23 files covered. (13.74%)

9 existing lines in 4 files now uncovered.

777 of 2000 relevant lines covered (38.85%)

101.8 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

90.4

/src/map/graph.rs

use glam::Vec2;

use crate::systems::movement::NodeId;

use super::direction::Direction;

use bitflags::bitflags;

bitflags! {
    /// Defines who can traverse a given edge using flags for fast checking.
    #[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
    pub struct TraversalFlags: u8 {
        const PACMAN = 1 << 0;
        const GHOST = 1 << 1;

        /// Convenience flag for edges that all entities can use
        const ALL = Self::PACMAN.bits() | Self::GHOST.bits();
    }
}

/// Represents a directed edge from one node to another with a given weight (e.g., distance).
#[derive(Debug, Clone, Copy)]
pub struct Edge {
    /// The destination node of this edge.
    pub target: NodeId,
    /// The length of the edge.
    pub distance: f32,
    /// The cardinal direction of this edge.
    pub direction: Direction,
    /// Defines who is allowed to traverse this edge.
    pub traversal_flags: TraversalFlags,
}

/// Represents a node in the graph, defined by its position.
#[derive(Debug)]
pub struct Node {
    /// The 2D coordinates of the node.
    pub position: Vec2,
}

/// Represents the four possible directions from a node in the graph.
///
/// Each field contains an optional edge leading in that direction.
/// This structure is used to represent the adjacency list for each node,
/// providing O(1) access to edges in any cardinal direction.
#[derive(Debug, Default)]
pub struct Intersection {
    /// Edge leading upward from this node, if it exists.
    pub up: Option<Edge>,
    /// Edge leading downward from this node, if it exists.
    pub down: Option<Edge>,
    /// Edge leading leftward from this node, if it exists.
    pub left: Option<Edge>,
    /// Edge leading rightward from this node, if it exists.
    pub right: Option<Edge>,
}

impl Intersection {
    /// Returns an iterator over all edges from this intersection.
    ///
    /// This iterator yields only the edges that exist (non-None values).
    pub fn edges(&self) -> impl Iterator<Item = Edge> {
        [self.up, self.down, self.left, self.right].into_iter().flatten()
    }

    /// Retrieves the edge in the specified direction, if it exists.
    pub fn get(&self, direction: Direction) -> Option<Edge> {
        match direction {
            Direction::Up => self.up,
            Direction::Down => self.down,
            Direction::Left => self.left,
            Direction::Right => self.right,
        }
    }

    /// Sets the edge in the specified direction.
    ///
    /// This will overwrite any existing edge in that direction.
    pub fn set(&mut self, direction: Direction, edge: Edge) {
        match direction {
            Direction::Up => self.up = Some(edge),
            Direction::Down => self.down = Some(edge),
            Direction::Left => self.left = Some(edge),
            Direction::Right => self.right = Some(edge),
        }
    }
}

/// A directed graph structure using an adjacency list representation.
///
/// Nodes are stored in a vector, and their indices serve as their `NodeId`.
/// This design provides fast, O(1) lookups for node data. Edges are stored
/// in an adjacency list, where each node has a list of outgoing edges.
pub struct Graph {
    nodes: Vec<Node>,
    pub adjacency_list: Vec<Intersection>,
}

impl Graph {
    /// Creates a new, empty graph.
    pub fn new() -> Self {
        Graph {
            nodes: Vec::new(),
            adjacency_list: Vec::new(),
        }
    }

    /// Adds a new node with the given data to the graph and returns its ID.
    pub fn add_node(&mut self, data: Node) -> NodeId {
        let id = self.nodes.len();
        self.nodes.push(data);
        self.adjacency_list.push(Intersection::default());
        id
    }

    /// Connects a new node to the graph and adds an edge between the existing node and the new node.
    pub fn add_connected(&mut self, from: NodeId, direction: Direction, new_node: Node) -> Result<NodeId, &'static str> {
        let to = self.add_node(new_node);
        self.connect(from, to, false, None, direction)?;
        Ok(to)
    }

    /// Connects two existing nodes with an edge.
    pub fn connect(
        &mut self,
        from: NodeId,
        to: NodeId,
        replace: bool,
        distance: Option<f32>,
        direction: Direction,
    ) -> Result<(), &'static str> {
        if from >= self.adjacency_list.len() {
            return Err("From node does not exist.");
        }
        if to >= self.adjacency_list.len() {
            return Err("To node does not exist.");
        }

        let edge_a = self.add_edge(from, to, replace, distance, direction, TraversalFlags::ALL);
        let edge_b = self.add_edge(to, from, replace, distance, direction.opposite(), TraversalFlags::ALL);

        if edge_a.is_err() && edge_b.is_err() {
            return Err("Failed to connect nodes in both directions.");
        }

        Ok(())
    }

    /// Adds a directed edge between two nodes.
    ///
    /// If `distance` is `None`, it will be calculated automatically based on the
    /// Euclidean distance between the two nodes.
    ///
    /// # Errors
    ///
    /// Returns an error if:
    /// - The `from` node does not exist
    /// - An edge already exists in the specified direction
    /// - An edge already exists to the target node
    /// - The provided distance is not positive
    pub fn add_edge(
        &mut self,
        from: NodeId,
        to: NodeId,
        replace: bool,
        distance: Option<f32>,
        direction: Direction,
        traversal_flags: TraversalFlags,
    ) -> Result<(), &'static str> {
        let edge = Edge {
            target: to,
            distance: match distance {
                Some(distance) => {
                    if distance < 0.0 {
                        return Err("Edge distance must be on-negative.");
                    }
                    distance
                }
                None => {
                    // If no distance is provided, calculate it based on the positions of the nodes
                    let from_pos = self.nodes[from].position;
                    let to_pos = self.nodes[to].position;
                    from_pos.distance(to_pos)
                }
            },
            direction,
            traversal_flags,
        };

        if from >= self.adjacency_list.len() {
            return Err("From node does not exist.");
        }

        let adjacency_list = &mut self.adjacency_list[from];

        // Check if the edge already exists in this direction or to the same target
        if let Some(err) = adjacency_list.edges().find_map(|e| {
            if !replace {
                // If we're not replacing the edge, we don't want to replace an edge that already exists in this direction
                if e.direction == direction {
                    return Some(Err("Edge already exists in this direction."));
                } else if e.target == to {
                    return Some(Err("Edge already exists."));
                }
            }
            None
        }) {
            return err;
        }

        adjacency_list.set(direction, edge);

        Ok(())
    }

    /// Retrieves an immutable reference to a node's data.
    pub fn get_node(&self, id: NodeId) -> Option<&Node> {
        self.nodes.get(id)
    }

    /// Returns an iterator over all nodes in the graph.
    pub fn nodes(&self) -> impl Iterator<Item = &Node> {
        self.nodes.iter()
    }

    /// Returns an iterator over all edges in the graph.
    pub fn edges(&self) -> impl Iterator<Item = (NodeId, Edge)> + '_ {
        self.adjacency_list
            .iter()
            .enumerate()
            .flat_map(|(node_id, intersection)| intersection.edges().map(move |edge| (node_id, edge)))
    }

    /// Finds a specific edge from a source node to a target node.
    pub fn find_edge(&self, from: NodeId, to: NodeId) -> Option<Edge> {
        self.adjacency_list.get(from)?.edges().find(|edge| edge.target == to)
    }

    /// Finds an edge originating from a given node that follows a specific direction.
    pub fn find_edge_in_direction(&self, from: NodeId, direction: Direction) -> Option<Edge> {
        self.adjacency_list.get(from)?.get(direction)
    }
}

// Default implementation for creating an empty graph.
impl Default for Graph {
    fn default() -> Self {
        Self::new()
    }
}

1	use glam::Vec2;
2
3	use crate::systems::movement::NodeId;
4
5	use super::direction::Direction;
6
7	use bitflags::bitflags;
8
9	bitflags! {
10	/// Defines who can traverse a given edge using flags for fast checking.
11	#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
12	pub struct TraversalFlags: u8 {
13	const PACMAN = 1 << 0;
14	const GHOST = 1 << 1;
15
16	/// Convenience flag for edges that all entities can use
17	const ALL = Self::PACMAN.bits() \| Self::GHOST.bits();
18	}
19	}
20
21	/// Represents a directed edge from one node to another with a given weight (e.g., distance).
22	#[derive(Debug, Clone, Copy)]
23	pub struct Edge {
24	/// The destination node of this edge.
25	pub target: NodeId,
26	/// The length of the edge.
27	pub distance: f32,
28	/// The cardinal direction of this edge.
29	pub direction: Direction,
30	/// Defines who is allowed to traverse this edge.
31	pub traversal_flags: TraversalFlags,
32	}
33
34	/// Represents a node in the graph, defined by its position.
35	#[derive(Debug)]
36	pub struct Node {
37	/// The 2D coordinates of the node.
38	pub position: Vec2,
39	}
40
41	/// Represents the four possible directions from a node in the graph.
42	///
43	/// Each field contains an optional edge leading in that direction.
44	/// This structure is used to represent the adjacency list for each node,
45	/// providing O(1) access to edges in any cardinal direction.
46	#[derive(Debug, Default)]
47	pub struct Intersection {
48	/// Edge leading upward from this node, if it exists.
49	pub up: Option<Edge>,
50	/// Edge leading downward from this node, if it exists.
51	pub down: Option<Edge>,
52	/// Edge leading leftward from this node, if it exists.
53	pub left: Option<Edge>,
54	/// Edge leading rightward from this node, if it exists.
55	pub right: Option<Edge>,
56	}
57
58	impl Intersection {
59	/// Returns an iterator over all edges from this intersection.
60	///
61	/// This iterator yields only the edges that exist (non-None values).
62	pub fn edges(&self) -> impl Iterator<Item = Edge> {	1,344✔
63	[self.up, self.down, self.left, self.right].into_iter().flatten()	1,344✔
64	}	1,344✔
65
66	/// Retrieves the edge in the specified direction, if it exists.
67	pub fn get(&self, direction: Direction) -> Option<Edge> {	2,387✔
68	match direction {	2,387✔
69	Direction::Up => self.up,	596✔
70	Direction::Down => self.down,	596✔
71	Direction::Left => self.left,	597✔
72	Direction::Right => self.right,	598✔
73	}
74	}	2,387✔
75
76	/// Sets the edge in the specified direction.
77	///
78	/// This will overwrite any existing edge in that direction.
79	pub fn set(&mut self, direction: Direction, edge: Edge) {	1,338✔
80	match direction {	1,338✔
81	Direction::Up => self.up = Some(edge),	293✔
82	Direction::Down => self.down = Some(edge),	293✔
83	Direction::Left => self.left = Some(edge),	375✔
84	Direction::Right => self.right = Some(edge),	377✔
85	}
86	}	1,338✔
87	}
88
89	/// A directed graph structure using an adjacency list representation.
90	///
91	/// Nodes are stored in a vector, and their indices serve as their `NodeId`.
92	/// This design provides fast, O(1) lookups for node data. Edges are stored
93	/// in an adjacency list, where each node has a list of outgoing edges.
94	pub struct Graph {
95	nodes: Vec<Node>,
96	pub adjacency_list: Vec<Intersection>,
97	}
98
99	impl Graph {
100	/// Creates a new, empty graph.
101	pub fn new() -> Self {	11✔
102	Graph {	11✔
103	nodes: Vec::new(),	11✔
104	adjacency_list: Vec::new(),	11✔
105	}	11✔
106	}	11✔
107
108	/// Adds a new node with the given data to the graph and returns its ID.
109	pub fn add_node(&mut self, data: Node) -> NodeId {	640✔
110	let id = self.nodes.len();	640✔
111	self.nodes.push(data);	640✔
112	self.adjacency_list.push(Intersection::default());	640✔
113	id	640✔
114	}	640✔
115
116	/// Connects a new node to the graph and adds an edge between the existing node and the new node.
117	pub fn add_connected(&mut self, from: NodeId, direction: Direction, new_node: Node) -> Result<NodeId, &'static str> {	5✔
118	let to = self.add_node(new_node);	5✔
119	self.connect(from, to, false, None, direction)?;	5✔
120	Ok(to)	5✔
121	}	5✔
122
123	/// Connects two existing nodes with an edge.
124	pub fn connect(	668✔
125	&mut self,	668✔
126	from: NodeId,	668✔
127	to: NodeId,	668✔
128	replace: bool,	668✔
129	distance: Option<f32>,	668✔
130	direction: Direction,	668✔
131	) -> Result<(), &'static str> {	668✔
132	if from >= self.adjacency_list.len() {	668✔
133	return Err("From node does not exist.");	1✔
134	}	667✔
135	if to >= self.adjacency_list.len() {	667✔
136	return Err("To node does not exist.");	1✔
137	}	666✔
138		666✔
139	let edge_a = self.add_edge(from, to, replace, distance, direction, TraversalFlags::ALL);	666✔
140	let edge_b = self.add_edge(to, from, replace, distance, direction.opposite(), TraversalFlags::ALL);	666✔
141		666✔
142	if edge_a.is_err() && edge_b.is_err() {	666✔
143	return Err("Failed to connect nodes in both directions.");	×
144	}	666✔
145		666✔
146	Ok(())	666✔
147	}	668✔
148
149	/// Adds a directed edge between two nodes.
150	///
151	/// If `distance` is `None`, it will be calculated automatically based on the
152	/// Euclidean distance between the two nodes.
153	///
154	/// # Errors
155	///
156	/// Returns an error if:
157	/// - The `from` node does not exist
158	/// - An edge already exists in the specified direction
159	/// - An edge already exists to the target node
160	/// - The provided distance is not positive
161	pub fn add_edge(	1,340✔
162	&mut self,	1,340✔
163	from: NodeId,	1,340✔
164	to: NodeId,	1,340✔
165	replace: bool,	1,340✔
166	distance: Option<f32>,	1,340✔
167	direction: Direction,	1,340✔
168	traversal_flags: TraversalFlags,	1,340✔
169	) -> Result<(), &'static str> {	1,340✔
170	let edge = Edge {	1,339✔
171	target: to,	1,340✔
172	distance: match distance {	1,340✔
173	Some(distance) => {	6✔
174	if distance < 0.0 {	6✔
175	return Err("Edge distance must be on-negative.");	1✔
176	}	5✔
177	distance	5✔
178	}
179	None => {
180	// If no distance is provided, calculate it based on the positions of the nodes
181	let from_pos = self.nodes[from].position;	1,334✔
182	let to_pos = self.nodes[to].position;	1,334✔
183	from_pos.distance(to_pos)	1,334✔
184	}
185	},
186	direction,	1,339✔
187	traversal_flags,	1,339✔
188	};	1,339✔
189		1,339✔
190	if from >= self.adjacency_list.len() {	1,339✔
191	return Err("From node does not exist.");	×
192	}	1,339✔
193		1,339✔
194	let adjacency_list = &mut self.adjacency_list[from];	1,339✔
195
196	// Check if the edge already exists in this direction or to the same target
197	if let Some(err) = adjacency_list.edges().find_map(\|e\| {	1,339✔
198	if !replace {	811✔
199	// If we're not replacing the edge, we don't want to replace an edge that already exists in this direction
200	if e.direction == direction {	799✔
201	return Some(Err("Edge already exists in this direction."));	1✔
202	} else if e.target == to {	798✔
203	return Some(Err("Edge already exists."));	×
204	}	798✔
205	}	12✔
206	None	810✔
207	}) {	1,339✔
208	return err;	1✔
209	}	1,338✔
210		1,338✔
211	adjacency_list.set(direction, edge);	1,338✔
212		1,338✔
213	Ok(())	1,338✔
214	}	1,340✔
215
216	/// Retrieves an immutable reference to a node's data.
217	pub fn get_node(&self, id: NodeId) -> Option<&Node> {	309✔
218	self.nodes.get(id)	309✔
219	}	309✔
220
221	/// Returns an iterator over all nodes in the graph.
222	pub fn nodes(&self) -> impl Iterator<Item = &Node> {	3✔
223	self.nodes.iter()	3✔
224	}	3✔
225
226	/// Returns an iterator over all edges in the graph.
NEW 227	pub fn edges(&self) -> impl Iterator<Item = (NodeId, Edge)> + '_ {	×
NEW 228	self.adjacency_list	×
NEW 229	.iter()	×
NEW 230	.enumerate()	×
NEW 231	.flat_map(\|(node_id, intersection)\| intersection.edges().map(move \|edge\| (node_id, edge)))	×
232	}	×
233
234	/// Finds a specific edge from a source node to a target node.
235	pub fn find_edge(&self, from: NodeId, to: NodeId) -> Option<Edge> {	4✔
236	self.adjacency_list.get(from)?.edges().find(\|edge\| edge.target == to)	7✔
237	}	4✔
238
239	/// Finds an edge originating from a given node that follows a specific direction.
240	pub fn find_edge_in_direction(&self, from: NodeId, direction: Direction) -> Option<Edge> {	3✔
241	self.adjacency_list.get(from)?.get(direction)	3✔
242	}	3✔
243	}
244
245	// Default implementation for creating an empty graph.
246	impl Default for Graph {
247	fn default() -> Self {	×
248	Self::new()	×
249	}	×
250	}

Xevion / Pac-Man / 17012447928

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous