Package de.bsommerfeld.pathetic.api.pathing.heuristic

Class LinearHeuristicStrategy

java.lang.Object
de.bsommerfeld.pathetic.api.pathing.heuristic.LinearHeuristicStrategy
All Implemented Interfaces:
IHeuristicStrategy
public class LinearHeuristicStrategy extends Object implements IHeuristicStrategy
A linear heuristic strategy combining multiple distance metrics for pathfinding.

This implementation evaluates nodes using a weighted sum of:

  • Manhattan distance (grid movement)
  • Octile distance (diagonal-aware approximation)
  • Perpendicular deviation from the start-target line
  • Vertical (Y-axis) height difference

All metrics are computed in linear space (not squared), making this heuristic admissible and consistent when weights are properly configured.

Ideal for 3D grid-based environments with diagonal movement and path-straightness penalties.

API Note:
This heuristic strategy operates on floored coordinates to ensure consistent and predictable pathfinding behavior in grid-based environments. The floored coordinates represent the discrete grid cell positions that nodes occupy, which is essential for maintaining the admissibility and consistency of heuristic calculations in traditional pathfinding algorithms. Using floored coordinates prevents fractional grid positions from introducing inaccuracies or inconsistencies in distance calculations that could lead to suboptimal paths or heuristic violations.

While floored coordinates are preferred for grid-based pathfinding to maintain mathematical correctness and performance, there may be scenarios where continuous coordinates provide more accurate path planning. For example, when dealing with environments where nodes can occupy positions between grid cells or when high precision is required for movement within a cell, continuous coordinate handling should be considered. However, in standard 3D grid environments with discrete cell-based navigation, floored coordinates remain the optimal choice for reliable heuristic evaluation.

  • Constructor Details

    • LinearHeuristicStrategy

      public LinearHeuristicStrategy()

  • Method Details

    • calculate

      public double calculate(HeuristicContext context)
      Description copied from interface: IHeuristicStrategy
      Calculates the heuristic value (estimated cost) from the current position to the target.

      This method computes an estimate of the remaining cost to reach the target from the current position. The heuristic should be admissible (never overestimate the actual cost) to ensure optimal pathfinding results.

      Common heuristic functions include:

      • Manhattan distance for grid-based movement
      • Euclidean distance for free movement
      • Octile distance for diagonal movement
      • Combined metrics considering elevation and terrain
      Specified by:
      calculate in interface IHeuristicStrategy
      Parameters:
      context - the context containing information about the current position, target position, and other relevant pathfinding data
      Returns:
      the estimated cost from the current position to the target, must be non-negative
      See Also:

    • calculateTransitionCost

      public double calculateTransitionCost(PathPosition from, PathPosition to)
      Description copied from interface: IHeuristicStrategy
      Calculates the actual transition cost between two adjacent positions.

      This method determines the cost of moving from one position to another. The cost should reflect the actual difficulty or expense of the movement, taking into account factors such as:

      • Distance between positions
      • Terrain difficulty
      • Elevation changes
      • Movement penalties

      The transition cost is used to calculate the G-cost (actual cost from start) in the A* algorithm.

      Specified by:
      calculateTransitionCost in interface IHeuristicStrategy
      Parameters:
      from - the starting position of the movement
      to - the destination position of the movement
      Returns:
      the cost of moving from the 'from' position to the 'to' position, must be positive for valid movements
      See Also: