Package com.inductiveautomation.ignition.designer.blockandconnector.routing

Class AStar<T>

java.lang.Object
com.inductiveautomation.ignition.designer.blockandconnector.routing.AStar<T>
public abstract class AStar<T> extends Object
A* algorithm implementation using the method design pattern.

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    class 
    AStar.Path
     

  • Constructor Summary

    Constructors
    Constructor
    Description
    AStar()
    Default c'tor.

  • Method Summary

    Modifier and Type
    Method
    Description
    List<T>
    compute(T start)
    Find the shortest path to a goal starting from start.
    protected Double
    f(AStar<T>.Path p, T from, T to)
    Total cost function to reach the node to from from.
    protected abstract Double
    g(AStar<T>.Path path, T from, T to)
    Cost for the operation to go to to from from.
    protected abstract List<T>
    generateSuccessors(T node)
    Generate the successors for a given node.
    Double
    getCost()
    Get the cost to reach the last node in the path.
    int
    getExpandedCounter()
    Check how many times a node was expanded.
    protected abstract Double
    h(T from, T to)
    Estimated cost to reach a goal node.
    protected abstract boolean
    isGoal(T node)
    Check if the current node is a goal for the problem.

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • AStar

      public AStar()
      Default c'tor.

  • Method Details

    • isGoal

      protected abstract boolean isGoal(T node)
      Check if the current node is a goal for the problem.
      Parameters:
      node - The node to check.
      Returns:
      true if it is a goal, false otherwise.

    • g

      protected abstract Double g(AStar<T>.Path path, T from, T to)
      Cost for the operation to go to to from from.
      Parameters:
      from - The node we are leaving.
      to - The node we are reaching.
      Returns:
      The cost of the operation.

    • h

      protected abstract Double h(T from, T to)
      Estimated cost to reach a goal node. An admissible heuristic never gives a cost bigger than the real one. from.
      Parameters:
      from - The node we are leaving.
      to - The node we are reaching.
      Returns:
      The estimated cost to reach an object.

    • generateSuccessors

      protected abstract List<T> generateSuccessors(T node)
      Generate the successors for a given node.
      Parameters:
      node - The node we want to expand.
      Returns:
      A list of possible next steps.

    • getExpandedCounter

      public int getExpandedCounter()
      Check how many times a node was expanded.
      Returns:
      A counter of how many times a node was expanded.

    • f

      protected Double f(AStar<T>.Path p, T from, T to)
      Total cost function to reach the node to from from.

      The total cost is defined as: f(x) = g(x) + h(x).

      Parameters:
      from - The node we are leaving.
      to - The node we are reaching.
      Returns:
      The total cost.

    • getCost

      public Double getCost()
      Get the cost to reach the last node in the path.
      Returns:
      The cost for the found path.

    • compute

      public List<T> compute(T start)
      Find the shortest path to a goal starting from start.
      Parameters:
      start - The initial node.
      Returns:
      A list of nodes from the initial point to a goal, null if a path doesn't exist.