Package eu.iv4xr.framework.extensions.pathfinding

Class SurfaceNavGraph

java.lang.Object
eu.iv4xr.framework.extensions.pathfinding.SimpleNavGraph
eu.iv4xr.framework.extensions.pathfinding.SurfaceNavGraph
All Implemented Interfaces:
CanDealWithDynamicObstacle<LineIntersectable>, Navigatable<Integer>, Pathfinder2<Integer>, XPathfinder<Integer>
public class SurfaceNavGraph extends SimpleNavGraph implements XPathfinder<Integer>
A navigation-graph over a 3D-surface. The surface is described by a set of (convex) polygons/Faces. The navigation-graph over this surface is formed by the corners and centers of the Faces. Corners are connected to each other, as they are specified by each Face. Additionally, each corner of a Face f is connected to f's center point. For each two Faces f1 and f2 that are connected (having a common edge), we also connect their center-points.

Note: this class extends SimpleNavGraph, but note that whereas the latter use faces' centers as the nodes, this class uses both the centers and the faces' corners as nodes. So, it can find a path that SimpleNavGraph cannot find when an obstacle only covers the center of a target face, but not all its corners.

This navigation-graph also supports few additional features:

  • (1) It includes a PathFinder to calculate a path from one vertex in the nav-graph to another. By default, an A* PathFinder is used, though you can change that.
  • (2) An option to do memory-based navigation. This option is by default turned-on. Under this navigation mode, all vertices are initially marked as unseen. An agent can then incrementally mark vertices as "seen". Navigation is only possible over the part of the graph that were previously seen.
  • (3) An option to prefer travel through the faces' center points, or to travel along border edges. This is done my increasing the cost/distance of going to unpreferred vertices.
  • (4) This navigation-graph additionally marks vertices which are on the border-edges. A border-edge is an edge that is not shared by multiple Faces. The type of a vertex can asked via verticesType.get(i), which will return the type of vertex i. This returns either BORDER (if i is a border vertex), CENTER (if it is the center of a Face), or OTHER.
