Struct LineGraph
A graph that describes 3D edges/lines between points. Pathfinding can be done from any location on these edges to any location on another edge. Making it more intuitive for agents that can move smoothly along these edges.
Namespace: AnyPath.Graphs.Line
Assembly: AnyPath.dll
Syntax
public struct LineGraph : IGraph<LineGraphLocation>, IDisposableRemarks
This graph is very similar to AnyPath.Graphs.PlatformerGraph, but in 3D. Note that the words edge and line are used interchangeably throughout the documentation.
Note that this graph does not support Raycast queries to obtain a location. However, you can obtain the closest location on the graph from any point in space by using ClosestLocation(float3, float, int, out LineGraphLocation)
Constructors
LineGraph(IReadOnlyList<float3>, IReadOnlyList<Edge>, IReadOnlyList<Edge>, Allocator, bool, int, int)
Construct a LineGraph from a set of vertices and edge definitions
Declaration
public LineGraph(IReadOnlyList<float3> vertices, IReadOnlyList<LineGraph.Edge> undirectedEdges, IReadOnlyList<LineGraph.Edge> directedEdges, Allocator allocator, bool directedEdgesRaycastable = false, int edgesPerOctant = 16, int maxOctreeDepth = 5)Parameters
| Type | Name | Description |
|---|---|---|
| IReadOnlyList<float3> | vertices | Vertices to use |
| IReadOnlyList<LineGraph.Edge> | undirectedEdges | Indices connecting vertices together in an undirected fashion. Every pair of indices (i, i+1) describes an edge that connectets vertex i and vertex i + 1 in both directions |
| IReadOnlyList<LineGraph.Edge> | directedEdges | Indices connecting vertices together in a directed fashion. Every pair of indices (i, i+1) describes an edge that connectets vertex i to vertex i + 1 |
| Allocator | allocator | Allocator to use |
| bool | directedEdgesRaycastable | If true, directed edges can be returned by a closest edge query. This comes with the caveat that when you start a path from a directed edge and the goal is on the same edge but behind the starting location, a path will be found that goes in the opposite direction of that edge. |
| int | edgesPerOctant | Max edges per octant for the internal octree |
| int | maxOctreeDepth | Max depth of the internal octree for raycast/closest location accellerating. If your graph is very large it may be benificial to increase this value. Finding a good balance is key to having optimal raycast and closest location performance. |
LineGraph(Allocator, bool, int, int, int, int)
Preallocates an empty graph, to be populated later using any of the Populate(IReadOnlyList<float3>, IReadOnlyList<Edge>, IReadOnlyList<Edge>) methods
Declaration
public LineGraph(Allocator allocator, bool directedEdgesQueryable = false, int edgesPerOctant = 16, int maxOctreeDepth = 5, int initialVertexCapacity = 0, int intialEdgeCapacity = 0)Parameters
| Type | Name | Description |
|---|---|---|
| Allocator | allocator | Allocator to use |
| bool | directedEdgesQueryable | If true, directed edges can be returned by a closest/overlap query. This comes with the caveat that when you start a path from a directed edge and the goal is on the same edge but behind the starting location, a path will be found that goes in the opposite direction of that edge. |
| int | edgesPerOctant | Max edges per octant for the internal octree |
| int | maxOctreeDepth | Max depth of the internal octree for raycast/closest location accellerating. If your graph is very large it may be benificial to increase this value. Finding a good balance is key to having optimal raycast and closest location performance. |
| int | initialVertexCapacity | Hint to how many vertices are going to be added later, which can boost performance |
| int | intialEdgeCapacity | Hint to how many edges are going to be added later, which can boost performance |
Properties
DirectedEdgesQueryable
Indicates if a raycast or any overlap query will return directed edges
Declaration
public bool DirectedEdgesQueryable { get; }Property Value
| Type | Description |
|---|---|
| bool |
EdgeCount
Amount of edges (directed+undirected) contained in the graph.
Declaration
public int EdgeCount { get; }Property Value
| Type | Description |
|---|---|
| int |
Edges
Read only access to the edges that make up the graph
Declaration
public NativeArray<LineGraph.Edge>.ReadOnly Edges { get; }Property Value
| Type | Description |
|---|---|
| NativeArray<LineGraph.Edge>.ReadOnly |
Octree
Access to the internal octree of the graph for advanced location queries.
Declaration
public NativeOctree<int> Octree { get; }Property Value
| Type | Description |
|---|---|
| NativeOctree<int> |
Remarks
Warning: do not modify the octree as this will corrupt the state of the graph.
UndirectedEdgeCount
Amount of undirected edges. Undirected edges appear first in the raw Edges array. So any undirected edges start from this index.
Declaration
public int UndirectedEdgeCount { get; }Property Value
| Type | Description |
|---|---|
| int |
Vertices
Read only access to the vertices that make up the graph
Declaration
public NativeArray<float3>.ReadOnly Vertices { get; }Property Value
| Type | Description |
|---|---|
| NativeArray<float3>.ReadOnly |
Methods
ClosestLocation(NearestNeighbourCache, float3, float, ClosestLineLocationPredicate, out LineGraphLocation)
Returns the closest location on the graph from a point, with a custom 'filter' predicate. This predicate can be used for instance to check if there is a clear line of sight between the position and the location that is returned.
Declaration
public bool ClosestLocation(NativeOctree<int>.NearestNeighbourCache cache, float3 position, float maxDistance, ClosestLineLocationPredicate predicate, out LineGraphLocation location)Parameters
| Type | Name | Description |
|---|---|---|
| NativeOctree<int>.NearestNeighbourCache | cache | Re-usable cache for the algorithm. If you need to perform a lot of closest location queries in a row, it is faster to allocate this cache once and re-use it for every query. |
| float3 | position | The center position to search from |
| float | maxDistance | The max search radius. Locations beyond this distance will not be visited. |
| ClosestLineLocationPredicate | predicate | A custom function to determine wether a location is valid as a closest location. If false is returned, the next closest location after that is attempted, and so on. |
| LineGraphLocation | location | Returns the closest location on the graph |
Returns
| Type | Description |
|---|---|
| bool | Wether a location was found within the given radius |
Remarks
This function cannot be used in a burst compiled job context. Use the overload that accepts a Unity.Burst.FunctionPointer<T> instead.
ClosestLocation(NearestNeighbourCache, float3, float, out LineGraphLocation)
Returns the closest location on the graph from a point.
Declaration
public bool ClosestLocation(NativeOctree<int>.NearestNeighbourCache cache, float3 position, float maxDistance, out LineGraphLocation location)Parameters
| Type | Name | Description |
|---|---|---|
| NativeOctree<int>.NearestNeighbourCache | cache | Re-usable cache for the algorithm. If you need to perform a lot of closest location queries in a row, it is faster to allocate this cache once and re-use it for every query. |
| float3 | position | The center position to search from |
| float | maxDistance | The max search radius |
| LineGraphLocation | location | Returns the closest location on the graph |
Returns
| Type | Description |
|---|---|
| bool | Wether a location was found within the given radius |
ClosestLocation(NearestNeighbourCache, float3, float, int, out LineGraphLocation)
Returns the closest location on the graph from a point.
Declaration
public bool ClosestLocation(NativeOctree<int>.NearestNeighbourCache cache, float3 position, float maxDistance, int flagBitMask, out LineGraphLocation location)Parameters
| Type | Name | Description |
|---|---|---|
| NativeOctree<int>.NearestNeighbourCache | cache | Re-usable cache for the algorithm. If you need to perform a lot of closest location queries in a row, it is faster to allocate this cache once and re-use it for every query. |
| float3 | position | The center position to search from |
| float | maxDistance | The max search radius |
| int | flagBitMask | A bitwise AND is performed on the edge candidates and if any bit is true, the edge is considered. |
| LineGraphLocation | location | Returns the closest location on the graph |
Returns
| Type | Description |
|---|---|
| bool | Wether a location was found within the given radius |
ClosestLocation(NearestNeighbourCache, float3, float, FunctionPointer<ClosestLineLocationPredicate>, out LineGraphLocation)
Returns the closest location on the graph from a point, with a custom 'filter' predicate. This predicate can be used for instance to check if there is a clear line of sight between the position and the location that is returned.
Declaration
public bool ClosestLocation(NativeOctree<int>.NearestNeighbourCache cache, float3 position, float maxDistance, FunctionPointer<ClosestLineLocationPredicate> predicate, out LineGraphLocation location)Parameters
| Type | Name | Description |
|---|---|---|
| NativeOctree<int>.NearestNeighbourCache | cache | Re-usable cache for the algorithm. If you need to perform a lot of closest location queries in a row, it is faster to allocate this cache once and re-use it for every query. |
| float3 | position | The center position to search from |
| float | maxDistance | The max search radius. Locations beyond this distance will not be visited. |
| FunctionPointer<ClosestLineLocationPredicate> | predicate | A custom function to determine wether a location is valid as a closest location. If false is returned, the next closest location after that is attempted, and so on. |
| LineGraphLocation | location | Returns the closest location on the graph |
Returns
| Type | Description |
|---|---|
| bool | Wether a location was found within the given radius |
ClosestLocation(float3, float, ClosestLineLocationPredicate, out LineGraphLocation)
Returns the closest location on the graph from a point, with a custom 'filter' predicate. This predicate can be used for instance to check if there is a clear line of sight between the position and the location that is returned.
Declaration
public bool ClosestLocation(float3 position, float maxDistance, ClosestLineLocationPredicate predicate, out LineGraphLocation location)Parameters
| Type | Name | Description |
|---|---|---|
| float3 | position | The center position to search from |
| float | maxDistance | The max search radius. Locations beyond this distance will not be visited. |
| ClosestLineLocationPredicate | predicate | A custom function to determine wether a location is valid as a closest location. If false is returned, the next closest location after that is attempted, and so on. |
| LineGraphLocation | location | Returns the closest location on the graph |
Returns
| Type | Description |
|---|---|
| bool | Wether a location was found within the given radius |
Remarks
This function cannot be used in a burst compiled job context. Use the overload that accepts a Unity.Burst.FunctionPointer<T> instead.
ClosestLocation(float3, float, out LineGraphLocation)
Returns the closest location on the graph from a point.
Declaration
public bool ClosestLocation(float3 position, float maxDistance, out LineGraphLocation location)Parameters
| Type | Name | Description |
|---|---|---|
| float3 | position | The center position to search from |
| float | maxDistance | The max search radius |
| LineGraphLocation | location | Returns the closest location on the graph |
Returns
| Type | Description |
|---|---|
| bool | Wether a location was found within the given radius |
ClosestLocation(float3, float, int, out LineGraphLocation)
Returns the closest location on the graph from a point.
Declaration
public bool ClosestLocation(float3 position, float maxDistance, int flagBitMask, out LineGraphLocation location)Parameters
| Type | Name | Description |
|---|---|---|
| float3 | position | The center position to search from |
| float | maxDistance | The max search radius |
| int | flagBitMask | A bitwise AND is performed on the edge candidates and if any bit is true, the edge is considered. |
| LineGraphLocation | location | Returns the closest location on the graph |
Returns
| Type | Description |
|---|---|
| bool | Wether a location was found within the given radius |
ClosestLocation(float3, float, FunctionPointer<ClosestLineLocationPredicate>, out LineGraphLocation)
Returns the closest location on the graph from a point, with a custom 'filter' predicate. This predicate can be used for instance to check if there is a clear line of sight between the position and the location that is returned.
Declaration
public bool ClosestLocation(float3 position, float maxDistance, FunctionPointer<ClosestLineLocationPredicate> predicate, out LineGraphLocation location)Parameters
| Type | Name | Description |
|---|---|---|
| float3 | position | The center position to search from |
| float | maxDistance | The max search radius. Locations beyond this distance will not be visited. |
| FunctionPointer<ClosestLineLocationPredicate> | predicate | A custom function to determine wether a location is valid as a closest location. If false is returned, the next closest location after that is attempted, and so on. |
| LineGraphLocation | location | Returns the closest location on the graph |
Returns
| Type | Description |
|---|---|
| bool | Wether a location was found within the given radius |
Collect(LineGraphLocation, ref NativeList<Edge<LineGraphLocation>>)
Implement adding all the directed edges that go from the input node.
Declaration
public void Collect(LineGraphLocation location, ref NativeList<Edge<LineGraphLocation>> edgeBuffer)Parameters
| Type | Name | Description |
|---|---|---|
| LineGraphLocation | location | |
| NativeList<Edge<LineGraphLocation>> | edgeBuffer | Add edges to other nodes to this buffer. The buffer is automatically cleared each time before this method is called. Warning: do not modify the edgeBuffer itself. Only add to it. The ref keyword is only used for performance reasons. |
ContainsEdgeId(int)
Does an edge with a given Id exist?
Declaration
public bool ContainsEdgeId(int edgeId)Parameters
| Type | Name | Description |
|---|---|---|
| int | edgeId |
Returns
| Type | Description |
|---|---|
| bool |
GetEdgeIndex(int)
Returns the index of an edge from it's Id. Note that Id's are optional so if you didn't supply Id's upon creation, this method will not work. Also note that if more edges share the same Id, this method will also not work.
Declaration
public int GetEdgeIndex(int edgeId)Parameters
| Type | Name | Description |
|---|---|---|
| int | edgeId | The Id of the edge |
Returns
| Type | Description |
|---|---|
| int |
Remarks
Throws an error of the Id is not present
GetEnumerator()
Returns an enumerator that enumerates all edges/locations in the graph. This can be used to construct ALT heuristics.
Declaration
public LineGraph.Enumerator GetEnumerator()Returns
| Type | Description |
|---|---|
| LineGraph.Enumerator |
GetLocationFromEdgeId(int)
Returns a location for pathfinding queries from an edge's Id. Note that this Id must have been manually assigned to the edge's upon creation. id
The exact position on the edge is set at the center by default. But this value can be modified to be anywhere between or on the endpoints using PositionT.
Declaration
public LineGraphLocation GetLocationFromEdgeId(int edgeId)Parameters
| Type | Name | Description |
|---|---|---|
| int | edgeId | The id of the edge |
Returns
| Type | Description |
|---|---|
| LineGraphLocation |
Remarks
Throws an error if the edgeId isn't present
GetLocationFromEdgeIndex(int)
Returns a location for pathfinding queries from an edge index.
The exact position on the edge is set at the center by default. But this value can be modified to be anywhere between or on the endpoints using PositionT.
Declaration
public LineGraphLocation GetLocationFromEdgeIndex(int edgeIndex)Parameters
| Type | Name | Description |
|---|---|---|
| int | edgeIndex |
Returns
| Type | Description |
|---|---|
| LineGraphLocation |
GetOverlappingEdgeIndices(AABB, NativeHashSet<int>)
Appends all edge indices whose AABB's overlap with a rectangle to a hashset, so that no duplicates can ocur.
Declaration
public void GetOverlappingEdgeIndices(AABB aabb, NativeHashSet<int> indices)Parameters
| Type | Name | Description |
|---|---|---|
| AABB | aabb | Rectangle to test against |
| NativeHashSet<int> | indices | The results are appended to this set. The set is not cleared beforehand |
Populate(LineGraph)
Copies the contents of the source graph into this graph. This can be useful if you want almost the exact same graph but will apply small modifications using SetUnwalkable(int) or SetEnterCostAndFlags(int, float, int) on this graph after populating it.
Declaration
public void Populate(LineGraph source)Parameters
| Type | Name | Description |
|---|---|---|
| LineGraph | source | The source graph to copy |
Remarks
This method is burst compatible, meaning it can be used inside a job to populate the graph with high performance, if you need frequent updates.
Note that this method writes to the graph and as such it should not be used while there are active pathfinding queries running on it. The source graph is allowed be in use though.
Source and destination settings should match
Exceptions
| Type | Condition |
|---|---|
| InvalidOperationException | Throws when the value of DirectedEdgesQueryable is different than that of the source |
Populate(IReadOnlyList<float3>, IReadOnlyList<Edge>, IReadOnlyList<Edge>)
Populate the graph with vertices and edges
Declaration
public void Populate(IReadOnlyList<float3> vertices, IReadOnlyList<LineGraph.Edge> undirectedEdges, IReadOnlyList<LineGraph.Edge> directedEdges = null)Parameters
| Type | Name | Description |
|---|---|---|
| IReadOnlyList<float3> | vertices | Vertices to use |
| IReadOnlyList<LineGraph.Edge> | undirectedEdges | Indices connecting vertices together in an undirected fashion. Every pair of indices (i, i+1) describes an edge that connectets vertex i and vertex i + 1 in both directions |
| IReadOnlyList<LineGraph.Edge> | directedEdges | Indices connecting vertices together in a directed fashion. Every pair of indices (i, i+1) describes an edge that connectets vertex i to vertex i + 1 |
Remarks
Do not use this method when the graph is in use for pathfinding, as it writes to the internals of the graph
Populate(NativeArray<float3>, NativeArray<Edge>, NativeArray<Edge>)
Populate the graph with vertices and edges
Declaration
public void Populate(NativeArray<float3> vertices, NativeArray<LineGraph.Edge> undirectedEdges, NativeArray<LineGraph.Edge> directedEdges = default)Parameters
| Type | Name | Description |
|---|---|---|
| NativeArray<float3> | vertices | Vertices to use |
| NativeArray<LineGraph.Edge> | undirectedEdges | Indices connecting vertices together in an undirected fashion. Every pair of indices (i, i+1) describes an edge that connectets vertex i and vertex i + 1 in both directions |
| NativeArray<LineGraph.Edge> | directedEdges | Indices connecting vertices together in a directed fashion. Every pair of indices (i, i+1) describes an edge that connectets vertex i to vertex i + 1. Leave default to not use any directed edges |
Remarks
This method is burst compatible, meaning it can be used inside a job to populate the graph with high performance, if you need frequent updates.
Do not use this method when the graph is in use for pathfinding, as it writes to the internals of the graph. If you need frequent updates, a common technique is to use a double buffer and swap two graphs as one is updated.
SetEnterCostAndFlags(int, float, int)
Overwrites the enter cost and flags for an edge at index. The index can be obtained via GetOverlappingEdgeIndices(AABB, NativeHashSet<int>), GetEdgeIndex(int) or ClosestLocation(float3, float, int, out LineGraphLocation)
Declaration
public void SetEnterCostAndFlags(int edgeIndex, float enterCost, int flags)Parameters
| Type | Name | Description |
|---|---|---|
| int | edgeIndex | index of the edge to overwrite |
| float | enterCost | new enter cost for the edge. A value of infinity makes the edge unwalkable, essentialy removing it from the graph. Note that raycasting can still return this edge. |
| int | flags | New flags for this edge |
Remarks
This method writes to the graph and as such it cannot be used while pathfinding queries are active on it
SetUnwalkable(int)
Makes an edge unwalkable, assigning it a cost of infinity.
Declaration
public void SetUnwalkable(int edgeIndex)Parameters
| Type | Name | Description |
|---|---|---|
| int | edgeIndex | index of the edge to overwrite |
Remarks
This method writes to the graph and as such it cannot be used while pathfinding queries are active on it
TryGetEdgeIndex(int, out int)
Returns the index of an edge from it's Id. Note that Id's are optional so if you didn't supply Id's upon creation, this method will not work. Also note that if more edges share the same Id, this method will also not work.
Declaration
public bool TryGetEdgeIndex(int edgeId, out int edgeIndex)Parameters
| Type | Name | Description |
|---|---|---|
| int | edgeId | The Id of the edge |
| int | edgeIndex | If successful, set to the index of the edge that carries the Id |
Returns
| Type | Description |
|---|---|
| bool |