Package com.kraken.api.service.pathfinding

Class LocalPathfinder

  • @Singleton
public class LocalPathfinder
extends java.lang.Object

    The LocalPathfinder class is responsible for pathfinding within a local 104x104 tile 3D game scene. It provides methods to compute paths using Breadth First Search (BFS), determine sparse paths for waypoints where directional changes occur, render paths visually, and validate the reachability of points within the currently loaded scene. This class is useful for AI, navigation, and player movement scenarios.

    The class supports the following functionalities:

    • Constructor Summary

      Constructors 
      Constructor Description
      LocalPathfinder()  

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      java.util.List<net.runelite.api.coords.WorldPoint> findApproximatePath​(net.runelite.api.coords.WorldPoint start, net.runelite.api.coords.WorldArea area)
      Finds an approximate path to a random reachable tile within a specified WorldArea.
      java.util.List<net.runelite.api.coords.WorldPoint> findApproximatePath​(net.runelite.api.coords.WorldPoint start, net.runelite.api.coords.WorldPoint target)
      Finds an approximate path to a random reachable tile within a default radius of 5 tiles around the target location.
      java.util.List<net.runelite.api.coords.WorldPoint> findApproximatePath​(net.runelite.api.coords.WorldPoint start, net.runelite.api.coords.WorldPoint target, int radius)
      Finds an approximate path to a random reachable tile within a specified radius around the target location.
      java.util.List<net.runelite.api.coords.WorldPoint> findApproximatePathWithBackoff​(net.runelite.api.coords.WorldPoint start, net.runelite.api.coords.WorldPoint target, int radius)
      Attempts to find a path to a reachable tile within a specified radius of the target.
      net.runelite.api.coords.WorldPoint findEdgeOfScene​(net.runelite.api.coords.WorldPoint target)  
      java.util.List<net.runelite.api.coords.WorldPoint> findPath​(net.runelite.api.coords.WorldPoint start, net.runelite.api.coords.WorldPoint target)
      Calculates and returns a path from a starting point to a target point within the game world.
      java.util.List<net.runelite.api.coords.WorldPoint> findPathWithBackoff​(net.runelite.api.coords.WorldPoint start, net.runelite.api.coords.WorldPoint target)
      Attempts to find a path to the target.
      java.util.List<net.runelite.api.coords.WorldPoint> findSparsePath​(net.runelite.api.coords.WorldPoint start, net.runelite.api.coords.WorldPoint target)
      Finds a sparse path between a starting point and a target point by filtering out unnecessary intermediate points from a previously computed dense path.
      java.util.List<net.runelite.api.Tile> findWaypointsTo​(net.runelite.api.Tile from, net.runelite.api.Tile to)
      Finds the waypoints needed to navigate from the starting Tile to the destination Tile.
      java.util.List<net.runelite.api.coords.WorldPoint> randomizeSparsePath​(net.runelite.api.coords.WorldPoint start, java.util.List<net.runelite.api.coords.WorldPoint> sparsePath, int maxOffset)
      Convenience overload that keeps endpoints and uses a default attempt count.
      java.util.List<net.runelite.api.coords.WorldPoint> randomizeSparsePath​(net.runelite.api.coords.WorldPoint start, java.util.List<net.runelite.api.coords.WorldPoint> sparsePath, int maxOffset, int attemptsPerPoint, boolean keepEndpoints)
      Creates a randomized variation of a sparse path by slightly offsetting waypoints while ensuring each candidate waypoint is still reachable.
      java.util.List<net.runelite.api.coords.WorldPoint> reachableTiles​(net.runelite.api.coords.WorldPoint origin)
      Returns a list of all reachable tiles from the origins position using a breadth-first search algorithm.
      void renderMinimapPath​(java.util.List<net.runelite.api.coords.WorldPoint> path, java.awt.Graphics2D graphics, java.awt.Color color)
      Renders a path on the minimap.
      void renderPath​(java.util.List<net.runelite.api.coords.WorldPoint> path, java.awt.Graphics2D graphics, java.awt.Color pathColor)
      Renders a series of tiles representing a path on the game canvas.

      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    • Constructor Detail

      • LocalPathfinder

        public LocalPathfinder()

    • Method Detail

      • findSparsePath

        public java.util.List<net.runelite.api.coords.WorldPoint> findSparsePath​(net.runelite.api.coords.WorldPoint start,
                                                                         net.runelite.api.coords.WorldPoint target)
        Finds a sparse path between a starting point and a target point by filtering out unnecessary intermediate points from a previously computed dense path.

        The method calculates directional changes in the dense path and retains only the waypoints where the direction changes, along with the final destination. This ensures a simplified path that accurately represents the required turns or path changes while omitting redundant points.

        Parameters:
        start - @WorldPoint representing the starting location of the path.
        target - @WorldPoint representing the destination point of the path.
        Returns:
        A @List of @WorldPoint objects representing the sparse path. Returns an empty list if no path can be computed.

      • randomizeSparsePath

        public java.util.List<net.runelite.api.coords.WorldPoint> randomizeSparsePath​(net.runelite.api.coords.WorldPoint start,
                                                                              java.util.List<net.runelite.api.coords.WorldPoint> sparsePath,
                                                                              int maxOffset,
                                                                              int attemptsPerPoint,
                                                                              boolean keepEndpoints)
        Creates a randomized variation of a sparse path by slightly offsetting waypoints while ensuring each candidate waypoint is still reachable.

        The method samples up to attemptsPerPoint random offsets per waypoint within maxOffset tiles. A candidate is accepted only if it is present in the set of reachable tiles from the selected origin (the start for the first waypoint when provided, otherwise the original waypoint). If no candidate is valid, the original waypoint is kept.

        Parameters:
        start - The starting point for the path. Used as the reachability origin for the first waypoint when provided.
        sparsePath - The sparse path to randomize.
        maxOffset - The maximum offset (in tiles) to apply to a waypoint in any direction.
        attemptsPerPoint - The number of random candidates to try per waypoint.
        keepEndpoints - Whether to keep the first and last waypoint unchanged.
        Returns:
        A new list of WorldPoints representing the randomized sparse path.

      • randomizeSparsePath

        public java.util.List<net.runelite.api.coords.WorldPoint> randomizeSparsePath​(net.runelite.api.coords.WorldPoint start,
                                                                              java.util.List<net.runelite.api.coords.WorldPoint> sparsePath,
                                                                              int maxOffset)
        Convenience overload that keeps endpoints and uses a default attempt count.
        Parameters:
        start - The starting point for the path.
        sparsePath - The sparse path to randomize.
        maxOffset - The maximum offset (in tiles) to apply to a waypoint in any direction.
        Returns:
        A new list of WorldPoints representing the randomized sparse path.

      • findPath

        public java.util.List<net.runelite.api.coords.WorldPoint> findPath​(net.runelite.api.coords.WorldPoint start,
                                                                   net.runelite.api.coords.WorldPoint target)
        Calculates and returns a path from a starting point to a target point within the game world. If the target point is outside the scene, the method attempts to determine the edge of the scene closest to the target and calculates a path to that edge instead.

        If the target point is within the loaded scene, the method directly computes the path to the target using the findScenePath method. If the target is outside the scene, it finds the nearest edge point to the target and calculates a path to that point.

        Parameters:
        start - @WorldPoint representing the starting location of the path.
        target - @WorldPoint representing the destination point of the path.
        Returns:
        A @List of @WorldPoint objects representing the calculated path from the start to the target (or closest reachable edge point). If no path can be calculated, an empty list is returned.

      • findPathWithBackoff

        public java.util.List<net.runelite.api.coords.WorldPoint> findPathWithBackoff​(net.runelite.api.coords.WorldPoint start,
                                                                              net.runelite.api.coords.WorldPoint target)
        Attempts to find a path to the target. If the target is unreachable, it attempts to find a path to a tile closer to the start point by "backing off" from the target in an exponential/incremental fashion.

        The backoff strategy works by calculating points along the line between the target and the start. It steps back by 1 tile, then 3, then 6, then 10, etc., until a reachable path is found or the search backs up all the way to the start.

        Parameters:
        start - The starting WorldPoint.
        target - The desired target WorldPoint.
        Returns:
        A List of WorldPoints representing the path to the target or the best approximate location found. Returns an empty list if no path can be found.

      • findApproximatePathWithBackoff

        public java.util.List<net.runelite.api.coords.WorldPoint> findApproximatePathWithBackoff​(net.runelite.api.coords.WorldPoint start,
                                                                                         net.runelite.api.coords.WorldPoint target,
                                                                                         int radius)
        Attempts to find a path to a reachable tile within a specified radius of the target. If no reachable tiles are found near the target, it linearly "backs off" from the target towards the start point and searches for reachable tiles near those intermediate points.

        This strategy is useful for getting as close as possible to a destination that might be completely unreachable (e.g., inside a wall or on an island), by finding the closest valid cluster of tiles along the path.

        Parameters:
        start - The starting WorldPoint.
        target - The target WorldPoint.
        radius - The radius (Chebyshev distance) to search for reachable tiles around the target/backoff points.
        Returns:
        A list of WorldPoints representing the path to the best found location, or an empty list if none found.

      • findApproximatePath

        public java.util.List<net.runelite.api.coords.WorldPoint> findApproximatePath​(net.runelite.api.coords.WorldPoint start,
                                                                              net.runelite.api.coords.WorldPoint target)
        Finds an approximate path to a random reachable tile within a default radius of 5 tiles around the target location.
        Parameters:
        start - The starting WorldPoint.
        target - The target WorldPoint.
        Returns:
        A list of WorldPoints representing the path to the approximate target.

      • findApproximatePath

        public java.util.List<net.runelite.api.coords.WorldPoint> findApproximatePath​(net.runelite.api.coords.WorldPoint start,
                                                                              net.runelite.api.coords.WorldPoint target,
                                                                              int radius)
        Finds an approximate path to a random reachable tile within a specified radius around the target location.

        This method first calculates all reachable tiles from the start point using BFS. It then filters these tiles to find ones that lie within the specified square radius (Chebyshev distance) of the target point. Finally, it selects one of these candidates at random and computes a path to it.

        Parameters:
        start - The starting WorldPoint.
        target - The target WorldPoint.
        radius - The radius (in tiles) around the target to search for reachable tiles.
        Returns:
        A list of WorldPoints representing the path to the approximate target.

      • findApproximatePath

        public java.util.List<net.runelite.api.coords.WorldPoint> findApproximatePath​(net.runelite.api.coords.WorldPoint start,
                                                                              net.runelite.api.coords.WorldArea area)
        Finds an approximate path to a random reachable tile within a specified WorldArea.
        Parameters:
        start - The starting WorldPoint.
        area - The WorldArea to search for reachable tiles within.
        Returns:
        A list of WorldPoints representing the path to a random point within the area.

      • reachableTiles

        public java.util.List<net.runelite.api.coords.WorldPoint> reachableTiles​(net.runelite.api.coords.WorldPoint origin)
        Returns a list of all reachable tiles from the origins position using a breadth-first search algorithm. This method considers the collision data to determine which tiles can be reached.
        Parameters:
        origin - The point to query from
        Returns:
        A list of WorldPoint objects representing all reachable tiles from the origin.

      • findEdgeOfScene

        public net.runelite.api.coords.WorldPoint findEdgeOfScene​(net.runelite.api.coords.WorldPoint target)

      • findWaypointsTo

        public java.util.List<net.runelite.api.Tile> findWaypointsTo​(net.runelite.api.Tile from,
                                                             net.runelite.api.Tile to)
        Finds the waypoints needed to navigate from the starting Tile to the destination Tile. This method calculates a path using directional and distance matrices, while considering collision data within the game world. If a direct path is not possible, it searches for the closest accessible tile around the destination.

        Note that both the starting and destination tiles must reside on the same plane (z-coordinate). If they are not, this method will return null.

        Credit to Vitalite and TonicBox for this methods implementation. It was taken from their scene API: Link
        Parameters:
        from - the starting Tile from which the path needs to be calculated.
        to - the destination Tile to which the path needs to lead.
        Returns:
        a List of Tile objects representing the calculated waypoints to the destination, or null if the path cannot be calculated (e.g., due to inaccessible areas or mismatched planes).

      • renderMinimapPath

        public void renderMinimapPath​(java.util.List<net.runelite.api.coords.WorldPoint> path,
                              java.awt.Graphics2D graphics,
                              java.awt.Color color)
        Renders a path on the minimap.
        Parameters:
        path - The list of WorldPoints representing the path.
        graphics - The graphics context to draw on.
        color - The color to use for drawing the path.

      • renderPath

        public void renderPath​(java.util.List<net.runelite.api.coords.WorldPoint> path,
                       java.awt.Graphics2D graphics,
                       java.awt.Color pathColor)
        Renders a series of tiles representing a path on the game canvas. This includes drawing connected lines between the tiles and optionally highlighting the last tile in the path.

        The method uses the provided Graphics2D instance to draw on the screen and a Color to style the tiles.

        Parameters:
        path - The list of WorldPoint objects representing the path. Each point is rendered on the game canvas.
        graphics - The Graphics2D instance used to render the path on the screen.
        pathColor - The Color used to draw the tiles on the path. The last tile is highlighted in red with partial transparency.