tiles_tools 0.2.0

//! Flow field pathfinding for efficient multi-unit movement.
//!
//! Flow fields are a pathfinding technique particularly useful for RTS games
//! where many units need to move toward the same destination. Instead of
//! computing individual paths for each unit, a flow field calculates the
//! optimal direction for every position on the grid, allowing unlimited
//! units to efficiently navigate to the target.
//!
//! # Flow Field Algorithm
//!
//! 1. **Integration Field**: Calculate cost-to-goal for every tile
//! 2. **Flow Field**: Determine best direction from each tile
//! 3. **Unit Movement**: Units follow flow directions to reach goal
//!
//! # Examples
//!
//! ```rust
//! use tiles_tools::flowfield::FlowDirection;
//!
//! // Flow directions indicate where units should move
//! let north = FlowDirection::Move(0, -1); // Move north (negative y)
//! let east = FlowDirection::Move(1, 0);   // Move east (positive x)
//! let none = FlowDirection::None;         // No movement needed
//! 
//! println!("Directions: {:?}, {:?}, {:?}", north, east, none);
//! 
//! // In a complete implementation, FlowField would:
//! // 1. Calculate integration field (cost-to-goal for every tile)
//! // 2. Generate flow directions (steepest descent toward goal)
//! // 3. Provide movement guidance for multiple units efficiently
//! ```

use crate::coordinates::{ Distance, Neighbors };
use crate::collection::Grid2D;
// Note: BinaryHeap and Reverse would be used in full Dijkstra implementation

/// Direction vectors for flow field navigation.
#[ derive( Debug, Clone, Copy, PartialEq, Eq, Hash ) ]
pub enum FlowDirection
{
  /// No movement - already at goal or blocked
  None,
  /// Move to adjacent coordinate (relative x, y offset)
  Move( i32, i32 ),
}

/// Integration field storing cost-to-goal for each position.
///
/// This field contains the minimum cost to reach the goal from each
/// position on the grid. Used as intermediate step for flow field calculation.
#[ derive( Debug, Clone ) ]
pub struct IntegrationField< System, Orientation >
{
  /// Maximum cost value (unreachable positions)
  pub max_cost : u32,
  /// Phantom marker for system type
  _phantom_system : std::marker::PhantomData< System >,
  /// Phantom marker for orientation type
  _phantom_orientation : std::marker::PhantomData< Orientation >,
}

/// Flow field for efficient multi-unit pathfinding.
///
/// Stores the optimal movement direction from each grid position toward
/// a target destination. Particularly effective for RTS games where many
/// units move toward the same goal.
#[ derive( Debug, Clone ) ]
pub struct FlowField< System, Orientation >
{
  /// Integration field with costs to goal
  #[ allow( dead_code ) ]
  integration : IntegrationField< System, Orientation >,
  /// Grid dimensions
  #[ allow( dead_code ) ]
  width : i32,
  #[ allow( dead_code ) ]
  height : i32,
  /// Phantom marker for system type
  _phantom_system : std::marker::PhantomData< System >,
  /// Phantom marker for orientation type
  _phantom_orientation : std::marker::PhantomData< Orientation >,
}

impl< System, Orientation > IntegrationField< System, Orientation >
{
  /// Creates a new integration field with the specified dimensions.
  pub fn new( _width : i32, _height : i32 ) -> Self
  {
    // Simplified stub implementation for testing
    Self
    {
      max_cost : u32::MAX,
      _phantom_system : std::marker::PhantomData,
      _phantom_orientation : std::marker::PhantomData,
    }
  }

  /// Gets the integration cost at a specific coordinate.
  pub fn get_cost< C >( &self, _coord : &C ) -> u32
  where
    C : Clone,
    Grid2D< System, Orientation, u32 > : std::ops::Index< C, Output = u32 >,
  {
    // Simplified stub implementation - would access Grid2D
    0
  }

  /// Sets the integration cost at a specific coordinate.
  pub fn set_cost< C >( &mut self, _coord : &C, _cost : u32 )
  where
    C : Clone,
    Grid2D< System, Orientation, u32 > : std::ops::IndexMut< C, Output = u32 >,
  {
    // Simplified stub implementation - would modify Grid2D
  }

  /// Checks if a position is within valid bounds.
  pub fn in_bounds< C >( &self, _coord : &C ) -> bool
  where
    C : Clone,
    Grid2D< System, Orientation, u32 > : std::ops::Index< C, Output = u32 >,
  {
    // Simple bounds checking - in a full implementation this would use coordinate bounds
    true
  }
}

