pedalkernel_layout/
routing.rs

1//! Phase 5: Wire routing (orthogonal Manhattan paths).
2//!
3//! Routes wires between component pins using orthogonal (Manhattan) paths.
4//! Signal path wires run horizontally on the center line. Supply wires run
5//! vertically to the rails. Feedback wires route along the bottom.
6
7use crate::graph::LayoutGraph;
8use crate::types::*;
9use std::collections::{BTreeMap, BTreeSet};
10
11/// Radius for obstacle avoidance — if an L-route corner is within this
12/// distance of a component center, switch to a Z-route.
13const OBSTACLE_RADIUS: f32 = 25.0;
14
15/// Route all wires in the layout based on the graph connectivity.
16pub fn route_wires(layout: &mut Layout, graph: &LayoutGraph) {
17    let mut wires = Vec::new();
18
19    // Build a map from component name to placed position
20    let comp_positions: BTreeMap<&str, (f32, f32)> = layout
21        .components
22        .iter()
23        .map(|c| (c.name.as_str(), (c.x, c.y)))
24        .collect();
25
26    // Build a map from component name to index in layout.components
27    let comp_indices: BTreeMap<&str, usize> = layout
28        .components
29        .iter()
30        .enumerate()
31        .map(|(i, c)| (c.name.as_str(), i))
32        .collect();
33
34    // Collect all component centers as obstacles for wire routing
35    let obstacles: Vec<(f32, f32)> = layout.components.iter().map(|c| (c.x, c.y)).collect();
36
37    // Collect feedback component pairs for feedback wire detection
38    let feedback_comps: BTreeSet<(usize, usize)> = graph
39        .edges
40        .iter()
41        .filter(|e| e.is_feedback)
42        .map(|e| (e.from, e.to))
43        .collect();
44
45    // GND rail Y for feedback wire routing below signal path
46    let gnd_rail_y = layout
47        .supply_rails
48        .iter()
49        .find(|r| r.name == "gnd")
50        .map(|r| r.y)
51        .unwrap_or(layout.bounds.height);
52    let feedback_y = gnd_rail_y - 20.0;
53
54    // For each net group, route wires between the components
55    for ng in &graph.net_groups {
56        let net_name = ng
57            .name
58            .clone()
59            .unwrap_or_else(|| format!("net_{}", ng.index));
60
61        let is_supply_net = ng.name.as_deref() == Some("vcc") || ng.name.as_deref() == Some("gnd");
62
63        // Check if this net contains a feedback edge
64        let is_feedback_net = ng.component_ids.iter().any(|cid_a| {
65            let node_a = graph.id_to_node.get(cid_a).copied();
66            ng.component_ids.iter().any(|cid_b| {
67                let node_b = graph.id_to_node.get(cid_b).copied();
68                if let (Some(a), Some(b)) = (node_a, node_b) {
69                    feedback_comps.contains(&(a, b)) || feedback_comps.contains(&(b, a))
70                } else {
71                    false
72                }
73            })
74        });
75
76        // Collect positioned components in this net
77        let mut positions: Vec<(String, f32, f32)> = Vec::new();
78        for cid in &ng.component_ids {
79            // Map anchor IDs
80            let lookup_name = match cid.as_str() {
81                "__in" | "__out" | "__vcc" | "__gnd" => continue, // Skip anchors
82                name => name,
83            };
84            if let Some(&(x, y)) = comp_positions.get(lookup_name) {
85                positions.push((lookup_name.to_string(), x, y));
86            }
87        }
88
89        if positions.len() < 2 {
90            // Handle supply connections as stub wires
91            if is_supply_net && positions.len() == 1 {
92                let (name, x, y) = &positions[0];
93                let rail_y = if ng.name.as_deref() == Some("vcc") {
94                    layout
95                        .supply_rails
96                        .iter()
97                        .find(|r| r.name == "vcc")
98                        .map(|r| r.y)
99                        .unwrap_or(0.0)
100                } else {
101                    layout
102                        .supply_rails
103                        .iter()
104                        .find(|r| r.name == "gnd")
105                        .map(|r| r.y)
106                        .unwrap_or(layout.bounds.height)
107                };
108
109                wires.push(Wire {
110                    net: net_name,
111                    points: vec![[*x, *y], [*x, rail_y]],
112                    signal_path: false,
113                    monitor_index_start: comp_indices
114                        .get(name.as_str())
115                        .and_then(|&i| layout.components[i].monitor_index),
116                    monitor_index_end: None,
117                });
118            }
119            continue;
120        }
121
122        // Sort positions by x (left to right for signal flow)
123        positions.sort_by(|a, b| a.1.partial_cmp(&b.1).unwrap_or(std::cmp::Ordering::Equal));
124
125        // Route wires between consecutive components in the net
126        for window in positions.windows(2) {
127            let (name_a, x_a, y_a) = &window[0];
128            let (name_b, x_b, y_b) = &window[1];
129
130            let start = Point::new(*x_a, *y_a);
131            let end = Point::new(*x_b, *y_b);
132
133            let points = if is_feedback_net {
134                // Feedback wires route below signal path
135                route_wire_feedback(start, end, feedback_y)
136            } else {
137                route_wire_with_obstacles(start, end, &obstacles)
138            };
139
140            let is_signal = !is_supply_net
141                && ng.name.as_deref() != Some("vcc")
142                && ng.name.as_deref() != Some("gnd");
143
144            let monitor_start = comp_indices
145                .get(name_a.as_str())
146                .and_then(|&i| layout.components[i].monitor_index);
147            let monitor_end = comp_indices
148                .get(name_b.as_str())
149                .and_then(|&i| layout.components[i].monitor_index);
150
151            wires.push(Wire {
152                net: net_name.clone(),
153                points: points.into_iter().map(|p| [p.x, p.y]).collect(),
154                signal_path: is_signal,
155                monitor_index_start: monitor_start,
156                monitor_index_end: monitor_end,
157            });
158        }
159    }
160
161    layout.wires = wires;
162}
163
164/// Route a single wire between two points using orthogonal (Manhattan) routing.
165///
166/// - If same Y: straight horizontal line
167/// - If same X: straight vertical line
168/// - Otherwise: L-route (horizontal then vertical)
169fn route_wire(start: Point, end: Point) -> Vec<Point> {
170    const EPSILON: f32 = 0.5;
171
172    if (start.y - end.y).abs() < EPSILON {
173        // Same horizontal level: straight line
174        vec![start, end]
175    } else if (start.x - end.x).abs() < EPSILON {
176        // Same vertical level: straight line
177        vec![start, end]
178    } else {
179        // L-route: horizontal first, then vertical
180        let mid = Point::new(end.x, start.y);
181        vec![start, mid, end]
182    }
183}
184
185/// Route a wire with obstacle avoidance. Uses an L-route if the corner is
186/// clear of components, otherwise falls back to a Z-route through the midpoint.
187fn route_wire_with_obstacles(start: Point, end: Point, obstacles: &[(f32, f32)]) -> Vec<Point> {
188    let basic = route_wire(start, end);
189
190    // Only L-routes (3 points) need obstacle checking
191    if basic.len() != 3 {
192        return basic;
193    }
194
195    let corner = &basic[1];
196    let corner_blocked = obstacles.iter().any(|&(ox, oy)| {
197        // Don't count start/end positions as obstacles
198        let is_endpoint = ((ox - start.x).abs() < 1.0 && (oy - start.y).abs() < 1.0)
199            || ((ox - end.x).abs() < 1.0 && (oy - end.y).abs() < 1.0);
200        if is_endpoint {
201            return false;
202        }
203        let dx = corner.x - ox;
204        let dy = corner.y - oy;
205        (dx * dx + dy * dy).sqrt() < OBSTACLE_RADIUS
206    });
207
208    if corner_blocked {
209        // Z-route through the midpoint X
210        let mid_x = (start.x + end.x) / 2.0;
211        route_wire_z(start, end, mid_x)
212    } else {
213        basic
214    }
215}
216
217/// Route a wire with a Z-route (horizontal, vertical jog, horizontal) to
218/// avoid obstacles. Used when an L-route would cross a component.
219fn route_wire_z(start: Point, end: Point, jog_x: f32) -> Vec<Point> {
220    vec![
221        start,
222        Point::new(jog_x, start.y),
223        Point::new(jog_x, end.y),
224        end,
225    ]
226}
227
228/// Route a feedback wire below the signal path.
229fn route_wire_feedback(start: Point, end: Point, bottom_y: f32) -> Vec<Point> {
230    vec![
231        start,
232        Point::new(start.x, bottom_y),
233        Point::new(end.x, bottom_y),
234        end,
235    ]
236}
237
238#[cfg(test)]
239mod tests {
240    use super::*;
241
242    #[test]
243    fn straight_horizontal() {
244        let pts = route_wire(Point::new(0.0, 100.0), Point::new(200.0, 100.0));
245        assert_eq!(pts.len(), 2);
246    }
247
248    #[test]
249    fn straight_vertical() {
250        let pts = route_wire(Point::new(100.0, 0.0), Point::new(100.0, 200.0));
251        assert_eq!(pts.len(), 2);
252    }
253
254    #[test]
255    fn l_route() {
256        let pts = route_wire(Point::new(0.0, 0.0), Point::new(200.0, 100.0));
257        assert_eq!(pts.len(), 3);
258        assert_eq!(pts[1].x, 200.0);
259        assert_eq!(pts[1].y, 0.0);
260    }
261}
pedalkernel_layout/routing.rs

pedalkernel_layout/
routing.rs