Author:
Wish

  • Field Details

    • faces

      public ArrayList<Face> faces
      The convex-polygons/faces that overlay the vertices of this navigation graph. Each Face is defined by corners, which are vertices of this navigation graph. A Face describes a (small) surface that is physically navigatable. This navigation graph itself does not specify how to navigate to an arbitrary point in a Face (except when it is one of its corners), but knowing the surface the user of this class at least infer alternate locations to navigate to. It is up to the user how to use such information.

    • verticesType

      public ArrayList<SurfaceNavGraph.VertexType> verticesType
      verticesType.get(i) specifies the type of vertex i. It is either CENTER, BORDER, or OTHER.

    • seenVertices

      public ArrayList<Boolean> seenVertices
      If seenVertices.get(i) is true it means that vertex i is considered to have been "seen", for the purpose of memory-based navigation.

    • faceToCenterIdMap

      HashMap<Face,​Integer> faceToCenterIdMap
      This maps the Faces to their corresponding center-points. The center-point is represented by their id/index in the vertices array.

    • numberOfBaseVertices

      public int numberOfBaseVertices
      The number of vertices that are corners of the Faces (so, vertices which are not centers). These vertices will also have id between 0 and numberOfBaseVertices-1.

    • PREFER_CENTER

      public static final int PREFER_CENTER
      See Also:
      Constant Field Values

    • PREFER_BORDER

      public static final int PREFER_BORDER
      See Also:
      Constant Field Values

    • NO_PREFERENCE

      public static final int NO_PREFERENCE
      See Also:
      Constant Field Values

    • travelPreferrence

      public int travelPreferrence
      Specify preference when trying to find a path over the nav-graph. When this preference is PREFER_CENTER, we prefer a path that goes through the centers of the faces. This is done by applying penalty to the cost of traversal to non-center vertices. When this preference is PREFER_BORDER, we prefer a path that goes through border-vertices. PREFER_CENTER is the default.

    • faceAreaThresholdToAddCenterNode

      float faceAreaThresholdToAddCenterNode
      A threshold for the minimum area of a face to be considered when adding center points to the navigation graph. Only faces whose area is at least this threshold will have a center-point added as an extra navigation node.

    • pathfinder

      Pathfinder<Integer> pathfinder

    • perfect_memory_pathfinding

      public boolean perfect_memory_pathfinding
      If true, the pathfinder will assume that the whole navgraph has been "seen", so no vertex would count as unreacahble because it is still unseen. This essentially turns off memory-based path finding. The default of this flag is false.

  • Constructor Details

    • SurfaceNavGraph

      public SurfaceNavGraph​(Mesh mesh, float faceAreaThresholdToAddCenterNode)
      Create an intance of SurfaceNavGraph from a given mesh. Note that for each face in the mesh, this constructor will also add the center-point of the face in the created navigation graph. This is done if the face's area is large enough; that is, if it exceeds the threshold faceAreaThresholdToAddCenterNode.

  • Method Details

    • usingPerfectMemoryPathfinding

      public boolean usingPerfectMemoryPathfinding()
      When true then the pathfinder will consider all nodes in the graph to have been seen.
      Specified by:
      usingPerfectMemoryPathfinding in interface XPathfinder<Integer>

    • setPerfectMemoryPathfinding

      public void setPerfectMemoryPathfinding​(Boolean flag)
      When true then the pathfinder will consider all nodes in the graph to have been seen.
      Specified by:
      setPerfectMemoryPathfinding in interface XPathfinder<Integer>

    • wipeOutMemory

      public void wipeOutMemory()
      Mark all vertices as "unseen".
      Specified by:
      wipeOutMemory in interface XPathfinder<Integer>

    • setPathFinder

      public void setPathFinder​(Pathfinder<Integer> pf)

    • markAsSeen

      public void markAsSeen​(Integer v)
      Mark the given vertex as "seen" for the purpose of memory-based navigation. Since Faces' center-points were added artificially (they were not explicitly present in the mesh-data used to build this nav-graph), the agent that calls this method may not check if it also saw center-points. This method will therefore take the heuristic to mark a center-point as seen if one of its non-center neighbor is marked as seen.
      Specified by:
      markAsSeen in interface XPathfinder<Integer>

    • markAsSeen

      public void markAsSeen​(List<Integer> seen)
      Mark the given vertices as "seen".
      Specified by:
      markAsSeen in interface XPathfinder<Integer>

    • markAsSeen

      public void markAsSeen​(int... seen)

    • numberOfSeen

      public int numberOfSeen()

    • hasbeenSeen

      public boolean hasbeenSeen​(Integer nd)
      Description copied from interface: XPathfinder
      Check is the given node is marked as "has been seen".
      Specified by:
      hasbeenSeen in interface XPathfinder<Integer>

    • isBlocked

      boolean isBlocked​(Vec3 x, Vec3 y)
      Check if the line from x to y is blocked by any of the blocking obstacles.

    • getNearestUnblockedVertex

      public Integer getNearestUnblockedVertex​(Vec3 location, float faceDistThreshold)
      This method returns a vertex v in the navgraph which is 'nearest' to the given 3D location, such that the straight line between the location and this vertex v is unobstructed. To find v, the method first searches for a face F, whose distance to the given location is below the threshold faceDistThreshold. Then v is searched among the vertices on this face F. The method returns one with the least distance to the location, where a straight line between them is unobstructed by any of the obstacles. If no such F nor v can be found, the method returns null. The method ignores whether the vertices of F has been seen/explored or not.

    • neighbours

      public Iterable<Integer> neighbours​(Integer id)
      Return the neighboring vertices of id. Only neighbors marked as "seen" will be returned (so as to support the memory-based navigation).
      Specified by:
      neighbours in interface Navigatable<Integer>
      Overrides:
      neighbours in class SimpleNavGraph
      Parameters:
      id - the index of the vertex to inspect.
      Returns:
      an iterable of the connected neighbours.

    • heuristic

      public float heuristic​(Integer from, Integer to)
      Defining the distance between two NEIGHBORING vertices.
      Specified by:
      heuristic in interface Navigatable<Integer>
      Overrides:
      heuristic in class SimpleNavGraph
      Parameters:
      from - : the index of the vertex to travel from.
      to - : the index of the vertex to travel to.
      Returns:
      the estimated distance.

    • findPath

      public ArrayList<Integer> findPath​(Integer start, Integer goal)
      Return a path from the given start-vertex to the goal-vertex. If the goal-vertex is reachable, a path will be returned. A* is used as the default path-finder, which should return the optimal path to get to the goal. The path-finding will be memory-based. That is, only navigation over vertices marked as seen will be possible.
      Specified by:
      findPath in interface Pathfinder2<Integer>

    • findPath

      public ArrayList<Integer> findPath​(Vec3 start, Vec3 goal, float faceDistThreshold)
      The same as the other findPath. This will return a path from a vertex v0 closest to the given start position, to a vertex closest to the given goal location. It is up to the agent to figure out how to get from its own physical start location to the starting vertex, and to get from the goal vertex vn to its actual goal location. The method calculates the start and goal-nodes such that the straight line between them and the corresponding start and goal locations are not blocked by any of the blocking obstacles. The parameter faceDistThreshold is a threshold defining how far the Face F0 on which v0 is from the start location is allowed to be. And similarly how far the face Fn on which vn is, from the goal location is allowed to be.

    • getFrontierVertices

      List<Pair<Integer,​Integer>> getFrontierVertices()
      This returns the set of frontier-vertices. A vertex is a frontier vertex if it is a seen/explored vertex and it has at least one unexplored and unblocked neighbor. The method returns pairs of (v,z) where v is a frontier and z is one of its unexplored and unblocked neighbor.

    • getFrontier

      public List<Integer> getFrontier()
      This returns the set of frontier-vertices. A vertex is a frontier vertex if it is a seen/explored vertex and it has at least one unexplored and unblocked neighbor
      Specified by:
      getFrontier in interface XPathfinder<Integer>

    • explore

      public List<Integer> explore​(Vec3 startLocation, float faceDistThreshold)
      Find a path to an unexplored and unblocked vertex w which is the geometrically 'closest' to the given the given start location. The path starts at the given start-location and ends at that unseen vertex.

      More precisely, we first look an explored vertex v in the vicinity of the given start-location, that can be reached by a straight line from the start location, without being blocked. The w meant above is the closest to this intermediate v. The face F on which this v is located must be of distance at most faceDistThreshold from the start-location.

      If no no such path nor intermediate v can be found, the method returns null.

    • explore

      public List<Integer> explore​(Integer startVertex)
      Find a path to an unseen/unexplored vertex which is the geometrically closest to the given starting vertex. The path starts at the start-vertex and ends at that unseen vertex. If no no such path can be found, the method returns null.

      More precisely, the method looks for a frontier v that is closest to the start vertex, and is reachable from this start vertex. It then constructs a path from the starting vertex to v, and adds an unblocked neighbor w of v to the path. This w exists, by definition of v being a frontier.

      Specified by:
      explore in interface XPathfinder<Integer>

    • explore

      public List<Integer> explore​(Integer startVertex, Integer heuristicVertex)
      Find a path from the start-vertex to an unseen/unexplored vertex which is the geometrically closest to the given heuristic-vertex. The path starts at the start-vertex and ends at that unseen vertex. If no no such path can be found, the method returns null.

      More precisely, the method looks for a frontier v that is closest to the heuristic vertex, and is reachable from the start-vertex. It then constructs a path from the starting vertex to v, and adds an unblocked neighbor w of v to the path. This w exists, by definition of v being a frontier.

      Specified by:
      explore in interface XPathfinder<Integer>

    • explore

      public List<Integer> explore​(Vec3 startLocation, Vec3 targetLocation, float faceDistThreshold, float viewDistance, List<Vec3> excludedVertises)
      This variant of explore will try to find an already seen and reachable vertex w, which is closest to some target location t. This target t is usually a location that which the agent has not seen before. We will be looking for a w which is furthermore as such that t is within a given view-distance (so that when we travel to w then we can see t. w should not be too close to the given start-location either (it should be further than 0.5 distance unit from the start-location). More precisely, we first look for an explored vertex v in the vicinity of the given start-location, that can be reached by a straight line from the start location, without being blocked and this is also the vertex near to the destination we want to be there. The w meant above should be reachable from this intermediate v. The face F on which this v is located must be of distance at most faceDistThreshold from the start-location. If such a v and w can be found, this method returns a path to w (with w itself at the end of the path), else the method returns null. The list of excluded vertices specify which candidates should NOT be considered for v (e.g. because they have been considered earlier).

    • explore

      public List<Integer> explore​(int startVertex, Vec3 targetLocation, float viewDistance, List<Vec3> excludedVertises)
      This variant of explore will try to find an already seen and reachable vertex v, which is closest to some target location t. This target t is usually a location that which the agent has not seen before. We will be looking for a v which is furthermore as such that t is within a given view-distance (so that when we travel to v then we can see t. v should not be too close to the given start-location either (it should be further than 0.5 distance unit from the start-location). If such v can be found, the method returns path to v (including v itself, at the end of the path), else the method returns null. The list of excluded vertices specify which candidates should NOT be considered for v (e.g. because they have been considered earlier).

    • enhancedFindPath

      public ArrayList<Integer> enhancedFindPath​(Vec3 start, Vec3 goal, float faceDistThreshold)
      Similar to the other findPath method, this will search for a path from a vertex v0, close to the start-location, to a vertex v1 close to the given goal location. The nodes v0 and v1 are chosen such that the straight line between them and the corresponding start and goal locations are not blocked by any of the blocking obstacles. If such a path exists, it will be returned, and else null is returned. The other findPath method will always the node closest to the start-location respectively the goal-location as the v0 and v1. Sometimes this does not yield a path, e.g. because v1 is not seen yet. This variant of findPath considers all possible vertices around the start position and the goal position. For example if S and T are the set of vertices around the start p0 and goal-location q, respectively, they are first sorted based on their distance to p0 and q respectively. The S and T will be searched for the first (hence the closest to p0 and q) for which a path exists between them. This path is then returned. The vertices in S and T are determined by first finding faces F and G closest to p0 and q. The vertices are the just the vertices of these faces, respectively. The parameter faceDistThreshold is a threshold defining how far the Face S/T from p0/q is allowed to be.

    • getNearestUnblockedVertices

      public List<Integer> getNearestUnblockedVertices​(Vec3 location, float faceDistThreshold)
      This method search for a Face f that "contains" the given position p. The method then returns the vertices v of this face f, for which the line between p and v is unobstructed by some obstacle. The list is also sorted by the vertices' distance to p. The method ignores whether the vertices of f has been seen/explored or not. To be more precise, the method searches for the first face f that is within some small threshold-distance to p. This is less accurate than searching literally for the containing face, but faster. If no such f can be found, the method returns null.

    • debugCheckNeighbor

      public void debugCheckNeighbor​(Integer i, Integer k)
      For debugging: check if node k is a neighbor of node i.

    • debugCheckPath

      public void debugCheckPath​(Integer i, Integer k)
      For debugging: check if there is a path from node i to node k.

    • debugCheckPath_withAllNodesMadeVisible

      public void debugCheckPath_withAllNodesMadeVisible​(Integer i, Integer k)
      For debugging: check if there is a path from node i to node k, assuming that the whole nav-graph has been seen by the agent.