Package eu.iv4xr.framework.extensions.pathfinding

Class SimpleNavGraph

java.lang.Object
eu.iv4xr.framework.extensions.pathfinding.SimpleNavGraph
All Implemented Interfaces:
CanDealWithDynamicObstacle<LineIntersectable>, Navigatable<Integer>
Direct Known Subclasses:
SurfaceNavGraph
public class SimpleNavGraph extends Object implements Navigatable<Integer>, CanDealWithDynamicObstacle<LineIntersectable>
This class is provides an implementation of a navigation graph (an instance of Navigatable) that facilitates pathfinding over a 3D-surface defined by a surface-mesh with obstacles. By 3D surface we mean that it is a surface in a 3D space. An obstacle is an object that can block travel along one or more edges in a navigation graph. It moreover may have a dynamic state (can change at the runtime), which is either blocking, or non-blocking. If we don't have obstacles, that is also fine; we simply don't add any to the graph. For the actual pathfinding over the graph, you can e.g. use AStar that can take an instance of Navigatable to find a path between two nodes in a navigation graph.

This class itself only keeps a navigation graph. In particular, it does not keep the original surface-mesh. Instead, we can convert a given surface-mesh to instance of this navigation graph using the method:

fromMeshFaceAverage(Mesh)
The center of the faces in the surface-mesh will be converted the nodes of this navigation-graph. Two nodes are connected by an edge if the original faces they belong to are adjacent. Travel is assumed to be possible by following such edges.
Author:
Naraenda

  • Field Details

    • vertices

      public ArrayList<Vec3> vertices
      The set of vertices that form the navigation graph. The index of the vertex is its id. So if v = vertices(i), then i is its id, and vertices(i) actually returns the 3D position of the vertex.

    • edges

      public EdgeMap edges
      Describe the connectivity (edges) between the vertices.

    • obstacles

      public ArrayList<Obstacle<LineIntersectable>> obstacles

  • Constructor Details

  • Method Details

    • addObstacle

      public void addObstacle​(LineIntersectable obstacle)
      Add the obstacle to this navgraph. The obstacle is set as non-blocking.
      Specified by:
      addObstacle in interface CanDealWithDynamicObstacle<LineIntersectable>

    • addObstacleInBlockingState

      public void addObstacleInBlockingState​(LineIntersectable obstacle)
      Add the obstacle to this navgraph. The obstacle is set as blocking.

    • removeObstacle

      public void removeObstacle​(LineIntersectable tobeRemoved)
      Specified by:
      removeObstacle in interface CanDealWithDynamicObstacle<LineIntersectable>

    • isBlocking

      public boolean isBlocking​(LineIntersectable obstacle)
      Return the state of this obstacle. True means that it is in the blocking state.
      Specified by:
      isBlocking in interface CanDealWithDynamicObstacle<LineIntersectable>

    • setBlockingState

      public void setBlockingState​(LineIntersectable obstacle, boolean isBlocking)
      Description copied from interface: CanDealWithDynamicObstacle
      Set the the state of this obstacle to blocking or unblocking.
      Specified by:
      setBlockingState in interface CanDealWithDynamicObstacle<LineIntersectable>
      isBlocking - If true then the obstacle will be set to its blocking state, and else non-blocking.

    • getBlockingStatus

      public Boolean getBlockingStatus​(LineIntersectable obstacle)
      Return the status of the given obstacle, if it is marked as blocking (true) or non-blocking (false). Return null of the said obstacle is not known.

    • neighbours

      public Iterable<Integer> neighbours​(Integer id)
      Description copied from interface: Navigatable
      An interable that can be used by pathfinders to explore a node's connections.
      Specified by:
      neighbours in interface Navigatable<Integer>
      Parameters:
      id - the index of the vertex to inspect.
      Returns:
      an iterable of the connected neighbours.

    • position

      public Vec3 position​(int i)

    • heuristic

      public float heuristic​(Integer from, Integer to)
      Heuristic distance between any two vertices. Here it is chosen to be the geometric distance between them.
      Specified by:
      heuristic in interface Navigatable<Integer>
      Parameters:
      from - : the index of the vertex to travel from.
      to - : the index of the vertex to travel to.
      Returns:
      the estimated distance.

    • distance

      public float distance​(Integer from, Integer to)
      The distance between two NEIGHBORING vertices. If the connection is not blocked, it is deined to be their geometric distance, and else +inf.
      Specified by:
      distance in interface Navigatable<Integer>
      Parameters:
      from - : the index of the vertex to travel from.
      to - : the index of the vertex to travel to.
      Returns:
      the measured distance. NaN if nodes are not connected.

    • fromMeshFaceAverage

      public static SimpleNavGraph fromMeshFaceAverage​(Mesh mesh)
      Generates a SimpleNavGraph from a mesh where a vertex in the navigation graph corresponds to the average center of a face in the mesh. This works with any mesh, but only meshes that consist out of convex faces will guarantee to produce a useful result.
      Parameters:
      mesh - a convex mesh.
      Returns:
      a SimpleNavGraph constructed from the given mesh.