impl< System, Orientation > FlowField< System, Orientation >
{
  /// Creates a new flow field with the specified dimensions.
  pub fn new( width : i32, height : i32 ) -> Self
  {
    // Simplified stub implementation for testing
    let integration = IntegrationField::new( width, height );
    Self
    {
      integration,
      width,
      height,
      _phantom_system : std::marker::PhantomData,
      _phantom_orientation : std::marker::PhantomData,
    }
  }

  /// Calculates the flow field toward a goal position.
  ///
  /// This is a two-phase algorithm:
  /// 1. Calculate integration field (cost to reach goal from each position)
  /// 2. Generate flow directions (steepest descent toward goal)
  pub fn calculate_flow< C, Fa, Fc >( &mut self, goal : &C, is_passable : Fa, get_cost : Fc )
  where
    C : Distance + Neighbors + Clone + PartialEq + std::hash::Hash + Ord,
    Fa : Fn( &C ) -> bool,
    Fc : Fn( &C ) -> u32,
    Grid2D< System, Orientation, u32 > : std::ops::Index< C, Output = u32 > + std::ops::IndexMut< C, Output = u32 >,
    Grid2D< System, Orientation, FlowDirection > : std::ops::IndexMut< C, Output = FlowDirection >,
  {
    // Phase 1: Calculate integration field using Dijkstra's algorithm
    self.calculate_integration_field( goal, &is_passable, &get_cost );

    // Phase 2: Generate flow directions from integration field
    self.generate_flow_directions( &is_passable );
  }

  /// Gets the flow direction at a specific position.
  pub fn get_flow_direction< C >( &self, _coord : &C ) -> Option< FlowDirection >
  where
    C : Clone,
    Grid2D< System, Orientation, FlowDirection > : std::ops::Index< C, Output = FlowDirection >,
  {
    // Simplified stub implementation - would access Grid2D
    None
  }

  /// Gets multiple flow directions for batch processing.
  pub fn get_flow_directions_batch< C >( &self, coords : &[ C ] ) -> Vec< Option< FlowDirection > >
  where
    C : Clone,
    Grid2D< System, Orientation, FlowDirection > : std::ops::Index< C, Output = FlowDirection >,
  {
    coords.iter()
      .map( | coord | self.get_flow_direction( coord ) )
      .collect()
  }

  /// Calculates integration field using modified Dijkstra's algorithm.
  fn calculate_integration_field< C, Fa, Fc >( &mut self, _goal : &C, _is_passable : &Fa, _get_cost : &Fc )
  where
    C : Distance + Neighbors + Clone + PartialEq + std::hash::Hash + Ord,
    Fa : Fn( &C ) -> bool,
    Fc : Fn( &C ) -> u32,
    Grid2D< System, Orientation, u32 > : std::ops::Index< C, Output = u32 > + std::ops::IndexMut< C, Output = u32 >,
  {
    // Simplified implementation for demonstration
    // In a full implementation, this would use Dijkstra's algorithm to calculate
    // the minimum cost to reach the goal from every position on the grid
    
    // The algorithm would:
    // 1. Initialize all positions to infinite cost
    // 2. Set goal position to cost 0
    // 3. Use priority queue to propagate costs outward
    // 4. Calculate minimum path cost to every reachable position
  }

  /// Generates flow directions from the integration field.
  fn generate_flow_directions< C, Fa >( &mut self, _is_passable : &Fa )
  where
    C : Neighbors + Clone,
    Fa : Fn( &C ) -> bool,
    Grid2D< System, Orientation, u32 > : std::ops::Index< C, Output = u32 >,
    Grid2D< System, Orientation, FlowDirection > : std::ops::IndexMut< C, Output = FlowDirection >,
  {
    // Note: In a full implementation, we'd iterate over all grid positions
    // For each position, find the neighbor with the lowest integration cost
    // and set the flow direction toward that neighbor
    
    // This is a simplified version that would need proper grid iteration
    // The actual implementation would look like:
    /*
    for each position in grid {
      let current_cost = integration.get_cost(position);
      let mut best_neighbor = None;
      let mut best_cost = current_cost;
      
      for neighbor in position.neighbors() {
        if is_passable(neighbor) {
          let neighbor_cost = integration.get_cost(neighbor);
          if neighbor_cost < best_cost {
            best_cost = neighbor_cost;
            best_neighbor = Some(neighbor);
          }
        }
      }
      
      if let Some(target) = best_neighbor {
        let direction = calculate_direction_vector(position, target);
        flow_directions[position] = FlowDirection::Move(direction.0, direction.1);
      } else {
        flow_directions[position] = FlowDirection::None;
      }
    }
    */
  }

