deargui-vpl/docs/waypoints.md

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

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<Obstacle> Obstacles;  // Other nodes to avoid
    };
}

2. Routing Strategy Functions

Each routing pattern becomes a dedicated function:

namespace PathFinding
{
    // Strategy functions - each handles one routing pattern
    
    // Same-block routing (output param to input param on same block)
    std::vector<ImVec2> RouteSameBlock(
        const RoutingContext& ctx);
    
    // Z-shape routing (down -> across -> up)
    std::vector<ImVec2> RouteZShape(
        const RoutingContext& ctx,
        float horizontalY);  // Y position for horizontal segment
    
    // U-shape routing (around blocks)
    std::vector<ImVec2> RouteUShape(
        const RoutingContext& ctx,
        bool routeAbove);  // Route above or below blocks
    
    // Horizontal flow routing (side-to-side flow pins)
    std::vector<ImVec2> RouteHorizontalFlow(
        const RoutingContext& ctx);
    
    // Simple L-shape routing (generic fallback)
    std::vector<ImVec2> RouteLShape(
        const RoutingContext& ctx);
    
    // Complex routing around obstacles
    std::vector<ImVec2> RouteAroundObstacles(
        const RoutingContext& ctx,
        bool preferLeft);  // Prefer routing left or right
}

3. Helper Functions

Extract common logic into reusable helpers:

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:

namespace PathFinding
{
    // Main entry point - dispatches to appropriate routing strategy
    std::vector<ImVec2> 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<ImVec2> 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<Obstacle>& 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