# Waypoints Pathfinding Consolidation Plan ## Overview This document outlines the refactoring plan for consolidating `pathfinding.cpp` to improve maintainability, readability, and extensibility. The current `GenerateWaypoints` function is a monolithic 700+ line function with deeply nested conditionals. We will refactor it into a modular system with dedicated routing strategies. ## Current Issues 1. **Monolithic Function**: `GenerateWaypoints` is 700+ lines with deeply nested conditionals 2. **Parameter Proliferation**: 9+ individual parameters make the API hard to use and extend 3. **Code Duplication**: Similar routing logic is repeated in multiple branches 4. **Limited Context**: No access to node type, pin type, or other metadata that could improve routing decisions 5. **Hard to Test**: Large function makes unit testing individual strategies difficult 6. **Hard to Maintain**: Adding new routing cases requires modifying the central function ## Goals 1. **Extract Routing Strategies**: Each routing pattern (Z-shape, U-shape, same-block, horizontal flow, etc.) becomes its own function 2. **Add Context Structure**: Pass `NodeContext` objects instead of individual parameters 3. **Improve Modularity**: Clear separation between routing strategy selection and execution 4. **Better Extensibility**: Easy to add new routing strategies without touching existing code 5. **Maintainability**: Each function has a single, clear responsibility ## Proposed Structure ### 1. Context Structures ```cpp namespace PathFinding { // Pin context - contains all information about a pin struct PinContext { ImVec2 Position; // Pin position ImVec2 Direction; // Flow direction (normalized) PinType Type; // Pin type (flow, parameter, etc.) PinKind Kind; // Input or Output bool IsFlowPin; // Flow control pin (vs parameter) bool IsParameterPin; // Parameter pin (data) }; // Node context - contains all information about a node struct NodeContext { ImVec2 Min; // Top-left corner ImVec2 Max; // Bottom-right corner NodeType Type; // Node type (Blueprint, Parameter, etc.) std::string BlockType; // Block type name (if applicable) bool IsGroup; // Is this a group node? float ZPosition; // Z-order }; // Routing context - complete context for pathfinding struct RoutingContext { PinContext StartPin; // Source pin context PinContext EndPin; // Target pin context NodeContext StartNode; // Source node context NodeContext EndNode; // Target node context float Margin; // Clearance margin std::vector Obstacles; // Other nodes to avoid }; } ``` ### 2. Routing Strategy Functions Each routing pattern becomes a dedicated function: ```cpp namespace PathFinding { // Strategy functions - each handles one routing pattern // Same-block routing (output param to input param on same block) std::vector RouteSameBlock( const RoutingContext& ctx); // Z-shape routing (down -> across -> up) std::vector RouteZShape( const RoutingContext& ctx, float horizontalY); // Y position for horizontal segment // U-shape routing (around blocks) std::vector RouteUShape( const RoutingContext& ctx, bool routeAbove); // Route above or below blocks // Horizontal flow routing (side-to-side flow pins) std::vector RouteHorizontalFlow( const RoutingContext& ctx); // Simple L-shape routing (generic fallback) std::vector RouteLShape( const RoutingContext& ctx); // Complex routing around obstacles std::vector RouteAroundObstacles( const RoutingContext& ctx, bool preferLeft); // Prefer routing left or right } ``` ### 3. Helper Functions Extract common logic into reusable helpers: ```cpp namespace PathFinding { // Strategy selection helpers enum class RoutingStrategy { SameBlock, // Same-block routing ZShape, // Simple Z-shape ZShapeAboveBlock, // Z-shape with horizontal above block ZShapeBelowBlock, // Z-shape with horizontal below block UShapeAbove, // U-shape above blocks UShapeBelow, // U-shape below blocks HorizontalFlow, // Side-to-side flow AroundObstacles, // Complex routing around obstacles LShape, // Simple L-shape fallback Direct // Straight line (no waypoints) }; // Determine which routing strategy to use RoutingStrategy SelectStrategy(const RoutingContext& ctx); // Geometry helpers bool IsSameBlock(const NodeContext& start, const NodeContext& end); bool NodesOverlapX(const NodeContext& start, const NodeContext& end); bool EndIsBelowStart(const RoutingContext& ctx); bool PinIsAtTop(const PinContext& pin, const NodeContext& node); bool PinIsOnLeft(const PinContext& pin, const NodeContext& node); // Clearance calculation helpers float CalculateHorizontalClearanceY( const RoutingContext& ctx, bool aboveBlock); float CalculateVerticalClearanceX( const RoutingContext& ctx, bool leftSide); // Obstacle detection helpers bool HorizontalSegmentIntersectsNode( const NodeContext& node, float y, float x1, float x2); bool SegmentIntersectsObstacles( const ImVec2& p1, const ImVec2& p2, const RoutingContext& ctx); } ``` ### 4. Main Entry Point The new `GenerateWaypoints` becomes a thin dispatcher: ```cpp namespace PathFinding { // Main entry point - dispatches to appropriate routing strategy std::vector GenerateWaypoints(const RoutingContext& ctx) { // Strategy selection auto strategy = SelectStrategy(ctx); // Dispatch to appropriate routing function switch (strategy) { case RoutingStrategy::SameBlock: return RouteSameBlock(ctx); case RoutingStrategy::ZShape: return RouteZShape(ctx, CalculateHorizontalClearanceY(ctx, false)); case RoutingStrategy::ZShapeAboveBlock: return RouteZShape(ctx, CalculateHorizontalClearanceY(ctx, true)); case RoutingStrategy::UShapeAbove: return RouteUShape(ctx, true); case RoutingStrategy::UShapeBelow: return RouteUShape(ctx, false); case RoutingStrategy::HorizontalFlow: return RouteHorizontalFlow(ctx); case RoutingStrategy::AroundObstacles: return RouteAroundObstacles(ctx, DeterminePreferredSide(ctx)); case RoutingStrategy::LShape: return RouteLShape(ctx); case RoutingStrategy::Direct: return {}; // No waypoints needed default: return RouteLShape(ctx); // Fallback } } // Convenience overload for backward compatibility std::vector GenerateWaypoints( const ImVec2& startPos, const ImVec2& endPos, const ImVec2& startDir, const ImVec2& endDir, const ImVec2& startNodeMin, const ImVec2& startNodeMax, const ImVec2& endNodeMin, const ImVec2& endNodeMax, float margin = 10.0f, const std::vector& obstacles = {}) { // Build context from parameters (for backward compatibility) RoutingContext ctx; ctx.StartPin.Position = startPos; ctx.StartPin.Direction = startDir; ctx.EndPin.Position = endPos; ctx.EndPin.Direction = endDir; ctx.StartNode.Min = startNodeMin; ctx.StartNode.Max = startNodeMax; ctx.EndNode.Min = endNodeMin; ctx.EndNode.Max = endNodeMax; ctx.Margin = margin; ctx.Obstacles = obstacles; return GenerateWaypoints(ctx); } } ``` ## Implementation Plan ### Phase 1: Add Context Structures (Low Risk) - [ ] Define `PinContext` structure in `pathfinding.h` - [ ] Define `NodeContext` structure in `pathfinding.h` - [ ] Define `RoutingContext` structure in `pathfinding.h` - [ ] Add `RoutingStrategy` enum in `pathfinding.h` - [ ] Update includes if needed (may need node/pin type definitions) ### Phase 2: Extract Helper Functions (Medium Risk) - [ ] Extract geometry helpers (`IsSameBlock`, `NodesOverlapX`, etc.) - [ ] Extract clearance calculation helpers - [ ] Extract obstacle detection helpers - [ ] Test each helper function independently - [ ] Update existing code to use helpers where possible ### Phase 3: Extract Routing Strategy Functions (High Risk) - [ ] Extract `RouteSameBlock` (lines ~161-200 in current code) - [ ] Extract `RouteZShape` (lines ~213-637 in current code) - [ ] Handle simple Z-shape case - [ ] Handle Z-shape with obstacle routing - [ ] Handle Z-shape above/below block variants - [ ] Extract `RouteUShape` (lines ~641-787 in current code) - [ ] Handle U-shape above blocks - [ ] Handle U-shape below blocks - [ ] Handle side routing variants - [ ] Extract `RouteHorizontalFlow` (lines ~790-847 in current code) - [ ] Extract `RouteLShape` (lines ~848-855 in current code) - [ ] Extract `RouteAroundObstacles` (complex routing logic) - [ ] Test each routing function with existing test cases ### Phase 4: Implement Strategy Selection (Medium Risk) - [ ] Implement `SelectStrategy` function - [ ] Handle same-block detection - [ ] Handle vertical flow (down to up) - [ ] Handle horizontal flow - [ ] Handle generic cases - [ ] Implement main `GenerateWaypoints` dispatcher - [ ] Test strategy selection logic ### Phase 5: Add Enhanced Context Support (Future Enhancement) - [ ] Modify calling code to pass `Node*` and `Pin*` objects instead of just positions - [ ] Populate `PinContext` with actual pin metadata (type, kind, etc.) - [ ] Populate `NodeContext` with actual node metadata (type, block type, etc.) - [ ] Use metadata to make smarter routing decisions - [ ] Example: Use pin type to determine if special routing is needed ### Phase 6: Backward Compatibility & Testing (Low Risk) - [ ] Keep old function signature as convenience overload - [ ] Test all existing call sites still work - [ ] Run regression tests - [ ] Update any documentation ## File Organization ``` pathfinding.h - Context structures (PinContext, NodeContext, RoutingContext) - RoutingStrategy enum - Function declarations pathfinding.cpp - Helper functions - Strategy selection (SelectStrategy) - Routing strategy implementations - Main GenerateWaypoints dispatcher - Backward compatibility overload ``` ## Testing Strategy 1. **Unit Tests for Helpers**: Test each helper function with known inputs 2. **Integration Tests**: Test each routing strategy with sample scenarios 3. **Regression Tests**: Verify existing call sites produce same results 4. **Visual Tests**: Manually verify routing looks correct in the UI ## Benefits 1. **Maintainability**: Each routing strategy is isolated and easy to modify 2. **Testability**: Small functions are easier to unit test 3. **Extensibility**: Adding new routing strategies is straightforward 4. **Readability**: Clear separation of concerns, easier to understand 5. **Context Awareness**: Can make smarter decisions with full node/pin context 6. **Performance**: Potential for optimization within individual strategies ## Migration Notes - Keep old function signature for backward compatibility - Gradually migrate call sites to use context objects - All existing code should continue to work during transition ## Open Questions 1. **Node/Pin Type Dependencies**: Do we need to include full `Node*` and `Pin*` pointers, or just metadata? - Answer: Start with metadata, can add pointers later if needed 2. **Obstacle Collection**: Should obstacles be part of context or passed separately? - Answer: Part of context for consistency 3. **Error Handling**: How should we handle invalid contexts (e.g., invalid bounds)? - Answer: Return empty waypoint list and log warning 4. **Constants**: Should clearance constants stay in namespace or move to context? - Answer: Keep in namespace Constants for now, can be made configurable later