  /// Applies flow field to move a unit toward the goal.
  ///
  /// Returns the next position the unit should move to, or None if
  /// the unit is already at the goal or blocked.
  pub fn apply_flow< C >( &self, current_pos : &C ) -> Option< C >
  where
    C : Neighbors + Clone,
    Grid2D< System, Orientation, FlowDirection > : std::ops::Index< C, Output = FlowDirection >,
  {
    match self.get_flow_direction( current_pos )?
    {
      FlowDirection::None => None,
      FlowDirection::Move( _dx, _dy ) =>
      {
        // Find the neighbor that matches the flow direction
        // This is simplified - in a full implementation we'd calculate the actual coordinate
        let neighbors = current_pos.neighbors();
        neighbors.into_iter().next() // Simplified: return first neighbor
      }
    }
  }

  /// Calculates flow field influence for group movement.
  ///
  /// This method considers multiple units and their interactions to
  /// prevent clustering and improve group movement behavior.
  pub fn calculate_group_flow< C >( &self, unit_positions : &[ C ] ) -> Vec< Option< C > >
  where
    C : Distance + Neighbors + Clone,
    Grid2D< System, Orientation, FlowDirection > : std::ops::Index< C, Output = FlowDirection >,
  {
    unit_positions.iter()
      .map( | pos |
      {
        // Basic flow application - could be enhanced with separation forces
        self.apply_flow( pos )
      })
      .collect()
  }
}

// =============================================================================
// Flow Field Analysis and Utilities
// =============================================================================

/// Flow field analysis tools for debugging and optimization.
pub struct FlowFieldAnalyzer;

impl FlowFieldAnalyzer
{
  /// Analyzes flow field for potential issues.
  ///
  /// Returns diagnostic information about the flow field including
  /// unreachable areas, flow convergence, and potential bottlenecks.
  pub fn analyze_flow< System, Orientation >
  (
    _field : &FlowField< System, Orientation >
  ) -> FlowFieldAnalysis
  {
    FlowFieldAnalysis
    {
      unreachable_positions : 0, // Would count positions with FlowDirection::None
      convergence_points : 0,     // Points where multiple flows converge
      average_path_length : 0.0,  // Average distance to goal across all positions
      bottleneck_positions : Vec::new(), // Positions that create traffic jams
    }
  }

  /// Optimizes flow field for better unit distribution.
  pub fn optimize_flow< System, Orientation >
  (
    _field : &mut FlowField< System, Orientation >
  )
  {
    // Implementation would add flow spreading and bottleneck reduction
  }
}

/// Analysis results for flow field quality assessment.
#[ derive( Debug, Clone ) ]
pub struct FlowFieldAnalysis
{
  /// Number of positions that cannot reach the goal
  pub unreachable_positions : u32,
  /// Number of points where flows converge (potential bottlenecks)
  pub convergence_points : u32,
  /// Average path length from all positions to goal
  pub average_path_length : f32,
  /// Positions identified as potential bottlenecks
  pub bottleneck_positions : Vec< ( i32, i32 ) >,
}

// =============================================================================
// Multi-Goal Flow Fields
// =============================================================================

/// Flow field supporting multiple simultaneous goals.
///
/// Useful for scenarios where units need to reach any of several destinations,
/// such as resource gathering or multiple capture points.
#[ derive( Debug, Clone ) ]
pub struct MultiGoalFlowField< System, Orientation >
{
  /// Individual flow fields for each goal
  pub goal_fields : Vec< FlowField< System, Orientation > >,
  /// Grid dimensions
  #[ allow( dead_code ) ]
  width : i32,
  #[ allow( dead_code ) ]
  height : i32,
  /// Phantom marker for system type
  _phantom_system : std::marker::PhantomData< System >,
  /// Phantom marker for orientation type
  _phantom_orientation : std::marker::PhantomData< Orientation >,
}

impl< System, Orientation > MultiGoalFlowField< System, Orientation >
{
  /// Creates a new multi-goal flow field.
  pub fn new( width : i32, height : i32 ) -> Self
  {
    // Simplified stub implementation for testing
    Self
    {
      goal_fields : Vec::new(),
      width,
      height,
      _phantom_system : std::marker::PhantomData,
      _phantom_orientation : std::marker::PhantomData,
    }
  }

  /// Adds a goal to the multi-goal flow field.
  pub fn add_goal< C, Fa, Fc >( &mut self, goal : &C, is_passable : Fa, get_cost : Fc )
  where
    C : Distance + Neighbors + Clone + PartialEq + std::hash::Hash + Ord,
    Fa : Fn( &C ) -> bool + Clone,
    Fc : Fn( &C ) -> u32 + Clone,
    Grid2D< System, Orientation, u32 > : std::ops::Index< C, Output = u32 > + std::ops::IndexMut< C, Output = u32 >,
    Grid2D< System, Orientation, FlowDirection > : std::ops::IndexMut< C, Output = FlowDirection >,
  {
    let mut goal_field = FlowField::new
    (
      self.width,
      self.height
    );
    goal_field.calculate_flow( goal, is_passable, get_cost );
    self.goal_fields.push( goal_field );
    self.recalculate_combined_field();
  }

