Package games.stendhal.server.core.pathfinder

Class Pathfinder.TreeNode

java.lang.Object
games.stendhal.server.core.pathfinder.Pathfinder.TreeNode
Enclosing class:
Pathfinder
protected abstract class Pathfinder.TreeNode extends Object
The pathfinder node.

  • Constructor Details

    • TreeNode

      protected TreeNode​(int x, int y)
      The default constructor with positional information.
      Parameters:
      x - the x-position of the node.
      y - the y-position of the node.

  • Method Details

    • getX

      public int getX()
      Return the x-position of the node.
      Returns:
      the x-position of the node.

    • getY

      public int getY()
      Return the y-position of the node.
      Returns:
      the y-position of the node.

    • getParent

      public Pathfinder.TreeNode getParent()
      Return the parent node.
      Returns:
      the parent node.

    • getCost

      protected double getCost()
      The cost of moving to this node.
      Returns:
      movement cost

    • getHeuristic

      public double getHeuristic​(Pathfinder.TreeNode nodeGoal)
      Calculates the heuristic for the move form node1 to node2.

      The right heuristic is very important for A* - a over estimated heuristic will turn A* in to bsf - a under estimated heuristic will turn A* in to Dijkstra's so the manhattan distance seams to be the optimal heuristic here. But it has one disadvantage. It will expand to much. Several nodes will have the same f value It will search the area of the size (abs(startX - goalX) + 1) * (abs(startY - goalY) + 1) So a tie-breaker is needed. 1% square distace seems to work fine. A* will prefer nodes closer to the goal.

      Parameters:
      nodeGoal -
      Returns:
      heuristic value for move

    • isValid

      public boolean isValid()
      Checks if the entity could stand on the position of this node.
      Returns:
      true if the the entity could stand on the position

    • isValid

      public abstract boolean isValid​(int x, int y)
      Checks if the entity could stand on the given by the coordinates.
      Parameters:
      x - coordinate of the position to be checked
      y - coordinate of the position to be checked
      Returns:
      true if the the entity could stand on the position

    • createNode

      public abstract Pathfinder.TreeNode createNode​(int x, int y)
      Create a new TreeNode.
      Parameters:
      x - x coordinate of the created node
      y - y coordinate of the created node
      Returns:
      a TreeNode

    • createChildren

      public void createChildren()
      Creates valid child nodes.

      The child nodes have to be

      • a valid position
      • a f value less than maxDistance (checked against the given node)

    • createNodeID

      protected abstract int createNodeID​(int x, int y)
      Calculates the node id.
      Parameters:
      x - of the node
      y - of the node
      Returns:
      the id of the node

    • isOpen

      public final boolean isOpen()

    • setOpen

      public final void setOpen​(boolean open)

    • equals

      public boolean equals​(Object obj)
      Overrides:
      equals in class Object

    • hashCode

      public int hashCode()
      Overrides:
      hashCode in class Object