Package ai.path

Class Pathfinding

java.lang.Object
ai.path.Pathfinding
public class Pathfinding extends Object
This class contains currently 2 pathfinding methods: - a-star (A*) - dijkstra
Since:
08.07.2021
Author:
Juyas

  • Constructor Details

    • Pathfinding

      public Pathfinding()

  • Method Details

    • dijkstra

      public static <Position> Optional<ResultPath<Position>> dijkstra(Map<Position> map)
      A flexible implementation of the dijkstra pathfinding algorithm. It uses a finite possibly directional weighted graph structure to find the shortest possible path from a given start node to a given target node. This method will find the global shortest possible path, if there is one, but it might be less efficient for large graphs compared to A* (a-star).
      Type Parameters:
      Position - any class describing a node - untouched by the algorithm - only for the result to make sense
      Parameters:
      map - a map containing a graph of weighted node references
      Returns:
      an optional containing the shortest path if there is one

    • astar

      public static <Position> Optional<ResultPath<Position>> astar(Map<Position> map, BiFunction<Position,Position,Float> hCost)
      A fully modifiable version of the A* (a-star) algorithm. It uses a finite possibly directional weighted graph structure to find the shortest possible path from a given start node to a given target node. This method will not check every possible path, so if the weights are not equally distributed, it may lead to results, that are not the best solution to the problem.
      Type Parameters:
      Position - any class describing a node - untouched by the algorithm - only for the result to make sense
      Parameters:
      map - a map containing a graph of weighted node references
      hCost - the hCost algorithm which should make a guess about how far posA is away from posB. It is required, that the calculation never results in a value less than 0 and it is preferred to be exactly 0 if both positions are identical. If possible, it is usually a good approach to measure the distance between both positions or a value that is proportional to that distance.
      Returns:
      an optional containing the found path if there is one