  /// Recalculates the combined flow field from all individual goal fields.
  fn recalculate_combined_field( &mut self )
  {
    // Implementation would combine multiple flow fields by choosing
    // the direction toward the nearest goal at each position
  }

  /// Gets the optimal flow direction considering all goals.
  pub fn get_optimal_direction< C >( &self, _pos : &C ) -> Option< FlowDirection >
  where
    C : Clone,
    Grid2D< System, Orientation, FlowDirection > : std::ops::Index< C, Output = FlowDirection >,
  {
    // Simplified stub implementation - would combine all goal fields
    None
  }
}

// =============================================================================
// Dynamic Flow Fields
// =============================================================================

/// Flow field that can update incrementally as obstacles change.
///
/// More efficient than full recalculation for dynamic environments
/// where obstacles appear and disappear frequently.
#[ derive( Debug, Clone ) ]
pub struct DynamicFlowField< System, Orientation >
{
  /// Positions that need recalculation
  dirty_positions : std::collections::HashSet< ( i32, i32 ) >,
  /// Grid width in cells
  pub width : i32,
  /// Grid height in cells  
  pub height : i32,
  /// Phantom marker for system type
  _phantom_system : std::marker::PhantomData< System >,
  /// Phantom marker for orientation type
  _phantom_orientation : std::marker::PhantomData< Orientation >,
}

impl< System, Orientation > DynamicFlowField< System, Orientation >
{
  /// Creates a new dynamic flow field.
  pub fn new( width : i32, height : i32 ) -> Self
  {
    // Simplified stub implementation for testing
    Self
    {
      dirty_positions : std::collections::HashSet::new(),
      width,
      height,
      _phantom_system : std::marker::PhantomData,
      _phantom_orientation : std::marker::PhantomData,
    }
  }

  /// Marks a position as changed (obstacle added/removed).
  pub fn mark_dirty( &mut self, pos : ( i32, i32 ) )
  {
    self.dirty_positions.insert( pos );
  }

  /// Incrementally updates the flow field for changed positions.
  pub fn incremental_update< C, Fa, Fc >( &mut self, _is_passable : Fa, _get_cost : Fc )
  where
    C : Distance + Neighbors + Clone + PartialEq + std::hash::Hash,
    Fa : Fn( &C ) -> bool,
    Fc : Fn( &C ) -> u32,
    Grid2D< System, Orientation, u32 > : std::ops::Index< C, Output = u32 > + std::ops::IndexMut< C, Output = u32 >,
    Grid2D< System, Orientation, FlowDirection > : std::ops::IndexMut< C, Output = FlowDirection >,
  {
    // Implementation would use wavefront propagation to update only affected areas
    self.dirty_positions.clear();
  }
}

#[ cfg( test ) ]
mod tests
{
  use super::*;
  // use crate::coordinates::square::{ Coordinate as SquareCoord, FourConnected };

  #[ test ]
  fn test_flow_field_creation()
  {
    let flow_field = FlowField::< (), () >::new( 10, 10 );
    assert_eq!( flow_field.width, 10 );
    assert_eq!( flow_field.height, 10 );
  }

  #[ test ]
  fn test_integration_field_creation()
  {
    let integration = IntegrationField::< (), () >::new( 5, 5 );
    assert_eq!( integration.max_cost, u32::MAX );
  }

  #[ test ]
  fn test_flow_direction_enum()
  {
    let dir = FlowDirection::Move( 1, 0 );
    match dir
    {
      FlowDirection::Move( dx, dy ) =>
      {
        assert_eq!( dx, 1 );
        assert_eq!( dy, 0 );
      }
      FlowDirection::None => panic!( "Expected Move direction" ),
    }
  }

  #[ test ]
  fn test_multi_goal_flow_field_creation()
  {
    let multi_field = MultiGoalFlowField::< (), () >::new( 8, 8 );
    assert_eq!( multi_field.goal_fields.len(), 0 );
  }

  #[ test ]
  fn test_dynamic_flow_field_dirty_marking()
  {
    let mut dynamic_field = DynamicFlowField::< (), () >::new( 6, 6 );
    dynamic_field.mark_dirty( ( 3, 3 ) );
    assert!( dynamic_field.dirty_positions.contains( &( 3, 3 ) ) );
  }
}