From 8722a9920c1f6119bf6e769cba270e63097f8e25 Mon Sep 17 00:00:00 2001
From: chai <215380520@qq.com>
Date: Thu, 23 May 2024 10:08:29 +0800
Subject: + astar project
---
.../Graphs/Navmesh/AABBTree.cs | 381 ++++++
.../Graphs/Navmesh/AABBTree.cs.meta | 7 +
.../Graphs/Navmesh/BBTree.cs | 578 +++++++++
.../Graphs/Navmesh/BBTree.cs.meta | 7 +
.../Graphs/Navmesh/ColliderMeshBuilder2D.cs | 336 ++++++
.../Graphs/Navmesh/ColliderMeshBuilder2D.cs.meta | 11 +
.../Graphs/Navmesh/Jobs.meta | 8 +
.../Graphs/Navmesh/Jobs/JobBuildNodes.cs | 92 ++
.../Graphs/Navmesh/Jobs/JobBuildNodes.cs.meta | 11 +
.../Navmesh/Jobs/JobBuildTileMeshFromVertices.cs | 105 ++
.../Jobs/JobBuildTileMeshFromVertices.cs.meta | 11 +
.../Navmesh/Jobs/JobBuildTileMeshFromVoxels.cs | 288 +++++
.../Jobs/JobBuildTileMeshFromVoxels.cs.meta | 11 +
.../Jobs/JobCalculateTriangleConnections.cs | 73 ++
.../Jobs/JobCalculateTriangleConnections.cs.meta | 11 +
.../Graphs/Navmesh/Jobs/JobConnectTiles.cs | 159 +++
.../Graphs/Navmesh/Jobs/JobConnectTiles.cs.meta | 11 +
.../Graphs/Navmesh/Jobs/JobConvertAreasToTags.cs | 23 +
.../Navmesh/Jobs/JobConvertAreasToTags.cs.meta | 11 +
.../Graphs/Navmesh/Jobs/JobCreateTiles.cs | 115 ++
.../Graphs/Navmesh/Jobs/JobCreateTiles.cs.meta | 11 +
.../Navmesh/Jobs/JobTransformTileCoordinates.cs | 32 +
.../Jobs/JobTransformTileCoordinates.cs.meta | 11 +
.../Graphs/Navmesh/Jobs/JobWriteNodeConnections.cs | 60 +
.../Navmesh/Jobs/JobWriteNodeConnections.cs.meta | 11 +
.../Graphs/Navmesh/NavmeshTile.cs | 106 ++
.../Graphs/Navmesh/NavmeshTile.cs.meta | 12 +
.../Graphs/Navmesh/RecastBuilder.cs | 49 +
.../Graphs/Navmesh/RecastBuilder.cs.meta | 11 +
.../Graphs/Navmesh/RecastMeshGatherer.cs | 1134 ++++++++++++++++++
.../Graphs/Navmesh/RecastMeshGatherer.cs.meta | 11 +
.../Graphs/Navmesh/TileBuilder.cs | 366 ++++++
.../Graphs/Navmesh/TileBuilder.cs.meta | 11 +
.../Graphs/Navmesh/TileHandler.cs | 1258 ++++++++++++++++++++
.../Graphs/Navmesh/TileHandler.cs.meta | 8 +
.../Graphs/Navmesh/TileLayout.cs | 96 ++
.../Graphs/Navmesh/TileLayout.cs.meta | 11 +
.../Graphs/Navmesh/TileMesh.cs | 41 +
.../Graphs/Navmesh/TileMesh.cs.meta | 11 +
.../Graphs/Navmesh/TileMeshes.cs | 193 +++
.../Graphs/Navmesh/TileMeshes.cs.meta | 11 +
.../Graphs/Navmesh/Voxels.meta | 2 +
.../Graphs/Navmesh/Voxels/CompactVoxelField.cs | 132 ++
.../Navmesh/Voxels/CompactVoxelField.cs.meta | 11 +
.../Graphs/Navmesh/Voxels/LinkedVoxelField.cs | 295 +++++
.../Graphs/Navmesh/Voxels/LinkedVoxelField.cs.meta | 11 +
.../Graphs/Navmesh/Voxels/VoxelContour.cs | 710 +++++++++++
.../Graphs/Navmesh/Voxels/VoxelContour.cs.meta | 11 +
.../Graphs/Navmesh/Voxels/VoxelMesh.cs | 542 +++++++++
.../Graphs/Navmesh/Voxels/VoxelMesh.cs.meta | 11 +
.../Graphs/Navmesh/Voxels/VoxelPolygonClipper.cs | 205 ++++
.../Navmesh/Voxels/VoxelPolygonClipper.cs.meta | 12 +
.../Graphs/Navmesh/Voxels/VoxelRasterization.cs | 484 ++++++++
.../Navmesh/Voxels/VoxelRasterization.cs.meta | 11 +
.../Graphs/Navmesh/Voxels/VoxelRegion.cs | 813 +++++++++++++
.../Graphs/Navmesh/Voxels/VoxelRegion.cs.meta | 11 +
56 files changed, 8964 insertions(+)
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/AABBTree.cs
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/AABBTree.cs.meta
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/BBTree.cs
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/BBTree.cs.meta
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/ColliderMeshBuilder2D.cs
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/ColliderMeshBuilder2D.cs.meta
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs.meta
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobBuildNodes.cs
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobBuildNodes.cs.meta
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobBuildTileMeshFromVertices.cs
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobBuildTileMeshFromVertices.cs.meta
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobBuildTileMeshFromVoxels.cs
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobBuildTileMeshFromVoxels.cs.meta
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobCalculateTriangleConnections.cs
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobCalculateTriangleConnections.cs.meta
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobConnectTiles.cs
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobConnectTiles.cs.meta
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobConvertAreasToTags.cs
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobConvertAreasToTags.cs.meta
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobCreateTiles.cs
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobCreateTiles.cs.meta
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobTransformTileCoordinates.cs
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobTransformTileCoordinates.cs.meta
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobWriteNodeConnections.cs
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobWriteNodeConnections.cs.meta
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/NavmeshTile.cs
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/NavmeshTile.cs.meta
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/RecastBuilder.cs
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/RecastBuilder.cs.meta
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/RecastMeshGatherer.cs
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/RecastMeshGatherer.cs.meta
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/TileBuilder.cs
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/TileBuilder.cs.meta
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/TileHandler.cs
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/TileHandler.cs.meta
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/TileLayout.cs
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/TileLayout.cs.meta
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/TileMesh.cs
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/TileMesh.cs.meta
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/TileMeshes.cs
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/TileMeshes.cs.meta
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Voxels.meta
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Voxels/CompactVoxelField.cs
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Voxels/CompactVoxelField.cs.meta
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Voxels/LinkedVoxelField.cs
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Voxels/LinkedVoxelField.cs.meta
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Voxels/VoxelContour.cs
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Voxels/VoxelContour.cs.meta
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Voxels/VoxelMesh.cs
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Voxels/VoxelMesh.cs.meta
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Voxels/VoxelPolygonClipper.cs
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Voxels/VoxelPolygonClipper.cs.meta
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Voxels/VoxelRasterization.cs
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Voxels/VoxelRasterization.cs.meta
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Voxels/VoxelRegion.cs
create mode 100644 Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Voxels/VoxelRegion.cs.meta
(limited to 'Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh')
diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/AABBTree.cs b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/AABBTree.cs
new file mode 100644
index 0000000..5794204
--- /dev/null
+++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/AABBTree.cs
@@ -0,0 +1,381 @@
+// #define VALIDATE_AABB_TREE
+using UnityEngine;
+using System.Collections.Generic;
+using Pathfinding.Util;
+using Unity.Mathematics;
+using UnityEngine.Assertions;
+
+namespace Pathfinding.Graphs.Navmesh {
+ ///
+ /// Axis Aligned Bounding Box Tree.
+ ///
+ /// Holds a bounding box tree with arbitrary data.
+ ///
+ /// The tree self-balances itself regularly when nodes are added.
+ ///
+ public class AABBTree {
+ Node[] nodes = new Node[0];
+ int root = NoNode;
+ readonly Stack freeNodes = new Stack();
+ int rebuildCounter = 64;
+ const int NoNode = -1;
+
+ struct Node {
+ public Bounds bounds;
+ public uint flags;
+ const uint TagInsideBit = 1u << 30;
+ const uint TagPartiallyInsideBit = 1u << 31;
+ const uint AllocatedBit = 1u << 29;
+ const uint ParentMask = ~(TagInsideBit | TagPartiallyInsideBit | AllocatedBit);
+ public const int InvalidParent = (int)ParentMask;
+ public bool wholeSubtreeTagged {
+ get => (flags & TagInsideBit) != 0;
+ set => flags = (flags & ~TagInsideBit) | (value ? TagInsideBit : 0);
+ }
+ public bool subtreePartiallyTagged {
+ get => (flags & TagPartiallyInsideBit) != 0;
+ set => flags = (flags & ~TagPartiallyInsideBit) | (value ? TagPartiallyInsideBit : 0);
+ }
+ public bool isAllocated {
+ get => (flags & AllocatedBit) != 0;
+ set => flags = (flags & ~AllocatedBit) | (value ? AllocatedBit : 0);
+ }
+ public bool isLeaf => left == NoNode;
+ public int parent {
+ get => (int)(flags & ParentMask);
+ set => flags = (flags & ~ParentMask) | (uint)value;
+ }
+ public int left;
+ public int right;
+ public T value;
+ }
+
+ /// A key to a leaf node in the tree
+ public readonly struct Key {
+ internal readonly int value;
+ public int node => value - 1;
+ public bool isValid => value != 0;
+ internal Key(int node) { this.value = node + 1; }
+ }
+
+ static float ExpansionRequired (Bounds b, Bounds b2) {
+ var union = b;
+ union.Encapsulate(b2);
+ return union.size.x*union.size.y*union.size.z - b.size.x*b.size.y*b.size.z;
+ }
+
+ /// User data for a node in the tree
+ public T this[Key key] => nodes[key.node].value;
+
+ /// Bounding box of a given node
+ public Bounds GetBounds (Key key) {
+ if (!key.isValid) throw new System.ArgumentException("Key is not valid");
+ var node = nodes[key.node];
+ if (!node.isAllocated) throw new System.ArgumentException("Key does not point to an allocated node");
+ if (!node.isLeaf) throw new System.ArgumentException("Key does not point to a leaf node");
+ return node.bounds;
+ }
+
+ int AllocNode () {
+ if (!freeNodes.TryPop(out int newNodeId)) {
+ int prevLength = nodes.Length;
+ Memory.Realloc(ref nodes, Mathf.Max(8, nodes.Length*2));
+ for (int i = nodes.Length - 1; i >= prevLength; i--) FreeNode(i);
+ newNodeId = freeNodes.Pop();
+#if VALIDATE_AABB_TREE
+ Assert.IsFalse(nodes[newNodeId].isAllocated);
+#endif
+ }
+ return newNodeId;
+ }
+
+ void FreeNode (int node) {
+ nodes[node].isAllocated = false;
+ nodes[node].value = default;
+ freeNodes.Push(node);
+ }
+
+ ///
+ /// Rebuilds the whole tree.
+ ///
+ /// This can make it more balanced, and thus faster to query.
+ ///
+ public void Rebuild () {
+ var leaves = new UnsafeSpan(Unity.Collections.Allocator.Temp, nodes.Length);
+ int nLeaves = 0;
+ for (int i = 0; i < nodes.Length; i++) {
+ if (!nodes[i].isAllocated) continue;
+ if (nodes[i].isLeaf) leaves[nLeaves++] = i;
+ else FreeNode(i);
+ }
+ root = Rebuild(leaves.Slice(0, nLeaves), Node.InvalidParent);
+ rebuildCounter = Mathf.Max(64, nLeaves / 3);
+ Validate(root);
+ }
+
+ /// Removes all nodes from the tree
+ public void Clear () {
+ for (int i = 0; i < nodes.Length; i++) {
+ if (nodes[i].isAllocated) FreeNode(i);
+ }
+ root = NoNode;
+ rebuildCounter = 64;
+ }
+
+ struct AABBComparer : IComparer {
+ public Node[] nodes;
+ public int dim;
+
+ public int Compare(int a, int b) => nodes[a].bounds.center[dim].CompareTo(nodes[b].bounds.center[dim]);
+ }
+
+ static int ArgMax (Vector3 v) {
+ var m = Mathf.Max(v.x, Mathf.Max(v.y, v.z));
+ return m == v.x ? 0: (m == v.y ? 1 : 2);
+ }
+
+ int Rebuild (UnsafeSpan leaves, int parent) {
+ if (leaves.Length == 0) return NoNode;
+ if (leaves.Length == 1) {
+ nodes[leaves[0]].parent = parent;
+ return leaves[0];
+ }
+
+ var bounds = nodes[leaves[0]].bounds;
+ for (int i = 1; i < leaves.Length; i++) bounds.Encapsulate(nodes[leaves[i]].bounds);
+
+ leaves.Sort(new AABBComparer { nodes = nodes, dim = ArgMax(bounds.extents) });
+ var nodeId = AllocNode();
+ nodes[nodeId] = new Node {
+ bounds = bounds,
+ left = Rebuild(leaves.Slice(0, leaves.Length/2), nodeId),
+ right = Rebuild(leaves.Slice(leaves.Length/2), nodeId),
+ parent = parent,
+ isAllocated = true,
+ };
+ return nodeId;
+ }
+
+ ///
+ /// Moves a node to a new position.
+ ///
+ /// This will update the tree structure to account for the new bounding box.
+ /// This is equivalent to removing the node and adding it again with the new bounds, but it preserves the key value.
+ ///
+ /// Key to the node to move
+ /// New bounds of the node
+ public void Move (Key key, Bounds bounds) {
+ var value = nodes[key.node].value;
+ Remove(key);
+ var newKey = Add(bounds, value);
+ // The first node added after a remove will have the same node index as the just removed node
+ Assert.IsTrue(newKey.node == key.node);
+ }
+
+ [System.Diagnostics.Conditional("VALIDATE_AABB_TREE")]
+ void Validate (int node) {
+ if (node == NoNode) return;
+ var n = nodes[node];
+ Assert.IsTrue(n.isAllocated);
+ if (node == root) {
+ Assert.AreEqual(Node.InvalidParent, n.parent);
+ } else {
+ Assert.AreNotEqual(Node.InvalidParent, n.parent);
+ }
+ if (n.isLeaf) {
+ Assert.AreEqual(NoNode, n.right);
+ } else {
+ Assert.AreNotEqual(NoNode, n.right);
+ Assert.AreNotEqual(n.left, n.right);
+ Assert.AreEqual(node, nodes[n.left].parent);
+ Assert.AreEqual(node, nodes[n.right].parent);
+ Assert.IsTrue(math.all((float3)n.bounds.min <= (float3)nodes[n.left].bounds.min + 0.0001f));
+ Assert.IsTrue(math.all((float3)n.bounds.max >= (float3)nodes[n.left].bounds.max - 0.0001f));
+ Assert.IsTrue(math.all((float3)n.bounds.min <= (float3)nodes[n.right].bounds.min + 0.0001f));
+ Assert.IsTrue(math.all((float3)n.bounds.max >= (float3)nodes[n.right].bounds.max - 0.0001f));
+ Validate(n.left);
+ Validate(n.right);
+ }
+ }
+
+ public Bounds Remove (Key key) {
+ if (!key.isValid) throw new System.ArgumentException("Key is not valid");
+ var node = nodes[key.node];
+ if (!node.isAllocated) throw new System.ArgumentException("Key does not point to an allocated node");
+ if (!node.isLeaf) throw new System.ArgumentException("Key does not point to a leaf node");
+
+ if (key.node == root) {
+ root = NoNode;
+ FreeNode(key.node);
+ return node.bounds;
+ }
+
+ // Remove the parent from the tree and replace it with sibling
+ var parentToRemoveId = node.parent;
+ var parentToRemove = nodes[parentToRemoveId];
+ var siblingId = parentToRemove.left == key.node ? parentToRemove.right : parentToRemove.left;
+ FreeNode(parentToRemoveId);
+ FreeNode(key.node);
+ nodes[siblingId].parent = parentToRemove.parent;
+
+ if (parentToRemove.parent == Node.InvalidParent) {
+ root = siblingId;
+ } else {
+ if (nodes[parentToRemove.parent].left == parentToRemoveId) {
+ nodes[parentToRemove.parent].left = siblingId;
+ } else {
+ nodes[parentToRemove.parent].right = siblingId;
+ }
+ }
+
+ // Rebuild bounding boxes
+ var tmpNodeId = nodes[siblingId].parent;
+ while (tmpNodeId != Node.InvalidParent) {
+ ref var tmpNode = ref nodes[tmpNodeId];
+ var bounds = nodes[tmpNode.left].bounds;
+ bounds.Encapsulate(nodes[tmpNode.right].bounds);
+ tmpNode.bounds = bounds;
+ tmpNode.subtreePartiallyTagged = nodes[tmpNode.left].subtreePartiallyTagged | nodes[tmpNode.right].subtreePartiallyTagged;
+ tmpNodeId = tmpNode.parent;
+ }
+ Validate(root);
+ return node.bounds;
+ }
+
+ public Key Add (Bounds bounds, T value) {
+ var newNodeId = AllocNode();
+
+ nodes[newNodeId] = new Node {
+ bounds = bounds,
+ parent = Node.InvalidParent,
+ left = NoNode,
+ right = NoNode,
+ value = value,
+ isAllocated = true,
+ };
+
+ if (root == NoNode) {
+ root = newNodeId;
+ Validate(root);
+ return new Key(newNodeId);
+ }
+
+ int nodeId = root;
+ while (true) {
+ var node = nodes[nodeId];
+
+ // We can no longer guarantee that the whole subtree of this node is tagged,
+ // as the new node is not tagged
+ nodes[nodeId].wholeSubtreeTagged = false;
+
+ if (node.isLeaf) {
+ var newInnerId = AllocNode();
+
+ if (node.parent != Node.InvalidParent) {
+ if (nodes[node.parent].left == nodeId) nodes[node.parent].left = newInnerId;
+ else nodes[node.parent].right = newInnerId;
+ }
+
+ bounds.Encapsulate(node.bounds);
+ nodes[newInnerId] = new Node {
+ bounds = bounds,
+ left = nodeId,
+ right = newNodeId,
+ parent = node.parent,
+ isAllocated = true,
+ };
+ nodes[newNodeId].parent = nodes[nodeId].parent = newInnerId;
+ if (root == nodeId) root = newInnerId;
+
+ if (rebuildCounter-- <= 0) Rebuild();
+ Validate(root);
+ return new Key(newNodeId);
+ } else {
+ // Inner node
+ nodes[nodeId].bounds.Encapsulate(bounds);
+ float leftCost = ExpansionRequired(nodes[node.left].bounds, bounds);
+ float rightCost = ExpansionRequired(nodes[node.right].bounds, bounds);
+ nodeId = leftCost < rightCost ? node.left : node.right;
+ }
+ }
+ }
+
+ /// Queries the tree for all objects that touch the specified bounds.
+ /// Bounding box to search within
+ /// The results will be added to the buffer
+ public void Query(Bounds bounds, List buffer) => QueryNode(root, bounds, buffer);
+
+ void QueryNode (int node, Bounds bounds, List buffer) {
+ if (node == NoNode || !bounds.Intersects(nodes[node].bounds)) return;
+
+ if (nodes[node].isLeaf) {
+ buffer.Add(nodes[node].value);
+ } else {
+ // Search children
+ QueryNode(nodes[node].left, bounds, buffer);
+ QueryNode(nodes[node].right, bounds, buffer);
+ }
+ }
+
+ /// Queries the tree for all objects that have been previously tagged using the method.
+ /// The results will be added to the buffer
+ /// If true, all tags will be cleared after this call. If false, the tags will remain and can be queried again later.
+ public void QueryTagged(List buffer, bool clearTags = false) => QueryTaggedNode(root, clearTags, buffer);
+
+ void QueryTaggedNode (int node, bool clearTags, List buffer) {
+ if (node == NoNode || !nodes[node].subtreePartiallyTagged) return;
+
+ if (clearTags) {
+ nodes[node].wholeSubtreeTagged = false;
+ nodes[node].subtreePartiallyTagged = false;
+ }
+
+ if (nodes[node].isLeaf) {
+ buffer.Add(nodes[node].value);
+ } else {
+ QueryTaggedNode(nodes[node].left, clearTags, buffer);
+ QueryTaggedNode(nodes[node].right, clearTags, buffer);
+ }
+ }
+
+ ///
+ /// Tags a particular object.
+ ///
+ /// Any previously tagged objects stay tagged.
+ /// You can retrieve the tagged objects using the method.
+ ///
+ /// Key to the object to tag
+ public void Tag (Key key) {
+ if (!key.isValid) throw new System.ArgumentException("Key is not valid");
+ if (key.node < 0 || key.node >= nodes.Length) throw new System.ArgumentException("Key does not point to a valid node");
+ ref var node = ref nodes[key.node];
+ if (!node.isAllocated) throw new System.ArgumentException("Key does not point to an allocated node");
+ if (!node.isLeaf) throw new System.ArgumentException("Key does not point to a leaf node");
+ node.wholeSubtreeTagged = true;
+ int nodeId = key.node;
+ while (nodeId != Node.InvalidParent) {
+ nodes[nodeId].subtreePartiallyTagged = true;
+ nodeId = nodes[nodeId].parent;
+ }
+ }
+
+ ///
+ /// Tags all objects that touch the specified bounds.
+ ///
+ /// Any previously tagged objects stay tagged.
+ /// You can retrieve the tagged objects using the method.
+ ///
+ /// Bounding box to search within
+ public void Tag(Bounds bounds) => TagNode(root, bounds);
+
+ bool TagNode (int node, Bounds bounds) {
+ if (node == NoNode || nodes[node].wholeSubtreeTagged) return true; // Nothing to do
+ if (!bounds.Intersects(nodes[node].bounds)) return false;
+
+ // TODO: Could make this less conservative by propagating info from the child nodes
+ nodes[node].subtreePartiallyTagged = true;
+ if (nodes[node].isLeaf) return nodes[node].wholeSubtreeTagged = true;
+ else return nodes[node].wholeSubtreeTagged = TagNode(nodes[node].left, bounds) & TagNode(nodes[node].right, bounds);
+ }
+ }
+}
diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/AABBTree.cs.meta b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/AABBTree.cs.meta
new file mode 100644
index 0000000..50515ca
--- /dev/null
+++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/AABBTree.cs.meta
@@ -0,0 +1,7 @@
+fileFormatVersion: 2
+guid: 183e10f9cadca424792b5f940ce3fe3d
+MonoImporter:
+ serializedVersion: 2
+ defaultReferences: []
+ executionOrder: 0
+ icon: {instanceID: 0}
diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/BBTree.cs b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/BBTree.cs
new file mode 100644
index 0000000..c06ec78
--- /dev/null
+++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/BBTree.cs
@@ -0,0 +1,578 @@
+//#define ASTARDEBUG //"BBTree Debug" If enables, some queries to the tree will show debug lines. Turn off multithreading when using this since DrawLine calls cannot be called from a different thread
+
+using System;
+using System.Collections.Generic;
+using UnityEngine;
+using Unity.Mathematics;
+using Unity.Burst;
+using Unity.Collections;
+using Unity.Collections.LowLevel.Unsafe;
+using Pathfinding.Drawing;
+
+namespace Pathfinding.Graphs.Navmesh {
+ using Pathfinding.Util;
+
+ ///
+ /// Axis Aligned Bounding Box Tree.
+ /// Holds a bounding box tree of triangles.
+ ///
+ [BurstCompile]
+ public struct BBTree : IDisposable {
+ /// Holds all tree nodes
+ UnsafeList tree;
+ UnsafeList nodePermutation;
+
+ const int MaximumLeafSize = 4;
+
+ public IntRect Size => tree.Length == 0 ? default : tree[0].rect;
+
+ // We need a stack while searching the tree.
+ // We use a stack allocated array for this to avoid allocations.
+ // A tile can at most contain NavmeshBase.VertexIndexMask triangles.
+ // This works out to about a million. A perfectly balanced tree can fit this in log2(1000000/4) = 18 levels.
+ // but we add a few more levels just to be safe, in case the tree is not perfectly balanced.
+ const int MAX_TREE_HEIGHT = 26;
+
+ public void Dispose () {
+ nodePermutation.Dispose();
+ tree.Dispose();
+ }
+
+ /// Build a BBTree from a list of triangles.
+ /// The triangles. Each triplet of 3 indices represents a node. The triangles are assumed to be in clockwise order.
+ /// The vertices of the triangles.
+ public BBTree(UnsafeSpan triangles, UnsafeSpan vertices) {
+ if (triangles.Length % 3 != 0) throw new ArgumentException("triangles must be a multiple of 3 in length");
+ Build(ref triangles, ref vertices, out this);
+ }
+
+ [BurstCompile]
+ static void Build (ref UnsafeSpan triangles, ref UnsafeSpan vertices, out BBTree bbTree) {
+ var nodeCount = triangles.Length/3;
+ // We will use approximately 2N tree nodes
+ var tree = new UnsafeList((int)(nodeCount * 2.1f), Allocator.Persistent, NativeArrayOptions.UninitializedMemory);
+ // We will use approximately N node references
+ var nodes = new UnsafeList((int)(nodeCount * 1.1f), Allocator.Persistent, NativeArrayOptions.UninitializedMemory);
+
+ // This will store the order of the nodes while the tree is being built
+ // It turns out that it is a lot faster to do this than to actually modify
+ // the nodes and nodeBounds arrays (presumably since that involves shuffling
+ // around 20 bytes of memory (sizeof(pointer) + sizeof(IntRect)) per node
+ // instead of 4 bytes (sizeof(int)).
+ // It also means we don't have to make a copy of the nodes array since
+ // we do not modify it
+ var permutation = new NativeArray(nodeCount, Allocator.Temp);
+ for (int i = 0; i < nodeCount; i++) {
+ permutation[i] = i;
+ }
+
+ // Precalculate the bounds of the nodes in XZ space.
+ // It turns out that calculating the bounds is a bottleneck and precalculating
+ // the bounds makes it around 3 times faster to build a tree
+ var nodeBounds = new NativeArray(nodeCount, Allocator.Temp);
+ for (int i = 0; i < nodeCount; i++) {
+ var v0 = ((int3)vertices[triangles[i*3+0]]).xz;
+ var v1 = ((int3)vertices[triangles[i*3+1]]).xz;
+ var v2 = ((int3)vertices[triangles[i*3+2]]).xz;
+ var mn = math.min(v0, math.min(v1, v2));
+ var mx = math.max(v0, math.max(v1, v2));
+ nodeBounds[i] = new IntRect(mn.x, mn.y, mx.x, mx.y);
+ }
+
+ if (nodeCount > 0) BuildSubtree(permutation, nodeBounds, ref nodes, ref tree, 0, nodeCount, false, 0);
+ nodeBounds.Dispose();
+ permutation.Dispose();
+
+ bbTree = new BBTree {
+ tree = tree,
+ nodePermutation = nodes,
+ };
+ }
+
+ static int SplitByX (NativeArray nodesBounds, NativeArray permutation, int from, int to, int divider) {
+ int mx = to;
+
+ for (int i = from; i < mx; i++) {
+ var cr = nodesBounds[permutation[i]];
+ var cx = (cr.xmin + cr.xmax)/2;
+ if (cx > divider) {
+ mx--;
+ // Swap items i and mx
+ var tmp = permutation[mx];
+ permutation[mx] = permutation[i];
+ permutation[i] = tmp;
+ i--;
+ }
+ }
+ return mx;
+ }
+
+ static int SplitByZ (NativeArray nodesBounds, NativeArray permutation, int from, int to, int divider) {
+ int mx = to;
+
+ for (int i = from; i < mx; i++) {
+ var cr = nodesBounds[permutation[i]];
+ var cx = (cr.ymin + cr.ymax)/2;
+ if (cx > divider) {
+ mx--;
+ // Swap items i and mx
+ var tmp = permutation[mx];
+ permutation[mx] = permutation[i];
+ permutation[i] = tmp;
+ i--;
+ }
+ }
+ return mx;
+ }
+
+ static int BuildSubtree (NativeArray permutation, NativeArray nodeBounds, ref UnsafeList nodes, ref UnsafeList tree, int from, int to, bool odd, int depth) {
+ var rect = NodeBounds(permutation, nodeBounds, from, to);
+ int boxId = tree.Length;
+ tree.Add(new BBTreeBox(rect));
+
+ if (to - from <= MaximumLeafSize) {
+ if (depth > MAX_TREE_HEIGHT) {
+ Debug.LogWarning($"Maximum tree height of {MAX_TREE_HEIGHT} exceeded (got depth of {depth}). Querying this tree may fail. Is the tree very unbalanced?");
+ }
+ var box = tree[boxId];
+ var nodeOffset = box.nodeOffset = nodes.Length;
+ tree[boxId] = box;
+ nodes.Length += MaximumLeafSize;
+ // Assign all nodes to the array. Note that we also need clear unused slots as the array from the pool may contain any information
+ for (int i = 0; i < MaximumLeafSize; i++) {
+ nodes[nodeOffset + i] = i < to - from ? permutation[from + i] : -1;
+ }
+ return boxId;
+ } else {
+ int splitIndex;
+ if (odd) {
+ // X
+ int divider = (rect.xmin + rect.xmax)/2;
+ splitIndex = SplitByX(nodeBounds, permutation, from, to, divider);
+ } else {
+ // Y/Z
+ int divider = (rect.ymin + rect.ymax)/2;
+ splitIndex = SplitByZ(nodeBounds, permutation, from, to, divider);
+ }
+
+ int margin = (to - from)/8;
+ bool veryUneven = splitIndex <= from + margin || splitIndex >= to - margin;
+ if (veryUneven) {
+ // All nodes were on one side of the divider
+ // Try to split along the other axis
+
+ if (!odd) {
+ // X
+ int divider = (rect.xmin + rect.xmax)/2;
+ splitIndex = SplitByX(nodeBounds, permutation, from, to, divider);
+ } else {
+ // Y/Z
+ int divider = (rect.ymin + rect.ymax)/2;
+ splitIndex = SplitByZ(nodeBounds, permutation, from, to, divider);
+ }
+ veryUneven = splitIndex <= from + margin || splitIndex >= to - margin;
+
+ if (veryUneven) {
+ // Almost all nodes were on one side of the divider
+ // Just pick one half
+ splitIndex = (from+to)/2;
+ }
+ }
+
+ var left = BuildSubtree(permutation, nodeBounds, ref nodes, ref tree, from, splitIndex, !odd, depth+1);
+ var right = BuildSubtree(permutation, nodeBounds, ref nodes, ref tree, splitIndex, to, !odd, depth+1);
+ var box = tree[boxId];
+ box.left = left;
+ box.right = right;
+ tree[boxId] = box;
+
+ return boxId;
+ }
+ }
+
+ /// Calculates the bounding box in XZ space of all nodes between from (inclusive) and to (exclusive)
+ static IntRect NodeBounds (NativeArray permutation, NativeArray nodeBounds, int from, int to) {
+ var mn = (int2)nodeBounds[permutation[from]].Min;
+ var mx = (int2)nodeBounds[permutation[from]].Max;
+
+ for (int j = from + 1; j < to; j++) {
+ var otherRect = nodeBounds[permutation[j]];
+ var rmin = new int2(otherRect.xmin, otherRect.ymin);
+ var rmax = new int2(otherRect.xmax, otherRect.ymax);
+ mn = math.min(mn, rmin);
+ mx = math.max(mx, rmax);
+ }
+
+ return new IntRect(mn.x, mn.y, mx.x, mx.y);
+ }
+
+ [BurstCompile]
+ public readonly struct ProjectionParams {
+ public readonly float2x3 planeProjection;
+ public readonly float2 projectedUpNormalized;
+ public readonly float3 projectionAxis;
+ public readonly float distanceScaleAlongProjectionAxis;
+ public readonly DistanceMetric distanceMetric;
+ // bools are for some reason not blittable by the burst compiler, so we have to use a byte
+ readonly byte alignedWithXZPlaneBacking;
+
+ public bool alignedWithXZPlane => alignedWithXZPlaneBacking != 0;
+
+ ///
+ /// Calculates the squared distance from a point to a box when projected to 2D.
+ ///
+ /// The input rectangle is assumed to be on the XZ plane, and to actually represent an infinitely tall box (along the Y axis).
+ ///
+ /// The planeProjection matrix projects points from 3D to 2D. The box will also be projected.
+ /// The upProjNormalized vector is the normalized direction orthogonal to the 2D projection.
+ /// It is the direction pointing out of the plane from the projection's point of view.
+ ///
+ /// In the special case that the projection just projects 3D coordinates onto the XZ plane, this is
+ /// equivalent to the distance from a point to a rectangle in 2D.
+ ///
+ public float SquaredRectPointDistanceOnPlane (IntRect rect, float3 p) {
+ return SquaredRectPointDistanceOnPlane(in this, ref rect, ref p);
+ }
+
+ [BurstCompile(FloatMode = FloatMode.Fast)]
+ private static float SquaredRectPointDistanceOnPlane (in ProjectionParams projection, ref IntRect rect, ref float3 p) {
+ if (projection.alignedWithXZPlane) {
+ var p1 = new float2(rect.xmin, rect.ymin) * Int3.PrecisionFactor;
+ var p4 = new float2(rect.xmax, rect.ymax) * Int3.PrecisionFactor;
+ var closest = math.clamp(p.xz, p1, p4);
+ return math.lengthsq(closest - p.xz);
+ } else {
+ var p1 = new float3(rect.xmin, 0, rect.ymin) * Int3.PrecisionFactor - p;
+ var p4 = new float3(rect.xmax, 0, rect.ymax) * Int3.PrecisionFactor - p;
+ var p2 = new float3(rect.xmin, 0, rect.ymax) * Int3.PrecisionFactor - p;
+ var p3 = new float3(rect.xmax, 0, rect.ymin) * Int3.PrecisionFactor - p;
+ var p1proj = math.mul(projection.planeProjection, p1);
+ var p2proj = math.mul(projection.planeProjection, p2);
+ var p3proj = math.mul(projection.planeProjection, p3);
+ var p4proj = math.mul(projection.planeProjection, p4);
+ var upNormal = new float2(projection.projectedUpNormalized.y, -projection.projectedUpNormalized.x);
+ // Calculate the dot product of pNproj and upNormal for all N, this is the distance between p and pN
+ // along the direction orthogonal to upProjNormalized.
+ // The box is infinite along the up direction (since it is only a rect). When projected down to 2D
+ // this results in an infinite line with a given thickness (a beam).
+ // This is assuming the projection direction is not parallel to the world up direction, in which case we
+ // would have entered the other branch of this if statement.
+ // The minumum value and maximum value in dists gives us the signed distance to this beam
+ // from the point p.
+ var dists = math.mul(math.transpose(new float2x4(p1proj, p2proj, p3proj, p4proj)), upNormal);
+ // Calculate the shortest distance to the beam (may be 0 if p is inside the beam).
+ var dist = math.clamp(0, math.cmin(dists), math.cmax(dists));
+ return dist*dist;
+ }
+ }
+
+ public ProjectionParams(NNConstraint constraint, GraphTransform graphTransform) {
+ const float MAX_ERROR_IN_RADIANS = 0.01f;
+
+ // The normal of the plane we are projecting onto (if any).
+ if (constraint != null && constraint.distanceMetric.projectionAxis != Vector3.zero) {
+ // (inf,inf,inf) is a special value indicating to use the graph's natural up direction
+ if (float.IsPositiveInfinity(constraint.distanceMetric.projectionAxis.x)) {
+ projectionAxis = new float3(0, 1, 0);
+ } else {
+ projectionAxis = math.normalizesafe(graphTransform.InverseTransformVector(constraint.distanceMetric.projectionAxis));
+ }
+
+ if (projectionAxis.x*projectionAxis.x + projectionAxis.z*projectionAxis.z < MAX_ERROR_IN_RADIANS*MAX_ERROR_IN_RADIANS) {
+ // We could let the code below handle this case, but since it is a common case we can optimize it a bit
+ // by using a fast-path here.
+ projectedUpNormalized = float2.zero;
+ planeProjection = new float2x3(1, 0, 0, 0, 0, 1); // math.transpose(new float3x2(new float3(1, 0, 0), new float3(0, 0, 1)));
+ distanceMetric = DistanceMetric.ScaledManhattan;
+ alignedWithXZPlaneBacking = (byte)1;
+ distanceScaleAlongProjectionAxis = math.max(constraint.distanceMetric.distanceScaleAlongProjectionDirection, 0);
+ return;
+ }
+
+ // Find any two vectors which are perpendicular to the normal (and each other)
+ var planeAxis1 = math.normalizesafe(math.cross(new float3(1, 0, 1), projectionAxis));
+
+ if (math.all(planeAxis1 == 0)) planeAxis1 = math.normalizesafe(math.cross(new float3(-1, 0, 1), projectionAxis));
+ var planeAxis2 = math.normalizesafe(math.cross(projectionAxis, planeAxis1));
+ // Note: The inverse of an orthogonal matrix is its transpose, and the transpose is faster to compute
+ planeProjection = math.transpose(new float3x2(planeAxis1, planeAxis2));
+ // The projection of the (0,1,0) vector onto the plane.
+ // This is important because the BBTree stores its rectangles in the XZ plane.
+ // If the projection is close enough to the XZ plane, we snap to that because it allows us to use faster and more precise distance calculations.
+ projectedUpNormalized = math.lengthsq(planeProjection.c1) <= MAX_ERROR_IN_RADIANS*MAX_ERROR_IN_RADIANS ? float2.zero : math.normalize(planeProjection.c1);
+ distanceMetric = DistanceMetric.ScaledManhattan;
+ alignedWithXZPlaneBacking = math.all(projectedUpNormalized == 0) ? (byte)1 : (byte)0;
+
+ // The distance along the projection axis is scaled by a cost factor to make the distance
+ // along the projection direction more or less important compared to the distance in the plane.
+ // Usually the projection direction is less important.
+ // For example, when an agent looks for the closest node, it is typically more interested in finding a point close
+ // to it which is more or less directly below it, than it is in finding a point which is closer, but requires sideways movement.
+ // Even if this value is zero we will use the distance along the projection axis to break ties.
+ // Otherwise, when getting the nearest node in e.g. a tall building, it would not be well defined
+ // which floor of the building was closest.
+ distanceScaleAlongProjectionAxis = math.max(constraint.distanceMetric.distanceScaleAlongProjectionDirection, 0);
+ } else {
+ projectionAxis = float3.zero;
+ planeProjection = default;
+ projectedUpNormalized = default;
+ distanceMetric = DistanceMetric.Euclidean;
+ alignedWithXZPlaneBacking = 1;
+ distanceScaleAlongProjectionAxis = 0;
+ }
+ }
+ }
+
+ public float DistanceSqrLowerBound (float3 p, in ProjectionParams projection) {
+ if (tree.Length == 0) return float.PositiveInfinity;
+ return projection.SquaredRectPointDistanceOnPlane(tree[0].rect, p);
+ }
+
+ ///
+ /// Queries the tree for the closest node to p constrained by the NNConstraint trying to improve an existing solution.
+ /// Note that this function will only fill in the constrained node.
+ /// If you want a node not constrained by any NNConstraint, do an additional search with constraint = NNConstraint.None
+ ///
+ /// Point to search around
+ /// Optionally set to constrain which nodes to return
+ /// The best squared distance for the previous solution. Will be updated with the best distance
+ /// after this search. Supply positive infinity to start the search from scratch.
+ /// This search will start from the previous NNInfo and improve it if possible. Will be updated with the new result.
+ /// Even if the search fails on this call, the solution will never be worse than previous.
+ /// The nodes what this BBTree was built from
+ /// The triangles that this BBTree was built from
+ /// The vertices that this BBTree was built from
+ /// Projection parameters derived from the constraint
+ public void QueryClosest (float3 p, NNConstraint constraint, in ProjectionParams projection, ref float distanceSqr, ref NNInfo previous, GraphNode[] nodes, UnsafeSpan triangles, UnsafeSpan vertices) {
+ if (tree.Length == 0) return;
+
+ UnsafeSpan stack;
+ unsafe {
+ NearbyNodesIterator.BoxWithDist* stackPtr = stackalloc NearbyNodesIterator.BoxWithDist[MAX_TREE_HEIGHT];
+ stack = new UnsafeSpan(stackPtr, MAX_TREE_HEIGHT);
+ }
+ stack[0] = new NearbyNodesIterator.BoxWithDist {
+ index = 0,
+ distSqr = 0.0f,
+ };
+ var it = new NearbyNodesIterator {
+ stack = stack,
+ stackSize = 1,
+ indexInLeaf = 0,
+ point = p,
+ projection = projection,
+ distanceThresholdSqr = distanceSqr,
+ tieBreakingDistanceThreshold = float.PositiveInfinity,
+ tree = tree.AsUnsafeSpan(),
+ nodes = nodePermutation.AsUnsafeSpan(),
+ triangles = triangles,
+ vertices = vertices,
+ };
+
+ // We use an iterator which searches through the tree and returns nodes closer than it.distanceThresholdSqr.
+ // The iterator is compiled using burst for high performance, but when a new candidate node is found we need
+ // to evaluate it in pure C# due to the NNConstraint being a C# class.
+ // TODO: If constraint==null (or NNConstraint.None) we could run the whole thing in burst to improve perf even more.
+ var result = previous;
+ while (it.stackSize > 0 && it.MoveNext()) {
+ var current = it.current;
+ if (constraint == null || constraint.Suitable(nodes[current.node])) {
+ it.distanceThresholdSqr = current.distanceSq;
+ it.tieBreakingDistanceThreshold = current.tieBreakingDistance;
+ result = new NNInfo(nodes[current.node], current.closestPointOnNode, current.distanceSq);
+ }
+ }
+ distanceSqr = it.distanceThresholdSqr;
+ previous = result;
+ }
+
+ struct CloseNode {
+ public int node;
+ public float distanceSq;
+ public float tieBreakingDistance;
+ public float3 closestPointOnNode;
+ }
+
+ public enum DistanceMetric: byte {
+ Euclidean,
+ ScaledManhattan,
+ }
+
+ [BurstCompile]
+ struct NearbyNodesIterator : IEnumerator {
+ public UnsafeSpan stack;
+ public int stackSize;
+ public UnsafeSpan tree;
+ public UnsafeSpan nodes;
+ public UnsafeSpan triangles;
+ public UnsafeSpan vertices;
+ public int indexInLeaf;
+ public float3 point;
+ public ProjectionParams projection;
+ public float distanceThresholdSqr;
+ public float tieBreakingDistanceThreshold;
+ internal CloseNode current;
+
+ public CloseNode Current => current;
+
+ public struct BoxWithDist {
+ public int index;
+ public float distSqr;
+ }
+
+ public bool MoveNext () {
+ return MoveNext(ref this);
+ }
+
+ void IDisposable.Dispose () {}
+
+ void System.Collections.IEnumerator.Reset() => throw new NotSupportedException();
+ object System.Collections.IEnumerator.Current => throw new NotSupportedException();
+
+ // Note: Using FloatMode=Fast here can cause NaNs in rare cases.
+ // I have not tracked down why, but it is not unreasonable given that FloatMode=Fast assumes that infinities do not happen.
+ [BurstCompile(FloatMode = FloatMode.Default)]
+ static bool MoveNext (ref NearbyNodesIterator it) {
+ var distanceThresholdSqr = it.distanceThresholdSqr;
+ while (true) {
+ if (it.stackSize == 0) {
+ return false;
+ }
+
+ // Pop the last element from the stack
+ var boxRef = it.stack[it.stackSize-1];
+
+ // If we cannot possibly find anything better than the current best solution in here, skip this box.
+ // Allow the search when we can find an equally close node, because tie breaking
+ // may cause this search to find a better node.
+ if (boxRef.distSqr > distanceThresholdSqr) {
+ it.stackSize--;
+ // Setting this to zero shouldn't be necessary in theory, as a leaf will always (in theory) be searched completely.
+ // However, in practice the distance to a node may be a tiny bit lower than the distance to the box containing the node, due to floating point errors.
+ // and so the leaf's search may be terminated early if a point is found on a node exactly on the border of the box.
+ // In that case it is important that we reset the iterator to the start of the next leaf.
+ it.indexInLeaf = 0;
+ continue;
+ }
+
+ BBTreeBox box = it.tree[boxRef.index];
+ if (box.IsLeaf) {
+ for (int i = it.indexInLeaf; i < MaximumLeafSize; i++) {
+ var node = it.nodes[box.nodeOffset + i];
+ if (node == -1) break;
+ var ti1 = (uint)(node*3 + 0);
+ var ti2 = (uint)(node*3 + 1);
+ var ti3 = (uint)(node*3 + 2);
+ if (ti3 >= it.triangles.length) throw new Exception("Invalid node index");
+ Unity.Burst.CompilerServices.Hint.Assume(ti1 < it.triangles.length && ti2 < it.triangles.length && ti3 < it.triangles.length);
+ var vi1 = it.vertices[it.triangles[ti1]];
+ var vi2 = it.vertices[it.triangles[ti2]];
+ var vi3 = it.vertices[it.triangles[ti3]];
+ if (it.projection.distanceMetric == DistanceMetric.Euclidean) {
+ var v1 = (float3)vi1;
+ var v2 = (float3)vi2;
+ var v3 = (float3)vi3;
+ Polygon.ClosestPointOnTriangleByRef(in v1, in v2, in v3, in it.point, out var closest);
+ var sqrDist = math.distancesq(closest, it.point);
+ if (sqrDist < distanceThresholdSqr) {
+ it.indexInLeaf = i + 1;
+ it.current = new CloseNode {
+ node = node,
+ distanceSq = sqrDist,
+ tieBreakingDistance = 0,
+ closestPointOnNode = closest,
+ };
+ return true;
+ }
+ } else {
+ Polygon.ClosestPointOnTriangleProjected(ref vi1, ref vi2, ref vi3, ref it.projection, ref it.point, out var closest, out var sqrDist, out var distAlongProjection);
+ // Check if this point is better than the previously best point.
+ // Handling ties here is important, in case the navmesh has multiple overlapping regions (e.g. a multi-story building).
+ if (sqrDist < distanceThresholdSqr || (sqrDist == distanceThresholdSqr && distAlongProjection < it.tieBreakingDistanceThreshold)) {
+ it.indexInLeaf = i + 1;
+ it.current = new CloseNode {
+ node = node,
+ distanceSq = sqrDist,
+ tieBreakingDistance = distAlongProjection,
+ closestPointOnNode = closest,
+ };
+ return true;
+ }
+ }
+ }
+ it.indexInLeaf = 0;
+ it.stackSize--;
+ } else {
+ it.stackSize--;
+
+ int first = box.left, second = box.right;
+ var firstDist = it.projection.SquaredRectPointDistanceOnPlane(it.tree[first].rect, it.point);
+ var secondDist = it.projection.SquaredRectPointDistanceOnPlane(it.tree[second].rect, it.point);
+
+ if (secondDist < firstDist) {
+ // Swap
+ Memory.Swap(ref first, ref second);
+ Memory.Swap(ref firstDist, ref secondDist);
+ }
+
+ if (it.stackSize + 2 > it.stack.Length) {
+ throw new InvalidOperationException("Tree is too deep. Overflowed the internal stack.");
+ }
+
+ // Push both children on the stack so that we can explore them later (if they are not too far away).
+ // We push the one with the smallest distance last so that it will be popped first.
+ if (secondDist <= distanceThresholdSqr) it.stack[it.stackSize++] = new BoxWithDist {
+ index = second,
+ distSqr = secondDist,
+ };
+ if (firstDist <= distanceThresholdSqr) it.stack[it.stackSize++] = new BoxWithDist {
+ index = first,
+ distSqr = firstDist,
+ };
+ }
+ }
+ }
+ }
+
+ struct BBTreeBox {
+ public IntRect rect;
+
+ public int nodeOffset;
+ public int left, right;
+
+ public bool IsLeaf => nodeOffset >= 0;
+
+ public BBTreeBox (IntRect rect) {
+ nodeOffset = -1;
+ this.rect = rect;
+ left = right = -1;
+ }
+ }
+
+ public void DrawGizmos (CommandBuilder draw) {
+ Gizmos.color = new Color(1, 1, 1, 0.5F);
+ if (tree.Length == 0) return;
+ DrawGizmos(ref draw, 0, 0);
+ }
+
+ void DrawGizmos (ref CommandBuilder draw, int boxi, int depth) {
+ BBTreeBox box = tree[boxi];
+
+ var min = (Vector3) new Int3(box.rect.xmin, 0, box.rect.ymin);
+ var max = (Vector3) new Int3(box.rect.xmax, 0, box.rect.ymax);
+
+ Vector3 center = (min+max)*0.5F;
+ Vector3 size = max-min;
+
+ size = new Vector3(size.x, 1, size.z);
+ center.y += depth * 2;
+
+ draw.xz.WireRectangle(center, new float2(size.x, size.z), AstarMath.IntToColor(depth, 1f));
+
+ if (!box.IsLeaf) {
+ DrawGizmos(ref draw, box.left, depth + 1);
+ DrawGizmos(ref draw, box.right, depth + 1);
+ }
+ }
+ }
+}
diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/BBTree.cs.meta b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/BBTree.cs.meta
new file mode 100644
index 0000000..9ed7a3e
--- /dev/null
+++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/BBTree.cs.meta
@@ -0,0 +1,7 @@
+fileFormatVersion: 2
+guid: 3a20480c673fd40a5bd2a4cc2206dbc4
+MonoImporter:
+ serializedVersion: 2
+ defaultReferences: []
+ executionOrder: 0
+ icon: {instanceID: 0}
diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/ColliderMeshBuilder2D.cs b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/ColliderMeshBuilder2D.cs
new file mode 100644
index 0000000..98f433f
--- /dev/null
+++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/ColliderMeshBuilder2D.cs
@@ -0,0 +1,336 @@
+using UnityEngine;
+using System.Collections.Generic;
+using Unity.Mathematics;
+using Unity.Collections;
+using Unity.Collections.LowLevel.Unsafe;
+using Unity.Burst;
+using UnityEngine.Assertions;
+using UnityEngine.Profiling;
+using Pathfinding.Util;
+using UnityEngine.Tilemaps;
+
+
+namespace Pathfinding.Graphs.Navmesh {
+ [BurstCompile]
+ public struct CircleGeometryUtilities {
+ ///
+ /// Cached values for CircleRadiusAdjustmentFactor.
+ ///
+ /// We can calculate the area of a polygonized circle, and equate that with the area of a unit circle
+ ///
+ /// x * cos(math.PI / steps) * sin(math.PI/steps) * steps = pi
+ ///
+ /// Solving for the factor that makes them equal (x) gives the expression below.
+ ///
+ /// Generated using the python code:
+ ///
+ /// [math.sqrt(2 * math.pi / (i * math.sin(2 * math.pi / i))) for i in range(3, 23)]
+ ///
+ ///
+ /// It would be nice to generate this using a static constructor, but that is not supported by Unity's burst compiler.
+ ///
+ static readonly float[] circleRadiusAdjustmentFactors = new float[] {
+ 1.56f, 1.25f, 1.15f, 1.1f, 1.07f, 1.05f, 1.04f, 1.03f, 1.03f, 1.02f, 1.02f, 1.02f, 1.01f, 1.01f, 1.01f, 1.01f, 1.01f, 1.01f, 1.01f, 1.01f,
+ };
+
+ /// The number of steps required to get a circle with a maximum error of maxError
+ public static int CircleSteps (Matrix4x4 matrix, float radius, float maxError) {
+ // Take the maximum scale factor among the 3 axes.
+ // If the current matrix has a uniform scale then they are all the same.
+ var maxScaleFactor = math.sqrt(math.max(math.max(math.lengthsq((Vector3)matrix.GetColumn(0)), math.lengthsq((Vector3)matrix.GetColumn(1))), math.lengthsq((Vector3)matrix.GetColumn(2))));
+ var realWorldRadius = radius * maxScaleFactor;
+
+ // This expression is the first taylor expansion term of the formula below.
+ // It is almost identical to the formula below, but it avoids expensive trigonometric functions.
+ // return math.max(3, (int)math.ceil(math.PI * math.sqrt(realWorldRadius / (2*maxError))));
+ var cosAngle = 1 - maxError / realWorldRadius;
+ int steps = math.max(3, (int)math.ceil(math.PI / math.acos(cosAngle)));
+ return steps;
+ }
+
+ ///
+ /// Radius factor to adjust for circle approximation errors.
+ /// If a circle is approximated by fewer segments, it will be slightly smaller than the original circle.
+ /// This factor is used to adjust the radius of the circle so that the resulting circle will have roughly the same area as the original circle.
+ ///
+#if MODULE_COLLECTIONS_2_0_0_OR_NEWER && UNITY_2022_2_OR_NEWER
+ [GenerateTestsForBurstCompatibility]
+#endif
+ public static float CircleRadiusAdjustmentFactor (int steps) {
+ var index = steps - 3;
+ if (index < circleRadiusAdjustmentFactors.Length) {
+ if (index < 0) throw new System.ArgumentOutOfRangeException("Steps must be at least 3");
+ return circleRadiusAdjustmentFactors[index];
+ } else {
+ // Larger steps are approximately one
+ return 1;
+ }
+ }
+ }
+
+ [BurstCompile]
+ public static class ColliderMeshBuilder2D {
+ public static int GenerateMeshesFromColliders (Collider2D[] colliders, int numColliders, float maxError, out NativeArray outputVertices, out NativeArray outputIndices, out NativeArray outputShapeMeshes) {
+ var group = new PhysicsShapeGroup2D();
+ var shapeList = new NativeList(numColliders, Allocator.Temp);
+ var verticesList = new NativeList(numColliders*4, Allocator.Temp);
+ var matricesList = new NativeList(numColliders, Allocator.Temp);
+ var colliderIndexList = new NativeList(numColliders, Allocator.Temp);
+#if ENABLE_UNITY_COLLECTIONS_CHECKS
+ var tempHandle = AtomicSafetyHandle.GetTempMemoryHandle();
+#endif
+ var handledRigidbodies = new HashSet();
+ Profiler.BeginSample("GetShapes");
+
+ // Get the low level physics shapes from all colliders
+ var indexOffset = 0;
+ for (int i = 0; i < numColliders; i++) {
+ var coll = colliders[i];
+ // Prevent errors from being logged when calling GetShapes on a collider that has no shapes
+ if (coll == null || coll.shapeCount == 0) continue;
+
+ var rigid = coll.attachedRigidbody;
+ int shapeCount;
+ if (rigid == null) {
+ if (coll is TilemapCollider2D tilemapColl) {
+ // Ensure the tilemap is up to date
+ tilemapColl.ProcessTilemapChanges();
+ }
+ shapeCount = coll.GetShapes(group);
+ } else if (handledRigidbodies.Add(rigid)) {
+ // Trying to get the shapes from a collider that is attached to a rigidbody will log annoying errors (this seems like a Unity bug tbh),
+ // so we must call GetShapes on the rigidbody instead.
+ shapeCount = rigid.GetShapes(group);
+ } else {
+ continue;
+ }
+ shapeList.Length += shapeCount;
+ verticesList.Length += group.vertexCount;
+ var subShapes = shapeList.AsArray().GetSubArray(shapeList.Length - shapeCount, shapeCount);
+ var subVertices = verticesList.AsArray().GetSubArray(verticesList.Length - group.vertexCount, group.vertexCount);
+ // Using AsArray and then GetSubArray will create an invalid safety handle due to unity limitations.
+ // We work around this by setting the safety handle to a temporary handle.
+#if ENABLE_UNITY_COLLECTIONS_CHECKS
+ NativeArrayUnsafeUtility.SetAtomicSafetyHandle(ref subShapes, tempHandle);
+ NativeArrayUnsafeUtility.SetAtomicSafetyHandle(ref subVertices, tempHandle);
+#endif
+ group.GetShapeData(subShapes, subVertices);
+ for (int j = 0; j < shapeCount; j++) {
+ var shape = subShapes[j];
+ shape.vertexStartIndex += indexOffset;
+ subShapes[j] = shape;
+ }
+ indexOffset += subVertices.Length;
+ matricesList.AddReplicate(group.localToWorldMatrix, shapeCount);
+ colliderIndexList.AddReplicate(i, shapeCount);
+ }
+ Profiler.EndSample();
+ Assert.AreEqual(shapeList.Length, matricesList.Length);
+
+ Profiler.BeginSample("GenerateMeshes");
+ var vertexBuffer = new NativeList(Allocator.Temp);
+ var indexBuffer = new NativeList(Allocator.Temp);
+ var shapeSpan = shapeList.AsUnsafeSpan();
+ var verticesSpan = verticesList.AsUnsafeSpan().Reinterpret();
+ var matricesSpan = matricesList.AsUnsafeSpan();
+ var indexSpan = colliderIndexList.AsUnsafeSpan();
+ outputShapeMeshes = new NativeArray(shapeList.Length, Allocator.Persistent);
+ var outputShapeMeshesSpan = outputShapeMeshes.AsUnsafeSpan();
+ int outputMeshCount;
+ unsafe {
+ outputMeshCount = GenerateMeshesFromShapes(
+ ref shapeSpan,
+ ref verticesSpan,
+ ref matricesSpan,
+ ref indexSpan,
+ ref UnsafeUtility.AsRef >(vertexBuffer.GetUnsafeList()),
+ ref UnsafeUtility.AsRef >(indexBuffer.GetUnsafeList()),
+ ref outputShapeMeshesSpan,
+ maxError
+ );
+ }
+
+ Profiler.EndSample();
+ Profiler.BeginSample("Copy");
+ outputVertices = vertexBuffer.ToArray(Allocator.Persistent);
+ outputIndices = new NativeArray(indexBuffer.AsArray().Reinterpret(12), Allocator.Persistent);
+ Profiler.EndSample();
+ return outputMeshCount;
+ }
+
+ public struct ShapeMesh {
+ public Matrix4x4 matrix;
+ public Bounds bounds;
+ public int startIndex;
+ public int endIndex;
+ public int tag;
+ }
+
+ static void AddCapsuleMesh (float2 c1, float2 c2, ref Matrix4x4 shapeMatrix, float radius, float maxError, ref UnsafeList outputVertices, ref UnsafeList outputIndices, ref float3 mn, ref float3 mx) {
+ var steps = math.max(4, CircleGeometryUtilities.CircleSteps(shapeMatrix, radius, maxError));
+ // We are only generating a semicircle at a time, so reduce the number of steps
+ steps = (steps / 2) + 1;
+ radius = radius * CircleGeometryUtilities.CircleRadiusAdjustmentFactor(2*(steps-1));
+
+ var center1 = new Vector3(c1.x, c1.y, 0);
+ var center2 = new Vector3(c2.x, c2.y, 0);
+ var axis = math.normalizesafe(c2 - c1);
+ var crossAxis = new float2(-axis.y, axis.x);
+ var dx = radius * new Vector3(crossAxis.x, crossAxis.y, 0);
+ var dy = radius * new Vector3(axis.x, axis.y, 0);
+ var angle = math.PI / (steps-1);
+
+ var startVertex = outputVertices.Length;
+ var startVertex2 = startVertex + steps;
+ outputVertices.Length += steps*2;
+ for (int j = 0; j < steps; j++) {
+ math.sincos(angle * j, out var sin, out var cos);
+
+ // Generate first semi-circle
+ var p = center1 + cos * dx - sin * dy;
+ mn = math.min(mn, p);
+ mx = math.max(mx, p);
+ outputVertices[startVertex + j] = p;
+
+ // Generate second semi-circle
+ p = center2 - cos * dx + sin * dy;
+ mn = math.min(mn, p);
+ mx = math.max(mx, p);
+ outputVertices[startVertex2 + j] = p;
+ }
+ var startIndex = outputIndices.Length;
+ var startIndex2 = startIndex + steps-2;
+ outputIndices.Length += (steps-2)*2;
+ for (int j = 1; j < steps - 1; j++) {
+ // Triangle for first semi-circle
+ outputIndices[startIndex + j - 1] = new int3(startVertex, startVertex + j, startVertex + j + 1);
+ // Triangle for second semi-circle
+ outputIndices[startIndex2 + j - 1] = new int3(startVertex2, startVertex2 + j, startVertex2 + j + 1);
+ }
+
+ // Generate the connection between the two semi-circles
+ outputIndices.Add(new int3(startVertex, startVertex + steps - 1, startVertex2));
+ outputIndices.Add(new int3(startVertex, startVertex2, startVertex2 + steps - 1));
+ }
+
+ [BurstCompile]
+ public static int GenerateMeshesFromShapes (
+ ref UnsafeSpan shapes,
+ ref UnsafeSpan vertices,
+ ref UnsafeSpan shapeMatrices,
+ ref UnsafeSpan groupIndices,
+ ref UnsafeList outputVertices,
+ ref UnsafeList outputIndices,
+ ref UnsafeSpan outputShapeMeshes,
+ float maxError
+ ) {
+ var groupStartIndex = 0;
+ var mn = new float3(float.MaxValue, float.MaxValue, float.MaxValue);
+ var mx = new float3(float.MinValue, float.MinValue, float.MinValue);
+ int outputMeshIndex = 0;
+ for (int i = 0; i < shapes.Length; i++) {
+ var shape = shapes[i];
+ var shapeVertices = vertices.Slice(shape.vertexStartIndex, shape.vertexCount);
+ var shapeMatrix = shapeMatrices[i];
+ switch (shape.shapeType) {
+ case PhysicsShapeType2D.Circle: {
+ var steps = CircleGeometryUtilities.CircleSteps(shapeMatrix, shape.radius, maxError);
+ var radius = shape.radius * CircleGeometryUtilities.CircleRadiusAdjustmentFactor(steps);
+ var center = new Vector3(shapeVertices[0].x, shapeVertices[0].y, 0);
+ var d1 = new Vector3(radius, 0, 0);
+ var d2 = new Vector3(0, radius, 0);
+ var angle = 2 * math.PI / steps;
+ var startVertex = outputVertices.Length;
+ for (int j = 0; j < steps; j++) {
+ math.sincos(angle * j, out var sin, out var cos);
+ var p = center + cos * d1 + sin * d2;
+ mn = math.min(mn, p);
+ mx = math.max(mx, p);
+ outputVertices.Add(p);
+ }
+ for (int j = 1; j < steps; j++) {
+ outputIndices.Add(new int3(startVertex, startVertex + j, startVertex + (j + 1) % steps));
+ }
+ break;
+ }
+ case PhysicsShapeType2D.Capsule: {
+ var c1 = shapeVertices[0];
+ var c2 = shapeVertices[1];
+ AddCapsuleMesh(c1, c2, ref shapeMatrix, shape.radius, maxError, ref outputVertices, ref outputIndices, ref mn, ref mx);
+ break;
+ }
+ case PhysicsShapeType2D.Polygon: {
+ var startVertex = outputVertices.Length;
+ outputVertices.Resize(startVertex + shape.vertexCount, NativeArrayOptions.UninitializedMemory);
+ for (int j = 0; j < shape.vertexCount; j++) {
+ var p = new Vector3(shapeVertices[j].x, shapeVertices[j].y, 0);
+ mn = math.min(mn, p);
+ mx = math.max(mx, p);
+ outputVertices[startVertex + j] = p;
+ }
+ outputIndices.SetCapacity(math.ceilpow2(outputIndices.Length + (shape.vertexCount - 2)));
+ for (int j = 1; j < shape.vertexCount - 1; j++) {
+ outputIndices.AddNoResize(new int3(startVertex, startVertex + j, startVertex + j + 1));
+ }
+ break;
+ }
+ case PhysicsShapeType2D.Edges: {
+ if (shape.radius > maxError) {
+ for (int j = 0; j < shape.vertexCount - 1; j++) {
+ AddCapsuleMesh(shapeVertices[j], shapeVertices[j+1], ref shapeMatrix, shape.radius, maxError, ref outputVertices, ref outputIndices, ref mn, ref mx);
+ }
+ } else {
+ var startVertex = outputVertices.Length;
+ outputVertices.Resize(startVertex + shape.vertexCount, NativeArrayOptions.UninitializedMemory);
+ for (int j = 0; j < shape.vertexCount; j++) {
+ var p = new Vector3(shapeVertices[j].x, shapeVertices[j].y, 0);
+ mn = math.min(mn, p);
+ mx = math.max(mx, p);
+ outputVertices[startVertex + j] = p;
+ }
+ outputIndices.SetCapacity(math.ceilpow2(outputIndices.Length + (shape.vertexCount - 1)));
+ for (int j = 0; j < shape.vertexCount - 1; j++) {
+ // An edge is represented by a degenerate triangle
+ outputIndices.AddNoResize(new int3(startVertex + j, startVertex + j + 1, startVertex + j + 1));
+ }
+ }
+ break;
+ }
+ default:
+ throw new System.Exception("Unexpected PhysicsShapeType2D");
+ }
+
+ // Merge shapes which are in the same group into a single ShapeMesh struct.
+ // This is done to reduce the per-shape overhead a bit.
+ // Don't do it too much, though, since that can cause filtering to not work too well.
+ // For example if a recast graph recalculates a single tile in a 2D scene, we don't want to include the whole collider for the
+ // TilemapCollider2D in the scene when doing rasterization, only the shapes around the tile that is recalculated.
+ // We will still process the whole TilemapCollider2D (no way around that), but we want to be able to exclude shapes shapes as quickly as possible
+ // based on their bounding boxes.
+ const int DesiredTrianglesPerGroup = 100;
+ if (i == shapes.Length - 1 || groupIndices[i] != groupIndices[i+1] || outputIndices.Length - groupStartIndex > DesiredTrianglesPerGroup) {
+ // Transform the bounding box to world space
+ // This is not the tightest bounding box, but it is good enough
+ var m = new ToWorldMatrix(new float3x3((float4x4)shapeMatrix));
+ var bounds = new Bounds((mn + mx)*0.5f, mx - mn);
+ bounds = m.ToWorld(bounds);
+ bounds.center += (Vector3)shapeMatrix.GetColumn(3);
+
+ outputShapeMeshes[outputMeshIndex++] = new ShapeMesh {
+ bounds = bounds,
+ matrix = shapeMatrix,
+ startIndex = groupStartIndex * 3,
+ endIndex = outputIndices.Length * 3,
+ tag = groupIndices[i]
+ };
+
+ mn = new float3(float.MaxValue, float.MaxValue, float.MaxValue);
+ mx = new float3(float.MinValue, float.MinValue, float.MinValue);
+ groupStartIndex = outputIndices.Length;
+ }
+ }
+
+ return outputMeshIndex;
+ }
+ }
+}
diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/ColliderMeshBuilder2D.cs.meta b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/ColliderMeshBuilder2D.cs.meta
new file mode 100644
index 0000000..12bd06e
--- /dev/null
+++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/ColliderMeshBuilder2D.cs.meta
@@ -0,0 +1,11 @@
+fileFormatVersion: 2
+guid: 65d5806c4978b7e46b69297ca838f91c
+MonoImporter:
+ externalObjects: {}
+ serializedVersion: 2
+ defaultReferences: []
+ executionOrder: 0
+ icon: {instanceID: 0}
+ userData:
+ assetBundleName:
+ assetBundleVariant:
diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs.meta b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs.meta
new file mode 100644
index 0000000..6867f71
--- /dev/null
+++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs.meta
@@ -0,0 +1,8 @@
+fileFormatVersion: 2
+guid: 7d87dc471eec3ae4dac67ee232391350
+folderAsset: yes
+DefaultImporter:
+ externalObjects: {}
+ userData:
+ assetBundleName:
+ assetBundleVariant:
diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobBuildNodes.cs b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobBuildNodes.cs
new file mode 100644
index 0000000..841c86d
--- /dev/null
+++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobBuildNodes.cs
@@ -0,0 +1,92 @@
+using Pathfinding.Jobs;
+using Pathfinding.Util;
+using Unity.Collections;
+using Unity.Jobs;
+using UnityEngine;
+using UnityEngine.Profiling;
+
+namespace Pathfinding.Graphs.Navmesh.Jobs {
+ ///
+ /// Builds nodes and tiles and prepares them for pathfinding.
+ ///
+ /// Takes input from a job and outputs a .
+ ///
+ /// This job takes the following steps:
+ /// - Calculate connections between nodes inside each tile
+ /// - Create node and tile objects
+ /// - Connect adjacent tiles together
+ ///
+ public struct JobBuildNodes {
+ AstarPath astar;
+ uint graphIndex;
+ public uint initialPenalty;
+ public bool recalculateNormals;
+ public float maxTileConnectionEdgeDistance;
+ Matrix4x4 graphToWorldSpace;
+ TileLayout tileLayout;
+
+ public class BuildNodeTilesOutput : IProgress, System.IDisposable {
+ public TileBuilder.TileBuilderOutput dependency;
+ public NavmeshTile[] tiles;
+
+ public float Progress => dependency.Progress;
+
+ public void Dispose () {
+ }
+ }
+
+ internal JobBuildNodes(RecastGraph graph, TileLayout tileLayout) {
+ this.astar = graph.active;
+ this.tileLayout = tileLayout;
+ this.graphIndex = graph.graphIndex;
+ this.initialPenalty = graph.initialPenalty;
+ this.recalculateNormals = graph.RecalculateNormals;
+ this.maxTileConnectionEdgeDistance = graph.MaxTileConnectionEdgeDistance;
+ this.graphToWorldSpace = tileLayout.transform.matrix;
+ }
+
+ public Promise Schedule (DisposeArena arena, Promise dependency) {
+ var input = dependency.GetValue();
+ var tileRect = input.tileMeshes.tileRect;
+ UnityEngine.Assertions.Assert.AreEqual(input.tileMeshes.tileMeshes.Length, tileRect.Area);
+ var tiles = new NavmeshTile[tileRect.Area];
+ var tilesGCHandle = System.Runtime.InteropServices.GCHandle.Alloc(tiles);
+ var nodeConnections = new NativeArray(tileRect.Area, Allocator.Persistent);
+
+ var calculateConnectionsJob = new JobCalculateTriangleConnections {
+ tileMeshes = input.tileMeshes.tileMeshes,
+ nodeConnections = nodeConnections,
+ }.Schedule(dependency.handle);
+
+ var tileWorldSize = new Vector2(tileLayout.TileWorldSizeX, tileLayout.TileWorldSizeZ);
+ var createTilesJob = new JobCreateTiles {
+ tileMeshes = input.tileMeshes.tileMeshes,
+ tiles = tilesGCHandle,
+ tileRect = tileRect,
+ graphTileCount = tileLayout.tileCount,
+ graphIndex = graphIndex,
+ initialPenalty = initialPenalty,
+ recalculateNormals = recalculateNormals,
+ graphToWorldSpace = this.graphToWorldSpace,
+ tileWorldSize = tileWorldSize,
+ }.Schedule(dependency.handle);
+
+ var applyConnectionsJob = new JobWriteNodeConnections {
+ nodeConnections = nodeConnections,
+ tiles = tilesGCHandle,
+ }.Schedule(JobHandle.CombineDependencies(calculateConnectionsJob, createTilesJob));
+
+ Profiler.BeginSample("Scheduling ConnectTiles");
+ var connectTilesDependency = JobConnectTiles.ScheduleBatch(tilesGCHandle, applyConnectionsJob, tileRect, tileWorldSize, maxTileConnectionEdgeDistance);
+ Profiler.EndSample();
+
+ arena.Add(tilesGCHandle);
+ arena.Add(nodeConnections);
+
+ return new Promise(connectTilesDependency, new BuildNodeTilesOutput {
+ dependency = input,
+ tiles = tiles,
+ });
+ }
+ }
+}
diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobBuildNodes.cs.meta b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobBuildNodes.cs.meta
new file mode 100644
index 0000000..c8446f5
--- /dev/null
+++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobBuildNodes.cs.meta
@@ -0,0 +1,11 @@
+fileFormatVersion: 2
+guid: bd51eca97d285874d997d22edd420a27
+MonoImporter:
+ externalObjects: {}
+ serializedVersion: 2
+ defaultReferences: []
+ executionOrder: 0
+ icon: {instanceID: 0}
+ userData:
+ assetBundleName:
+ assetBundleVariant:
diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobBuildTileMeshFromVertices.cs b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobBuildTileMeshFromVertices.cs
new file mode 100644
index 0000000..f68ed2b
--- /dev/null
+++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobBuildTileMeshFromVertices.cs
@@ -0,0 +1,105 @@
+using Pathfinding.Util;
+using Unity.Burst;
+using Unity.Collections;
+using Unity.Collections.LowLevel.Unsafe;
+using Unity.Jobs;
+using UnityEngine;
+
+namespace Pathfinding.Graphs.Navmesh.Jobs {
+ ///
+ /// Builds tiles from raw mesh vertices and indices.
+ ///
+ /// This job takes the following steps:
+ /// - Transform all vertices using the matrix.
+ /// - Remove duplicate vertices
+ /// - If is enabled: ensure all triangles are laid out in the clockwise direction.
+ ///
+ [BurstCompile(FloatMode = FloatMode.Default)]
+ public struct JobBuildTileMeshFromVertices : IJob {
+ public NativeArray vertices;
+ public NativeArray indices;
+ public Matrix4x4 meshToGraph;
+ public NativeArray outputBuffers;
+ public bool recalculateNormals;
+
+
+ [BurstCompile(FloatMode = FloatMode.Fast)]
+ public struct JobTransformTileCoordinates : IJob {
+ public NativeArray vertices;
+ public NativeArray outputVertices;
+ public Matrix4x4 matrix;
+
+ public void Execute () {
+ for (int i = 0; i < vertices.Length; i++) {
+ outputVertices[i] = (Int3)matrix.MultiplyPoint3x4(vertices[i]);
+ }
+ }
+ }
+
+ public struct BuildNavmeshOutput : IProgress, System.IDisposable {
+ public NativeArray tiles;
+
+ public float Progress => 0.0f;
+
+ public void Dispose () {
+ for (int i = 0; i < tiles.Length; i++) tiles[i].Dispose();
+ tiles.Dispose();
+ }
+ }
+
+ public static Promise Schedule (NativeArray vertices, NativeArray indices, Matrix4x4 meshToGraph, bool recalculateNormals) {
+ if (vertices.Length > NavmeshBase.VertexIndexMask) throw new System.ArgumentException("Too many vertices in the navmesh graph. Provided " + vertices.Length + ", but the maximum number of vertices per tile is " + NavmeshBase.VertexIndexMask + ". You can raise this limit by enabling ASTAR_RECAST_LARGER_TILES in the A* Inspector Optimizations tab");
+
+ var outputBuffers = new NativeArray(1, Allocator.Persistent);
+
+ var job = new JobBuildTileMeshFromVertices {
+ vertices = vertices,
+ indices = indices,
+ meshToGraph = meshToGraph,
+ outputBuffers = outputBuffers,
+ recalculateNormals = recalculateNormals,
+ }.Schedule();
+ return new Promise(job, new BuildNavmeshOutput {
+ tiles = outputBuffers,
+ });
+ }
+
+ public void Execute () {
+ var int3vertices = new NativeArray(vertices.Length, Allocator.Temp);
+ var tags = new NativeArray(indices.Length / 3, Allocator.Temp, NativeArrayOptions.ClearMemory);
+
+ new JobTransformTileCoordinates {
+ vertices = vertices,
+ outputVertices = int3vertices,
+ matrix = meshToGraph,
+ }.Execute();
+
+ unsafe {
+ UnityEngine.Assertions.Assert.IsTrue(this.outputBuffers.Length == 1);
+ var tile = (TileMesh.TileMeshUnsafe*) this.outputBuffers.GetUnsafePtr();
+ var outputVertices = &tile->verticesInTileSpace;
+ var outputTriangles = &tile->triangles;
+ var outputTags = &tile->tags;
+ *outputVertices = new UnsafeAppendBuffer(0, 4, Allocator.Persistent);
+ *outputTriangles = new UnsafeAppendBuffer(0, 4, Allocator.Persistent);
+ *outputTags = new UnsafeAppendBuffer(0, 4, Allocator.Persistent);
+ new MeshUtility.JobRemoveDuplicateVertices {
+ vertices = int3vertices,
+ triangles = indices,
+ tags = tags,
+ outputVertices = outputVertices,
+ outputTriangles = outputTriangles,
+ outputTags = outputTags,
+ }.Execute();
+
+ if (recalculateNormals) {
+ var verticesSpan = outputVertices->AsUnsafeSpan();
+ var trianglesSpan = outputTriangles->AsUnsafeSpan();
+ MeshUtility.MakeTrianglesClockwise(ref verticesSpan, ref trianglesSpan);
+ }
+ }
+
+ int3vertices.Dispose();
+ }
+ }
+}
diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobBuildTileMeshFromVertices.cs.meta b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobBuildTileMeshFromVertices.cs.meta
new file mode 100644
index 0000000..b7f6886
--- /dev/null
+++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobBuildTileMeshFromVertices.cs.meta
@@ -0,0 +1,11 @@
+fileFormatVersion: 2
+guid: a22b53fa064d9344988e2a86b73851b1
+MonoImporter:
+ externalObjects: {}
+ serializedVersion: 2
+ defaultReferences: []
+ executionOrder: 0
+ icon: {instanceID: 0}
+ userData:
+ assetBundleName:
+ assetBundleVariant:
diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobBuildTileMeshFromVoxels.cs b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobBuildTileMeshFromVoxels.cs
new file mode 100644
index 0000000..a6ca868
--- /dev/null
+++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobBuildTileMeshFromVoxels.cs
@@ -0,0 +1,288 @@
+using Pathfinding.Jobs;
+using Pathfinding.Util;
+using Pathfinding.Graphs.Navmesh.Voxelization.Burst;
+using Unity.Burst;
+using Unity.Collections;
+using Unity.Collections.LowLevel.Unsafe;
+using Unity.Jobs;
+using UnityEngine;
+using Unity.Profiling;
+
+namespace Pathfinding.Graphs.Navmesh.Jobs {
+ ///
+ /// Scratch space for building navmesh tiles using voxelization.
+ ///
+ /// This uses quite a lot of memory, so it is used by a single worker thread for multiple tiles in order to minimize allocations.
+ ///
+ public struct TileBuilderBurst : IArenaDisposable {
+ public LinkedVoxelField linkedVoxelField;
+ public CompactVoxelField compactVoxelField;
+ public NativeList distanceField;
+ public NativeQueue tmpQueue1;
+ public NativeQueue tmpQueue2;
+ public NativeList contours;
+ public NativeList contourVertices;
+ public VoxelMesh voxelMesh;
+
+ public TileBuilderBurst (int width, int depth, int voxelWalkableHeight, int maximumVoxelYCoord) {
+ linkedVoxelField = new LinkedVoxelField(width, depth, maximumVoxelYCoord);
+ compactVoxelField = new CompactVoxelField(width, depth, voxelWalkableHeight, Allocator.Persistent);
+ tmpQueue1 = new NativeQueue(Allocator.Persistent);
+ tmpQueue2 = new NativeQueue(Allocator.Persistent);
+ distanceField = new NativeList(0, Allocator.Persistent);
+ contours = new NativeList(Allocator.Persistent);
+ contourVertices = new NativeList(Allocator.Persistent);
+ voxelMesh = new VoxelMesh {
+ verts = new NativeList(Allocator.Persistent),
+ tris = new NativeList(Allocator.Persistent),
+ areas = new NativeList(Allocator.Persistent),
+ };
+ }
+
+ void IArenaDisposable.DisposeWith (DisposeArena arena) {
+ arena.Add(linkedVoxelField);
+ arena.Add(compactVoxelField);
+ arena.Add(distanceField);
+ arena.Add(tmpQueue1);
+ arena.Add(tmpQueue2);
+ arena.Add(contours);
+ arena.Add(contourVertices);
+ arena.Add(voxelMesh);
+ }
+ }
+
+ ///
+ /// Builds tiles from a polygon soup using voxelization.
+ ///
+ /// This job takes the following steps:
+ /// - Voxelize the input meshes
+ /// - Filter and process the resulting voxelization in various ways to remove unwanted artifacts and make it better suited for pathfinding.
+ /// - Extract a walkable surface from the voxelization.
+ /// - Triangulate this surface and create navmesh tiles from it.
+ ///
+ /// This job uses work stealing to distribute the work between threads. The communication happens using a shared queue and the atomic variable.
+ ///
+ [BurstCompile(CompileSynchronously = true)]
+ // TODO: [BurstCompile(FloatMode = FloatMode.Fast)]
+ public struct JobBuildTileMeshFromVoxels : IJob {
+ public TileBuilderBurst tileBuilder;
+ [ReadOnly]
+ public TileBuilder.BucketMapping inputMeshes;
+ [ReadOnly]
+ public NativeArray tileGraphSpaceBounds;
+ public Matrix4x4 voxelToTileSpace;
+
+ ///
+ /// Limits of the graph space bounds for the whole graph on the XZ plane.
+ ///
+ /// Used to crop the border tiles to exactly the limits of the graph's bounding box.
+ ///
+ public Vector2 graphSpaceLimits;
+
+ [NativeDisableUnsafePtrRestriction]
+ public unsafe TileMesh.TileMeshUnsafe* outputMeshes;
+
+ /// Max number of tiles to process in this job
+ public int maxTiles;
+
+ public int voxelWalkableClimb;
+ public uint voxelWalkableHeight;
+ public float cellSize;
+ public float cellHeight;
+ public float maxSlope;
+ public RecastGraph.DimensionMode dimensionMode;
+ public RecastGraph.BackgroundTraversability backgroundTraversability;
+ public Matrix4x4 graphToWorldSpace;
+ public int characterRadiusInVoxels;
+ public int tileBorderSizeInVoxels;
+ public int minRegionSize;
+ public float maxEdgeLength;
+ public float contourMaxError;
+ [ReadOnly]
+ public NativeArray relevantGraphSurfaces;
+ public RecastGraph.RelevantGraphSurfaceMode relevantGraphSurfaceMode;
+
+ [NativeDisableUnsafePtrRestriction]
+ public unsafe int* currentTileCounter;
+
+ public void SetOutputMeshes (NativeArray arr) {
+ unsafe {
+ outputMeshes = (TileMesh.TileMeshUnsafe*)arr.GetUnsafeReadOnlyPtr();
+ }
+ }
+
+ public void SetCounter (NativeReference counter) {
+ unsafe {
+ // Note: The pointer cast is only necessary when using early versions of the collections package.
+ currentTileCounter = (int*)counter.GetUnsafePtr();
+ }
+ }
+
+ private static readonly ProfilerMarker MarkerVoxelize = new ProfilerMarker("Voxelize");
+ private static readonly ProfilerMarker MarkerFilterLedges = new ProfilerMarker("FilterLedges");
+ private static readonly ProfilerMarker MarkerFilterLowHeightSpans = new ProfilerMarker("FilterLowHeightSpans");
+ private static readonly ProfilerMarker MarkerBuildCompactField = new ProfilerMarker("BuildCompactField");
+ private static readonly ProfilerMarker MarkerBuildConnections = new ProfilerMarker("BuildConnections");
+ private static readonly ProfilerMarker MarkerErodeWalkableArea = new ProfilerMarker("ErodeWalkableArea");
+ private static readonly ProfilerMarker MarkerBuildDistanceField = new ProfilerMarker("BuildDistanceField");
+ private static readonly ProfilerMarker MarkerBuildRegions = new ProfilerMarker("BuildRegions");
+ private static readonly ProfilerMarker MarkerBuildContours = new ProfilerMarker("BuildContours");
+ private static readonly ProfilerMarker MarkerBuildMesh = new ProfilerMarker("BuildMesh");
+ private static readonly ProfilerMarker MarkerConvertAreasToTags = new ProfilerMarker("ConvertAreasToTags");
+ private static readonly ProfilerMarker MarkerRemoveDuplicateVertices = new ProfilerMarker("RemoveDuplicateVertices");
+ private static readonly ProfilerMarker MarkerTransformTileCoordinates = new ProfilerMarker("TransformTileCoordinates");
+
+ public void Execute () {
+ for (int k = 0; k < maxTiles; k++) {
+ // Grab the next tile index that we should calculate
+ int i;
+ unsafe {
+ i = System.Threading.Interlocked.Increment(ref UnsafeUtility.AsRef(currentTileCounter)) - 1;
+ }
+ if (i >= tileGraphSpaceBounds.Length) return;
+
+ tileBuilder.linkedVoxelField.ResetLinkedVoxelSpans();
+ if (dimensionMode == RecastGraph.DimensionMode.Dimension2D && backgroundTraversability == RecastGraph.BackgroundTraversability.Walkable) {
+ tileBuilder.linkedVoxelField.SetWalkableBackground();
+ }
+
+ var bucketStart = i > 0 ? inputMeshes.bucketRanges[i-1] : 0;
+ var bucketEnd = inputMeshes.bucketRanges[i];
+ MarkerVoxelize.Begin();
+ new JobVoxelize {
+ inputMeshes = inputMeshes.meshes,
+ bucket = inputMeshes.pointers.GetSubArray(bucketStart, bucketEnd - bucketStart),
+ voxelWalkableClimb = voxelWalkableClimb,
+ voxelWalkableHeight = voxelWalkableHeight,
+ cellSize = cellSize,
+ cellHeight = cellHeight,
+ maxSlope = maxSlope,
+ graphTransform = graphToWorldSpace,
+ graphSpaceBounds = tileGraphSpaceBounds[i],
+ graphSpaceLimits = graphSpaceLimits,
+ voxelArea = tileBuilder.linkedVoxelField,
+ }.Execute();
+ MarkerVoxelize.End();
+
+
+
+ MarkerFilterLedges.Begin();
+ new JobFilterLedges {
+ field = tileBuilder.linkedVoxelField,
+ voxelWalkableClimb = voxelWalkableClimb,
+ voxelWalkableHeight = voxelWalkableHeight,
+ cellSize = cellSize,
+ cellHeight = cellHeight,
+ }.Execute();
+ MarkerFilterLedges.End();
+
+ MarkerFilterLowHeightSpans.Begin();
+ new JobFilterLowHeightSpans {
+ field = tileBuilder.linkedVoxelField,
+ voxelWalkableHeight = voxelWalkableHeight,
+ }.Execute();
+ MarkerFilterLowHeightSpans.End();
+
+ MarkerBuildCompactField.Begin();
+ new JobBuildCompactField {
+ input = tileBuilder.linkedVoxelField,
+ output = tileBuilder.compactVoxelField,
+ }.Execute();
+ MarkerBuildCompactField.End();
+
+ MarkerBuildConnections.Begin();
+ new JobBuildConnections {
+ field = tileBuilder.compactVoxelField,
+ voxelWalkableHeight = (int)voxelWalkableHeight,
+ voxelWalkableClimb = voxelWalkableClimb,
+ }.Execute();
+ MarkerBuildConnections.End();
+
+ MarkerErodeWalkableArea.Begin();
+ new JobErodeWalkableArea {
+ field = tileBuilder.compactVoxelField,
+ radius = characterRadiusInVoxels,
+ }.Execute();
+ MarkerErodeWalkableArea.End();
+
+ MarkerBuildDistanceField.Begin();
+ new JobBuildDistanceField {
+ field = tileBuilder.compactVoxelField,
+ output = tileBuilder.distanceField,
+ }.Execute();
+ MarkerBuildDistanceField.End();
+
+ MarkerBuildRegions.Begin();
+ new JobBuildRegions {
+ field = tileBuilder.compactVoxelField,
+ distanceField = tileBuilder.distanceField,
+ borderSize = tileBorderSizeInVoxels,
+ minRegionSize = Mathf.RoundToInt(minRegionSize),
+ srcQue = tileBuilder.tmpQueue1,
+ dstQue = tileBuilder.tmpQueue2,
+ relevantGraphSurfaces = relevantGraphSurfaces,
+ relevantGraphSurfaceMode = relevantGraphSurfaceMode,
+ cellSize = cellSize,
+ cellHeight = cellHeight,
+ graphTransform = graphToWorldSpace,
+ graphSpaceBounds = tileGraphSpaceBounds[i],
+ }.Execute();
+ MarkerBuildRegions.End();
+
+ MarkerBuildContours.Begin();
+ new JobBuildContours {
+ field = tileBuilder.compactVoxelField,
+ maxError = contourMaxError,
+ maxEdgeLength = maxEdgeLength,
+ buildFlags = VoxelUtilityBurst.RC_CONTOUR_TESS_WALL_EDGES | VoxelUtilityBurst.RC_CONTOUR_TESS_TILE_EDGES,
+ cellSize = cellSize,
+ outputContours = tileBuilder.contours,
+ outputVerts = tileBuilder.contourVertices,
+ }.Execute();
+ MarkerBuildContours.End();
+
+ MarkerBuildMesh.Begin();
+ new JobBuildMesh {
+ contours = tileBuilder.contours,
+ contourVertices = tileBuilder.contourVertices,
+ mesh = tileBuilder.voxelMesh,
+ field = tileBuilder.compactVoxelField,
+ }.Execute();
+ MarkerBuildMesh.End();
+
+ unsafe {
+ TileMesh.TileMeshUnsafe* outputTileMesh = outputMeshes + i;
+ *outputTileMesh = new TileMesh.TileMeshUnsafe {
+ verticesInTileSpace = new UnsafeAppendBuffer(0, 4, Allocator.Persistent),
+ triangles = new UnsafeAppendBuffer(0, 4, Allocator.Persistent),
+ tags = new UnsafeAppendBuffer(0, 4, Allocator.Persistent),
+ };
+
+ MarkerConvertAreasToTags.Begin();
+ new JobConvertAreasToTags {
+ areas = tileBuilder.voxelMesh.areas,
+ }.Execute();
+ MarkerConvertAreasToTags.End();
+
+ MarkerRemoveDuplicateVertices.Begin();
+ new MeshUtility.JobRemoveDuplicateVertices {
+ vertices = tileBuilder.voxelMesh.verts.AsArray(),
+ triangles = tileBuilder.voxelMesh.tris.AsArray(),
+ tags = tileBuilder.voxelMesh.areas.AsArray(),
+ outputTags = &outputTileMesh->tags,
+ outputVertices = &outputTileMesh->verticesInTileSpace,
+ outputTriangles = &outputTileMesh->triangles,
+ }.Execute();
+ MarkerRemoveDuplicateVertices.End();
+
+ MarkerTransformTileCoordinates.Begin();
+ new JobTransformTileCoordinates {
+ vertices = &outputTileMesh->verticesInTileSpace,
+ matrix = voxelToTileSpace,
+ }.Execute();
+ MarkerTransformTileCoordinates.End();
+ }
+ }
+ }
+ }
+}
diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobBuildTileMeshFromVoxels.cs.meta b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobBuildTileMeshFromVoxels.cs.meta
new file mode 100644
index 0000000..4e77298
--- /dev/null
+++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobBuildTileMeshFromVoxels.cs.meta
@@ -0,0 +1,11 @@
+fileFormatVersion: 2
+guid: 20aeb827260a74a4492e7687fdebb14f
+MonoImporter:
+ externalObjects: {}
+ serializedVersion: 2
+ defaultReferences: []
+ executionOrder: 0
+ icon: {instanceID: 0}
+ userData:
+ assetBundleName:
+ assetBundleVariant:
diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobCalculateTriangleConnections.cs b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobCalculateTriangleConnections.cs
new file mode 100644
index 0000000..b0da1ed
--- /dev/null
+++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobCalculateTriangleConnections.cs
@@ -0,0 +1,73 @@
+using Unity.Burst;
+using Unity.Collections;
+using Unity.Jobs;
+using Unity.Mathematics;
+using UnityEngine.Assertions;
+
+namespace Pathfinding.Graphs.Navmesh.Jobs {
+ ///
+ /// Calculates node connections between triangles within each tile.
+ /// Connections between tiles are handled at a later stage in .
+ ///
+ [BurstCompile]
+ public struct JobCalculateTriangleConnections : IJob {
+ [ReadOnly]
+ public NativeArray tileMeshes;
+ [WriteOnly]
+ public NativeArray nodeConnections;
+
+ public struct TileNodeConnectionsUnsafe {
+ /// Stream of packed connection edge infos (from )
+ public Unity.Collections.LowLevel.Unsafe.UnsafeAppendBuffer neighbours;
+ /// Number of neighbours for each triangle
+ public Unity.Collections.LowLevel.Unsafe.UnsafeAppendBuffer neighbourCounts;
+ }
+
+ public void Execute () {
+ Assert.AreEqual(tileMeshes.Length, nodeConnections.Length);
+
+ var nodeRefs = new NativeParallelHashMap(128, Allocator.Temp);
+ bool duplicates = false;
+ for (int ti = 0; ti < tileMeshes.Length; ti++) {
+ nodeRefs.Clear();
+ var tile = tileMeshes[ti];
+ var numIndices = tile.triangles.Length / sizeof(int);
+ var neighbours = new Unity.Collections.LowLevel.Unsafe.UnsafeAppendBuffer(numIndices * 2 * 4, 4, Allocator.Persistent);
+ var neighbourCounts = new Unity.Collections.LowLevel.Unsafe.UnsafeAppendBuffer(numIndices * 4, 4, Allocator.Persistent);
+ const int TriangleIndexBits = 28;
+ unsafe {
+ Assert.IsTrue(numIndices % 3 == 0);
+ var triangles = (int*)tile.triangles.Ptr;
+ for (int i = 0, j = 0; i < numIndices; i += 3, j++) {
+ duplicates |= !nodeRefs.TryAdd(new int2(triangles[i+0], triangles[i+1]), (uint)j | (0 << TriangleIndexBits));
+ duplicates |= !nodeRefs.TryAdd(new int2(triangles[i+1], triangles[i+2]), (uint)j | (1 << TriangleIndexBits));
+ duplicates |= !nodeRefs.TryAdd(new int2(triangles[i+2], triangles[i+0]), (uint)j | (2 << TriangleIndexBits));
+ }
+
+ for (int i = 0; i < numIndices; i += 3) {
+ var cnt = 0;
+ for (int edge = 0; edge < 3; edge++) {
+ if (nodeRefs.TryGetValue(new int2(triangles[i+((edge+1) % 3)], triangles[i+edge]), out var match)) {
+ var other = match & ((1 << TriangleIndexBits) - 1);
+ var otherEdge = (int)(match >> TriangleIndexBits);
+ neighbours.Add(other);
+ var edgeInfo = Connection.PackShapeEdgeInfo((byte)edge, (byte)otherEdge, true, true, true);
+ neighbours.Add((int)edgeInfo);
+ cnt += 1;
+ }
+ }
+ neighbourCounts.Add(cnt);
+ }
+ }
+ nodeConnections[ti] = new TileNodeConnectionsUnsafe {
+ neighbours = neighbours,
+ neighbourCounts = neighbourCounts,
+ };
+ }
+
+ if (duplicates) {
+ UnityEngine.Debug.LogWarning("Duplicate triangle edges were found in the input mesh. These have been removed. Are you sure your mesh is suitable for being used as a navmesh directly?\nThis could be caused by the mesh's normals not being consistent.");
+ }
+ }
+ }
+}
diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobCalculateTriangleConnections.cs.meta b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobCalculateTriangleConnections.cs.meta
new file mode 100644
index 0000000..4bc3c35
--- /dev/null
+++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobCalculateTriangleConnections.cs.meta
@@ -0,0 +1,11 @@
+fileFormatVersion: 2
+guid: 30417132dbc15504abbdf1b70224c006
+MonoImporter:
+ externalObjects: {}
+ serializedVersion: 2
+ defaultReferences: []
+ executionOrder: 0
+ icon: {instanceID: 0}
+ userData:
+ assetBundleName:
+ assetBundleVariant:
diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobConnectTiles.cs b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobConnectTiles.cs
new file mode 100644
index 0000000..0782ecf
--- /dev/null
+++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobConnectTiles.cs
@@ -0,0 +1,159 @@
+using Unity.Collections;
+using Unity.Jobs;
+using Unity.Jobs.LowLevel.Unsafe;
+using Unity.Mathematics;
+using UnityEngine;
+
+namespace Pathfinding.Graphs.Navmesh.Jobs {
+ ///
+ /// Connects adjacent tiles together.
+ ///
+ /// This only creates connections between tiles. Connections internal to a tile should be handled by .
+ ///
+ /// Use the method to connect a bunch of tiles efficiently using maximum parallelism.
+ ///
+ public struct JobConnectTiles : IJob {
+ /// GCHandle referring to a NavmeshTile[] array of size tileRect.Width*tileRect.Height
+ public System.Runtime.InteropServices.GCHandle tiles;
+ public int coordinateSum;
+ public int direction;
+ public int zOffset;
+ public int zStride;
+ Vector2 tileWorldSize;
+ IntRect tileRect;
+ /// Maximum vertical distance between two tiles to create a connection between them
+ public float maxTileConnectionEdgeDistance;
+
+ static readonly Unity.Profiling.ProfilerMarker ConnectTilesMarker = new Unity.Profiling.ProfilerMarker("ConnectTiles");
+
+ ///
+ /// Schedule jobs to connect all the given tiles with each other while exploiting as much parallelism as possible.
+ /// tilesHandle should be a GCHandle referring to a NavmeshTile[] array of size tileRect.Width*tileRect.Height.
+ ///
+ public static JobHandle ScheduleBatch (System.Runtime.InteropServices.GCHandle tilesHandle, JobHandle dependency, IntRect tileRect, Vector2 tileWorldSize, float maxTileConnectionEdgeDistance) {
+ // First connect all tiles with an EVEN coordinate sum
+ // This would be the white squares on a chess board.
+ // Then connect all tiles with an ODD coordinate sum (which would be all black squares on a chess board).
+ // This will prevent the different threads that do all
+ // this in parallel from conflicting with each other.
+ // The directions are also done separately
+ // first they are connected along the X direction and then along the Z direction.
+ // Looping over 0 and then 1
+
+ int workers = Mathf.Max(1, JobsUtility.JobWorkerCount);
+ var handles = new NativeArray(workers, Allocator.Temp);
+ for (int coordinateSum = 0; coordinateSum <= 1; coordinateSum++) {
+ for (int direction = 0; direction <= 1; direction++) {
+ for (int i = 0; i < workers; i++) {
+ handles[i] = new JobConnectTiles {
+ tiles = tilesHandle,
+ tileRect = tileRect,
+ tileWorldSize = tileWorldSize,
+ coordinateSum = coordinateSum,
+ direction = direction,
+ maxTileConnectionEdgeDistance = maxTileConnectionEdgeDistance,
+ zOffset = i,
+ zStride = workers,
+ }.Schedule(dependency);
+ }
+ dependency = JobHandle.CombineDependencies(handles);
+ }
+ }
+
+ return dependency;
+ }
+
+ ///
+ /// Schedule jobs to connect all the given tiles inside innerRect with tiles that are outside it, while exploiting as much parallelism as possible.
+ /// tilesHandle should be a GCHandle referring to a NavmeshTile[] array of size tileRect.Width*tileRect.Height.
+ ///
+ public static JobHandle ScheduleRecalculateBorders (System.Runtime.InteropServices.GCHandle tilesHandle, JobHandle dependency, IntRect tileRect, IntRect innerRect, Vector2 tileWorldSize, float maxTileConnectionEdgeDistance) {
+ var w = innerRect.Width;
+ var h = innerRect.Height;
+
+ // Note: conservative estimate of number of handles. There may be fewer in reality.
+ var allDependencies = new NativeArray(2*w + 2*math.max(0, h - 2), Allocator.Temp);
+ int count = 0;
+ for (int z = 0; z < h; z++) {
+ for (int x = 0; x < w; x++) {
+ // Check if the tile is on the border of the inner rect
+ if (!(x == 0 || z == 0 || x == w - 1 || z == h - 1)) continue;
+
+ var tileX = innerRect.xmin + x;
+ var tileZ = innerRect.ymin + z;
+
+ // For a corner tile, the jobs need to run sequentially
+ var dep = dependency;
+ for (int direction = 0; direction < 4; direction++) {
+ var nx = tileX + (direction == 0 ? 1 : direction == 1 ? -1 : 0);
+ var nz = tileZ + (direction == 2 ? 1 : direction == 3 ? -1 : 0);
+ if (innerRect.Contains(nx, nz) || !tileRect.Contains(nx, nz)) {
+ continue;
+ }
+
+ dep = new JobConnectTilesSingle {
+ tiles = tilesHandle,
+ tileIndex1 = tileX + tileZ * tileRect.Width,
+ tileIndex2 = nx + nz * tileRect.Width,
+ tileWorldSize = tileWorldSize,
+ maxTileConnectionEdgeDistance = maxTileConnectionEdgeDistance,
+ }.Schedule(dep);
+ }
+
+ allDependencies[count++] = dep;
+ }
+ }
+ return JobHandle.CombineDependencies(allDependencies);
+ }
+
+ public void Execute () {
+ var tiles = (NavmeshTile[])this.tiles.Target;
+
+ var tileRectDepth = tileRect.Height;
+ var tileRectWidth = tileRect.Width;
+ for (int z = zOffset; z < tileRectDepth; z += zStride) {
+ for (int x = 0; x < tileRectWidth; x++) {
+ if ((x + z) % 2 == coordinateSum) {
+ int tileIndex1 = x + z * tileRectWidth;
+ int tileIndex2;
+ if (direction == 0 && x < tileRectWidth - 1) {
+ tileIndex2 = x + 1 + z * tileRectWidth;
+ } else if (direction == 1 && z < tileRectDepth - 1) {
+ tileIndex2 = x + (z + 1) * tileRectWidth;
+ } else {
+ continue;
+ }
+
+ ConnectTilesMarker.Begin();
+ NavmeshBase.ConnectTiles(tiles[tileIndex1], tiles[tileIndex2], tileWorldSize.x, tileWorldSize.y, maxTileConnectionEdgeDistance);
+ ConnectTilesMarker.End();
+ }
+ }
+ }
+ }
+ }
+
+ ///
+ /// Connects two adjacent tiles together.
+ ///
+ /// This only creates connections between tiles. Connections internal to a tile should be handled by .
+ ///
+ struct JobConnectTilesSingle : IJob {
+ /// GCHandle referring to a NavmeshTile[] array of size tileRect.Width*tileRect.Height
+ public System.Runtime.InteropServices.GCHandle tiles;
+ /// Index of the first tile in the array
+ public int tileIndex1;
+ /// Index of the second tile in the array
+ public int tileIndex2;
+ /// Size of a tile in world units
+ public Vector2 tileWorldSize;
+ /// Maximum vertical distance between two tiles to create a connection between them
+ public float maxTileConnectionEdgeDistance;
+
+ public void Execute () {
+ var tiles = (NavmeshTile[])this.tiles.Target;
+
+ NavmeshBase.ConnectTiles(tiles[tileIndex1], tiles[tileIndex2], tileWorldSize.x, tileWorldSize.y, maxTileConnectionEdgeDistance);
+ }
+ }
+}
diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobConnectTiles.cs.meta b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobConnectTiles.cs.meta
new file mode 100644
index 0000000..766f092
--- /dev/null
+++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobConnectTiles.cs.meta
@@ -0,0 +1,11 @@
+fileFormatVersion: 2
+guid: dd00a18824d04764783722c547fb60f7
+MonoImporter:
+ externalObjects: {}
+ serializedVersion: 2
+ defaultReferences: []
+ executionOrder: 0
+ icon: {instanceID: 0}
+ userData:
+ assetBundleName:
+ assetBundleVariant:
diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobConvertAreasToTags.cs b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobConvertAreasToTags.cs
new file mode 100644
index 0000000..2197d9c
--- /dev/null
+++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobConvertAreasToTags.cs
@@ -0,0 +1,23 @@
+using Pathfinding.Graphs.Navmesh.Voxelization.Burst;
+using Unity.Burst;
+using Unity.Collections;
+using Unity.Collections.LowLevel.Unsafe;
+using Unity.Jobs;
+
+namespace Pathfinding.Graphs.Navmesh.Jobs {
+ /// Convert recast region IDs to the tags that should be applied to the nodes
+ [BurstCompile]
+ public struct JobConvertAreasToTags : IJob {
+ public NativeList areas;
+
+ public void Execute () {
+ unsafe {
+ for (int i = 0; i < areas.Length; i++) {
+ var area = areas[i];
+ // The user supplied IDs start at 1 because 0 is reserved for NotWalkable
+ areas[i] = (area & VoxelUtilityBurst.TagReg) != 0 ? (area & VoxelUtilityBurst.TagRegMask) - 1 : 0;
+ }
+ }
+ }
+ }
+}
diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobConvertAreasToTags.cs.meta b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobConvertAreasToTags.cs.meta
new file mode 100644
index 0000000..3b4daad
--- /dev/null
+++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobConvertAreasToTags.cs.meta
@@ -0,0 +1,11 @@
+fileFormatVersion: 2
+guid: 229fdb01207c1ab4796deea78744e136
+MonoImporter:
+ externalObjects: {}
+ serializedVersion: 2
+ defaultReferences: []
+ executionOrder: 0
+ icon: {instanceID: 0}
+ userData:
+ assetBundleName:
+ assetBundleVariant:
diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobCreateTiles.cs b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobCreateTiles.cs
new file mode 100644
index 0000000..44368b3
--- /dev/null
+++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobCreateTiles.cs
@@ -0,0 +1,115 @@
+using Pathfinding.Util;
+using Unity.Collections;
+using Unity.Jobs;
+using UnityEngine;
+using UnityEngine.Assertions;
+using UnityEngine.Profiling;
+
+namespace Pathfinding.Graphs.Navmesh.Jobs {
+ ///
+ /// Builds tiles optimized for pathfinding, from a list of .
+ ///
+ /// This job takes the following steps:
+ /// - Transform all vertices using the matrix.
+ /// - Remove duplicate vertices
+ /// - If is enabled: ensure all triangles are laid out in the clockwise direction.
+ ///
+ public struct JobCreateTiles : IJob {
+ /// An array of of length tileRect.Width*tileRect.Height
+ [ReadOnly]
+ public NativeArray tileMeshes;
+
+ ///
+ /// An array of of length tileRect.Width*tileRect.Height.
+ /// This array will be filled with the created tiles.
+ ///
+ public System.Runtime.InteropServices.GCHandle tiles;
+
+ /// Graph index of the graph that these nodes will be added to
+ public uint graphIndex;
+
+ ///
+ /// Number of tiles in the graph.
+ ///
+ /// This may be much bigger than the that we are actually processing.
+ /// For example if a graph update is performed, the will just cover the tiles that are recalculated,
+ /// while will contain all tiles in the graph.
+ ///
+ public Int2 graphTileCount;
+
+ ///
+ /// Rectangle of tiles that we are processing.
+ ///
+ /// (xmax, ymax) must be smaller than graphTileCount.
+ /// If for examples is (10, 10) and is {2, 3, 5, 6} then we are processing tiles (2, 3) to (5, 6) inclusive.
+ ///
+ public IntRect tileRect;
+
+ /// Initial penalty for all nodes in the tile
+ public uint initialPenalty;
+
+ ///
+ /// If true, all triangles will be guaranteed to be laid out in clockwise order.
+ /// If false, their original order will be preserved.
+ ///
+ public bool recalculateNormals;
+
+ /// Size of a tile in world units along the graph's X and Z axes
+ public Vector2 tileWorldSize;
+
+ /// Matrix to convert from graph space to world space
+ public Matrix4x4 graphToWorldSpace;
+
+ public void Execute () {
+ var tiles = (NavmeshTile[])this.tiles.Target;
+ Assert.AreEqual(tileMeshes.Length, tiles.Length);
+ Assert.AreEqual(tileRect.Area, tileMeshes.Length);
+ Assert.IsTrue(tileRect.xmax < graphTileCount.x);
+ Assert.IsTrue(tileRect.ymax < graphTileCount.y);
+
+ var tileRectWidth = tileRect.Width;
+ var tileRectDepth = tileRect.Height;
+
+ for (int z = 0; z < tileRectDepth; z++) {
+ for (int x = 0; x < tileRectWidth; x++) {
+ var tileIndex = z*tileRectWidth + x;
+ // If we are just updating a part of the graph we still want to assign the nodes the proper global tile index
+ var graphTileIndex = (z + tileRect.ymin)*graphTileCount.x + (x + tileRect.xmin);
+ var mesh = tileMeshes[tileIndex];
+
+ // Convert tile space to graph space and world space
+ var verticesInGraphSpace = mesh.verticesInTileSpace.AsUnsafeSpan().Clone(Allocator.Persistent);
+ var verticesInWorldSpace = verticesInGraphSpace.Clone(Allocator.Persistent);
+ var tileSpaceToGraphSpaceOffset = (Int3) new Vector3(tileWorldSize.x * (x + tileRect.xmin), 0, tileWorldSize.y * (z + tileRect.ymin));
+ for (int i = 0; i < verticesInGraphSpace.Length; i++) {
+ var v = verticesInGraphSpace[i] + tileSpaceToGraphSpaceOffset;
+ verticesInGraphSpace[i] = v;
+ verticesInWorldSpace[i] = (Int3)graphToWorldSpace.MultiplyPoint3x4((Vector3)v);
+ }
+
+ // Create a new navmesh tile and assign its settings
+ var triangles = mesh.triangles.AsUnsafeSpan().Clone(Allocator.Persistent);
+ var tile = new NavmeshTile {
+ x = x + tileRect.xmin,
+ z = z + tileRect.ymin,
+ w = 1,
+ d = 1,
+ tris = triangles,
+ vertsInGraphSpace = verticesInGraphSpace,
+ verts = verticesInWorldSpace,
+ bbTree = new BBTree(triangles, verticesInGraphSpace),
+ nodes = new TriangleMeshNode[triangles.Length/3],
+ // Leave empty for now, it will be filled in later
+ graph = null,
+ };
+
+ Profiler.BeginSample("CreateNodes");
+ NavmeshBase.CreateNodes(tile, tile.tris, graphTileIndex, graphIndex, mesh.tags.AsUnsafeSpan(), false, null, initialPenalty, false);
+ Profiler.EndSample();
+
+ tiles[tileIndex] = tile;
+ }
+ }
+ }
+ }
+}
diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobCreateTiles.cs.meta b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobCreateTiles.cs.meta
new file mode 100644
index 0000000..3f72140
--- /dev/null
+++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobCreateTiles.cs.meta
@@ -0,0 +1,11 @@
+fileFormatVersion: 2
+guid: b86cf43938afd654a8f1b711e55977d7
+MonoImporter:
+ externalObjects: {}
+ serializedVersion: 2
+ defaultReferences: []
+ executionOrder: 0
+ icon: {instanceID: 0}
+ userData:
+ assetBundleName:
+ assetBundleVariant:
diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobTransformTileCoordinates.cs b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobTransformTileCoordinates.cs
new file mode 100644
index 0000000..b5b1a67
--- /dev/null
+++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobTransformTileCoordinates.cs
@@ -0,0 +1,32 @@
+using Unity.Burst;
+using Unity.Collections.LowLevel.Unsafe;
+using Unity.Jobs;
+using UnityEngine;
+
+namespace Pathfinding.Graphs.Navmesh.Jobs {
+ ///
+ /// Transforms vertices from voxel coordinates to tile coordinates.
+ ///
+ /// This essentially constitutes multiplying the vertices by the .
+ ///
+ /// Note: The input space is in raw voxel coordinates, the output space is in tile coordinates stored in millimeters (as is typical for the Int3 struct. See ).
+ ///
+ [BurstCompile(FloatMode = FloatMode.Fast)]
+ public struct JobTransformTileCoordinates : IJob {
+ /// Element type Int3
+ public unsafe UnsafeAppendBuffer* vertices;
+ public Matrix4x4 matrix;
+
+ public void Execute () {
+ unsafe {
+ int vertexCount = vertices->Length / UnsafeUtility.SizeOf();
+ for (int i = 0; i < vertexCount; i++) {
+ // Transform from voxel indices to a proper Int3 coordinate, then convert it to a Vector3 float coordinate
+ var vPtr1 = (Int3*)vertices->Ptr + i;
+ var p = new Vector3(vPtr1->x, vPtr1->y, vPtr1->z);
+ *vPtr1 = (Int3)matrix.MultiplyPoint3x4(p);
+ }
+ }
+ }
+ }
+}
diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobTransformTileCoordinates.cs.meta b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobTransformTileCoordinates.cs.meta
new file mode 100644
index 0000000..291734c
--- /dev/null
+++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobTransformTileCoordinates.cs.meta
@@ -0,0 +1,11 @@
+fileFormatVersion: 2
+guid: ff97d8db3ca9a074dbfbd83fa5ad16be
+MonoImporter:
+ externalObjects: {}
+ serializedVersion: 2
+ defaultReferences: []
+ executionOrder: 0
+ icon: {instanceID: 0}
+ userData:
+ assetBundleName:
+ assetBundleVariant:
diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobWriteNodeConnections.cs b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobWriteNodeConnections.cs
new file mode 100644
index 0000000..ea8ef05
--- /dev/null
+++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobWriteNodeConnections.cs
@@ -0,0 +1,60 @@
+using Pathfinding.Util;
+using Unity.Collections;
+using Unity.Jobs;
+using UnityEngine.Assertions;
+using UnityEngine.Profiling;
+
+namespace Pathfinding.Graphs.Navmesh.Jobs {
+ ///
+ /// Writes connections to each node in each tile.
+ ///
+ /// It also calculates the connection costs between nodes.
+ ///
+ /// This job is run after all tiles have been built and the connections have been calculated.
+ ///
+ /// See:
+ ///
+ public struct JobWriteNodeConnections : IJob {
+ /// Connections for each tile
+ [ReadOnly]
+ public NativeArray nodeConnections;
+ /// Array of
+ public System.Runtime.InteropServices.GCHandle tiles;
+
+ public void Execute () {
+ var tiles = (NavmeshTile[])this.tiles.Target;
+ Assert.AreEqual(nodeConnections.Length, tiles.Length);
+
+ for (int i = 0; i < tiles.Length; i++) {
+ Profiler.BeginSample("CreateConnections");
+ var connections = nodeConnections[i];
+ Apply(tiles[i].nodes, connections);
+ connections.neighbourCounts.Dispose();
+ connections.neighbours.Dispose();
+ Profiler.EndSample();
+ }
+ }
+
+ void Apply (TriangleMeshNode[] nodes, JobCalculateTriangleConnections.TileNodeConnectionsUnsafe connections) {
+ var neighbourCountsReader = connections.neighbourCounts.AsReader();
+ var neighboursReader = connections.neighbours.AsReader();
+
+ for (int i = 0; i < nodes.Length; i++) {
+ var node = nodes[i];
+ var neighbourCount = neighbourCountsReader.ReadNext();
+ var conns = node.connections = ArrayPool.ClaimWithExactLength(neighbourCount);
+ for (int j = 0; j < neighbourCount; j++) {
+ var otherIndex = neighboursReader.ReadNext();
+ var shapeEdgeInfo = (byte)neighboursReader.ReadNext();
+ var other = nodes[otherIndex];
+ var cost = (node.position - other.position).costMagnitude;
+ conns[j] = new Connection(
+ other,
+ (uint)cost,
+ shapeEdgeInfo
+ );
+ }
+ }
+ }
+ }
+}
diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobWriteNodeConnections.cs.meta b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobWriteNodeConnections.cs.meta
new file mode 100644
index 0000000..91359d9
--- /dev/null
+++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobWriteNodeConnections.cs.meta
@@ -0,0 +1,11 @@
+fileFormatVersion: 2
+guid: eea3ec9fc5dd8604c9902e09277d86d2
+MonoImporter:
+ externalObjects: {}
+ serializedVersion: 2
+ defaultReferences: []
+ executionOrder: 0
+ icon: {instanceID: 0}
+ userData:
+ assetBundleName:
+ assetBundleVariant:
diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/NavmeshTile.cs b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/NavmeshTile.cs
new file mode 100644
index 0000000..fd5adc7
--- /dev/null
+++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/NavmeshTile.cs
@@ -0,0 +1,106 @@
+namespace Pathfinding.Graphs.Navmesh {
+ using Pathfinding.Util;
+ using Unity.Collections;
+
+ ///
+ /// A single tile in a recast or navmesh graph.
+ ///
+ /// A tile is a single rectangular (but usually square) part of the graph.
+ /// Tiles can be updated individually, which is great for large worlds where updating the whole graph would take a long time.
+ ///
+ public class NavmeshTile : INavmeshHolder {
+ ///
+ /// All vertices in the tile.
+ /// The vertices are in graph space.
+ ///
+ /// This represents an allocation using the Persistent allocator.
+ ///
+ public UnsafeSpan vertsInGraphSpace;
+ ///
+ /// All vertices in the tile.
+ /// The vertices are in world space.
+ ///
+ /// This represents an allocation using the Persistent allocator.
+ ///
+ public UnsafeSpan verts;
+ ///
+ /// All triangle indices in the tile.
+ /// One triangle is 3 indices.
+ /// The triangles are in the same order as the .
+ ///
+ /// This represents an allocation using the Persistent allocator.
+ ///
+ public UnsafeSpan tris;
+
+ /// Tile X Coordinate
+ public int x;
+
+ /// Tile Z Coordinate
+ public int z;
+
+ ///
+ /// Width, in tile coordinates.
+ /// Warning: Widths other than 1 are not supported. This is mainly here for possible future features.
+ ///
+ public int w;
+
+ ///
+ /// Depth, in tile coordinates.
+ /// Warning: Depths other than 1 are not supported. This is mainly here for possible future features.
+ ///
+ public int d;
+
+ /// All nodes in the tile
+ public TriangleMeshNode[] nodes;
+
+ /// Bounding Box Tree for node lookups
+ public BBTree bbTree;
+
+ /// Temporary flag used for batching
+ public bool flag;
+
+ /// The graph which contains this tile
+ public NavmeshBase graph;
+
+ #region INavmeshHolder implementation
+
+ public void GetTileCoordinates (int tileIndex, out int x, out int z) {
+ x = this.x;
+ z = this.z;
+ }
+
+ public int GetVertexArrayIndex (int index) {
+ return index & NavmeshBase.VertexIndexMask;
+ }
+
+ /// Get a specific vertex in the tile
+ public Int3 GetVertex (int index) {
+ int idx = index & NavmeshBase.VertexIndexMask;
+
+ return verts[idx];
+ }
+
+ public Int3 GetVertexInGraphSpace (int index) {
+ return vertsInGraphSpace[index & NavmeshBase.VertexIndexMask];
+ }
+
+ /// Transforms coordinates from graph space to world space
+ public GraphTransform transform { get { return graph.transform; } }
+
+ #endregion
+
+ public void GetNodes (System.Action action) {
+ if (nodes == null) return;
+ for (int i = 0; i < nodes.Length; i++) action(nodes[i]);
+ }
+
+ public void Dispose () {
+ unsafe {
+ bbTree.Dispose();
+ vertsInGraphSpace.Free(Allocator.Persistent);
+ verts.Free(Allocator.Persistent);
+ tris.Free(Allocator.Persistent);
+ }
+ }
+ }
+}
diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/NavmeshTile.cs.meta b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/NavmeshTile.cs.meta
new file mode 100644
index 0000000..b37dca1
--- /dev/null
+++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/NavmeshTile.cs.meta
@@ -0,0 +1,12 @@
+fileFormatVersion: 2
+guid: 7408cbadf2e744d22853a92b15abede1
+timeCreated: 1474405146
+licenseType: Store
+MonoImporter:
+ serializedVersion: 2
+ defaultReferences: []
+ executionOrder: 0
+ icon: {instanceID: 0}
+ userData:
+ assetBundleName:
+ assetBundleVariant:
diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/RecastBuilder.cs b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/RecastBuilder.cs
new file mode 100644
index 0000000..2cd925b
--- /dev/null
+++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/RecastBuilder.cs
@@ -0,0 +1,49 @@
+using Pathfinding.Graphs.Navmesh.Jobs;
+
+namespace Pathfinding.Graphs.Navmesh {
+ /// Helper methods for scanning a recast graph
+ public struct RecastBuilder {
+ ///
+ /// Builds meshes for the given tiles in a graph.
+ /// Call Schedule on the returned object to actually start the job.
+ ///
+ /// You may want to adjust the settings on the returned object before calling Schedule.
+ ///
+ ///
+ /// // Scans the first 6x6 chunk of tiles of the recast graph (the IntRect uses inclusive coordinates)
+ /// var graph = AstarPath.active.data.recastGraph;
+ /// var buildSettings = RecastBuilder.BuildTileMeshes(graph, new TileLayout(graph), new IntRect(0, 0, 5, 5));
+ /// var disposeArena = new Pathfinding.Jobs.DisposeArena();
+ /// var promise = buildSettings.Schedule(disposeArena);
+ ///
+ /// AstarPath.active.AddWorkItem(() => {
+ /// // Block until the asynchronous job completes
+ /// var result = promise.Complete();
+ /// TileMeshes tiles = result.tileMeshes.ToManaged();
+ /// // Take the scanned tiles and place them in the graph,
+ /// // but not at their original location, but 2 tiles away, rotated 90 degrees.
+ /// tiles.tileRect = tiles.tileRect.Offset(new Int2(2, 0));
+ /// tiles.Rotate(1);
+ /// graph.ReplaceTiles(tiles);
+ ///
+ /// // Dispose unmanaged data
+ /// disposeArena.DisposeAll();
+ /// result.Dispose();
+ /// });
+ ///
+ ///
+ public static TileBuilder BuildTileMeshes (RecastGraph graph, TileLayout tileLayout, IntRect tileRect) {
+ return new TileBuilder(graph, tileLayout, tileRect);
+ }
+
+ ///
+ /// Builds nodes given some tile meshes.
+ /// Call Schedule on the returned object to actually start the job.
+ ///
+ /// See:
+ ///
+ public static JobBuildNodes BuildNodeTiles (RecastGraph graph, TileLayout tileLayout) {
+ return new JobBuildNodes(graph, tileLayout);
+ }
+ }
+}
diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/RecastBuilder.cs.meta b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/RecastBuilder.cs.meta
new file mode 100644
index 0000000..6682ef1
--- /dev/null
+++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/RecastBuilder.cs.meta
@@ -0,0 +1,11 @@
+fileFormatVersion: 2
+guid: b6b7a26d35ca0154fa87ac69a555cce1
+MonoImporter:
+ externalObjects: {}
+ serializedVersion: 2
+ defaultReferences: []
+ executionOrder: 0
+ icon: {instanceID: 0}
+ userData:
+ assetBundleName:
+ assetBundleVariant:
diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/RecastMeshGatherer.cs b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/RecastMeshGatherer.cs
new file mode 100644
index 0000000..0a0e180
--- /dev/null
+++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/RecastMeshGatherer.cs
@@ -0,0 +1,1134 @@
+using UnityEngine;
+using System.Collections.Generic;
+using Unity.Mathematics;
+using Unity.Collections;
+using Unity.Burst;
+
+namespace Pathfinding.Graphs.Navmesh {
+ using System;
+ using Pathfinding;
+ using Voxelization.Burst;
+ using Pathfinding.Util;
+ using Pathfinding.Jobs;
+ using Pathfinding.Drawing;
+ using UnityEngine.Profiling;
+
+ [BurstCompile]
+ public class RecastMeshGatherer {
+ readonly int terrainDownsamplingFactor;
+ public readonly LayerMask mask;
+ public readonly List tagMask;
+ readonly float maxColliderApproximationError;
+ public readonly Bounds bounds;
+ public readonly UnityEngine.SceneManagement.Scene scene;
+ Dictionary cachedMeshes = new Dictionary();
+ readonly Dictionary cachedTreePrefabs = new Dictionary();
+ readonly List > vertexBuffers;
+ readonly List > triangleBuffers;
+ readonly List meshData;
+ readonly RecastGraph.PerLayerModification[] modificationsByLayer;
+ readonly RecastGraph.PerLayerModification[] modificationsByLayer2D;
+#if UNITY_EDITOR
+ readonly List<(UnityEngine.Object, Mesh)> meshesUnreadableAtRuntime = new List<(UnityEngine.Object, Mesh)>();
+#else
+ bool anyNonReadableMesh = false;
+#endif
+
+ List meshes;
+ List dummyMaterials = new List();
+
+ public RecastMeshGatherer (UnityEngine.SceneManagement.Scene scene, Bounds bounds, int terrainDownsamplingFactor, LayerMask mask, List tagMask, List perLayerModifications, float maxColliderApproximationError) {
+ // Clamp to at least 1 since that's the resolution of the heightmap
+ terrainDownsamplingFactor = Math.Max(terrainDownsamplingFactor, 1);
+
+ this.bounds = bounds;
+ this.terrainDownsamplingFactor = terrainDownsamplingFactor;
+ this.mask = mask;
+ this.tagMask = tagMask ?? new List();
+ this.maxColliderApproximationError = maxColliderApproximationError;
+ this.scene = scene;
+ meshes = ListPool.Claim();
+ vertexBuffers = ListPool >.Claim();
+ triangleBuffers = ListPool >.Claim();
+ cachedMeshes = ObjectPoolSimple >.Claim();
+ meshData = ListPool.Claim();
+ modificationsByLayer = RecastGraph.PerLayerModification.ToLayerLookup(perLayerModifications, RecastGraph.PerLayerModification.Default);
+ // 2D colliders default to being unwalkable
+ var default2D = RecastGraph.PerLayerModification.Default;
+ default2D.mode = RecastMeshObj.Mode.UnwalkableSurface;
+ modificationsByLayer2D = RecastGraph.PerLayerModification.ToLayerLookup(perLayerModifications, default2D);
+ }
+
+ struct TreeInfo {
+ public List submeshes;
+ public bool supportsRotation;
+ }
+
+ public struct MeshCollection : IArenaDisposable {
+ List > vertexBuffers;
+ List > triangleBuffers;
+ public NativeArray meshes;
+#if UNITY_EDITOR
+ public List<(UnityEngine.Object, Mesh)> meshesUnreadableAtRuntime;
+#endif
+
+ public MeshCollection (List > vertexBuffers, List > triangleBuffers, NativeArray meshes
+#if UNITY_EDITOR
+ , List<(UnityEngine.Object, Mesh)> meshesUnreadableAtRuntime
+#endif
+ ) {
+ this.vertexBuffers = vertexBuffers;
+ this.triangleBuffers = triangleBuffers;
+ this.meshes = meshes;
+#if UNITY_EDITOR
+ this.meshesUnreadableAtRuntime = meshesUnreadableAtRuntime;
+#endif
+ }
+
+ void IArenaDisposable.DisposeWith (DisposeArena arena) {
+ for (int i = 0; i < vertexBuffers.Count; i++) {
+ arena.Add(vertexBuffers[i]);
+ arena.Add(triangleBuffers[i]);
+ }
+ arena.Add(meshes);
+ }
+ }
+
+ [BurstCompile]
+ static void CalculateBounds (ref UnsafeSpan vertices, ref float4x4 localToWorldMatrix, out Bounds bounds) {
+ if (vertices.Length == 0) {
+ bounds = new Bounds();
+ } else {
+ float3 max = float.NegativeInfinity;
+ float3 min = float.PositiveInfinity;
+ for (uint i = 0; i < vertices.Length; i++) {
+ var v = math.transform(localToWorldMatrix, vertices[i]);
+ max = math.max(max, v);
+ min = math.min(min, v);
+ }
+ bounds = new Bounds((min+max)*0.5f, max-min);
+ }
+ }
+
+ public MeshCollection Finalize () {
+#if UNITY_EDITOR
+ // This skips the Mesh.isReadable check
+ Mesh.MeshDataArray data = UnityEditor.MeshUtility.AcquireReadOnlyMeshData(meshData);
+#else
+ Mesh.MeshDataArray data = Mesh.AcquireReadOnlyMeshData(meshData);
+#endif
+ var meshes = new NativeArray(this.meshes.Count, Allocator.Persistent);
+ int meshBufferOffset = vertexBuffers.Count;
+
+ UnityEngine.Profiling.Profiler.BeginSample("Copying vertices");
+ // TODO: We should be able to hold the `data` for the whole scan and not have to copy all vertices/triangles
+ for (int i = 0; i < data.Length; i++) {
+ MeshUtility.GetMeshData(data, i, out var verts, out var tris);
+ vertexBuffers.Add(verts);
+ triangleBuffers.Add(tris);
+ }
+ UnityEngine.Profiling.Profiler.EndSample();
+
+ UnityEngine.Profiling.Profiler.BeginSample("Creating RasterizationMeshes");
+ for (int i = 0; i < meshes.Length; i++) {
+ var gatheredMesh = this.meshes[i];
+ int bufferIndex;
+ if (gatheredMesh.meshDataIndex >= 0) {
+ bufferIndex = meshBufferOffset + gatheredMesh.meshDataIndex;
+ } else {
+ bufferIndex = -(gatheredMesh.meshDataIndex+1);
+ }
+
+ var bounds = gatheredMesh.bounds;
+ var vertexSpan = vertexBuffers[bufferIndex].Reinterpret().AsUnsafeReadOnlySpan();
+ if (bounds == new Bounds()) {
+ // Recalculate bounding box
+ float4x4 m = gatheredMesh.matrix;
+ CalculateBounds(ref vertexSpan, ref m, out bounds);
+ }
+
+ var triangles = triangleBuffers[bufferIndex];
+ meshes[i] = new RasterizationMesh {
+ vertices = vertexSpan,
+ triangles = triangles.AsUnsafeSpan().Slice(gatheredMesh.indexStart, (gatheredMesh.indexEnd != -1 ? gatheredMesh.indexEnd : triangles.Length) - gatheredMesh.indexStart),
+ area = gatheredMesh.area,
+ areaIsTag = gatheredMesh.areaIsTag,
+ bounds = bounds,
+ matrix = gatheredMesh.matrix,
+ solid = gatheredMesh.solid,
+ doubleSided = gatheredMesh.doubleSided,
+ flatten = gatheredMesh.flatten,
+ };
+ }
+ UnityEngine.Profiling.Profiler.EndSample();
+
+ cachedMeshes.Clear();
+ ObjectPoolSimple >.Release(ref cachedMeshes);
+ ListPool.Release(ref this.meshes);
+
+ data.Dispose();
+
+ return new MeshCollection(
+ vertexBuffers,
+ triangleBuffers,
+ meshes
+#if UNITY_EDITOR
+ , this.meshesUnreadableAtRuntime
+#endif
+ );
+ }
+
+ ///
+ /// Add vertex and triangle buffers that can later be used to create a .
+ ///
+ /// The returned index can be used in the field of the struct.
+ ///
+ public int AddMeshBuffers (Vector3[] vertices, int[] triangles) {
+ return AddMeshBuffers(new NativeArray(vertices, Allocator.Persistent), new NativeArray(triangles, Allocator.Persistent));
+ }
+
+ ///
+ /// Add vertex and triangle buffers that can later be used to create a .
+ ///
+ /// The returned index can be used in the field of the struct.
+ ///
+ public int AddMeshBuffers (NativeArray vertices, NativeArray triangles) {
+ var meshDataIndex = -vertexBuffers.Count-1;
+
+ vertexBuffers.Add(vertices);
+ triangleBuffers.Add(triangles);
+ return meshDataIndex;
+ }
+
+ /// Add a mesh to the list of meshes to rasterize
+ public void AddMesh (Renderer renderer, Mesh gatheredMesh) {
+ if (ConvertMeshToGatheredMesh(renderer, gatheredMesh, out var gm)) {
+ meshes.Add(gm);
+ }
+ }
+
+ /// Add a mesh to the list of meshes to rasterize
+ public void AddMesh (GatheredMesh gatheredMesh) {
+ meshes.Add(gatheredMesh);
+ }
+
+ /// Holds info about a mesh to be rasterized
+ public struct GatheredMesh {
+ ///
+ /// Index in the meshData array.
+ /// Can be retrieved from the method.
+ ///
+ public int meshDataIndex;
+ ///
+ /// Area ID of the mesh. 0 means walkable, and -1 indicates that the mesh should be treated as unwalkable.
+ /// Other positive values indicate a custom area ID which will create a seam in the navmesh.
+ ///
+ public int area;
+ /// Start index in the triangle array
+ public int indexStart;
+ /// End index in the triangle array. -1 indicates the end of the array.
+ public int indexEnd;
+
+
+ /// World bounds of the mesh. Assumed to already be multiplied with the .
+ public Bounds bounds;
+
+ /// Matrix to transform the vertices by
+ public Matrix4x4 matrix;
+
+ ///
+ /// If true then the mesh will be treated as solid and its interior will be unwalkable.
+ /// The unwalkable region will be the minimum to maximum y coordinate in each cell.
+ ///
+ public bool solid;
+ /// See
+ public bool doubleSided;
+ /// See
+ public bool flatten;
+ /// See
+ public bool areaIsTag;
+
+ ///
+ /// Recalculate the from the vertices.
+ ///
+ /// The bounds will not be recalculated immediately.
+ ///
+ public void RecalculateBounds () {
+ // This will cause the bounds to be recalculated later
+ bounds = new Bounds();
+ }
+
+ public void ApplyRecastMeshObj (RecastMeshObj recastMeshObj) {
+ area = AreaFromSurfaceMode(recastMeshObj.mode, recastMeshObj.surfaceID);
+ areaIsTag = recastMeshObj.mode == RecastMeshObj.Mode.WalkableSurfaceWithTag;
+ solid |= recastMeshObj.solid;
+ }
+
+ public void ApplyLayerModification (RecastGraph.PerLayerModification modification) {
+ area = AreaFromSurfaceMode(modification.mode, modification.surfaceID);
+ areaIsTag = modification.mode == RecastMeshObj.Mode.WalkableSurfaceWithTag;
+ }
+ }
+
+ enum MeshType {
+ Mesh,
+ Box,
+ Capsule,
+ }
+
+ struct MeshCacheItem : IEquatable {
+ public MeshType type;
+ public Mesh mesh;
+ public int rows;
+ public int quantizedHeight;
+
+ public MeshCacheItem (Mesh mesh) {
+ type = MeshType.Mesh;
+ this.mesh = mesh;
+ rows = 0;
+ quantizedHeight = 0;
+ }
+
+ public static readonly MeshCacheItem Box = new MeshCacheItem {
+ type = MeshType.Box,
+ mesh = null,
+ rows = 0,
+ quantizedHeight = 0,
+ };
+
+ public bool Equals (MeshCacheItem other) {
+ return type == other.type && mesh == other.mesh && rows == other.rows && quantizedHeight == other.quantizedHeight;
+ }
+
+ public override int GetHashCode () {
+ return (((int)type * 31 ^ (mesh != null ? mesh.GetHashCode() : -1)) * 31 ^ rows) * 31 ^ quantizedHeight;
+ }
+ }
+
+ bool MeshFilterShouldBeIncluded (MeshFilter filter) {
+ if (filter.TryGetComponent(out var rend)) {
+ if (filter.sharedMesh != null && rend.enabled && (((1 << filter.gameObject.layer) & mask) != 0 || (tagMask.Count > 0 && tagMask.Contains(filter.tag)))) {
+ if (!(filter.TryGetComponent(out var rmo) && rmo.enabled)) {
+ return true;
+ }
+ }
+ }
+ return false;
+ }
+
+ bool ConvertMeshToGatheredMesh (Renderer renderer, Mesh mesh, out GatheredMesh gatheredMesh) {
+ // Ignore meshes that do not have a Position vertex attribute.
+ // This can happen for meshes that are empty, i.e. have no vertices at all.
+ if (!mesh.HasVertexAttribute(UnityEngine.Rendering.VertexAttribute.Position)) {
+ gatheredMesh = default;
+ return false;
+ }
+
+#if !UNITY_EDITOR
+ if (!mesh.isReadable) {
+ // Cannot scan this
+ if (!anyNonReadableMesh) {
+ Debug.LogError("Some meshes could not be included when scanning the graph because they are marked as not readable. This includes the mesh '" + mesh.name + "'. You need to mark the mesh with read/write enabled in the mesh importer. Alternatively you can only rasterize colliders and not meshes. Mesh Collider meshes still need to be readable.", mesh);
+ }
+ anyNonReadableMesh = true;
+ gatheredMesh = default;
+ return false;
+ }
+#endif
+
+ renderer.GetSharedMaterials(dummyMaterials);
+ var submeshStart = renderer is MeshRenderer mrend ? mrend.subMeshStartIndex : 0;
+ var submeshCount = dummyMaterials.Count;
+
+ int indexStart = 0;
+ int indexEnd = -1;
+ if (submeshStart > 0 || submeshCount < mesh.subMeshCount) {
+ var a = mesh.GetSubMesh(submeshStart);
+ var b = mesh.GetSubMesh(submeshStart + submeshCount - 1);
+ indexStart = a.indexStart;
+ indexEnd = b.indexStart + b.indexCount;
+ }
+
+ // Check the cache to avoid allocating
+ // a new array unless necessary
+ if (!cachedMeshes.TryGetValue(new MeshCacheItem(mesh), out int meshBufferIndex)) {
+#if UNITY_EDITOR
+ if (!mesh.isReadable) meshesUnreadableAtRuntime.Add((renderer, mesh));
+#endif
+ meshBufferIndex = meshData.Count;
+ meshData.Add(mesh);
+ cachedMeshes[new MeshCacheItem(mesh)] = meshBufferIndex;
+ }
+
+ gatheredMesh = new GatheredMesh {
+ meshDataIndex = meshBufferIndex,
+ bounds = renderer.bounds,
+ indexStart = indexStart,
+ indexEnd = indexEnd,
+ matrix = renderer.localToWorldMatrix,
+ doubleSided = false,
+ flatten = false,
+ };
+ return true;
+ }
+
+ GatheredMesh? GetColliderMesh (MeshCollider collider, Matrix4x4 localToWorldMatrix) {
+ if (collider.sharedMesh != null) {
+ Mesh mesh = collider.sharedMesh;
+
+ // Ignore meshes that do not have a Position vertex attribute.
+ // This can happen for meshes that are empty, i.e. have no vertices at all.
+ if (!mesh.HasVertexAttribute(UnityEngine.Rendering.VertexAttribute.Position)) {
+ return null;
+ }
+
+#if !UNITY_EDITOR
+ if (!mesh.isReadable) {
+ // Cannot scan this
+ if (!anyNonReadableMesh) {
+ Debug.LogError("Some mesh collider meshes could not be included when scanning the graph because they are marked as not readable. This includes the mesh '" + mesh.name + "'. You need to mark the mesh with read/write enabled in the mesh importer.", mesh);
+ }
+ anyNonReadableMesh = true;
+ return null;
+ }
+#endif
+
+ // Check the cache to avoid allocating
+ // a new array unless necessary
+ if (!cachedMeshes.TryGetValue(new MeshCacheItem(mesh), out int meshDataIndex)) {
+#if UNITY_EDITOR
+ if (!mesh.isReadable) meshesUnreadableAtRuntime.Add((collider, mesh));
+#endif
+ meshDataIndex = meshData.Count;
+ meshData.Add(mesh);
+ cachedMeshes[new MeshCacheItem(mesh)] = meshDataIndex;
+ }
+
+ return new GatheredMesh {
+ meshDataIndex = meshDataIndex,
+ bounds = collider.bounds,
+ areaIsTag = false,
+ area = 0,
+ indexStart = 0,
+ indexEnd = -1,
+ // Treat the collider as solid iff the collider is convex
+ solid = collider.convex,
+ matrix = localToWorldMatrix,
+ doubleSided = false,
+ flatten = false,
+ };
+ }
+
+ return null;
+ }
+
+ public void CollectSceneMeshes () {
+ if (tagMask.Count > 0 || mask != 0) {
+ // This is unfortunately the fastest way to find all mesh filters.. and it is not particularly fast.
+ // Note: We have to sort these because the recast graph is not completely deterministic in terms of ordering of meshes.
+ // Different ordering can in rare cases lead to different spans being merged which can lead to different navmeshes.
+ var meshFilters = UnityCompatibility.FindObjectsByTypeSorted();
+ bool containedStatic = false;
+
+ for (int i = 0; i < meshFilters.Length; i++) {
+ MeshFilter filter = meshFilters[i];
+
+ if (!MeshFilterShouldBeIncluded(filter)) continue;
+
+ // Note, guaranteed to have a renderer as MeshFilterShouldBeIncluded checks for it.
+ // but it can be either a MeshRenderer or a SkinnedMeshRenderer
+ filter.TryGetComponent(out var rend);
+
+ if (rend.isPartOfStaticBatch) {
+ // Statically batched meshes cannot be used due to Unity limitations
+ // log a warning about this
+ containedStatic = true;
+ } else {
+ // Only include it if it intersects with the graph
+ if (rend.bounds.Intersects(bounds)) {
+ if (ConvertMeshToGatheredMesh(rend, filter.sharedMesh, out var gatheredMesh)) {
+ gatheredMesh.ApplyLayerModification(modificationsByLayer[filter.gameObject.layer]);
+ meshes.Add(gatheredMesh);
+ }
+ }
+ }
+ }
+
+ if (containedStatic) {
+ Debug.LogWarning("Some meshes were statically batched. These meshes can not be used for navmesh calculation" +
+ " due to technical constraints.\nDuring runtime scripts cannot access the data of meshes which have been statically batched.\n" +
+ "One way to solve this problem is to use cached startup (Save & Load tab in the inspector) to only calculate the graph when the game is not playing.");
+ }
+ }
+ }
+
+ static int AreaFromSurfaceMode (RecastMeshObj.Mode mode, int surfaceID) {
+ switch (mode) {
+ default:
+ case RecastMeshObj.Mode.UnwalkableSurface:
+ return -1;
+ case RecastMeshObj.Mode.WalkableSurface:
+ return 0;
+ case RecastMeshObj.Mode.WalkableSurfaceWithSeam:
+ case RecastMeshObj.Mode.WalkableSurfaceWithTag:
+ return surfaceID;
+ }
+ }
+
+ /// Find all relevant RecastMeshObj components and create ExtraMeshes for them
+ public void CollectRecastMeshObjs () {
+ var buffer = ListPool.Claim();
+
+ // Get all recast mesh objects inside the bounds
+ RecastMeshObj.GetAllInBounds(buffer, bounds);
+
+ // Create an RasterizationMesh object
+ // for each RecastMeshObj
+ for (int i = 0; i < buffer.Count; i++) {
+ AddRecastMeshObj(buffer[i]);
+ }
+
+ ListPool.Release(ref buffer);
+ }
+
+ void AddRecastMeshObj (RecastMeshObj recastMeshObj) {
+ if (recastMeshObj.includeInScan == RecastMeshObj.ScanInclusion.AlwaysExclude) return;
+ if (recastMeshObj.includeInScan == RecastMeshObj.ScanInclusion.Auto && (((mask >> recastMeshObj.gameObject.layer) & 1) == 0 && !tagMask.Contains(recastMeshObj.tag))) return;
+
+ recastMeshObj.ResolveMeshSource(out var filter, out var collider, out var collider2D);
+
+ if (filter != null) {
+ // Add based on mesh filter
+ Mesh mesh = filter.sharedMesh;
+ if (filter.TryGetComponent(out var rend) && mesh != null) {
+ if (ConvertMeshToGatheredMesh(rend, filter.sharedMesh, out var gatheredMesh)) {
+ gatheredMesh.ApplyRecastMeshObj(recastMeshObj);
+ meshes.Add(gatheredMesh);
+ }
+ }
+ } else if (collider != null) {
+ // Add based on collider
+
+ if (ConvertColliderToGatheredMesh(collider) is GatheredMesh rmesh) {
+ rmesh.ApplyRecastMeshObj(recastMeshObj);
+ meshes.Add(rmesh);
+ }
+ } else if (collider2D != null) {
+ // 2D colliders are handled separately
+ } else {
+ if (recastMeshObj.geometrySource == RecastMeshObj.GeometrySource.Auto) {
+ Debug.LogError("Couldn't get geometry source for RecastMeshObject ("+recastMeshObj.gameObject.name +"). It didn't have a collider or MeshFilter+Renderer attached", recastMeshObj.gameObject);
+ } else {
+ Debug.LogError("Couldn't get geometry source for RecastMeshObject ("+recastMeshObj.gameObject.name +"). It didn't have a " + recastMeshObj.geometrySource + " attached", recastMeshObj.gameObject);
+ }
+ }
+ }
+
+ public void CollectTerrainMeshes (bool rasterizeTrees, float desiredChunkSize) {
+ // Find all terrains in the scene
+ var terrains = Terrain.activeTerrains;
+
+ if (terrains.Length > 0) {
+ // Loop through all terrains in the scene
+ for (int j = 0; j < terrains.Length; j++) {
+ if (terrains[j].terrainData == null) continue;
+
+ Profiler.BeginSample("Generate terrain chunks");
+ GenerateTerrainChunks(terrains[j], bounds, desiredChunkSize);
+ Profiler.EndSample();
+
+ if (rasterizeTrees) {
+ Profiler.BeginSample("Find tree meshes");
+ // Rasterize all tree colliders on this terrain object
+ CollectTreeMeshes(terrains[j]);
+ Profiler.EndSample();
+ }
+ }
+ }
+ }
+
+ void GenerateTerrainChunks (Terrain terrain, Bounds bounds, float desiredChunkSize) {
+ var terrainData = terrain.terrainData;
+
+ if (terrainData == null)
+ throw new ArgumentException("Terrain contains no terrain data");
+
+ Vector3 offset = terrain.GetPosition();
+ Vector3 center = offset + terrainData.size * 0.5F;
+
+ // Figure out the bounds of the terrain in world space
+ var terrainBounds = new Bounds(center, terrainData.size);
+
+ // Only include terrains which intersects the graph
+ if (!terrainBounds.Intersects(bounds))
+ return;
+
+ // Original heightmap size
+ int heightmapWidth = terrainData.heightmapResolution;
+ int heightmapDepth = terrainData.heightmapResolution;
+
+ // Size of a single sample
+ Vector3 sampleSize = terrainData.heightmapScale;
+ sampleSize.y = terrainData.size.y;
+
+ // Make chunks at least 12 quads wide
+ // since too small chunks just decreases performance due
+ // to the overhead of checking for bounds and similar things
+ const int MinChunkSize = 12;
+
+ // Find the number of samples along each edge that corresponds to a world size of desiredChunkSize
+ // Then round up to the nearest multiple of terrainSampleSize
+ var chunkSizeAlongX = Mathf.CeilToInt(Mathf.Max(desiredChunkSize / (sampleSize.x * terrainDownsamplingFactor), MinChunkSize)) * terrainDownsamplingFactor;
+ var chunkSizeAlongZ = Mathf.CeilToInt(Mathf.Max(desiredChunkSize / (sampleSize.z * terrainDownsamplingFactor), MinChunkSize)) * terrainDownsamplingFactor;
+ chunkSizeAlongX = Mathf.Min(chunkSizeAlongX, heightmapWidth);
+ chunkSizeAlongZ = Mathf.Min(chunkSizeAlongZ, heightmapDepth);
+ var worldChunkSizeAlongX = chunkSizeAlongX * sampleSize.x;
+ var worldChunkSizeAlongZ = chunkSizeAlongZ * sampleSize.z;
+
+ // Figure out which chunks might intersect the bounding box
+ var allChunks = new IntRect(0, 0, heightmapWidth / chunkSizeAlongX, heightmapDepth / chunkSizeAlongZ);
+ var chunks = float.IsFinite(bounds.size.x) ? new IntRect(
+ Mathf.FloorToInt((bounds.min.x - offset.x) / worldChunkSizeAlongX),
+ Mathf.FloorToInt((bounds.min.z - offset.z) / worldChunkSizeAlongZ),
+ Mathf.FloorToInt((bounds.max.x - offset.x) / worldChunkSizeAlongX),
+ Mathf.FloorToInt((bounds.max.z - offset.z) / worldChunkSizeAlongZ)
+ ) : allChunks;
+ chunks = IntRect.Intersection(chunks, allChunks);
+ if (!chunks.IsValid()) return;
+
+ // Sample the terrain heightmap
+ var sampleRect = new IntRect(
+ chunks.xmin * chunkSizeAlongX,
+ chunks.ymin * chunkSizeAlongZ,
+ Mathf.Min(heightmapWidth, (chunks.xmax+1) * chunkSizeAlongX) - 1,
+ Mathf.Min(heightmapDepth, (chunks.ymax+1) * chunkSizeAlongZ) - 1
+ );
+ float[, ] heights = terrainData.GetHeights(
+ sampleRect.xmin,
+ sampleRect.ymin,
+ sampleRect.Width,
+ sampleRect.Height
+ );
+ bool[, ] holes = terrainData.GetHoles(
+ sampleRect.xmin,
+ sampleRect.ymin,
+ sampleRect.Width - 1,
+ sampleRect.Height - 1
+ );
+
+ var chunksOffset = offset + new Vector3(chunks.xmin * chunkSizeAlongX * sampleSize.x, 0, chunks.ymin * chunkSizeAlongZ * sampleSize.z);
+ for (int z = chunks.ymin; z <= chunks.ymax; z++) {
+ for (int x = chunks.xmin; x <= chunks.xmax; x++) {
+ var chunk = ConvertHeightmapChunkToGatheredMesh(
+ heights,
+ holes,
+ sampleSize,
+ chunksOffset,
+ (x - chunks.xmin) * chunkSizeAlongX,
+ (z - chunks.ymin) * chunkSizeAlongZ,
+ chunkSizeAlongX,
+ chunkSizeAlongZ,
+ terrainDownsamplingFactor
+ );
+ chunk.ApplyLayerModification(modificationsByLayer[terrain.gameObject.layer]);
+ meshes.Add(chunk);
+ }
+ }
+ }
+
+ /// Returns ceil(lhs/rhs), i.e lhs/rhs rounded up
+ static int CeilDivision (int lhs, int rhs) {
+ return (lhs + rhs - 1)/rhs;
+ }
+
+ /// Generates a terrain chunk mesh
+ public GatheredMesh ConvertHeightmapChunkToGatheredMesh (float[, ] heights, bool[,] holes, Vector3 sampleSize, Vector3 offset, int x0, int z0, int width, int depth, int stride) {
+ // Downsample to a smaller mesh (full resolution will take a long time to rasterize)
+ // Round up the width to the nearest multiple of terrainSampleSize and then add 1
+ // (off by one because there are vertices at the edge of the mesh)
+ var heightmapDepth = heights.GetLength(0);
+ var heightmapWidth = heights.GetLength(1);
+ int resultWidth = CeilDivision(Mathf.Min(width, heightmapWidth - x0), stride) + 1;
+ int resultDepth = CeilDivision(Mathf.Min(depth, heightmapDepth - z0), stride) + 1;
+
+ // Create a mesh from the heightmap
+ var numVerts = resultWidth * resultDepth;
+ var verts = new NativeArray(numVerts, Allocator.Persistent, NativeArrayOptions.UninitializedMemory);
+
+ int numTris = (resultWidth-1)*(resultDepth-1)*2*3;
+ var tris = new NativeArray(numTris, Allocator.Persistent, NativeArrayOptions.UninitializedMemory);
+ // Using an UnsafeSpan instead of a NativeArray is much faster when writing to the array from C#
+ var vertsSpan = verts.AsUnsafeSpan();
+
+ // Create lots of vertices
+ for (int z = 0; z < resultDepth; z++) {
+ int sampleZ = Math.Min(z0 + z*stride, heightmapDepth-1);
+ for (int x = 0; x < resultWidth; x++) {
+ int sampleX = Math.Min(x0 + x*stride, heightmapWidth-1);
+ vertsSpan[z*resultWidth + x] = new Vector3(sampleX * sampleSize.x, heights[sampleZ, sampleX]*sampleSize.y, sampleZ * sampleSize.z) + offset;
+ }
+ }
+
+ // Create the mesh by creating triangles in a grid like pattern
+ int triangleIndex = 0;
+ var trisSpan = tris.AsUnsafeSpan();
+ for (int z = 0; z < resultDepth-1; z++) {
+ for (int x = 0; x < resultWidth-1; x++) {
+ // Try to check if the center of the cell is a hole or not.
+ // Note that the holes array has a size which is 1 less than the heightmap size
+ int sampleX = Math.Min(x0 + stride/2 + x*stride, heightmapWidth-2);
+ int sampleZ = Math.Min(z0 + stride/2 + z*stride, heightmapDepth-2);
+
+ if (holes[sampleZ, sampleX]) {
+ // Not a hole, generate a mesh here
+ trisSpan[triangleIndex] = z*resultWidth + x;
+ trisSpan[triangleIndex+1] = (z+1)*resultWidth + x+1;
+ trisSpan[triangleIndex+2] = z*resultWidth + x+1;
+ triangleIndex += 3;
+ trisSpan[triangleIndex] = z*resultWidth + x;
+ trisSpan[triangleIndex+1] = (z+1)*resultWidth + x;
+ trisSpan[triangleIndex+2] = (z+1)*resultWidth + x+1;
+ triangleIndex += 3;
+ }
+ }
+ }
+
+
+ var meshDataIndex = AddMeshBuffers(verts, tris);
+
+ var mesh = new GatheredMesh {
+ meshDataIndex = meshDataIndex,
+ // An empty bounding box indicates that it should be calculated from the vertices later.
+ bounds = new Bounds(),
+ indexStart = 0,
+ indexEnd = triangleIndex,
+ areaIsTag = false,
+ area = 0,
+ solid = false,
+ matrix = Matrix4x4.identity,
+ doubleSided = false,
+ flatten = false,
+ };
+ return mesh;
+ }
+
+ void CollectTreeMeshes (Terrain terrain) {
+ TerrainData data = terrain.terrainData;
+ var treeInstances = data.treeInstances;
+ var treePrototypes = data.treePrototypes;
+
+ for (int i = 0; i < treeInstances.Length; i++) {
+ TreeInstance instance = treeInstances[i];
+ TreePrototype prot = treePrototypes[instance.prototypeIndex];
+
+ // Make sure that the tree prefab exists
+ if (prot.prefab == null) {
+ continue;
+ }
+
+ if (!cachedTreePrefabs.TryGetValue(prot.prefab, out TreeInfo treeInfo)) {
+ treeInfo.submeshes = new List();
+
+ // The unity terrain system only supports rotation for trees with a LODGroup on the root object.
+ // Unity still sets the instance.rotation field to values even they are not used, so we need to explicitly check for this.
+ treeInfo.supportsRotation = prot.prefab.TryGetComponent(out var dummy);
+
+ var colliders = ListPool.Claim();
+ var rootMatrixInv = prot.prefab.transform.localToWorldMatrix.inverse;
+ prot.prefab.GetComponentsInChildren(false, colliders);
+ for (int j = 0; j < colliders.Count; j++) {
+ // The prefab has a collider, use that instead
+ var collider = colliders[j];
+
+ // Generate a mesh from the collider
+ if (ConvertColliderToGatheredMesh(collider, rootMatrixInv * collider.transform.localToWorldMatrix) is GatheredMesh mesh) {
+ // For trees, we only suppport generating a mesh from a collider. So we ignore the recastMeshObj.geometrySource field.
+ if (collider.gameObject.TryGetComponent(out var recastMeshObj) && recastMeshObj.enabled) {
+ if (recastMeshObj.includeInScan == RecastMeshObj.ScanInclusion.AlwaysExclude) continue;
+
+ mesh.ApplyRecastMeshObj(recastMeshObj);
+ } else {
+ mesh.ApplyLayerModification(modificationsByLayer[collider.gameObject.layer]);
+ }
+
+ // The bounds are incorrectly based on collider.bounds.
+ // It is incorrect because the collider is on the prefab, not on the tree instance
+ // so we need to recalculate the bounds based on the actual vertex positions
+ mesh.RecalculateBounds();
+ //mesh.matrix = collider.transform.localToWorldMatrix.inverse * mesh.matrix;
+ treeInfo.submeshes.Add(mesh);
+ }
+ }
+
+ ListPool.Release(ref colliders);
+ cachedTreePrefabs[prot.prefab] = treeInfo;
+ }
+
+ var treePosition = terrain.transform.position + Vector3.Scale(instance.position, data.size);
+ var instanceSize = new Vector3(instance.widthScale, instance.heightScale, instance.widthScale);
+ var prefabScale = Vector3.Scale(instanceSize, prot.prefab.transform.localScale);
+ var rotation = treeInfo.supportsRotation ? instance.rotation : 0;
+ var matrix = Matrix4x4.TRS(treePosition, Quaternion.AngleAxis(rotation * Mathf.Rad2Deg, Vector3.up), prefabScale);
+
+ for (int j = 0; j < treeInfo.submeshes.Count; j++) {
+ var item = treeInfo.submeshes[j];
+ item.matrix = matrix * item.matrix;
+ meshes.Add(item);
+ }
+ }
+ }
+
+ bool ShouldIncludeCollider (Collider collider) {
+ if (!collider.enabled || collider.isTrigger || !collider.bounds.Intersects(bounds) || (collider.TryGetComponent(out var rmo) && rmo.enabled)) return false;
+
+ var go = collider.gameObject;
+ if (((mask >> go.layer) & 1) != 0) return true;
+
+ // Iterate over the tag mask and use CompareTag instead of tagMask.Includes(collider.tag), as this will not allocate.
+ for (int i = 0; i < tagMask.Count; i++) {
+ if (go.CompareTag(tagMask[i])) return true;
+ }
+ return false;
+ }
+
+ public void CollectColliderMeshes () {
+ if (tagMask.Count == 0 && mask == 0) return;
+
+ var physicsScene = scene.GetPhysicsScene();
+ // Find all colliders that could possibly be inside the bounds
+ // TODO: Benchmark?
+ // Repeatedly do a OverlapBox check and make the buffer larger if it's too small.
+ int numColliders = 256;
+ Collider[] colliderBuffer = null;
+ bool finiteBounds = math.all(math.isfinite(bounds.extents));
+ if (!finiteBounds) {
+ colliderBuffer = UnityCompatibility.FindObjectsByTypeSorted();
+ numColliders = colliderBuffer.Length;
+ } else {
+ do {
+ if (colliderBuffer != null) ArrayPool.Release(ref colliderBuffer);
+ colliderBuffer = ArrayPool.Claim(numColliders * 4);
+ numColliders = physicsScene.OverlapBox(bounds.center, bounds.extents, colliderBuffer, Quaternion.identity, ~0, QueryTriggerInteraction.Ignore);
+ } while (numColliders == colliderBuffer.Length);
+ }
+
+
+ for (int i = 0; i < numColliders; i++) {
+ Collider collider = colliderBuffer[i];
+
+ if (ShouldIncludeCollider(collider)) {
+ if (ConvertColliderToGatheredMesh(collider) is GatheredMesh mesh) {
+ mesh.ApplyLayerModification(modificationsByLayer[collider.gameObject.layer]);
+ meshes.Add(mesh);
+ }
+ }
+ }
+
+ if (finiteBounds) ArrayPool.Release(ref colliderBuffer);
+ }
+
+ ///
+ /// Box Collider triangle indices can be reused for multiple instances.
+ /// Warning: This array should never be changed
+ ///
+ private readonly static int[] BoxColliderTris = {
+ 0, 1, 2,
+ 0, 2, 3,
+
+ 6, 5, 4,
+ 7, 6, 4,
+
+ 0, 5, 1,
+ 0, 4, 5,
+
+ 1, 6, 2,
+ 1, 5, 6,
+
+ 2, 7, 3,
+ 2, 6, 7,
+
+ 3, 4, 0,
+ 3, 7, 4
+ };
+
+ ///
+ /// Box Collider vertices can be reused for multiple instances.
+ /// Warning: This array should never be changed
+ ///
+ private readonly static Vector3[] BoxColliderVerts = {
+ new Vector3(-1, -1, -1),
+ new Vector3(1, -1, -1),
+ new Vector3(1, -1, 1),
+ new Vector3(-1, -1, 1),
+
+ new Vector3(-1, 1, -1),
+ new Vector3(1, 1, -1),
+ new Vector3(1, 1, 1),
+ new Vector3(-1, 1, 1),
+ };
+
+ ///
+ /// Rasterizes a collider to a mesh.
+ /// This will pass the col.transform.localToWorldMatrix to the other overload of this function.
+ ///
+ GatheredMesh? ConvertColliderToGatheredMesh (Collider col) {
+ return ConvertColliderToGatheredMesh(col, col.transform.localToWorldMatrix);
+ }
+
+ ///
+ /// Rasterizes a collider to a mesh assuming it's vertices should be multiplied with the matrix.
+ /// Note that the bounds of the returned RasterizationMesh is based on collider.bounds. So you might want to
+ /// call myExtraMesh.RecalculateBounds on the returned mesh to recalculate it if the collider.bounds would
+ /// not give the correct value.
+ ///
+ public GatheredMesh? ConvertColliderToGatheredMesh (Collider col, Matrix4x4 localToWorldMatrix) {
+ if (col is BoxCollider box) {
+ return RasterizeBoxCollider(box, localToWorldMatrix);
+ } else if (col is SphereCollider || col is CapsuleCollider) {
+ var scollider = col as SphereCollider;
+ var ccollider = col as CapsuleCollider;
+
+ float radius = scollider != null ? scollider.radius : ccollider.radius;
+ float height = scollider != null ? 0 : (ccollider.height*0.5f/radius) - 1;
+ Quaternion rot = Quaternion.identity;
+ // Capsule colliders can be aligned along the X, Y or Z axis
+ if (ccollider != null) rot = Quaternion.Euler(ccollider.direction == 2 ? 90 : 0, 0, ccollider.direction == 0 ? 90 : 0);
+ Matrix4x4 matrix = Matrix4x4.TRS(scollider != null ? scollider.center : ccollider.center, rot, Vector3.one*radius);
+
+ matrix = localToWorldMatrix * matrix;
+
+ return RasterizeCapsuleCollider(radius, height, col.bounds, matrix);
+ } else if (col is MeshCollider collider) {
+ return GetColliderMesh(collider, localToWorldMatrix);
+ }
+
+ return null;
+ }
+
+ GatheredMesh RasterizeBoxCollider (BoxCollider collider, Matrix4x4 localToWorldMatrix) {
+ Matrix4x4 matrix = Matrix4x4.TRS(collider.center, Quaternion.identity, collider.size*0.5f);
+
+ matrix = localToWorldMatrix * matrix;
+
+ if (!cachedMeshes.TryGetValue(MeshCacheItem.Box, out int meshDataIndex)) {
+ meshDataIndex = AddMeshBuffers(BoxColliderVerts, BoxColliderTris);
+ cachedMeshes[MeshCacheItem.Box] = meshDataIndex;
+ }
+
+ return new GatheredMesh {
+ meshDataIndex = meshDataIndex,
+ bounds = collider.bounds,
+ indexStart = 0,
+ indexEnd = -1,
+ areaIsTag = false,
+ area = 0,
+ solid = true,
+ matrix = matrix,
+ doubleSided = false,
+ flatten = false,
+ };
+ }
+
+ static int CircleSteps (Matrix4x4 matrix, float radius, float maxError) {
+ // Take the maximum scale factor among the 3 axes.
+ // If the current matrix has a uniform scale then they are all the same.
+ var maxScaleFactor = math.sqrt(math.max(math.max(math.lengthsq((Vector3)matrix.GetColumn(0)), math.lengthsq((Vector3)matrix.GetColumn(1))), math.lengthsq((Vector3)matrix.GetColumn(2))));
+ var realWorldRadius = radius * maxScaleFactor;
+
+ var cosAngle = 1 - maxError / realWorldRadius;
+ int steps = cosAngle < 0 ? 3 : (int)math.ceil(math.PI / math.acos(cosAngle));
+ return steps;
+ }
+
+ ///
+ /// If a circle is approximated by fewer segments, it will be slightly smaller than the original circle.
+ /// This factor is used to adjust the radius of the circle so that the resulting circle will have roughly the same area as the original circle.
+ ///
+ static float CircleRadiusAdjustmentFactor (int steps) {
+ return 0.5f * (1 - math.cos(2 * math.PI / steps));
+ }
+
+ GatheredMesh RasterizeCapsuleCollider (float radius, float height, Bounds bounds, Matrix4x4 localToWorldMatrix) {
+ // Calculate the number of rows to use
+ int rows = CircleSteps(localToWorldMatrix, radius, maxColliderApproximationError);
+
+ int cols = rows;
+
+ var cacheItem = new MeshCacheItem {
+ type = MeshType.Capsule,
+ mesh = null,
+ rows = rows,
+ // Capsules that differ by a very small amount in height will be rasterized in the same way
+ quantizedHeight = Mathf.RoundToInt(height/maxColliderApproximationError),
+ };
+
+ if (!cachedMeshes.TryGetValue(cacheItem, out var meshDataIndex)) {
+ // Generate a sphere/capsule mesh
+
+ var verts = new NativeArray(rows*cols + 2, Allocator.Persistent);
+
+ var tris = new NativeArray(rows*cols*2*3, Allocator.Persistent);
+
+ for (int r = 0; r < rows; r++) {
+ for (int c = 0; c < cols; c++) {
+ verts[c + r*cols] = new Vector3(Mathf.Cos(c*Mathf.PI*2/cols)*Mathf.Sin((r*Mathf.PI/(rows-1))), Mathf.Cos((r*Mathf.PI/(rows-1))) + (r < rows/2 ? height : -height), Mathf.Sin(c*Mathf.PI*2/cols)*Mathf.Sin((r*Mathf.PI/(rows-1))));
+ }
+ }
+
+ verts[verts.Length-1] = Vector3.up;
+ verts[verts.Length-2] = Vector3.down;
+
+ int triIndex = 0;
+
+ for (int i = 0, j = cols-1; i < cols; j = i++) {
+ tris[triIndex + 0] = (verts.Length-1);
+ tris[triIndex + 1] = (0*cols + j);
+ tris[triIndex + 2] = (0*cols + i);
+ triIndex += 3;
+ }
+
+ for (int r = 1; r < rows; r++) {
+ for (int i = 0, j = cols-1; i < cols; j = i++) {
+ tris[triIndex + 0] = (r*cols + i);
+ tris[triIndex + 1] = (r*cols + j);
+ tris[triIndex + 2] = ((r-1)*cols + i);
+ triIndex += 3;
+
+ tris[triIndex + 0] = ((r-1)*cols + j);
+ tris[triIndex + 1] = ((r-1)*cols + i);
+ tris[triIndex + 2] = (r*cols + j);
+ triIndex += 3;
+ }
+ }
+
+ for (int i = 0, j = cols-1; i < cols; j = i++) {
+ tris[triIndex + 0] = (verts.Length-2);
+ tris[triIndex + 1] = ((rows-1)*cols + j);
+ tris[triIndex + 2] = ((rows-1)*cols + i);
+ triIndex += 3;
+ }
+
+ UnityEngine.Assertions.Assert.AreEqual(triIndex, tris.Length);
+
+ // TOOD: Avoid allocating original C# array
+ // Store custom vertex buffers as negative indices
+ meshDataIndex = AddMeshBuffers(verts, tris);
+ cachedMeshes[cacheItem] = meshDataIndex;
+ }
+
+ return new GatheredMesh {
+ meshDataIndex = meshDataIndex,
+ bounds = bounds,
+ areaIsTag = false,
+ area = 0,
+ indexStart = 0,
+ indexEnd = -1,
+ solid = true,
+ matrix = localToWorldMatrix,
+ doubleSided = false,
+ flatten = false,
+ };
+ }
+
+ bool ShouldIncludeCollider2D (Collider2D collider) {
+ // Note: Some things are already checked, namely that:
+ // - collider.enabled is true
+ // - that the bounds intersect (at least approxmately)
+ // - that the collider is not a trigger
+
+ // This is not completely analogous to ShouldIncludeCollider, as this one will
+ // always include the collider if it has an attached RecastMeshObj, while
+ // 3D colliders handle RecastMeshObj components separately.
+ if (((mask >> collider.gameObject.layer) & 1) != 0) return true;
+ if ((collider.attachedRigidbody as Component ?? collider).TryGetComponent(out var rmo) && rmo.enabled && rmo.includeInScan == RecastMeshObj.ScanInclusion.AlwaysInclude) return true;
+
+ for (int i = 0; i < tagMask.Count; i++) {
+ if (collider.CompareTag(tagMask[i])) return true;
+ }
+ return false;
+ }
+
+ public void Collect2DColliderMeshes () {
+ if (tagMask.Count == 0 && mask == 0) return;
+
+ var physicsScene = scene.GetPhysicsScene2D();
+ // Find all colliders that could possibly be inside the bounds
+ // TODO: Benchmark?
+ int numColliders = 256;
+ Collider2D[] colliderBuffer = null;
+ bool finiteBounds = math.isfinite(bounds.extents.x) && math.isfinite(bounds.extents.y);
+
+ if (!finiteBounds) {
+ colliderBuffer = UnityCompatibility.FindObjectsByTypeSorted();
+ numColliders = colliderBuffer.Length;
+ } else {
+ // Repeatedly do a OverlapArea check and make the buffer larger if it's too small.
+ var min2D = (Vector2)bounds.min;
+ var max2D = (Vector2)bounds.max;
+ var filter = new ContactFilter2D().NoFilter();
+ // It would be nice to add the layer mask filter here as well,
+ // but we cannot since a collider may have a RecastMeshObj component
+ // attached, and in that case we want to include it even if it is on an excluded layer.
+ // The user may also want to include objects based on tags.
+ // But we can at least exclude all triggers.
+ filter.useTriggers = false;
+
+ do {
+ if (colliderBuffer != null) ArrayPool.Release(ref colliderBuffer);
+ colliderBuffer = ArrayPool.Claim(numColliders * 4);
+ numColliders = physicsScene.OverlapArea(min2D, max2D, filter, colliderBuffer);
+ } while (numColliders == colliderBuffer.Length);
+ }
+
+ // Filter out colliders that should not be included
+ for (int i = 0; i < numColliders; i++) {
+ if (!ShouldIncludeCollider2D(colliderBuffer[i])) colliderBuffer[i] = null;
+ }
+
+ int shapeMeshCount = ColliderMeshBuilder2D.GenerateMeshesFromColliders(colliderBuffer, numColliders, maxColliderApproximationError, out var vertices, out var indices, out var shapeMeshes);
+ var bufferIndex = AddMeshBuffers(vertices.Reinterpret(), indices);
+
+ for (int i = 0; i < shapeMeshCount; i++) {
+ var shape = shapeMeshes[i];
+
+ // Skip if the shape is not inside the bounds.
+ // This is a more granular check than the one done by the OverlapArea call above,
+ // since each collider may generate multiple shapes with different bounds.
+ // This is particularly important for TilemapColliders which may generate a lot of shapes.
+ if (!bounds.Intersects(shape.bounds)) continue;
+
+ var coll = colliderBuffer[shape.tag];
+ (coll.attachedRigidbody as Component ?? coll).TryGetComponent(out var recastMeshObj);
+
+ var rmesh = new GatheredMesh {
+ meshDataIndex = bufferIndex,
+ bounds = shape.bounds,
+ indexStart = shape.startIndex,
+ indexEnd = shape.endIndex,
+ areaIsTag = false,
+ // Colliders default to being unwalkable
+ area = -1,
+ solid = false,
+ matrix = shape.matrix,
+ doubleSided = true,
+ flatten = true,
+ };
+
+ if (recastMeshObj != null) {
+ if (recastMeshObj.includeInScan == RecastMeshObj.ScanInclusion.AlwaysExclude) continue;
+ rmesh.ApplyRecastMeshObj(recastMeshObj);
+ } else {
+ rmesh.ApplyLayerModification(modificationsByLayer2D[coll.gameObject.layer]);
+ }
+
+ // 2D colliders are never solid
+ rmesh.solid = false;
+
+ meshes.Add(rmesh);
+ }
+
+ if (finiteBounds) ArrayPool.Release(ref colliderBuffer);
+ shapeMeshes.Dispose();
+ }
+ }
+}
diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/RecastMeshGatherer.cs.meta b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/RecastMeshGatherer.cs.meta
new file mode 100644
index 0000000..da5dcf1
--- /dev/null
+++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/RecastMeshGatherer.cs.meta
@@ -0,0 +1,11 @@
+fileFormatVersion: 2
+guid: b37acf4e486d51b8394c1d8e2b0c59c2
+MonoImporter:
+ externalObjects: {}
+ serializedVersion: 2
+ defaultReferences: []
+ executionOrder: 0
+ icon: {instanceID: 0}
+ userData:
+ assetBundleName:
+ assetBundleVariant:
diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/TileBuilder.cs b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/TileBuilder.cs
new file mode 100644
index 0000000..f68f8a4
--- /dev/null
+++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/TileBuilder.cs
@@ -0,0 +1,366 @@
+using System.Collections.Generic;
+using Pathfinding.Graphs.Navmesh.Jobs;
+using Pathfinding.Jobs;
+using Pathfinding.Util;
+using Pathfinding.Graphs.Navmesh.Voxelization.Burst;
+using Unity.Collections;
+using Unity.Jobs;
+using Unity.Mathematics;
+using UnityEngine;
+using UnityEngine.Profiling;
+using UnityEngine.Assertions;
+
+namespace Pathfinding.Graphs.Navmesh {
+ ///
+ /// Settings for building tile meshes in a recast graph.
+ ///
+ /// See: for more documentation on the individual fields.
+ /// See:
+ ///
+ public struct TileBuilder {
+ public float walkableClimb;
+ public RecastGraph.CollectionSettings collectionSettings;
+ public RecastGraph.RelevantGraphSurfaceMode relevantGraphSurfaceMode;
+ public RecastGraph.DimensionMode dimensionMode;
+ public RecastGraph.BackgroundTraversability backgroundTraversability;
+
+ // TODO: Don't store in struct
+ public int tileBorderSizeInVoxels;
+ public float walkableHeight;
+ public float maxSlope;
+ // TODO: Specify in world units
+ public int characterRadiusInVoxels;
+ public int minRegionSize;
+ public float maxEdgeLength;
+ public float contourMaxError;
+ public UnityEngine.SceneManagement.Scene scene;
+ public TileLayout tileLayout;
+ public IntRect tileRect;
+ public List perLayerModifications;
+
+ public class TileBuilderOutput : IProgress, System.IDisposable {
+ public NativeReference currentTileCounter;
+ public TileMeshesUnsafe tileMeshes;
+#if UNITY_EDITOR
+ public List<(UnityEngine.Object, Mesh)> meshesUnreadableAtRuntime;
+#endif
+
+ public float Progress {
+ get {
+ var tileCount = tileMeshes.tileRect.Area;
+ var currentTile = Mathf.Min(tileCount, currentTileCounter.Value);
+ return tileCount > 0 ? currentTile / (float)tileCount : 0; // "Scanning tiles: " + currentTile + " of " + (tileCount) + " tiles...");
+ }
+ }
+
+ public void Dispose () {
+ tileMeshes.Dispose();
+ if (currentTileCounter.IsCreated) currentTileCounter.Dispose();
+#if UNITY_EDITOR
+ if (meshesUnreadableAtRuntime != null) ListPool<(UnityEngine.Object, Mesh)>.Release(ref meshesUnreadableAtRuntime);
+#endif
+ }
+ }
+
+ public TileBuilder (RecastGraph graph, TileLayout tileLayout, IntRect tileRect) {
+ this.tileLayout = tileLayout;
+ this.tileRect = tileRect;
+ // A walkableClimb higher than walkableHeight can cause issues when generating the navmesh since then it can in some cases
+ // Both be valid for a character to walk under an obstacle and climb up on top of it (and that cannot be handled with navmesh without links)
+ // The editor scripts also enforce this, but we enforce it here too just to be sure
+ this.walkableClimb = Mathf.Min(graph.walkableClimb, graph.walkableHeight);
+ this.collectionSettings = graph.collectionSettings;
+ this.dimensionMode = graph.dimensionMode;
+ this.backgroundTraversability = graph.backgroundTraversability;
+ this.tileBorderSizeInVoxels = graph.TileBorderSizeInVoxels;
+ this.walkableHeight = graph.walkableHeight;
+ this.maxSlope = graph.maxSlope;
+ this.characterRadiusInVoxels = graph.CharacterRadiusInVoxels;
+ this.minRegionSize = Mathf.RoundToInt(graph.minRegionSize);
+ this.maxEdgeLength = graph.maxEdgeLength;
+ this.contourMaxError = graph.contourMaxError;
+ this.relevantGraphSurfaceMode = graph.relevantGraphSurfaceMode;
+ this.scene = graph.active.gameObject.scene;
+ this.perLayerModifications = graph.perLayerModifications;
+ }
+
+ ///
+ /// Number of extra voxels on each side of a tile to ensure accurate navmeshes near the tile border.
+ /// The width of a tile is expanded by 2 times this value (1x to the left and 1x to the right)
+ ///
+ int TileBorderSizeInVoxels {
+ get {
+ return characterRadiusInVoxels + 3;
+ }
+ }
+
+ float TileBorderSizeInWorldUnits {
+ get {
+ return TileBorderSizeInVoxels*tileLayout.cellSize;
+ }
+ }
+
+ /// Get the world space bounds for all tiles, including an optional (graph space) padding around the tiles in the x and z axis
+ public Bounds GetWorldSpaceBounds (float xzPadding = 0) {
+ var graphSpaceBounds = tileLayout.GetTileBoundsInGraphSpace(tileRect.xmin, tileRect.ymin, tileRect.Width, tileRect.Height);
+ graphSpaceBounds.Expand(new Vector3(2*xzPadding, 0, 2*xzPadding));
+ return tileLayout.transform.Transform(graphSpaceBounds);
+ }
+
+ public RecastMeshGatherer.MeshCollection CollectMeshes (Bounds bounds) {
+ Profiler.BeginSample("Find Meshes for rasterization");
+ var mask = collectionSettings.layerMask;
+ var tagMask = collectionSettings.tagMask;
+ if (collectionSettings.collectionMode == RecastGraph.CollectionSettings.FilterMode.Layers) {
+ tagMask = null;
+ } else {
+ mask = -1;
+ }
+ var meshGatherer = new RecastMeshGatherer(scene, bounds, collectionSettings.terrainHeightmapDownsamplingFactor, collectionSettings.layerMask, collectionSettings.tagMask, perLayerModifications, tileLayout.cellSize / collectionSettings.colliderRasterizeDetail);
+
+ if (collectionSettings.rasterizeMeshes && dimensionMode == RecastGraph.DimensionMode.Dimension3D) {
+ Profiler.BeginSample("Find meshes");
+ meshGatherer.CollectSceneMeshes();
+ Profiler.EndSample();
+ }
+
+ Profiler.BeginSample("Find RecastMeshObj components");
+ meshGatherer.CollectRecastMeshObjs();
+ Profiler.EndSample();
+
+ if (collectionSettings.rasterizeTerrain && dimensionMode == RecastGraph.DimensionMode.Dimension3D) {
+ Profiler.BeginSample("Find terrains");
+ // Split terrains up into meshes approximately the size of a single chunk
+ var desiredTerrainChunkSize = tileLayout.cellSize*math.max(tileLayout.tileSizeInVoxels.x, tileLayout.tileSizeInVoxels.y);
+ meshGatherer.CollectTerrainMeshes(collectionSettings.rasterizeTrees, desiredTerrainChunkSize);
+ Profiler.EndSample();
+ }
+
+ if (collectionSettings.rasterizeColliders || dimensionMode == RecastGraph.DimensionMode.Dimension2D) {
+ Profiler.BeginSample("Find colliders");
+ if (dimensionMode == RecastGraph.DimensionMode.Dimension3D) {
+ meshGatherer.CollectColliderMeshes();
+ } else {
+ meshGatherer.Collect2DColliderMeshes();
+ }
+ Profiler.EndSample();
+ }
+
+ if (collectionSettings.onCollectMeshes != null) {
+ Profiler.BeginSample("Custom mesh collection");
+ collectionSettings.onCollectMeshes(meshGatherer);
+ Profiler.EndSample();
+ }
+
+ Profiler.BeginSample("Finalizing");
+ var result = meshGatherer.Finalize();
+ Profiler.EndSample();
+
+ // Warn if no meshes were found, but only if the tile rect covers the whole graph.
+ // If it's just a partial update, the user is probably not interested in this warning,
+ // as it is completely normal that there are some empty tiles.
+ if (tileRect == new IntRect(0, 0, tileLayout.tileCount.x - 1, tileLayout.tileCount.y - 1) && result.meshes.Length == 0) {
+ Debug.LogWarning("No rasterizable objects were found contained in the layers specified by the 'mask' variables");
+ }
+
+ Profiler.EndSample();
+ return result;
+ }
+
+ /// A mapping from tiles to the meshes that each tile touches
+ public struct BucketMapping {
+ /// All meshes that should be voxelized
+ public NativeArray meshes;
+ /// Indices into the array
+ public NativeArray pointers;
+ ///
+ /// For each tile, the range of pointers in that correspond to that tile.
+ /// This is a cumulative sum of the number of pointers in each bucket.
+ ///
+ /// Bucket i will contain pointers in the range [i > 0 ? bucketRanges[i-1] : 0, bucketRanges[i]).
+ ///
+ /// The length is the same as the number of tiles.
+ ///
+ public NativeArray bucketRanges;
+ }
+
+ /// Creates a list for every tile and adds every mesh that touches a tile to the corresponding list
+ BucketMapping PutMeshesIntoTileBuckets (RecastMeshGatherer.MeshCollection meshCollection, IntRect tileBuckets) {
+ var bucketCount = tileBuckets.Width*tileBuckets.Height;
+ var buckets = new NativeList[bucketCount];
+ var borderExpansion = TileBorderSizeInWorldUnits;
+
+ for (int i = 0; i < buckets.Length; i++) {
+ buckets[i] = new NativeList(Allocator.Persistent);
+ }
+
+ var offset = -tileBuckets.Min;
+ var clamp = new IntRect(0, 0, tileBuckets.Width - 1, tileBuckets.Height - 1);
+ var meshes = meshCollection.meshes;
+ for (int i = 0; i < meshes.Length; i++) {
+ var mesh = meshes[i];
+ var bounds = mesh.bounds;
+ var rect = tileLayout.GetTouchingTiles(bounds, borderExpansion);
+ rect = IntRect.Intersection(rect.Offset(offset), clamp);
+ for (int z = rect.ymin; z <= rect.ymax; z++) {
+ for (int x = rect.xmin; x <= rect.xmax; x++) {
+ buckets[x + z*tileBuckets.Width].Add(i);
+ }
+ }
+ }
+
+ // Concat buckets
+ int allPointersCount = 0;
+ for (int i = 0; i < buckets.Length; i++) allPointersCount += buckets[i].Length;
+ var allPointers = new NativeArray(allPointersCount, Allocator.Persistent, NativeArrayOptions.UninitializedMemory);
+ var bucketRanges = new NativeArray(bucketCount, Allocator.Persistent, NativeArrayOptions.UninitializedMemory);
+ allPointersCount = 0;
+ for (int i = 0; i < buckets.Length; i++) {
+ // If we have an empty bucket at the end of the array then allPointersCount might be equal to allPointers.Length which would cause an assert to trigger.
+ // So for empty buckets don't call the copy method
+ if (buckets[i].Length > 0) {
+ NativeArray.Copy(buckets[i].AsArray(), 0, allPointers, allPointersCount, buckets[i].Length);
+ }
+ allPointersCount += buckets[i].Length;
+ bucketRanges[i] = allPointersCount;
+ buckets[i].Dispose();
+ }
+
+ return new BucketMapping {
+ meshes = meshCollection.meshes,
+ pointers = allPointers,
+ bucketRanges = bucketRanges,
+ };
+ }
+
+ public Promise Schedule (DisposeArena arena) {
+ var tileCount = tileRect.Area;
+ Assert.IsTrue(tileCount > 0);
+
+ var tileRectWidth = tileRect.Width;
+ var tileRectDepth = tileRect.Height;
+
+ // Find all meshes that could affect the graph
+ var worldBounds = GetWorldSpaceBounds(TileBorderSizeInWorldUnits);
+ if (dimensionMode == RecastGraph.DimensionMode.Dimension2D) {
+ // In 2D mode, the bounding box of the graph only bounds it in the X and Y dimensions
+ worldBounds.extents = new Vector3(worldBounds.extents.x, worldBounds.extents.y, float.PositiveInfinity);
+ }
+ var meshes = CollectMeshes(worldBounds);
+
+ Profiler.BeginSample("PutMeshesIntoTileBuckets");
+ var buckets = PutMeshesIntoTileBuckets(meshes, tileRect);
+ Profiler.EndSample();
+
+ Profiler.BeginSample("Allocating tiles");
+ var tileMeshes = new NativeArray(tileCount, Allocator.Persistent, NativeArrayOptions.ClearMemory);
+
+ int width = tileLayout.tileSizeInVoxels.x + tileBorderSizeInVoxels*2;
+ int depth = tileLayout.tileSizeInVoxels.y + tileBorderSizeInVoxels*2;
+ var cellHeight = tileLayout.CellHeight;
+ // TODO: Move inside BuildTileMeshBurst
+ var voxelWalkableHeight = (uint)(walkableHeight/cellHeight);
+ var voxelWalkableClimb = Mathf.RoundToInt(walkableClimb/cellHeight);
+
+ var tileGraphSpaceBounds = new NativeArray(tileCount, Allocator.Persistent, NativeArrayOptions.UninitializedMemory);
+
+ for (int z = 0; z < tileRectDepth; z++) {
+ for (int x = 0; x < tileRectWidth; x++) {
+ int tileIndex = x + z*tileRectWidth;
+ var tileBounds = tileLayout.GetTileBoundsInGraphSpace(tileRect.xmin + x, tileRect.ymin + z);
+ // Expand borderSize voxels on each side
+ tileBounds.Expand(new Vector3(1, 0, 1)*TileBorderSizeInWorldUnits*2);
+ tileGraphSpaceBounds[tileIndex] = tileBounds;
+ }
+ }
+
+ Profiler.EndSample();
+ Profiler.BeginSample("Scheduling jobs");
+
+ var builders = new TileBuilderBurst[Mathf.Max(1, Mathf.Min(tileCount, Unity.Jobs.LowLevel.Unsafe.JobsUtility.JobWorkerCount + 1))];
+ var currentTileCounter = new NativeReference(0, Allocator.Persistent);
+ JobHandle dependencies = default;
+
+ var relevantGraphSurfaces = new NativeList(Allocator.Persistent);
+ var c = RelevantGraphSurface.Root;
+ while (c != null) {
+ relevantGraphSurfaces.Add(new JobBuildRegions.RelevantGraphSurfaceInfo {
+ position = c.transform.position,
+ range = c.maxRange,
+ });
+ c = c.Next;
+ }
+
+
+ // Having a few long running jobs is bad because Unity cannot inject more high priority jobs
+ // in between tile calculations. So we run each builder a number of times.
+ // Each step will just calculate one tile.
+ int tilesPerJob = Mathf.CeilToInt(Mathf.Sqrt(tileCount));
+ // Number of tiles calculated if every builder runs once
+ int tilesPerStep = tilesPerJob * builders.Length;
+ // Round up to make sure we run the jobs enough times
+ // We multiply by 2 to run a bit more jobs than strictly necessary.
+ // This is to ensure that if one builder just gets a bunch of long running jobs
+ // then the other builders can steal some work from it.
+ int jobSteps = 2 * (tileCount + tilesPerStep - 1) / tilesPerStep;
+ var jobTemplate = new JobBuildTileMeshFromVoxels {
+ tileBuilder = builders[0],
+ inputMeshes = buckets,
+ tileGraphSpaceBounds = tileGraphSpaceBounds,
+ voxelWalkableClimb = voxelWalkableClimb,
+ voxelWalkableHeight = voxelWalkableHeight,
+ voxelToTileSpace = Matrix4x4.Scale(new Vector3(tileLayout.cellSize, cellHeight, tileLayout.cellSize)) * Matrix4x4.Translate(-new Vector3(1, 0, 1)*TileBorderSizeInVoxels),
+ cellSize = tileLayout.cellSize,
+ cellHeight = cellHeight,
+ maxSlope = Mathf.Max(maxSlope, 0.0001f), // Ensure maxSlope is not 0, as then horizontal surfaces can sometimes get excluded due to floating point errors
+ dimensionMode = dimensionMode,
+ backgroundTraversability = backgroundTraversability,
+ graphToWorldSpace = tileLayout.transform.matrix,
+ // Crop all tiles to ensure they are inside the graph bounds (even if the tiles did not line up perfectly with the bounding box).
+ // Add the character radius, since it will be eroded away anyway, but subtract 1 voxel to ensure the nodes are strictly inside the bounding box
+ graphSpaceLimits = new Vector2(tileLayout.graphSpaceSize.x + (characterRadiusInVoxels-1)*tileLayout.cellSize, tileLayout.graphSpaceSize.z + (characterRadiusInVoxels-1)*tileLayout.cellSize),
+ characterRadiusInVoxels = characterRadiusInVoxels,
+ tileBorderSizeInVoxels = tileBorderSizeInVoxels,
+ minRegionSize = minRegionSize,
+ maxEdgeLength = maxEdgeLength,
+ contourMaxError = contourMaxError,
+ maxTiles = tilesPerJob,
+ relevantGraphSurfaces = relevantGraphSurfaces.AsArray(),
+ relevantGraphSurfaceMode = this.relevantGraphSurfaceMode,
+ };
+ jobTemplate.SetOutputMeshes(tileMeshes);
+ jobTemplate.SetCounter(currentTileCounter);
+ int maximumVoxelYCoord = (int)(tileLayout.graphSpaceSize.y / cellHeight);
+ for (int i = 0; i < builders.Length; i++) {
+ jobTemplate.tileBuilder = builders[i] = new TileBuilderBurst(width, depth, (int)voxelWalkableHeight, maximumVoxelYCoord);
+ var dep = new JobHandle();
+ for (int j = 0; j < jobSteps; j++) {
+ dep = jobTemplate.Schedule(dep);
+ }
+ dependencies = JobHandle.CombineDependencies(dependencies, dep);
+ }
+ JobHandle.ScheduleBatchedJobs();
+
+ Profiler.EndSample();
+
+ arena.Add(tileGraphSpaceBounds);
+ arena.Add(relevantGraphSurfaces);
+ arena.Add(buckets.bucketRanges);
+ arena.Add(buckets.pointers);
+ // Note: buckets.meshes references data in #meshes, so we don't have to dispose it separately
+ arena.Add(meshes);
+
+ // Dispose the mesh data after all jobs are completed.
+ // Note that the jobs use pointers to this data which are not tracked by the safety system.
+ for (int i = 0; i < builders.Length; i++) arena.Add(builders[i]);
+
+ return new Promise(dependencies, new TileBuilderOutput {
+ tileMeshes = new TileMeshesUnsafe(tileMeshes, tileRect, new Vector2(tileLayout.TileWorldSizeX, tileLayout.TileWorldSizeZ)),
+ currentTileCounter = currentTileCounter,
+#if UNITY_EDITOR
+ meshesUnreadableAtRuntime = meshes.meshesUnreadableAtRuntime,
+#endif
+ });
+ }
+ }
+}
diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/TileBuilder.cs.meta b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/TileBuilder.cs.meta
new file mode 100644
index 0000000..90f7f56
--- /dev/null
+++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/TileBuilder.cs.meta
@@ -0,0 +1,11 @@
+fileFormatVersion: 2
+guid: 1bfefed1cddc88f449cc850ad00f2f77
+MonoImporter:
+ externalObjects: {}
+ serializedVersion: 2
+ defaultReferences: []
+ executionOrder: 0
+ icon: {instanceID: 0}
+ userData:
+ assetBundleName:
+ assetBundleVariant:
diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/TileHandler.cs b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/TileHandler.cs
new file mode 100644
index 0000000..c182b03
--- /dev/null
+++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/TileHandler.cs
@@ -0,0 +1,1258 @@
+using System;
+using System.Collections.Generic;
+using UnityEngine;
+using Pathfinding.ClipperLib;
+using UnityEngine.Profiling;
+
+namespace Pathfinding.Graphs.Navmesh {
+ using Pathfinding;
+ using Pathfinding.Util;
+ using Pathfinding.Poly2Tri;
+ using Unity.Collections;
+ using Unity.Collections.LowLevel.Unsafe;
+ using Unity.Mathematics;
+ using Pathfinding.Graphs.Util;
+
+ ///
+ /// Utility class for updating tiles of navmesh/recast graphs.
+ ///
+ /// Most operations that this class does are asynchronous.
+ /// They will be added as work items to the AstarPath class
+ /// and executed when the pathfinding threads have finished
+ /// calculating their current paths.
+ ///
+ /// See: navmeshcutting (view in online documentation for working links)
+ /// See:
+ ///
+ public class TileHandler {
+ /// The underlaying graph which is handled by this instance
+ public readonly NavmeshBase graph;
+
+ /// Number of tiles along the x axis
+ int tileXCount;
+
+ /// Number of tiles along the z axis
+ int tileZCount;
+
+ /// Handles polygon clipping operations
+ readonly Clipper clipper = new Clipper();
+
+ /// Cached dictionary to avoid excessive allocations
+ readonly Dictionary cached_Int2_int_dict = new Dictionary();
+
+ ///
+ /// Which tile type is active on each tile index.
+ /// This array will be tileXCount*tileZCount elements long.
+ ///
+ TileType[] activeTileTypes;
+
+ /// Rotations of the active tiles
+ int[] activeTileRotations;
+
+ /// Offsets along the Y axis of the active tiles
+ int[] activeTileOffsets;
+
+ /// A flag for each tile that is set to true if it has been reloaded while batching is in progress
+ bool[] reloadedInBatch;
+
+ ///
+ /// NavmeshCut and NavmeshAdd components registered to this tile handler.
+ /// This is updated by the class.
+ /// See:
+ ///
+ public readonly GridLookup cuts;
+
+ ///
+ /// Positive while batching tile updates.
+ /// Batching tile updates has a positive effect on performance
+ ///
+ int batchDepth;
+
+ ///
+ /// True while batching tile updates.
+ /// Batching tile updates has a positive effect on performance
+ ///
+ bool isBatching { get { return batchDepth > 0; } }
+
+ ///
+ /// Utility for clipping polygons to rectangles.
+ /// Implemented as a struct and not a bunch of static methods
+ /// because it needs some buffer arrays that are best cached
+ /// to avoid excessive allocations
+ ///
+ // Note: Can technically be made readonly, but then C# will automatically copy the struct before every invocation
+ Voxelization.Int3PolygonClipper simpleClipper;
+
+ ///
+ /// True if the tile handler still has the same number of tiles and tile layout as the graph.
+ /// If the graph is rescanned the tile handler will get out of sync and needs to be recreated.
+ ///
+ public bool isValid {
+ get {
+ return graph != null && graph.exists && tileXCount == graph.tileXCount && tileZCount == graph.tileZCount;
+ }
+ }
+
+ public TileHandler (NavmeshBase graph) {
+ if (graph == null) throw new ArgumentNullException("graph");
+ if (graph.GetTiles() == null) Debug.LogWarning("Creating a TileHandler for a graph with no tiles. Please scan the graph before creating a TileHandler");
+ tileXCount = graph.tileXCount;
+ tileZCount = graph.tileZCount;
+ activeTileTypes = new TileType[tileXCount*tileZCount];
+ activeTileRotations = new int[activeTileTypes.Length];
+ activeTileOffsets = new int[activeTileTypes.Length];
+ reloadedInBatch = new bool[activeTileTypes.Length];
+ cuts = new GridLookup(new Int2(tileXCount, tileZCount));
+ this.graph = graph;
+ }
+
+ ///
+ /// Resize the tile handler to a different tile count.
+ /// See:
+ ///
+ public void Resize (IntRect newTileBounds) {
+ UnityEngine.Assertions.Assert.IsFalse(this.isBatching);
+ var newActiveTileTypes = new TileType[newTileBounds.Area];
+ var newActiveTileRotations = new int[newActiveTileTypes.Length];
+ var newActiveTileOffsets = new int[newActiveTileTypes.Length];
+ var newReloadedInBatch = new bool[newActiveTileTypes.Length];
+ for (int z = 0; z < tileZCount; z++) {
+ for (int x = 0; x < tileXCount; x++) {
+ if (newTileBounds.Contains(x, z)) {
+ var oldIndex = x + z*tileXCount;
+ var newIndex = (x - newTileBounds.xmin) + (z - newTileBounds.ymin)*newTileBounds.Width;
+ newActiveTileTypes[newIndex] = activeTileTypes[oldIndex];
+ newActiveTileRotations[newIndex] = activeTileRotations[oldIndex];
+ newActiveTileOffsets[newIndex] = activeTileOffsets[oldIndex];
+ }
+ }
+ }
+
+ this.tileXCount = newTileBounds.Width;
+ this.tileZCount = newTileBounds.Height;
+ this.activeTileTypes = newActiveTileTypes;
+ this.activeTileRotations = newActiveTileRotations;
+ this.activeTileOffsets = newActiveTileOffsets;
+ this.reloadedInBatch = newReloadedInBatch;
+
+ for (int z = 0; z < tileZCount; z++) {
+ for (int x = 0; x < tileXCount; x++) {
+ var tileIndex = x + z*tileXCount;
+ if (activeTileTypes[tileIndex] == null) {
+ UpdateTileType(graph.GetTile(x, z));
+ }
+ }
+ }
+
+ this.cuts.Resize(newTileBounds);
+ }
+
+ ///
+ /// Call to update the specified tiles with new information based on the navmesh/recast graph.
+ /// This is usually called right after a navmesh/recast graph has recalculated some tiles
+ /// and thus some calculations need to be done to take navmesh cutting into account
+ /// as well.
+ ///
+ /// Will reload all tiles in the list.
+ ///
+ public void OnRecalculatedTiles (NavmeshTile[] recalculatedTiles) {
+ for (int i = 0; i < recalculatedTiles.Length; i++) {
+ UpdateTileType(recalculatedTiles[i]);
+ }
+
+ StartBatchLoad();
+
+ for (int i = 0; i < recalculatedTiles.Length; i++) {
+ ReloadTile(recalculatedTiles[i].x, recalculatedTiles[i].z);
+ }
+
+ EndBatchLoad();
+ }
+
+ /// A template for a single tile in a navmesh/recast graph
+ public class TileType {
+ Int3[] verts;
+ int[] tris;
+ uint[] tags;
+ Int3 offset;
+ int lastYOffset;
+ int lastRotation;
+ int width;
+ int depth;
+
+ public int Width {
+ get {
+ return width;
+ }
+ }
+
+ public int Depth {
+ get {
+ return depth;
+ }
+ }
+
+ ///
+ /// Matrices for rotation.
+ /// Each group of 4 elements is a 2x2 matrix.
+ /// The XZ position is multiplied by this.
+ /// So
+ ///
+ /// //A rotation by 90 degrees clockwise, second matrix in the array
+ /// (5,2) * ((0, 1), (-1, 0)) = (2,-5)
+ ///
+ ///
+ private static readonly int[] Rotations = {
+ 1, 0, // Identity matrix
+ 0, 1,
+
+ 0, 1,
+ -1, 0,
+
+ -1, 0,
+ 0, -1,
+
+ 0, -1,
+ 1, 0
+ };
+
+ public TileType (UnsafeSpan sourceVerts, UnsafeSpan sourceTris, uint[] tags, Int3 tileSize, Int3 centerOffset, int width = 1, int depth = 1) {
+ tris = sourceTris.ToArray();
+ this.tags = tags;
+
+ verts = new Int3[sourceVerts.Length];
+
+ offset = tileSize/2;
+ offset.x *= width;
+ offset.z *= depth;
+ offset.y = 0;
+ offset += centerOffset;
+
+ for (int i = 0; i < sourceVerts.Length; i++) {
+ verts[i] = sourceVerts[i] + offset;
+ }
+
+ lastRotation = 0;
+ lastYOffset = 0;
+
+ this.width = width;
+ this.depth = depth;
+ }
+
+ ///
+ /// Create a new TileType.
+ /// First all vertices of the source mesh are offseted by the centerOffset.
+ /// The source mesh is assumed to be centered (after offsetting). Corners of the tile should be at tileSize*0.5 along all axes.
+ /// When width or depth is not 1, the tileSize param should not change, but corners of the tile are assumed to lie further out.
+ ///
+ /// The navmesh as a unity Mesh
+ /// The number of base tiles this tile type occupies on the x-axis
+ /// The number of base tiles this tile type occupies on the z-axis
+ /// Size of a single tile, the y-coordinate will be ignored.
+ /// This offset will be added to all vertices
+ public TileType (Mesh source, Int3 tileSize, Int3 centerOffset, int width = 1, int depth = 1) {
+ if (source == null) throw new ArgumentNullException("source");
+
+ Vector3[] vectorVerts = source.vertices;
+ tris = source.triangles;
+ verts = new Int3[vectorVerts.Length];
+ this.tags = null;
+
+ for (int i = 0; i < vectorVerts.Length; i++) {
+ verts[i] = (Int3)vectorVerts[i] + centerOffset;
+ }
+
+ offset = tileSize/2;
+ offset.x *= width;
+ offset.z *= depth;
+ offset.y = 0;
+
+ for (int i = 0; i < vectorVerts.Length; i++) {
+ verts[i] = verts[i] + offset;
+ }
+
+ lastRotation = 0;
+ lastYOffset = 0;
+
+ this.width = width;
+ this.depth = depth;
+ }
+
+ ///
+ /// Load a tile, result given by the vert and tris array.
+ /// Warning: For performance and memory reasons, the returned arrays are internal arrays, so they must not be modified in any way or
+ /// subsequent calls to Load may give corrupt output. The contents of the verts array is only valid until the next call to Load since
+ /// different rotations and y offsets can be applied.
+ /// If you need persistent arrays, please copy the returned ones.
+ ///
+ public void Load (out Int3[] verts, out int[] tris, out uint[] tags, int rotation, int yoffset) {
+ //Make sure it is a number 0 <= x < 4
+ rotation = ((rotation % 4) + 4) % 4;
+
+ //Figure out relative rotation (relative to previous rotation that is, since that is still applied to the verts array)
+ int tmp = rotation;
+ rotation = (rotation - (lastRotation % 4) + 4) % 4;
+ lastRotation = tmp;
+
+ verts = this.verts;
+
+ int relYOffset = yoffset - lastYOffset;
+ lastYOffset = yoffset;
+
+ if (rotation != 0 || relYOffset != 0) {
+ for (int i = 0; i < verts.Length; i++) {
+ Int3 op = verts[i] - offset;
+ Int3 p = op;
+ p.y += relYOffset;
+ p.x = op.x * Rotations[rotation*4 + 0] + op.z * Rotations[rotation*4 + 1];
+ p.z = op.x * Rotations[rotation*4 + 2] + op.z * Rotations[rotation*4 + 3];
+ verts[i] = p + offset;
+ }
+ }
+
+ tris = this.tris;
+ tags = this.tags;
+ }
+ }
+
+ ///
+ /// Vertices and triangles used as input for the navmesh cutting.
+ ///
+ /// The vertices are in tile-space. So (0,0) is a corner of the tile. Distances are the same as in graph-space.
+ ///
+ /// Warning: For performance and memory reasons, the returned arrays are internal arrays, so they must not be modified in any way or
+ /// subsequent calls to Load may give corrupt output. The contents of the verts array is only valid until the next call to GetSourceTileData since
+ /// different rotations and y offsets can be applied.
+ /// If you need persistent arrays, please copy the returned ones.
+ ///
+ public void GetSourceTileData (int x, int z, out Int3[] verts, out int[] tris, out uint[] tags) {
+ var tileIndex = x + z*tileXCount;
+ this.activeTileTypes[tileIndex].Load(out verts, out tris, out tags, activeTileRotations[tileIndex], activeTileOffsets[tileIndex]);
+ }
+
+ ///
+ /// Register that a tile can be loaded from source.
+ ///
+ /// Returns: Identifier for loading that tile type
+ ///
+ /// Assumes that the mesh has its pivot point at the center of the tile.
+ /// If it has not, you can supply a non-zero centerOffset to offset all vertices.
+ /// width of the tile. In base tiles, not world units.
+ /// depth of the tile. In base tiles, not world units.
+ /// Source mesh, must be readable.
+ public TileType RegisterTileType (Mesh source, Int3 centerOffset, int width = 1, int depth = 1) {
+ return new TileType(source, (Int3) new Vector3(graph.TileWorldSizeX, 0, graph.TileWorldSizeZ), centerOffset, width, depth);
+ }
+
+ public void CreateTileTypesFromGraph () {
+ NavmeshTile[] tiles = graph.GetTiles();
+ if (tiles == null)
+ return;
+
+ if (!isValid) {
+ throw new InvalidOperationException("Graph tiles are invalid (number of tiles is not equal to width*depth of the graph). You need to create a new tile handler if you have changed the graph.");
+ }
+
+ for (int z = 0; z < tileZCount; z++) {
+ for (int x = 0; x < tileXCount; x++) {
+ NavmeshTile tile = tiles[x + z*tileXCount];
+ UpdateTileType(tile);
+ }
+ }
+ }
+
+ void UpdateTileType (NavmeshTile tile) {
+ int x = tile.x;
+ int z = tile.z;
+
+ Int3 size = (Int3) new Vector3(graph.TileWorldSizeX, 0, graph.TileWorldSizeZ);
+ Bounds b = graph.GetTileBoundsInGraphSpace(x, z);
+ var centerOffset = -((Int3)b.min + new Int3(size.x*tile.w/2, 0, size.z*tile.d/2));
+
+ var tags = new uint[tile.nodes.Length];
+ for (int i = 0; i < tags.Length; i++) tags[i] = tile.nodes[i].Tag;
+ var tileType = new TileType(tile.vertsInGraphSpace, tile.tris, tags, size, centerOffset, tile.w, tile.d);
+
+ int index = x + z*tileXCount;
+
+ activeTileTypes[index] = tileType;
+ activeTileRotations[index] = 0;
+ activeTileOffsets[index] = 0;
+ }
+
+ ///
+ /// Start batch loading.
+ /// Every call to this method must be matched by exactly one call to EndBatchLoad.
+ ///
+ public void StartBatchLoad () {
+ batchDepth++;
+ if (batchDepth > 1) return;
+
+ AstarPath.active.AddWorkItem(new AstarWorkItem(force => {
+ graph.StartBatchTileUpdate();
+ return true;
+ }));
+ }
+
+ public void EndBatchLoad () {
+ if (batchDepth <= 0) throw new Exception("Ending batching when batching has not been started");
+ batchDepth--;
+
+ for (int i = 0; i < reloadedInBatch.Length; i++) reloadedInBatch[i] = false;
+
+ AstarPath.active.AddWorkItem(new AstarWorkItem((ctx, force) => {
+ Profiler.BeginSample("Apply Tile Modifications");
+ graph.EndBatchTileUpdate();
+ Profiler.EndSample();
+ return true;
+ }));
+ }
+
+ [Flags]
+ public enum CutMode {
+ /// Cut holes in the navmesh
+ CutAll = 1,
+ /// Cut the navmesh but do not remove the interior of the cuts
+ CutDual = 2,
+ /// Also cut using the extra shape that was provided
+ CutExtra = 4
+ }
+
+ /// Internal class describing a single NavmeshCut
+ class Cut {
+ /// Bounds in XZ space
+ public IntRect bounds;
+
+ /// X is the lower bound on the y axis, Y is the upper bounds on the Y axis
+ public Int2 boundsY;
+ public bool isDual;
+ public bool cutsAddedGeom;
+ public List contour;
+ }
+
+ /// Internal class representing a mesh which is the result of the CutPoly method
+ struct CuttingResult {
+ public Int3[] verts;
+ public int[] tris;
+ public uint[] tags;
+ }
+
+ ///
+ /// Cuts a piece of navmesh using navmesh cuts.
+ ///
+ /// Note: I am sorry for the really messy code in this method.
+ /// It really needs to be refactored.
+ ///
+ /// See: NavmeshBase.transform
+ /// See: CutMode
+ ///
+ /// Vertices that are going to be cut. Should be in graph space.
+ /// Triangles describing a mesh using the vertices.
+ /// Tags for each triangle. Will be passed to the resulting mesh.
+ /// If supplied the resulting mesh will be the intersection of the input mesh and this mesh.
+ /// Transform mapping graph space to world space.
+ /// Tiles in the recast graph which the mesh covers.
+ ///
+ /// Move navmesh cuts around randomly a bit, the larger the value the more they are moved around.
+ /// Used to prevent edge cases that can cause the clipping to fail.
+ CuttingResult CutPoly (Int3[] verts, int[] tris, uint[] tags, Int3[] extraShape, GraphTransform graphTransform, IntRect tiles, CutMode mode = CutMode.CutAll | CutMode.CutDual, int perturbate = -1) {
+ // Find all NavmeshAdd components that could be inside the bounds
+ List navmeshAdds = cuts.QueryRect(tiles);
+
+ // Nothing to do here
+ if ((verts.Length == 0 || tris.Length == 0) && navmeshAdds.Count == 0) {
+ return new CuttingResult {
+ verts = ArrayPool.Claim(0),
+ tris = ArrayPool.Claim(0),
+ tags = ArrayPool.Claim(0),
+ };
+ }
+
+ if (perturbate > 10) {
+ Debug.LogError("Too many perturbations aborting.\n" +
+ "This may cause a tile in the navmesh to become empty. " +
+ "Try to see see if any of your NavmeshCut or NavmeshAdd components use invalid custom meshes.");
+ return new CuttingResult {
+ verts = verts,
+ tris = tris,
+ tags = tags,
+ };
+ }
+
+ List extraClipShape = null;
+
+ // Do not cut with extra shape if there is no extra shape
+ if (extraShape == null && (mode & CutMode.CutExtra) != 0) {
+ throw new Exception("extraShape is null and the CutMode specifies that it should be used. Cannot use null shape.");
+ }
+
+ // Calculate tile bounds so that the correct cutting offset can be used
+ // The tile will be cut in local space (i.e it is at the world origin) so cuts need to be translated
+ // to that point from their world space coordinates
+ var graphSpaceBounds = graph.GetTileBoundsInGraphSpace(tiles);
+ var cutOffset = graphSpaceBounds.min;
+ var transform = graphTransform * Matrix4x4.TRS(cutOffset, Quaternion.identity, Vector3.one);
+ // cutRegionSize The cutting region is a rectangle with one corner at the origin and one at the coordinates of cutRegionSize
+ // NavmeshAdd components will be clipped against this rectangle. It is assumed that the input vertices do not extend outside the region.
+ // For navmesh tiles, cutRegionSize is set to the size of a single tile.
+ var cutRegionSize = new Vector2(graphSpaceBounds.size.x, graphSpaceBounds.size.z);
+ var characterRadius = graph.NavmeshCuttingCharacterRadius;
+
+ if ((mode & CutMode.CutExtra) != 0) {
+ extraClipShape = ListPool.Claim(extraShape.Length);
+ for (int i = 0; i < extraShape.Length; i++) {
+ var p = transform.InverseTransform(extraShape[i]);
+ extraClipShape.Add(new IntPoint(p.x, p.z));
+ }
+ }
+
+ // Find all NavmeshCut components that could be inside these bounds
+ List navmeshCuts;
+ if (mode == CutMode.CutExtra) {
+ // Not needed when only cutting extra
+ navmeshCuts = ListPool.Claim();
+ } else {
+ navmeshCuts = cuts.QueryRect(tiles);
+ }
+
+ var intersectingCuts = ListPool.Claim();
+
+ var cutInfos = PrepareNavmeshCutsForCutting(navmeshCuts, transform, perturbate, characterRadius);
+
+ var outverts = ListPool.Claim(verts.Length*2);
+ var outtris = ListPool.Claim(tris.Length);
+ var outtags = ListPool.Claim(tags.Length);
+
+ if (navmeshCuts.Count == 0 && navmeshAdds.Count == 0 && (mode & ~(CutMode.CutAll | CutMode.CutDual)) == 0 && (mode & CutMode.CutAll) != 0) {
+ // Fast path for the common case, no cuts or adds to the navmesh, so we just copy the vertices
+ CopyMesh(verts, tris, tags, outverts, outtris, outtags);
+ } else {
+ var poly = ListPool.Claim();
+ var point2Index = new Dictionary();
+ var polypoints = ListPool.Claim();
+
+ var clipResult = new Pathfinding.ClipperLib.PolyTree();
+ var intermediateClipResult = ListPool >.Claim();
+ var polyCache = StackPool.Claim();
+
+ // If we failed the previous iteration
+ // use a higher quality cutting
+ // this is heavier on the CPU, so only use it in special cases
+ clipper.StrictlySimple = perturbate > -1;
+ clipper.ReverseSolution = true;
+
+ Int3[] clipIn = null;
+ Int3[] clipOut = null;
+ Int2 clipSize = new Int2();
+
+ if (navmeshAdds.Count > 0) {
+ clipIn = new Int3[7];
+ clipOut = new Int3[7];
+ // TODO: What if the size is odd?
+ // Convert cutRegionSize to an Int2 (all the casting is used to scale it appropriately, Int2 does not have an explicit conversion)
+ clipSize = new Int2(((Int3)(Vector3)cutRegionSize).x, ((Int3)(Vector3)cutRegionSize).y);
+ }
+
+ // Iterate over all meshes that will make up the navmesh surface
+ Int3[] vertexBuffer = null;
+ for (int meshIndex = -1; meshIndex < navmeshAdds.Count; meshIndex++) {
+ // Current array of vertices and triangles that are being processed
+ Int3[] cverts;
+ int[] ctris;
+ uint[] ctags;
+ if (meshIndex == -1) {
+ cverts = verts;
+ ctris = tris;
+ ctags = tags;
+ } else {
+ navmeshAdds[meshIndex].GetMesh(ref vertexBuffer, out ctris, transform);
+ cverts = vertexBuffer;
+ ctags = null;
+ }
+
+ for (int tri = 0; tri < ctris.Length; tri += 3) {
+ Int3 tp1 = cverts[ctris[tri + 0]];
+ Int3 tp2 = cverts[ctris[tri + 1]];
+ Int3 tp3 = cverts[ctris[tri + 2]];
+ var tag = ctags != null ? ctags[tri/3] : 0;
+
+ if (VectorMath.IsColinearXZ(tp1, tp2, tp3)) {
+ Debug.LogWarning("Skipping degenerate triangle.");
+ continue;
+ }
+
+ var triBounds = new IntRect(tp1.x, tp1.z, tp1.x, tp1.z);
+ triBounds = triBounds.ExpandToContain(tp2.x, tp2.z);
+ triBounds = triBounds.ExpandToContain(tp3.x, tp3.z);
+
+ // Upper and lower bound on the Y-axis, the above bounds do not have Y axis information
+ int tpYMin = Math.Min(tp1.y, Math.Min(tp2.y, tp3.y));
+ int tpYMax = Math.Max(tp1.y, Math.Max(tp2.y, tp3.y));
+
+ intersectingCuts.Clear();
+ bool hasDual = false;
+
+ for (int i = 0; i < cutInfos.Count; i++) {
+ int ymin = cutInfos[i].boundsY.x;
+ int ymax = cutInfos[i].boundsY.y;
+
+ if (IntRect.Intersects(triBounds, cutInfos[i].bounds) && !(ymax< tpYMin || ymin > tpYMax) && (cutInfos[i].cutsAddedGeom || meshIndex == -1)) {
+ Int3 p1 = tp1;
+ p1.y = ymin;
+ Int3 p2 = tp1;
+ p2.y = ymax;
+
+ intersectingCuts.Add(i);
+ hasDual |= cutInfos[i].isDual;
+ }
+ }
+
+ // Check if this is just a simple triangle which no navmesh cuts intersect and
+ // there are no other special things that should be done
+ if (intersectingCuts.Count == 0 && (mode & CutMode.CutExtra) == 0 && (mode & CutMode.CutAll) != 0 && meshIndex == -1) {
+ // Just add the triangle and be done with it
+
+ // Refers to vertices to be added a few lines below
+ outtris.Add(outverts.Count + 0);
+ outtris.Add(outverts.Count + 1);
+ outtris.Add(outverts.Count + 2);
+
+ outverts.Add(tp1);
+ outverts.Add(tp2);
+ outverts.Add(tp3);
+
+ outtags.Add(tag);
+ continue;
+ }
+
+ // Add current triangle as subject polygon for cutting
+ poly.Clear();
+ if (meshIndex == -1) {
+ // Geometry from a tile mesh is assumed to be completely inside the tile
+ poly.Add(new IntPoint(tp1.x, tp1.z));
+ poly.Add(new IntPoint(tp2.x, tp2.z));
+ poly.Add(new IntPoint(tp3.x, tp3.z));
+ } else {
+ // Added geometry must be clipped against the tile bounds
+ clipIn[0] = tp1;
+ clipIn[1] = tp2;
+ clipIn[2] = tp3;
+
+ int ct = ClipAgainstRectangle(clipIn, clipOut, clipSize);
+
+ // Check if triangle was completely outside the tile
+ if (ct == 0) {
+ continue;
+ }
+
+ for (int q = 0; q < ct; q++)
+ poly.Add(new IntPoint(clipIn[q].x, clipIn[q].z));
+ }
+
+ point2Index.Clear();
+
+ // Loop through all possible modes
+ for (int cmode = 0; cmode < 4; cmode++) {
+ // Ignore modes which are not active
+ if ((((int)mode >> cmode) & 0x1) == 0)
+ continue;
+
+ if (1 << cmode == (int)CutMode.CutAll) {
+ CutAll(poly, intersectingCuts, cutInfos, clipResult);
+ } else if (1 << cmode == (int)CutMode.CutDual) {
+ // No duals, don't bother processing this
+ if (!hasDual)
+ continue;
+
+ CutDual(poly, intersectingCuts, cutInfos, hasDual, intermediateClipResult, clipResult);
+ } else if (1 << cmode == (int)CutMode.CutExtra) {
+ CutExtra(poly, extraClipShape, clipResult);
+ }
+
+ for (int exp = 0; exp < clipResult.ChildCount; exp++) {
+ PolyNode node = clipResult.Childs[exp];
+ List outer = node.Contour;
+ List holes = node.Childs;
+
+ if (holes.Count == 0 && outer.Count == 3 && meshIndex == -1) {
+ for (int i = 0; i < 3; i++) {
+ var p = new Int3((int)outer[i].X, 0, (int)outer[i].Y);
+ p.y = Pathfinding.Polygon.SampleYCoordinateInTriangle(tp1, tp2, tp3, p);
+
+ outtris.Add(outverts.Count);
+ outverts.Add(p);
+ }
+ outtags.Add(tag);
+ } else {
+ Poly2Tri.Polygon polygonToTriangulate = null;
+ // Loop over outer and all holes
+ int hole = -1;
+ List contour = outer;
+ while (contour != null) {
+ polypoints.Clear();
+ for (int i = 0; i < contour.Count; i++) {
+ // Create a new point
+ var pp = new PolygonPoint(contour[i].X, contour[i].Y);
+
+ // Add the point to the polygon
+ polypoints.Add(pp);
+
+ var p = new Int3((int)contour[i].X, 0, (int)contour[i].Y);
+ p.y = Pathfinding.Polygon.SampleYCoordinateInTriangle(tp1, tp2, tp3, p);
+
+ // Prepare a lookup table for pp -> vertex index
+ point2Index[pp] = outverts.Count;
+
+ // Add to resulting vertex list
+ outverts.Add(p);
+ }
+
+ Poly2Tri.Polygon contourPolygon = null;
+ if (polyCache.Count > 0) {
+ contourPolygon = polyCache.Pop();
+ contourPolygon.AddPoints(polypoints);
+ } else {
+ contourPolygon = new Poly2Tri.Polygon(polypoints);
+ }
+
+ // Since the outer contour is the first to be processed, polygonToTriangle will be null
+ // Holes are processed later, when polygonToTriangle is not null
+ if (hole == -1) {
+ polygonToTriangulate = contourPolygon;
+ } else {
+ polygonToTriangulate.AddHole(contourPolygon);
+ }
+
+ hole++;
+ contour = hole < holes.Count ? holes[hole].Contour : null;
+ }
+
+ // Triangulate the polygon with holes
+ try {
+ P2T.Triangulate(polygonToTriangulate);
+ } catch (Poly2Tri.PointOnEdgeException) {
+ Debug.LogWarning("PointOnEdgeException, perturbating vertices slightly.\nThis is usually fine. It happens sometimes because of rounding errors. Cutting will be retried a few more times.");
+ return CutPoly(verts, tris, tags, extraShape, graphTransform, tiles, mode, perturbate + 1);
+ }
+
+ try {
+ for (int i = 0; i < polygonToTriangulate.Triangles.Count; i++) {
+ Poly2Tri.DelaunayTriangle t = polygonToTriangulate.Triangles[i];
+
+ // Add the triangle with the correct indices (using the previously built lookup table)
+ outtris.Add(point2Index[t.Points._0]);
+ outtris.Add(point2Index[t.Points._1]);
+ outtris.Add(point2Index[t.Points._2]);
+ outtags.Add(tag);
+ }
+ } catch (System.Collections.Generic.KeyNotFoundException) {
+ Debug.LogWarning("KeyNotFoundException, perturbating vertices slightly.\nThis is usually fine. It happens sometimes because of rounding errors. Cutting will be retried a few more times.");
+ return CutPoly(verts, tris, tags, extraShape, graphTransform, tiles, mode, perturbate + 1);
+ }
+
+ PoolPolygon(polygonToTriangulate, polyCache);
+ }
+ }
+ }
+ }
+ }
+
+ if (vertexBuffer != null) ArrayPool.Release(ref vertexBuffer);
+ StackPool.Release(polyCache);
+ ListPool >.Release(ref intermediateClipResult);
+ ListPool.Release(ref poly);
+ ListPool.Release(ref polypoints);
+ }
+
+ // This next step will remove all duplicate vertices in the data (of which there are quite a few)
+ // and output the final vertex and triangle arrays to the outVertsArr and outTrisArr variables
+ var result = new CuttingResult();
+ Pathfinding.Polygon.CompressMesh(outverts, outtris, outtags, out result.verts, out result.tris, out result.tags);
+
+ // Notify the navmesh cuts that they were used
+ for (int i = 0; i < navmeshCuts.Count; i++) {
+ navmeshCuts[i].UsedForCut();
+ }
+
+ // Release back to pools
+ ListPool.Release(ref outverts);
+ ListPool.Release(ref outtris);
+ ListPool.Release(ref outtags);
+ ListPool.Release(ref intersectingCuts);
+
+ for (int i = 0; i < cutInfos.Count; i++) {
+ ListPool.Release(cutInfos[i].contour);
+ }
+
+ ListPool.Release(ref cutInfos);
+ ListPool.Release(ref navmeshCuts);
+ return result;
+ }
+
+ ///
+ /// Generates a list of cuts from the navmesh cut components.
+ /// Each cut has a single contour (NavmeshCut components may contain multiple).
+ ///
+ /// transform should transform a point from cut space to world space.
+ ///
+ static List PrepareNavmeshCutsForCutting (List navmeshCuts, GraphTransform transform, int perturbate, float characterRadius) {
+ System.Random rnd = null;
+ if (perturbate > 0) {
+ rnd = new System.Random();
+ }
+
+ var contourVertices = new UnsafeList(0, Allocator.Temp);
+ var contours = new UnsafeList(0, Allocator.Temp);
+ var result = ListPool.Claim();
+ for (int i = 0; i < navmeshCuts.Count; i++) {
+ // Generate random perturbation for this obstacle if required
+ Int2 perturbation = new Int2(0, 0);
+ if (perturbate > 0) {
+ // Create a perturbation vector, choose a point with coordinates in the set [-3*perturbate,3*perturbate]
+ // makes sure none of the coordinates are zero
+
+ perturbation.x = (rnd.Next() % 6*perturbate) - 3*perturbate;
+ if (perturbation.x >= 0) perturbation.x++;
+
+ perturbation.y = (rnd.Next() % 6*perturbate) - 3*perturbate;
+ if (perturbation.y >= 0) perturbation.y++;
+ }
+
+ unsafe {
+ navmeshCuts[i].GetContourBurst(&contourVertices, &contours, transform.inverseMatrix, characterRadius);
+ }
+
+ for (int j = 0; j < contours.Length; j++) {
+ NavmeshCut.ContourBurst contour = contours[j];
+
+ if (contour.endIndex <= contour.startIndex) {
+ Debug.LogError("A NavmeshCut component had a zero length contour. Ignoring that contour.");
+ continue;
+ }
+
+ // TODO: transform should include cutting offset
+ List i3contour = ListPool.Claim(contour.endIndex - contour.startIndex);
+ for (int q = contour.startIndex; q < contour.endIndex; q++) {
+ var p = contourVertices[q] * Int3.FloatPrecision;
+ var ip = new IntPoint((long)p.x, (long)p.y);
+ if (perturbate > 0) {
+ ip.X += perturbation.x;
+ ip.Y += perturbation.y;
+ }
+
+ i3contour.Add(ip);
+ }
+
+ IntRect contourBounds = new IntRect((int)i3contour[0].X, (int)i3contour[0].Y, (int)i3contour[0].X, (int)i3contour[0].Y);
+
+ for (int q = 0; q < i3contour.Count; q++) {
+ IntPoint p = i3contour[q];
+ contourBounds = contourBounds.ExpandToContain((int)p.X, (int)p.Y);
+ }
+
+ Cut cut = new Cut();
+
+ // Calculate bounds on the y axis
+ cut.boundsY = new Int2((int)(contour.ymin * Int3.FloatPrecision), (int)(contour.ymax * Int3.FloatPrecision));
+ cut.bounds = contourBounds;
+ cut.isDual = navmeshCuts[i].isDual;
+ cut.cutsAddedGeom = navmeshCuts[i].cutsAddedGeom;
+ cut.contour = i3contour;
+ result.Add(cut);
+ }
+
+ contours.Clear();
+ contourVertices.Clear();
+ }
+
+ contours.Dispose();
+ contourVertices.Dispose();
+ return result;
+ }
+
+ static void PoolPolygon (Poly2Tri.Polygon polygon, Stack pool) {
+ if (polygon.Holes != null)
+ for (int i = 0; i < polygon.Holes.Count; i++) {
+ polygon.Holes[i].Points.Clear();
+ polygon.Holes[i].ClearTriangles();
+
+ if (polygon.Holes[i].Holes != null)
+ polygon.Holes[i].Holes.Clear();
+
+ pool.Push(polygon.Holes[i]);
+ }
+ polygon.ClearTriangles();
+ if (polygon.Holes != null)
+ polygon.Holes.Clear();
+ polygon.Points.Clear();
+ pool.Push(polygon);
+ }
+
+ void CutAll (List poly, List intersectingCutIndices, List cuts, Pathfinding.ClipperLib.PolyTree result) {
+ clipper.Clear();
+ clipper.AddPolygon(poly, PolyType.ptSubject);
+
+ // Add all holes (cuts) as clip polygons
+ // TODO: AddPolygon allocates quite a lot, modify ClipperLib to use object pooling
+ for (int i = 0; i < intersectingCutIndices.Count; i++) {
+ clipper.AddPolygon(cuts[intersectingCutIndices[i]].contour, PolyType.ptClip);
+ }
+
+ result.Clear();
+ clipper.Execute(ClipType.ctDifference, result, PolyFillType.pftNonZero, PolyFillType.pftNonZero);
+ }
+
+ void CutDual (List