+ astar project

14 files changed, 2075 insertions, 0 deletions

diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Core/Collections/AstarMemory.cs b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Core/Collections/AstarMemory.cs
new file mode 100644
index 0000000..086e3cb
--- /dev/null
+++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Core/Collections/AstarMemory.cs
@@ -0,0 +1,97 @@
+using System;
+using Unity.Collections;
+using Unity.Collections.LowLevel.Unsafe;
+using Unity.Mathematics;
+
+namespace Pathfinding.Util {
+	/// <summary>Various utilities for handling arrays and memory</summary>
+	public static class Memory {
+		/// <summary>
+		/// Returns a new array with at most length newLength.
+		/// The array will contain a copy of all elements of arr up to but excluding the index newLength.
+		/// </summary>
+		public static T[] ShrinkArray<T>(T[] arr, int newLength) {
+			newLength = Math.Min(newLength, arr.Length);
+			var shrunkArr = new T[newLength];
+			Array.Copy(arr, shrunkArr, newLength);
+			return shrunkArr;
+		}
+
+		/// <summary>Swaps the variables a and b</summary>
+		[System.Runtime.CompilerServices.MethodImpl(System.Runtime.CompilerServices.MethodImplOptions.AggressiveInlining)]
+		public static void Swap<T>(ref T a, ref T b) {
+			T tmp = a;
+
+			a = b;
+			b = tmp;
+		}
+
+		public static void Realloc<T>(ref NativeArray<T> arr, int newSize, Allocator allocator, NativeArrayOptions options = NativeArrayOptions.ClearMemory) where T : struct {
+			if (arr.IsCreated && arr.Length >= newSize) return;
+
+			var newArr = new NativeArray<T>(newSize, allocator, options);
+			if (arr.IsCreated) {
+				// Copy over old data
+				NativeArray<T>.Copy(arr, newArr, arr.Length);
+				arr.Dispose();
+			}
+			arr = newArr;
+		}
+
+		public static void Realloc<T>(ref T[] arr, int newSize) {
+			if (arr == null) {
+				arr = new T[newSize];
+			} else if (newSize > arr.Length) {
+				var newArr = new T[newSize];
+				arr.CopyTo(newArr, 0);
+				arr = newArr;
+			}
+		}
+
+		public static T[] UnsafeAppendBufferToArray<T>(UnsafeAppendBuffer src) where T : unmanaged {
+			var elementCount = src.Length / UnsafeUtility.SizeOf<T>();
+			var dst = new T[elementCount];
+
+			unsafe {
+				var gCHandle = System.Runtime.InteropServices.GCHandle.Alloc(dst, System.Runtime.InteropServices.GCHandleType.Pinned);
+				System.IntPtr value = gCHandle.AddrOfPinnedObject();
+				UnsafeUtility.MemCpy((byte*)(void*)value, src.Ptr, (long)elementCount * (long)UnsafeUtility.SizeOf<T>());
+				gCHandle.Free();
+			}
+			return dst;
+		}
+
+		public static void Rotate3DArray<T>(T[] arr, int3 size, int dx, int dz) {
+			int width = size.x;
+			int height = size.y;
+			int depth = size.z;
+			dx = dx % width;
+			dz = dz % depth;
+			if (dx != 0) {
+				if (dx < 0) dx = width + dx;
+				var tmp = ArrayPool<T>.Claim(dx);
+				for (int y = 0; y < height; y++) {
+					var offset = y * width * depth;
+					for (int z = 0; z < depth; z++) {
+						Array.Copy(arr, offset + z * width + width - dx, tmp, 0, dx);
+						Array.Copy(arr, offset + z * width, arr, offset + z * width + dx, width - dx);
+						Array.Copy(tmp, 0, arr, offset + z * width, dx);
+					}
+				}
+				ArrayPool<T>.Release(ref tmp);
+			}
+
+			if (dz != 0) {
+				if (dz < 0) dz = depth + dz;
+				var tmp = ArrayPool<T>.Claim(dz * width);
+				for (int y = 0; y < height; y++) {
+					var offset = y * width * depth;
+					Array.Copy(arr, offset + (depth - dz) * width, tmp, 0, dz * width);
+					Array.Copy(arr, offset, arr, offset + dz * width, (depth - dz) * width);
+					Array.Copy(tmp, 0, arr, offset, dz * width);
+				}
+				ArrayPool<T>.Release(ref tmp);
+			}
+		}
+	}
+}
diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Core/Collections/AstarMemory.cs.meta b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Core/Collections/AstarMemory.cs.meta
new file mode 100644
index 0000000..2b61ad2
--- /dev/null
+++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Core/Collections/AstarMemory.cs.meta
@@ -0,0 +1,7 @@
+fileFormatVersion: 2
+guid: 9bdecddfdfec947eb8ed96282e4b1fe1
+MonoImporter:
+  serializedVersion: 2
+  defaultReferences: []
+  executionOrder: 0
+  icon: {instanceID: 0}
diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Core/Collections/BinaryHeap.cs b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Core/Collections/BinaryHeap.cs
new file mode 100644
index 0000000..d76a67d
--- /dev/null
+++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Core/Collections/BinaryHeap.cs
@@ -0,0 +1,359 @@
+// #define VALIDATE_BINARY_HEAP
+#pragma warning disable 162
+#pragma warning disable 429
+using Unity.Mathematics;
+using Unity.Collections;
+using Unity.Burst;
+using Unity.Burst.CompilerServices;
+
+namespace Pathfinding {
+	using Pathfinding.Util;
+
+	/// <summary>
+	/// Binary heap implementation.
+	/// Binary heaps are really fast for ordering nodes in a way that
+	/// makes it possible to get the node with the lowest F score.
+	/// Also known as a priority queue.
+	///
+	/// This has actually been rewritten as a 4-ary heap
+	/// for performance, but it's the same principle.
+	///
+	/// See: http://en.wikipedia.org/wiki/Binary_heap
+	/// See: https://en.wikipedia.org/wiki/D-ary_heap
+	/// </summary>
+	[BurstCompile]
+	public struct BinaryHeap {
+		/// <summary>Number of items in the tree</summary>
+		public int numberOfItems;
+
+		/// <summary>The tree will grow by at least this factor every time it is expanded</summary>
+		public const float GrowthFactor = 2;
+
+		/// <summary>
+		/// Number of children of each node in the tree.
+		/// Different values have been tested and 4 has been empirically found to perform the best.
+		/// See: https://en.wikipedia.org/wiki/D-ary_heap
+		/// </summary>
+		const int D = 4;
+
+		/// <summary>
+		/// Sort nodes by G score if there is a tie when comparing the F score.
+		/// Disabling this will improve pathfinding performance with around 2.5%
+		/// but may break ties between paths that have the same length in a less
+		/// desirable manner (only relevant for grid graphs).
+		/// </summary>
+		const bool SortGScores = true;
+
+		public const ushort NotInHeap = 0xFFFF;
+
+		/// <summary>Internal backing array for the heap</summary>
+		private UnsafeSpan<HeapNode> heap;
+
+		/// <summary>True if the heap does not contain any elements</summary>
+		public bool isEmpty => numberOfItems <= 0;
+
+		/// <summary>Item in the heap</summary>
+		private struct HeapNode {
+			public uint pathNodeIndex;
+			/// <summary>Bitpacked F and G scores</summary>
+			public ulong sortKey;
+
+			public HeapNode (uint pathNodeIndex, uint g, uint f) {
+				this.pathNodeIndex = pathNodeIndex;
+				this.sortKey = ((ulong)f << 32) | (ulong)g;
+			}
+
+			public uint F {
+				get => (uint)(sortKey >> 32);
+				set => sortKey = (sortKey & 0xFFFFFFFFUL) | ((ulong)value << 32);
+			}
+
+			public uint G => (uint)sortKey;
+		}
+
+		/// <summary>
+		/// Rounds up v so that it has remainder 1 when divided by D.
+		/// I.e it is of the form n*D + 1 where n is any non-negative integer.
+		/// </summary>
+		static int RoundUpToNextMultipleMod1 (int v) {
+			// I have a feeling there is a nicer way to do this
+			return v + (4 - ((v-1) % D)) % D;
+		}
+
+		/// <summary>Create a new heap with the specified initial capacity</summary>
+		public BinaryHeap (int capacity) {
+			// Make sure the size has remainder 1 when divided by D
+			// This allows us to always guarantee that indices used in the Remove method
+			// will never throw out of bounds exceptions
+			capacity = RoundUpToNextMultipleMod1(capacity);
+
+			heap = new UnsafeSpan<HeapNode>(Unity.Collections.Allocator.Persistent, capacity);
+			numberOfItems = 0;
+		}
+
+		public void Dispose () {
+			unsafe {
+				AllocatorManager.Free<HeapNode>(Allocator.Persistent, heap.ptr, heap.Length);
+			}
+		}
+
+		/// <summary>Removes all elements from the heap</summary>
+		public void Clear (UnsafeSpan<PathNode> pathNodes) {
+			// Clear all heap indices, and references to the heap nodes
+			for (int i = 0; i < numberOfItems; i++) {
+				pathNodes[heap[i].pathNodeIndex].heapIndex = NotInHeap;
+			}
+
+			numberOfItems = 0;
+		}
+
+		[System.Runtime.CompilerServices.MethodImpl(System.Runtime.CompilerServices.MethodImplOptions.AggressiveInlining)]
+		public uint GetPathNodeIndex(int heapIndex) => heap[heapIndex].pathNodeIndex;
+
+		[System.Runtime.CompilerServices.MethodImpl(System.Runtime.CompilerServices.MethodImplOptions.AggressiveInlining)]
+		public uint GetG(int heapIndex) => heap[heapIndex].G;
+
+		[System.Runtime.CompilerServices.MethodImpl(System.Runtime.CompilerServices.MethodImplOptions.AggressiveInlining)]
+		public uint GetF(int heapIndex) => heap[heapIndex].F;
+
+		public void SetH (int heapIndex, uint h) {
+			heap[heapIndex].F = heap[heapIndex].G + h;
+		}
+
+		/// <summary>Expands to a larger backing array when the current one is too small</summary>
+		static void Expand (ref UnsafeSpan<HeapNode> heap) {
+			// 65533 == 1 mod 4 and slightly smaller than 1<<16 = 65536
+			int newSize = math.max(heap.Length+4, math.min(65533, (int)math.round(heap.Length*GrowthFactor)));
+
+			// Make sure the size has remainder 1 when divided by D
+			// This allows us to always guarantee that indices used in the Remove method
+			// will never throw out of bounds exceptions
+			newSize = RoundUpToNextMultipleMod1(newSize);
+
+			// Check if the heap is really large
+			// Also note that heaps larger than this are not supported
+			// since PathNode.heapIndex is a ushort and can only store
+			// values up to 65535 (NotInHeap = 65535 is reserved however)
+			if (newSize > (1<<16) - 2) {
+				throw new System.Exception("Binary Heap Size really large (>65534). A heap size this large is probably the cause of pathfinding running in an infinite loop. ");
+			}
+
+			var newHeap = new UnsafeSpan<HeapNode>(Unity.Collections.Allocator.Persistent, newSize);
+			newHeap.CopyFrom(heap);
+			unsafe {
+				AllocatorManager.Free<HeapNode>(Allocator.Persistent, heap.ptr, heap.Length);
+			}
+#if ASTARDEBUG
+			UnityEngine.Debug.Log("Resizing binary heap to "+newSize);
+#endif
+			heap = newHeap;
+		}
+
+		/// <summary>Adds a node to the heap</summary>
+		public void Add (UnsafeSpan<PathNode> nodes, uint pathNodeIndex, uint g, uint f) {
+			Add(ref this, ref nodes, pathNodeIndex, g, f);
+		}
+
+		[BurstCompile]
+		static void Add (ref BinaryHeap binaryHeap, ref UnsafeSpan<PathNode> nodes, uint pathNodeIndex, uint g, uint f) {
+			ref var numberOfItems = ref binaryHeap.numberOfItems;
+			ref var heap = ref binaryHeap.heap;
+
+			// Check if node is already in the heap
+			ref var node = ref nodes[pathNodeIndex];
+			if (node.heapIndex != NotInHeap) {
+				var activeNode = new HeapNode(pathNodeIndex, g, f);
+				UnityEngine.Assertions.Assert.AreEqual(activeNode.pathNodeIndex, pathNodeIndex);
+				DecreaseKey(heap, nodes, activeNode, node.heapIndex);
+				Validate(ref nodes, ref binaryHeap);
+			} else {
+				if (numberOfItems == heap.Length) {
+					Expand(ref heap);
+				}
+				Validate(ref nodes, ref binaryHeap);
+
+				DecreaseKey(heap, nodes, new HeapNode(pathNodeIndex, g, f), (ushort)numberOfItems);
+				numberOfItems++;
+				Validate(ref nodes, ref binaryHeap);
+			}
+		}
+
+		static void DecreaseKey (UnsafeSpan<HeapNode> heap, UnsafeSpan<PathNode> nodes, HeapNode node, ushort index) {
+			// This is where 'obj' is in the binary heap logically speaking
+			// (for performance reasons we don't actually store it there until
+			// we know the final index, that's just a waste of CPU cycles)
+			uint bubbleIndex = index;
+
+			while (bubbleIndex != 0) {
+				// Parent node of the bubble node
+				uint parentIndex = (bubbleIndex-1) / D;
+
+				Hint.Assume(parentIndex < heap.length);
+				Hint.Assume(bubbleIndex < heap.length);
+				if (node.sortKey < heap[parentIndex].sortKey) {
+					// Swap the bubble node and parent node
+					// (we don't really need to store the bubble node until we know the final index though
+					// so we do that after the loop instead)
+					heap[bubbleIndex] = heap[parentIndex];
+					nodes[heap[bubbleIndex].pathNodeIndex].heapIndex = (ushort)bubbleIndex;
+					bubbleIndex = parentIndex;
+				} else {
+					break;
+				}
+			}
+
+			Hint.Assume(bubbleIndex < heap.length);
+			heap[bubbleIndex] = node;
+			nodes[node.pathNodeIndex].heapIndex = (ushort)bubbleIndex;
+		}
+
+		/// <summary>Returns the node with the lowest F score from the heap</summary>
+		public uint Remove (UnsafeSpan<PathNode> nodes, out uint g, out uint f) {
+			return Remove(ref nodes, ref this, out g, out f);
+		}
+
+		[BurstCompile]
+		static uint Remove (ref UnsafeSpan<PathNode> nodes, ref BinaryHeap binaryHeap, [NoAlias] out uint removedG, [NoAlias] out uint removedF) {
+			ref var numberOfItems = ref binaryHeap.numberOfItems;
+			var heap = binaryHeap.heap;
+
+			if (numberOfItems == 0) {
+				throw new System.InvalidOperationException("Removing item from empty heap");
+			}
+
+			// This is the smallest item in the heap.
+			// Mark it as removed from the heap.
+			Hint.Assume(0UL < heap.length);
+			uint returnIndex = heap[0].pathNodeIndex;
+			nodes[returnIndex].heapIndex = NotInHeap;
+			removedG = heap[0].G;
+			removedF = heap[0].F;
+
+			numberOfItems--;
+			if (numberOfItems == 0) {
+				return returnIndex;
+			}
+
+			// Last item in the heap array
+			Hint.Assume((uint)numberOfItems < heap.length);
+			var swapItem = heap[numberOfItems];
+			uint swapIndex = 0;
+			ulong comparisonKey = swapItem.sortKey;
+
+			// Trickle upwards
+			while (true) {
+				var parent = swapIndex;
+				uint pd = parent * D + 1;
+
+				// If this holds, then the indices used
+				// below are guaranteed to not throw an index out of bounds
+				// exception since we choose the size of the array in that way
+				if (pd < numberOfItems) {
+					// Find the child node with the smallest F score, or if equal, the smallest G score.
+					// The sorting key is the tuple (F,G).
+					// However, to be able to easily get the smallest index, we steal the lowest 2 bits of G
+					// and use it for the child index (0..3) instead.
+					// This means that tie-breaking will not be perfect, but in all practical cases it will
+					// yield exactly the same result since G scores typically differ by more than 4 anyway.
+					Hint.Assume(pd+0 < heap.length);
+					ulong l0 = (heap[pd+0].sortKey & ~0x3UL) | 0;
+					Hint.Assume(pd+1 < heap.length);
+					ulong l1 = (heap[pd+1].sortKey & ~0x3UL) | 1;
+					Hint.Assume(pd+2 < heap.length);
+					ulong l2 = (heap[pd+2].sortKey & ~0x3UL) | 2;
+					Hint.Assume(pd+3 < heap.length);
+					ulong l3 = (heap[pd+3].sortKey & ~0x3UL) | 3;
+
+					ulong smallest = l0;
+					// Not all children may exist, so we need to check that the index is valid
+					if (pd+1 < numberOfItems) smallest = math.min(smallest, l1);
+					if (pd+2 < numberOfItems) smallest = math.min(smallest, l2);
+					if (pd+3 < numberOfItems) smallest = math.min(smallest, l3);
+
+					if (smallest < comparisonKey) {
+						swapIndex = pd + (uint)(smallest & 0x3UL);
+
+						// One if the parent's children are smaller or equal, swap them
+						// (actually we are just pretenting we swapped them, we hold the swapItem
+						// in local variable and only assign it once we know the final index)
+						Hint.Assume(parent < heap.length);
+						Hint.Assume(swapIndex < heap.length);
+						heap[parent] = heap[swapIndex];
+						Hint.Assume(swapIndex < heap.length);
+						nodes[heap[swapIndex].pathNodeIndex].heapIndex = (ushort)parent;
+					} else {
+						break;
+					}
+				} else {
+					break;
+				}
+			}
+
+			// Assign element to the final position
+			Hint.Assume(swapIndex < heap.length);
+			heap[swapIndex] = swapItem;
+			nodes[swapItem.pathNodeIndex].heapIndex = (ushort)swapIndex;
+
+			// For debugging
+			Validate(ref nodes, ref binaryHeap);
+
+			return returnIndex;
+		}
+
+		[System.Diagnostics.Conditional("VALIDATE_BINARY_HEAP")]
+		static void Validate (ref UnsafeSpan<PathNode> nodes, ref BinaryHeap binaryHeap) {
+			for (int i = 1; i < binaryHeap.numberOfItems; i++) {
+				int parentIndex = (i-1)/D;
+				if (binaryHeap.heap[parentIndex].F > binaryHeap.heap[i].F) {
+					throw new System.Exception("Invalid state at " + i + ":" +  parentIndex + " ( " + binaryHeap.heap[parentIndex].F + " > " + binaryHeap.heap[i].F + " ) ");
+				}
+
+				if (binaryHeap.heap[parentIndex].sortKey > binaryHeap.heap[i].sortKey) {
+					throw new System.Exception("Invalid state at " + i + ":" +  parentIndex + " ( " + binaryHeap.heap[parentIndex].F + " > " + binaryHeap.heap[i].F + " ) ");
+				}
+
+				if (nodes[binaryHeap.heap[i].pathNodeIndex].heapIndex != i) {
+					throw new System.Exception("Invalid heap index");
+				}
+			}
+		}
+
+		/// <summary>
+		/// Rebuilds the heap by trickeling down all items.
+		/// Usually called after the hTarget on a path has been changed
+		/// </summary>
+		public void Rebuild (UnsafeSpan<PathNode> nodes) {
+#if ASTARDEBUG
+			int changes = 0;
+#endif
+
+			for (int i = 2; i < numberOfItems; i++) {
+				int bubbleIndex = i;
+				var node = heap[i];
+				uint nodeF = node.F;
+				while (bubbleIndex != 1) {
+					int parentIndex = bubbleIndex / D;
+
+					if (nodeF < heap[parentIndex].F) {
+						heap[bubbleIndex] = heap[parentIndex];
+						nodes[heap[bubbleIndex].pathNodeIndex].heapIndex = (ushort)bubbleIndex;
+
+						heap[parentIndex] = node;
+						nodes[heap[parentIndex].pathNodeIndex].heapIndex = (ushort)parentIndex;
+
+						bubbleIndex = parentIndex;
+#if ASTARDEBUG
+						changes++;
+#endif
+					} else {
+						break;
+					}
+				}
+			}
+
+#if ASTARDEBUG
+			UnityEngine.Debug.Log("+++ Rebuilt Heap - "+changes+" changes +++");
+#endif
+		}
+	}
+}
diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Core/Collections/BinaryHeap.cs.meta b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Core/Collections/BinaryHeap.cs.meta
new file mode 100644
index 0000000..0ba2009
--- /dev/null
+++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Core/Collections/BinaryHeap.cs.meta
@@ -0,0 +1,7 @@
+fileFormatVersion: 2
+guid: eb4299e8747f44ad2b4e086752108ea3
+MonoImporter:
+  serializedVersion: 2
+  defaultReferences: []
+  executionOrder: 0
+  icon: {instanceID: 0}
diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Core/Collections/CircularBuffer.cs b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Core/Collections/CircularBuffer.cs
new file mode 100644
index 0000000..37b88d2
--- /dev/null
+++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Core/Collections/CircularBuffer.cs
@@ -0,0 +1,244 @@
+using System.Collections;
+using System.Collections.Generic;
+using Pathfinding.Util;
+using Unity.Collections.LowLevel.Unsafe;
+using Unity.Mathematics;
+using UnityEngine.Assertions;
+
+namespace Pathfinding.Util {
+	/// <summary>
+	/// Implements an efficient circular buffer that can be appended to in both directions.
+	///
+	/// See: <see cref="NativeCircularBuffer"/>
+	/// </summary>
+	public struct CircularBuffer<T> : IReadOnlyList<T>, IReadOnlyCollection<T> {
+		internal T[] data;
+		internal int head;
+		int length;
+
+		/// <summary>Number of items in the buffer</summary>
+		public readonly int Length => length;
+		/// <summary>Absolute index of the first item in the buffer, may be negative or greater than <see cref="Length"/></summary>
+		public readonly int AbsoluteStartIndex => head;
+		/// <summary>Absolute index of the last item in the buffer, may be negative or greater than <see cref="Length"/></summary>
+		public readonly int AbsoluteEndIndex => head + length - 1;
+
+		/// <summary>First item in the buffer, throws if the buffer is empty</summary>
+		public readonly ref T First => ref data[head & (data.Length-1)];
+
+		/// <summary>Last item in the buffer, throws if the buffer is empty</summary>
+		public readonly ref T Last => ref data[(head+length-1) & (data.Length-1)];
+
+		readonly int IReadOnlyCollection<T>.Count {
+			get {
+				return length;
+			}
+		}
+
+		/// <summary>Create a new buffer with the given capacity</summary>
+		public CircularBuffer(int initialCapacity) {
+			data = ArrayPool<T>.Claim(initialCapacity);
+			head = 0;
+			length = 0;
+		}
+
+		/// <summary>
+		/// Create a new buffer using the given array as an internal store.
+		/// This will take ownership of the given array.
+		/// </summary>
+		public CircularBuffer(T[] backingArray) {
+			data = backingArray;
+			head = 0;
+			length = 0;
+		}
+
+		/// <summary>Resets the buffer's length to zero. Does not clear the current allocation</summary>
+		public void Clear () {
+			length = 0;
+			head = 0;
+		}
+
+		/// <summary>Appends a list of items to the end of the buffer</summary>
+		public void AddRange (List<T> items) {
+			// TODO: Can be optimized
+			for (int i = 0; i < items.Count; i++) PushEnd(items[i]);
+		}
+
+		/// <summary>Pushes a new item to the start of the buffer</summary>
+		[System.Runtime.CompilerServices.MethodImpl(System.Runtime.CompilerServices.MethodImplOptions.AggressiveInlining)]
+		public void PushStart (T item) {
+			if (data == null || length >= data.Length) Grow();
+			length += 1;
+			head -= 1;
+			this[0] = item;
+		}
+
+		/// <summary>Pushes a new item to the end of the buffer</summary>
+		[System.Runtime.CompilerServices.MethodImpl(System.Runtime.CompilerServices.MethodImplOptions.AggressiveInlining)]
+		public void PushEnd (T item) {
+			if (data == null || length >= data.Length) Grow();
+			length += 1;
+			this[length-1] = item;
+		}
+
+		/// <summary>Pushes a new item to the start or the end of the buffer</summary>
+		[System.Runtime.CompilerServices.MethodImpl(System.Runtime.CompilerServices.MethodImplOptions.AggressiveInlining)]
+		public void Push (bool toStart, T item) {
+			if (toStart) PushStart(item);
+			else PushEnd(item);
+		}
+
+		/// <summary>Removes and returns the first element</summary>
+		public T PopStart () {
+			if (length == 0) throw new System.InvalidOperationException();
+			var r = this[0];
+			head++;
+			length--;
+			return r;
+		}
+
+		/// <summary>Removes and returns the last element</summary>
+		public T PopEnd () {
+			if (length == 0) throw new System.InvalidOperationException();
+			var r = this[length-1];
+			length--;
+			return r;
+		}
+
+		/// <summary>Pops either from the start or from the end of the buffer</summary>
+		public T Pop (bool fromStart) {
+			if (fromStart) return PopStart();
+			else return PopEnd();
+		}
+
+		/// <summary>Return either the first element or the last element</summary>
+		public readonly T GetBoundaryValue (bool start) {
+			return GetAbsolute(start ? AbsoluteStartIndex : AbsoluteEndIndex);
+		}
+
+		/// <summary>Inserts an item at the given absolute index</summary>
+		public void InsertAbsolute (int index, T item) {
+			SpliceUninitializedAbsolute(index, 0, 1);
+			data[index & (data.Length - 1)] = item;
+		}
+
+		/// <summary>Removes toRemove items from the buffer, starting at startIndex, and then inserts the toInsert items at startIndex</summary>
+		public void Splice (int startIndex, int toRemove, List<T> toInsert) {
+			SpliceAbsolute(startIndex + head, toRemove, toInsert);
+		}
+
+		/// <summary>Like <see cref="Splice"/>, but startIndex is an absolute index</summary>
+		public void SpliceAbsolute (int startIndex, int toRemove, List<T> toInsert) {
+			if (toInsert == null) {
+				SpliceUninitializedAbsolute(startIndex, toRemove, 0);
+			} else {
+				SpliceUninitializedAbsolute(startIndex, toRemove, toInsert.Count);
+				for (int i = 0; i < toInsert.Count; i++) data[(startIndex + i) & (data.Length - 1)] = toInsert[i];
+			}
+		}
+
+		/// <summary>Like <see cref="Splice"/>, but the newly inserted items are left in an uninitialized state</summary>
+		public void SpliceUninitialized (int startIndex, int toRemove, int toInsert) {
+			SpliceUninitializedAbsolute(startIndex + head, toRemove, toInsert);
+		}
+
+		/// <summary>Like <see cref="SpliceUninitialized"/>, but startIndex is an absolute index</summary>
+		public void SpliceUninitializedAbsolute (int startIndex, int toRemove, int toInsert) {
+#if ENABLE_UNITY_COLLECTIONS_CHECKS
+			if (startIndex - head < 0 || startIndex + toRemove - head > length) throw new System.ArgumentOutOfRangeException();
+#endif
+			var itemsToAdd = toInsert - toRemove;
+			while (this.length + itemsToAdd > this.data.Length) Grow();
+
+			// move items [startIndex+length .. end] itemsToAdd steps forward in the array
+			MoveAbsolute(startIndex + toRemove, AbsoluteEndIndex, itemsToAdd);
+			this.length += itemsToAdd;
+		}
+
+		void MoveAbsolute (int startIndex, int endIndex, int deltaIndex) {
+			if (deltaIndex > 0) {
+				for (int i = endIndex; i >= startIndex; i--) data[(i+deltaIndex) & (data.Length-1)] = data[i & (data.Length-1)];
+			} else if (deltaIndex < 0) {
+				for (int i = startIndex; i <= endIndex; i++) data[(i+deltaIndex) & (data.Length-1)] = data[i & (data.Length-1)];
+			}
+		}
+
+		/// <summary>Indexes the buffer, with index 0 being the first element</summary>
+		public T this[int index] {
+			[System.Runtime.CompilerServices.MethodImpl(System.Runtime.CompilerServices.MethodImplOptions.AggressiveInlining)]
+			readonly get {
+#if UNITY_EDITOR
+				if ((uint)index >= length) throw new System.ArgumentOutOfRangeException();
+#endif
+				return data[(index+head) & (data.Length-1)];
+			}
+			[System.Runtime.CompilerServices.MethodImpl(System.Runtime.CompilerServices.MethodImplOptions.AggressiveInlining)]
+			set {
+#if UNITY_EDITOR
+				if ((uint)index >= length) throw new System.ArgumentOutOfRangeException();
+#endif
+				data[(index+head) & (data.Length-1)] = value;
+			}
+		}
+
+		/// <summary>
+		/// Indexes the buffer using absolute indices.
+		/// When pushing to and popping from the buffer, the absolute indices do not change.
+		/// So e.g. after doing PushStart(x) on an empty buffer, GetAbsolute(-1) will get the newly pushed element.
+		/// </summary>
+		[System.Runtime.CompilerServices.MethodImpl(System.Runtime.CompilerServices.MethodImplOptions.AggressiveInlining)]
+		public readonly T GetAbsolute (int index) {
+#if UNITY_EDITOR
+			if ((uint)(index - head) >= length) throw new System.ArgumentOutOfRangeException();
+#endif
+			return data[index & (data.Length-1)];
+		}
+
+		[System.Runtime.CompilerServices.MethodImpl(System.Runtime.CompilerServices.MethodImplOptions.AggressiveInlining)]
+		public readonly void SetAbsolute (int index, T value) {
+#if UNITY_EDITOR
+			if ((uint)(index - head) >= length) throw new System.ArgumentOutOfRangeException();
+#endif
+			data[index & (data.Length-1)] = value;
+		}
+
+		void Grow () {
+			var newData = ArrayPool<T>.Claim(System.Math.Max(4, data != null ? data.Length*2 : 0));
+			if (data != null) {
+				var inOrderItems = data.Length - (head & (data.Length-1));
+				System.Array.Copy(data, head & (data.Length-1), newData, head & (newData.Length - 1), inOrderItems);
+				var wraparoundItems = length - inOrderItems;
+				if (wraparoundItems > 0) System.Array.Copy(data, 0, newData, (head + inOrderItems) & (newData.Length - 1), wraparoundItems);
+				ArrayPool<T>.Release(ref data);
+			}
+			data = newData;
+		}
+
+		/// <summary>Release the backing array of this buffer back into an array pool</summary>
+		public void Pool () {
+			ArrayPool<T>.Release(ref data);
+			length = 0;
+			head = 0;
+		}
+
+		public IEnumerator<T> GetEnumerator () {
+			for (int i = 0; i < length; i++) {
+				yield return this[i];
+			}
+		}
+
+		IEnumerator IEnumerable.GetEnumerator () {
+			for (int i = 0; i < length; i++) {
+				yield return this[i];
+			}
+		}
+
+		public CircularBuffer<T> Clone () {
+			return new CircularBuffer<T> {
+					   data = data != null ? (T[])data.Clone() : null,
+					   length = length,
+					   head = head
+			};
+		}
+	}
+}
diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Core/Collections/CircularBuffer.cs.meta b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Core/Collections/CircularBuffer.cs.meta
new file mode 100644
index 0000000..ea6fc4e
--- /dev/null
+++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Core/Collections/CircularBuffer.cs.meta
@@ -0,0 +1,11 @@
+fileFormatVersion: 2
+guid: 2c76961280d816f42a709dc7150208c6
+MonoImporter:
+  externalObjects: {}
+  serializedVersion: 2
+  defaultReferences: []
+  executionOrder: 0
+  icon: {instanceID: 0}
+  userData: 
+  assetBundleName: 
+  assetBundleVariant: 
diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Core/Collections/HierarchicalBitset.cs b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Core/Collections/HierarchicalBitset.cs
new file mode 100644
index 0000000..ed23e94
--- /dev/null
+++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Core/Collections/HierarchicalBitset.cs
@@ -0,0 +1,288 @@
+using System.Collections;
+using System.Collections.Generic;
+using System.Diagnostics;
+using Unity.Burst;
+using Unity.Collections;
+using Unity.Collections.LowLevel.Unsafe;
+using Unity.Mathematics;
+using UnityEngine.Assertions;
+
+namespace Pathfinding.Util {
+	/// <summary>
+	/// Thread-safe hierarchical bitset.
+	///
+	/// Stores an array of bits. Each bit can be set or cleared individually from any thread.
+	///
+	/// Note: Setting the capacity is not thread-safe, nor is iterating over the bitset while it is being modified.
+	/// </summary>
+	[BurstCompile]
+	public struct HierarchicalBitset {
+		UnsafeSpan<ulong> l1;
+		UnsafeSpan<ulong> l2;
+		UnsafeSpan<ulong> l3;
+		Allocator allocator;
+
+		const int Log64 = 6;
+
+		public HierarchicalBitset (int size, Allocator allocator) {
+			this.allocator = allocator;
+			l1 = new UnsafeSpan<ulong>(allocator, (size + 64 - 1) >> Log64);
+			l2 = new UnsafeSpan<ulong>(allocator, (size + (64*64 - 1)) >> Log64 >> Log64);
+			l3 = new UnsafeSpan<ulong>(allocator, (size + (64*64*64 - 1)) >> Log64 >> Log64 >> Log64);
+			l1.FillZeros();
+			l2.FillZeros();
+			l3.FillZeros();
+		}
+
+		public bool IsCreated => Capacity > 0;
+
+		public void Dispose () {
+			l1.Free(allocator);
+			l2.Free(allocator);
+			l3.Free(allocator);
+			this = default;
+		}
+
+		public int Capacity {
+			get {
+				return l1.Length << Log64;
+			}
+			set {
+				if (value < Capacity) throw new System.ArgumentException("Shrinking the bitset is not supported");
+				if (value == Capacity) return;
+				var b = new HierarchicalBitset(value, allocator);
+
+				// Copy the old data
+				l1.CopyTo(b.l1);
+				l2.CopyTo(b.l2);
+				l3.CopyTo(b.l3);
+
+				Dispose();
+				this = b;
+			}
+		}
+
+		/// <summary>Number of set bits in the bitset</summary>
+		public int Count () {
+			int count = 0;
+			for (int i = 0; i < l1.Length; i++) {
+				count += math.countbits(l1[i]);
+			}
+			return count;
+		}
+
+		/// <summary>True if the bitset is empty</summary>
+		public bool IsEmpty {
+			get {
+				for (int i = 0; i < l3.Length; i++) {
+					if (l3[i] != 0) return false;
+				}
+				return true;
+			}
+		}
+
+		/// <summary>Clear all bits</summary>
+		public void Clear () {
+			// TODO: Optimize?
+			l1.FillZeros();
+			l2.FillZeros();
+			l3.FillZeros();
+		}
+
+		public void GetIndices (NativeList<int> result) {
+			var buffer = new NativeArray<int>(256, Allocator.Temp);
+			var iter = GetIterator(buffer.AsUnsafeSpan());
+			while (iter.MoveNext()) {
+				var span = iter.Current;
+				for (int i = 0; i < span.Length; i++) {
+					result.Add(span[i]);
+				}
+			}
+		}
+
+
+		[System.Runtime.CompilerServices.MethodImpl(System.Runtime.CompilerServices.MethodImplOptions.AggressiveInlining)]
+		static bool SetAtomic (ref UnsafeSpan<ulong> span, int index) {
+			var cellIndex = index >> Log64;
+			var currentValue = span[cellIndex];
+			// Note: 1 << index will only use the lower 6 bits of index
+			if ((currentValue & (1UL << index)) != 0) {
+				// Bit already set
+				return true;
+			}
+
+			// TODO: Use Interlocked.Or in newer .net versions
+			while (true) {
+				var actualValue = (ulong)System.Threading.Interlocked.CompareExchange(ref UnsafeUtility.As<ulong, long>(ref span[cellIndex]), (long)(currentValue | (1UL << index)), (long)currentValue);
+				if (actualValue != currentValue) currentValue = actualValue;
+				else break;
+			}
+			return false;
+		}
+
+		[System.Runtime.CompilerServices.MethodImpl(System.Runtime.CompilerServices.MethodImplOptions.AggressiveInlining)]
+		static bool ResetAtomic (ref UnsafeSpan<ulong> span, int index) {
+			var cellIndex = index >> Log64;
+			var currentValue = span[cellIndex];
+			// Note: 1 << index will only use the lower 6 bits of index
+			if ((currentValue & (1UL << index)) == 0) {
+				// Bit already cleared
+				return true;
+			}
+
+			// TODO: Use Interlocked.Or in newer .net versions
+			while (true) {
+				var actualValue = (ulong)System.Threading.Interlocked.CompareExchange(ref UnsafeUtility.As<ulong, long>(ref span[cellIndex]), (long)(currentValue & ~(1UL << index)), (long)currentValue);
+				if (actualValue != currentValue) currentValue = actualValue;
+				else break;
+			}
+			return false;
+		}
+
+		/// <summary>Get the value of a bit</summary>
+		[System.Runtime.CompilerServices.MethodImpl(System.Runtime.CompilerServices.MethodImplOptions.AggressiveInlining)]
+		public bool Get (int index) {
+			// Note: 1 << index will only use the lower 6 bits of index
+			return (l1[index >> Log64] & (1UL << index)) != 0;
+		}
+
+		/// <summary>Set a given bit to 1</summary>
+		[System.Runtime.CompilerServices.MethodImpl(System.Runtime.CompilerServices.MethodImplOptions.AggressiveInlining)]
+		public void Set (int index) {
+			if (SetAtomic(ref l1, index)) return;
+			SetAtomic(ref l2, index >> Log64);
+			SetAtomic(ref l3, index >> (2*Log64));
+		}
+
+		/// <summary>Set a given bit to 0</summary>
+		[System.Runtime.CompilerServices.MethodImpl(System.Runtime.CompilerServices.MethodImplOptions.AggressiveInlining)]
+		public void Reset (int index) {
+			if (ResetAtomic(ref l1, index)) return;
+			if (l1[index >> Log64] == 0) ResetAtomic(ref l2, index >> Log64);
+			if (l2[index >> (2*Log64)] == 0) ResetAtomic(ref l3, index >> (2*Log64));
+		}
+
+		/// <summary>Get an iterator over all set bits.</summary>
+		/// <param name="scratchBuffer">A buffer to use for temporary storage. A slice of this buffer will be returned on each iteration, filled with the indices of the set bits.</param>
+		public Iterator GetIterator (UnsafeSpan<int> scratchBuffer) {
+			return new Iterator(this, scratchBuffer);
+		}
+
+		[BurstCompile]
+		public struct Iterator : IEnumerator<UnsafeSpan<int> >, IEnumerable<UnsafeSpan<int> > {
+			HierarchicalBitset bitSet;
+			UnsafeSpan<int> result;
+			int resultCount;
+			int l3index;
+			int l3bitIndex;
+			int l2bitIndex;
+
+			public UnsafeSpan<int> Current => result.Slice(0, resultCount);
+
+			object IEnumerator.Current => throw new System.NotImplementedException();
+
+			public void Reset() => throw new System.NotImplementedException();
+
+			public void Dispose () {}
+
+			public IEnumerator<UnsafeSpan<int> > GetEnumerator() => this;
+
+			IEnumerator IEnumerable.GetEnumerator() => throw new System.NotImplementedException();
+
+			static int l2index(int l3index, int l3bitIndex) => (l3index << Log64) + l3bitIndex;
+			static int l1index(int l2index, int l2bitIndex) => (l2index << Log64) + l2bitIndex;
+
+			public Iterator (HierarchicalBitset bitSet, UnsafeSpan<int> result) {
+				this.bitSet = bitSet;
+				this.result = result;
+				resultCount = 0;
+				l3index = 0;
+				l3bitIndex = 0;
+				l2bitIndex = 0;
+				if (result.Length < 128) {
+					// Minimum is actually 64, but that can be very inefficient
+					throw new System.ArgumentException("Result array must be at least 128 elements long");
+				}
+			}
+
+			public bool MoveNext () {
+				return MoveNextBurst(ref this);
+			}
+
+			[BurstCompile]
+			public static bool MoveNextBurst (ref Iterator iter) {
+				return iter.MoveNextInternal();
+			}
+
+			// Inline
+			[System.Runtime.CompilerServices.MethodImpl(System.Runtime.CompilerServices.MethodImplOptions.AggressiveInlining)]
+			bool MoveNextInternal () {
+				// Store various data in local variables to avoid writing them to memory every time they are updated
+				uint resultCount = 0;
+				int l3index = this.l3index;
+				int l3bitIndex = this.l3bitIndex;
+				int l2bitIndex = this.l2bitIndex;
+				Assert.IsTrue(l2bitIndex < 64 && l3bitIndex < 64);
+
+				for (; l3index < bitSet.l3.length; l3index++) {
+					// Get the L3 cell, and mask out all bits we have already visited
+					var l3cell = bitSet.l3[l3index] & (~0UL << l3bitIndex);
+					if (l3cell == 0) continue;
+
+					while (l3cell != 0) {
+						// Find the next set bit in the L3 cell
+						l3bitIndex = math.tzcnt(l3cell);
+
+						// Nest check for level 2
+						int l2index = Iterator.l2index(l3index, l3bitIndex);
+						// The l2 cell is guaranteed to be non-zero, even after masking out the bits we have already visited
+						var l2cell = bitSet.l2[l2index] & (~0UL << l2bitIndex);
+						Assert.AreNotEqual(0, l2cell);
+
+						while (l2cell != 0) {
+							l2bitIndex = math.tzcnt(l2cell);
+							// Stop the loop if we have almost filled the result array
+							// Each L1 cell may contain up to 64 set bits
+							if (resultCount + 64 > result.Length) {
+								this.resultCount = (int)resultCount;
+								this.l3index = l3index;
+								this.l3bitIndex = l3bitIndex;
+								this.l2bitIndex = l2bitIndex;
+								return true;
+							}
+
+							int l1index = Iterator.l1index(l2index, l2bitIndex);
+							var l1cell = bitSet.l1[l1index];
+							int l1indexStart = l1index << Log64;
+							Assert.AreNotEqual(0, l1cell);
+
+							while (l1cell != 0) {
+								var l1bitIndex = math.tzcnt(l1cell);
+								l1cell &= l1cell - 1UL; // clear lowest bit
+								int index = l1indexStart + l1bitIndex;
+								Unity.Burst.CompilerServices.Hint.Assume(resultCount < (uint)result.Length);
+								result[resultCount++] = index;
+							}
+
+							l2cell &= l2cell - 1UL;
+						}
+
+						// Skip a bit at the L3 level
+						l3cell &= l3cell - 1UL; // clear lowest bit
+						// Enter new L2 level
+						l2bitIndex = 0;
+					}
+
+					l2bitIndex = 0;
+					l3bitIndex = 0;
+				}
+
+				this.resultCount = (int)resultCount;
+				this.l3index = l3index;
+				this.l3bitIndex = l3bitIndex;
+				this.l2bitIndex = l2bitIndex;
+				return resultCount > 0;
+			}
+		}
+	}
+}
diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Core/Collections/HierarchicalBitset.cs.meta b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Core/Collections/HierarchicalBitset.cs.meta
new file mode 100644
index 0000000..e49aade
--- /dev/null
+++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Core/Collections/HierarchicalBitset.cs.meta
@@ -0,0 +1,11 @@
+fileFormatVersion: 2
+guid: 7c9a4ed21e5f87d40aba2fcc4e01146d
+MonoImporter:
+  externalObjects: {}
+  serializedVersion: 2
+  defaultReferences: []
+  executionOrder: 0
+  icon: {instanceID: 0}
+  userData: 
+  assetBundleName: 
+  assetBundleVariant: 
diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Core/Collections/NativeCircularBuffer.cs b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Core/Collections/NativeCircularBuffer.cs
new file mode 100644
index 0000000..6f4eb4a
--- /dev/null
+++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Core/Collections/NativeCircularBuffer.cs
@@ -0,0 +1,318 @@
+using System.Collections;
+using System.Collections.Generic;
+using Unity.Collections;
+using Unity.Collections.LowLevel.Unsafe;
+using Unity.Mathematics;
+using UnityEngine.Assertions;
+
+namespace Pathfinding.Util {
+	/// <summary>
+	/// Implements an efficient circular buffer that can be appended to in both directions.
+	///
+	/// See: <see cref="CircularBuffer"/>
+	/// </summary>
+	public struct NativeCircularBuffer<T> : IReadOnlyList<T>, IReadOnlyCollection<T> where T : unmanaged {
+		[NativeDisableUnsafePtrRestriction]
+		internal unsafe T* data;
+		internal int head;
+		int length;
+		/// <summary>Capacity of the allocation minus 1. Invariant: (a power of two) minus 1</summary>
+		int capacityMask;
+
+		/// <summary>The allocator used to create the internal buffer.</summary>
+		public AllocatorManager.AllocatorHandle Allocator;
+		/// <summary>Number of items in the buffer</summary>
+		public readonly int Length => length;
+		/// <summary>Absolute index of the first item in the buffer, may be negative or greater than <see cref="Length"/></summary>
+		public readonly int AbsoluteStartIndex => head;
+		/// <summary>Absolute index of the last item in the buffer, may be negative or greater than <see cref="Length"/></summary>
+		public readonly int AbsoluteEndIndex => head + length - 1;
+
+		/// <summary>First item in the buffer throws if the buffer is empty</summary>
+		public readonly ref T First {
+			[System.Runtime.CompilerServices.MethodImpl(System.Runtime.CompilerServices.MethodImplOptions.AggressiveInlining)]
+			get {
+				unsafe {
+#if ENABLE_UNITY_COLLECTIONS_CHECKS
+					if (length == 0) throw new System.InvalidOperationException();
+#endif
+					return ref data[head & capacityMask];
+				}
+			}
+		}
+
+		/// <summary>Last item in the buffer, throws if the buffer is empty</summary>
+		public readonly ref T Last {
+			[System.Runtime.CompilerServices.MethodImpl(System.Runtime.CompilerServices.MethodImplOptions.AggressiveInlining)]
+			get {
+#if ENABLE_UNITY_COLLECTIONS_CHECKS
+				if (length == 0) throw new System.InvalidOperationException();
+#endif
+				unsafe { return ref data[(head+length-1) & capacityMask]; }
+			}
+		}
+
+		readonly int IReadOnlyCollection<T>.Count => Length;
+
+		public readonly bool IsCreated {
+			get {
+				unsafe {
+					return data != null;
+				}
+			}
+		}
+
+		/// <summary>Create a new empty buffer</summary>
+
+		public NativeCircularBuffer(AllocatorManager.AllocatorHandle allocator) {
+			unsafe {
+				data = null;
+			}
+			Allocator = allocator;
+			capacityMask = -1;
+			head = 0;
+			length = 0;
+		}
+
+		/// <summary>Create a new buffer with the given capacity</summary>
+		public NativeCircularBuffer(int initialCapacity, AllocatorManager.AllocatorHandle allocator) {
+			initialCapacity = math.ceilpow2(initialCapacity);
+			unsafe {
+				data = AllocatorManager.Allocate<T>(allocator, initialCapacity);
+				capacityMask = initialCapacity - 1;
+			}
+			Allocator = allocator;
+			head = 0;
+			length = 0;
+		}
+
+		unsafe public NativeCircularBuffer(CircularBuffer<T> buffer, out ulong gcHandle) : this(buffer.data, buffer.head, buffer.Length, out gcHandle) {}
+
+		unsafe public NativeCircularBuffer(T[] data, int head, int length, out ulong gcHandle) {
+			Assert.IsTrue((data.Length & (data.Length - 1)) == 0);
+			Assert.IsTrue(length <= data.Length);
+			unsafe {
+				this.data = (T*)UnsafeUtility.PinGCArrayAndGetDataAddress(data, out gcHandle);
+			}
+			this.capacityMask = data.Length - 1;
+			this.head = head;
+			this.length = length;
+			Allocator = Unity.Collections.Allocator.None;
+		}
+
+		/// <summary>Resets the buffer's length to zero. Does not clear the current allocation</summary>
+		public void Clear () {
+			length = 0;
+			head = 0;
+		}
+
+		/// <summary>Appends a list of items to the end of the buffer</summary>
+		public void AddRange (List<T> items) {
+			// TODO: Can be optimized
+			for (int i = 0; i < items.Count; i++) PushEnd(items[i]);
+		}
+
+		/// <summary>Pushes a new item to the start of the buffer</summary>
+		[System.Runtime.CompilerServices.MethodImpl(System.Runtime.CompilerServices.MethodImplOptions.AggressiveInlining)]
+		public void PushStart (T item) {
+			if (length > capacityMask) Grow();
+			length += 1;
+			head -= 1;
+			this[0] = item;
+		}
+
+		/// <summary>Pushes a new item to the end of the buffer</summary>
+		[System.Runtime.CompilerServices.MethodImpl(System.Runtime.CompilerServices.MethodImplOptions.AggressiveInlining)]
+		public void PushEnd (T item) {
+			if (length > capacityMask) Grow();
+			length += 1;
+			this[length-1] = item;
+		}
+
+		/// <summary>Pushes a new item to the start or the end of the buffer</summary>
+		[System.Runtime.CompilerServices.MethodImpl(System.Runtime.CompilerServices.MethodImplOptions.AggressiveInlining)]
+		public void Push (bool toStart, T item) {
+			if (toStart) PushStart(item);
+			else PushEnd(item);
+		}
+
+		/// <summary>Removes and returns the first element</summary>
+		public T PopStart () {
+#if ENABLE_UNITY_COLLECTIONS_CHECKS
+			if (length == 0) throw new System.InvalidOperationException();
+#endif
+			var r = this[0];
+			head++;
+			length--;
+			return r;
+		}
+
+		/// <summary>Removes and returns the last element</summary>
+		public T PopEnd () {
+#if ENABLE_UNITY_COLLECTIONS_CHECKS
+			if (length == 0) throw new System.InvalidOperationException();
+#endif
+			var r = this[length-1];
+			length--;
+			return r;
+		}
+
+		/// <summary>Pops either from the start or from the end of the buffer</summary>
+		public T Pop (bool fromStart) {
+			if (fromStart) return PopStart();
+			else return PopEnd();
+		}
+
+		/// <summary>Return either the first element or the last element</summary>
+		public readonly T GetBoundaryValue (bool start) {
+			return start ? GetAbsolute(AbsoluteStartIndex) : GetAbsolute(AbsoluteEndIndex);
+		}
+
+		/// <summary>Lowers the length of the buffer to the given value, and does nothing if the given value is greater or equal to the current length</summary>
+
+		public void TrimTo (int length) {
+#if ENABLE_UNITY_COLLECTIONS_CHECKS
+			if (length < 0) throw new System.ArgumentOutOfRangeException();
+#endif
+			this.length = math.min(this.length, length);
+		}
+
+		/// <summary>Removes toRemove items from the buffer, starting at startIndex, and then inserts the toInsert items at startIndex</summary>
+
+		public void Splice (int startIndex, int toRemove, List<T> toInsert) {
+			SpliceAbsolute(startIndex + head, toRemove, toInsert);
+		}
+
+		/// <summary>Like <see cref="Splice"/>, but startIndex is an absolute index</summary>
+
+		public void SpliceAbsolute (int startIndex, int toRemove, List<T> toInsert) {
+			SpliceUninitializedAbsolute(startIndex, toRemove, toInsert.Count);
+			unsafe {
+				for (int i = 0; i < toInsert.Count; i++) data[(startIndex + i) & capacityMask] = toInsert[i];
+			}
+		}
+
+		/// <summary>Like <see cref="Splice"/>, but the newly inserted items are left in an uninitialized state</summary>
+		public void SpliceUninitialized (int startIndex, int toRemove, int toInsert) {
+			SpliceUninitializedAbsolute(startIndex + head, toRemove, toInsert);
+		}
+
+		/// <summary>Like <see cref="SpliceUninitialized"/>, but startIndex is an absolute index</summary>
+		public void SpliceUninitializedAbsolute (int startIndex, int toRemove, int toInsert) {
+#if ENABLE_UNITY_COLLECTIONS_CHECKS
+			if (startIndex - head < 0 || startIndex + toRemove - head > length) throw new System.ArgumentOutOfRangeException();
+#endif
+			var itemsToAdd = toInsert - toRemove;
+			while (this.length + itemsToAdd > capacityMask + 1) Grow();
+
+			// move items [startIndex+length .. end] itemsToAdd steps forward in the array
+			MoveAbsolute(startIndex + toRemove, AbsoluteEndIndex, itemsToAdd);
+			this.length += itemsToAdd;
+		}
+
+		void MoveAbsolute (int startIndex, int endIndex, int deltaIndex) {
+			unsafe {
+				if (deltaIndex > 0) {
+					for (int i = endIndex; i >= startIndex; i--) data[(i+deltaIndex) & capacityMask] = data[i & capacityMask];
+				} else if (deltaIndex < 0) {
+					for (int i = startIndex; i <= endIndex; i++) data[(i+deltaIndex) & capacityMask] = data[i & capacityMask];
+				}
+			}
+		}
+
+		/// <summary>Indexes the buffer, with index 0 being the first element</summary>
+		public T this[int index] {
+			[System.Runtime.CompilerServices.MethodImpl(System.Runtime.CompilerServices.MethodImplOptions.AggressiveInlining)]
+			readonly get {
+#if ENABLE_UNITY_COLLECTIONS_CHECKS
+				if ((uint)index >= length) throw new System.ArgumentOutOfRangeException();
+#endif
+				unsafe {
+					return data[(index+head) & capacityMask];
+				}
+			}
+			[System.Runtime.CompilerServices.MethodImpl(System.Runtime.CompilerServices.MethodImplOptions.AggressiveInlining)]
+			set {
+#if ENABLE_UNITY_COLLECTIONS_CHECKS
+				if ((uint)index >= length) throw new System.ArgumentOutOfRangeException();
+#endif
+				unsafe {
+					data[(index+head) & capacityMask] = value;
+				}
+			}
+		}
+
+		/// <summary>
+		/// Indexes the buffer using absolute indices.
+		/// When pushing to and popping from the buffer, the absolute indices do not change.
+		/// So e.g. after doing PushStart(x) on an empty buffer, GetAbsolute(-1) will get the newly pushed element.
+		/// </summary>
+		[System.Runtime.CompilerServices.MethodImpl(System.Runtime.CompilerServices.MethodImplOptions.AggressiveInlining)]
+		public readonly T GetAbsolute (int index) {
+#if ENABLE_UNITY_COLLECTIONS_CHECKS
+			if ((uint)(index - head) >= length) throw new System.ArgumentOutOfRangeException();
+#endif
+			unsafe {
+				return data[index & capacityMask];
+			}
+		}
+
+		[System.Runtime.CompilerServices.MethodImpl(System.Runtime.CompilerServices.MethodImplOptions.NoInlining)]
+		void Grow () {
+			unsafe {
+				// Note: Will always be a power of 2 since capacity is a power of 2
+				var capacity = capacityMask + 1;
+				var newCapacity = math.max(4, capacity*2);
+				var newData = AllocatorManager.Allocate<T>(this.Allocator, newCapacity);
+				if (data != null) {
+					var inOrderItems = capacity - (head & capacityMask);
+					UnsafeUtility.MemCpy(newData + (head & (newCapacity - 1)), data + (head & capacityMask), inOrderItems * sizeof(T));
+					var wraparoundItems = length - inOrderItems;
+					if (wraparoundItems > 0) {
+						UnsafeUtility.MemCpy(newData + ((head + inOrderItems) & (newCapacity - 1)), data, wraparoundItems * sizeof(T));
+					}
+					AllocatorManager.Free(Allocator, data);
+				}
+				capacityMask = newCapacity - 1;
+				data = newData;
+			}
+		}
+
+		/// <summary>Releases the unmanaged memory held by this container</summary>
+		public void Dispose () {
+			capacityMask = -1;
+			length = 0;
+			head = 0;
+			unsafe {
+				AllocatorManager.Free(Allocator, data);
+				data = null;
+			}
+		}
+
+		public IEnumerator<T> GetEnumerator () {
+			for (int i = 0; i < length; i++) {
+				yield return this[i];
+			}
+		}
+
+		IEnumerator IEnumerable.GetEnumerator () {
+			for (int i = 0; i < length; i++) {
+				yield return this[i];
+			}
+		}
+
+		public NativeCircularBuffer<T> Clone () {
+			unsafe {
+				var newData = AllocatorManager.Allocate<T>(this.Allocator, capacityMask + 1);
+				UnsafeUtility.MemCpy(newData, data, length * sizeof(T));
+				return new NativeCircularBuffer<T> {
+						   data = newData,
+						   head = head,
+						   length = length,
+						   capacityMask = capacityMask,
+						   Allocator = this.Allocator
+				};
+			}
+		}
+	}
+}
diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Core/Collections/NativeCircularBuffer.cs.meta b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Core/Collections/NativeCircularBuffer.cs.meta
new file mode 100644
index 0000000..0e52bc5
--- /dev/null
+++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Core/Collections/NativeCircularBuffer.cs.meta
@@ -0,0 +1,11 @@
+fileFormatVersion: 2
+guid: c126a7f5fd26b684984ddef8030409f9
+MonoImporter:
+  externalObjects: {}
+  serializedVersion: 2
+  defaultReferences: []
+  executionOrder: 0
+  icon: {instanceID: 0}
+  userData: 
+  assetBundleName: 
+  assetBundleVariant: 
diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Core/Collections/SlabAllocator.cs b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Core/Collections/SlabAllocator.cs
new file mode 100644
index 0000000..51c276b
--- /dev/null
+++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Core/Collections/SlabAllocator.cs
@@ -0,0 +1,316 @@
+namespace Pathfinding.Util {
+	using Unity.Mathematics;
+	using Unity.Collections;
+	using Unity.Collections.LowLevel.Unsafe;
+
+	/// <summary>
+	/// A tiny slab allocator.
+	/// Allocates spans of type T in power-of-two sized blocks.
+	///
+	/// Note: This allocator has no support for merging adjacent freed blocks.
+	/// Therefore it is best suited for similarly sized allocations which are relatively small.
+	///
+	/// Can be used in burst jobs.
+	///
+	/// This is faster than allocating NativeArrays using the Temp allocator, and significantly faster
+	/// than allocating them using the Persistent allocator.
+	/// </summary>
+	public struct SlabAllocator<T> where T : unmanaged {
+		public const int MaxAllocationSizeIndex = 10;
+		const uint UsedBit = 1u << 31;
+		const uint AllocatedBit = 1u << 30;
+		const uint LengthMask = AllocatedBit - 1;
+		/// <summary>Allocation which is always invalid</summary>
+		public const int InvalidAllocation = -2;
+		/// <summary>Allocation representing a zero-length array</summary>
+		public const int ZeroLengthArray = -1;
+
+		[NativeDisableUnsafePtrRestriction]
+		unsafe AllocatorData* data;
+
+		struct AllocatorData {
+			public UnsafeList<byte> mem;
+			public unsafe fixed int freeHeads[MaxAllocationSizeIndex+1];
+		}
+
+		struct Header {
+			public uint length;
+		}
+
+		struct NextBlock {
+			public int next;
+		}
+
+		public bool IsCreated {
+			get {
+				unsafe {
+					return data != null;
+				}
+			}
+		}
+
+		public int ByteSize {
+			get {
+				unsafe {
+					return data->mem.Length;
+				}
+			}
+		}
+
+		public SlabAllocator(int initialCapacityBytes, AllocatorManager.AllocatorHandle allocator) {
+			unsafe {
+				data = AllocatorManager.Allocate<AllocatorData>(allocator);
+				data->mem = new UnsafeList<byte>(initialCapacityBytes, allocator);
+				Clear();
+			}
+		}
+
+		/// <summary>
+		/// Frees all existing allocations.
+		/// Does not free the underlaying unmanaged memory. Use <see cref="Dispose"/> for that.
+		/// </summary>
+		public void Clear () {
+			CheckDisposed();
+			unsafe {
+				data->mem.Clear();
+				for (int i = 0; i < MaxAllocationSizeIndex + 1; i++) {
+					data->freeHeads[i] = -1;
+				}
+			}
+		}
+
+
+		/// <summary>
+		/// Get the span representing the given allocation.
+		/// The returned array does not need to be disposed.
+		/// It is only valid until the next call to <see cref="Allocate"/>, <see cref="Free"/> or <see cref="Dispose"/>.
+		/// </summary>
+		public UnsafeSpan<T> GetSpan (int allocatedIndex) {
+			CheckDisposed();
+			unsafe {
+				if (allocatedIndex == ZeroLengthArray) return new UnsafeSpan<T>(null, 0);
+#if ENABLE_UNITY_COLLECTIONS_CHECKS
+				if (allocatedIndex < sizeof(Header) || allocatedIndex >= data->mem.Length) throw new System.IndexOutOfRangeException($"Invalid allocation {allocatedIndex}");
+#endif
+				var ptr = data->mem.Ptr + allocatedIndex;
+				var header = (Header*)(ptr - sizeof(Header));
+				var length = header->length & LengthMask;
+#if ENABLE_UNITY_COLLECTIONS_CHECKS
+				if (length > SizeIndexToElements(MaxAllocationSizeIndex)) throw new System.Exception($"Invalid allocation {allocatedIndex}");
+				if ((header->length & AllocatedBit) == 0) throw new System.Exception("Trying to get a span for an unallocated index");
+#endif
+				return new UnsafeSpan<T>(ptr, (int)length);
+			}
+		}
+
+		public List GetList (int allocatedIndex) {
+			return new List(this, allocatedIndex);
+		}
+
+		public void Realloc (ref int allocatedIndex, int nElements) {
+			CheckDisposed();
+			if (allocatedIndex == ZeroLengthArray) {
+				allocatedIndex = Allocate(nElements);
+				return;
+			}
+
+			unsafe {
+#if ENABLE_UNITY_COLLECTIONS_CHECKS
+				if (allocatedIndex < sizeof(Header) || allocatedIndex >= data->mem.Length) throw new System.IndexOutOfRangeException();
+#endif
+				var ptr = data->mem.Ptr + allocatedIndex;
+				var header = (Header*)(ptr - sizeof(Header));
+				var length = header->length & LengthMask;
+#if ENABLE_UNITY_COLLECTIONS_CHECKS
+				if (length > SizeIndexToElements(MaxAllocationSizeIndex)) throw new System.Exception("Invalid index");
+				if ((header->length & AllocatedBit) == 0) throw new System.Exception("Trying to get a span for an unallocated index");
+#endif
+				var capacityIndex = ElementsToSizeIndex((int)length);
+				var newCapacityIndex = ElementsToSizeIndex((int)nElements);
+				if (capacityIndex == newCapacityIndex) {
+					header->length = (uint)nElements | AllocatedBit | UsedBit;
+				} else {
+					int newAllocation = Allocate(nElements);
+					var oldSpan = GetSpan(allocatedIndex);
+					var newSpan = GetSpan(newAllocation);
+					oldSpan.Slice(0, math.min((int)length, nElements)).CopyTo(newSpan);
+					Free(allocatedIndex);
+					allocatedIndex = newAllocation;
+				}
+			}
+		}
+
+		internal static int SizeIndexToElements (int sizeIndex) {
+			return 1 << sizeIndex;
+		}
+
+		internal static int ElementsToSizeIndex (int nElements) {
+			if (nElements < 0) throw new System.Exception("SlabAllocator cannot allocate less than 1 element");
+			if (nElements == 0) return 0;
+			int sizeIndex = CollectionHelper.Log2Ceil(nElements);
+			if (sizeIndex > MaxAllocationSizeIndex) throw new System.Exception("SlabAllocator cannot allocate more than 2^(MaxAllocationSizeIndex-1) elements");
+			return sizeIndex;
+		}
+
+		/// <summary>
+		/// Allocates an array big enough to fit the given values and copies them to the new allocation.
+		/// Returns: An ID for the new allocation.
+		/// </summary>
+		public int Allocate (System.Collections.Generic.List<T> values) {
+			var index = Allocate(values.Count);
+			var span = GetSpan(index);
+			for (int i = 0; i < span.Length; i++) span[i] = values[i];
+			return index;
+		}
+
+		/// <summary>
+		/// Allocates an array big enough to fit the given values and copies them to the new allocation.
+		/// Returns: An ID for the new allocation.
+		/// </summary>
+		public int Allocate (NativeList<T> values) {
+			var index = Allocate(values.Length);
+			GetSpan(index).CopyFrom(values.AsArray());
+			return index;
+		}
+
+		/// <summary>
+		/// Allocates an array of type T with length nElements.
+		/// Must later be freed using <see cref="Free"/> (or <see cref="Dispose)"/>.
+		///
+		/// Returns: An ID for the new allocation.
+		/// </summary>
+		public int Allocate (int nElements) {
+			CheckDisposed();
+			if (nElements == 0) return ZeroLengthArray;
+			var sizeIndex = ElementsToSizeIndex(nElements);
+			unsafe {
+#if ENABLE_UNITY_COLLECTIONS_CHECKS
+				if (sizeIndex < 0 || sizeIndex > MaxAllocationSizeIndex) throw new System.Exception("Invalid size index " + sizeIndex);
+#endif
+				int head = data->freeHeads[sizeIndex];
+				if (head != -1) {
+					var ptr = data->mem.Ptr;
+					data->freeHeads[sizeIndex] = ((NextBlock*)(ptr + head))->next;
+					*(Header*)(ptr + head - sizeof(Header)) = new Header { length = (uint)nElements | UsedBit | AllocatedBit };
+					return head;
+				}
+
+				int headerStart = data->mem.Length;
+				int requiredSize = headerStart + sizeof(Header) + SizeIndexToElements(sizeIndex)*sizeof(T);
+				if (Unity.Burst.CompilerServices.Hint.Unlikely(requiredSize > data->mem.Capacity)) {
+					data->mem.SetCapacity(math.max(data->mem.Capacity*2, requiredSize));
+				}
+
+				// Set the length field directly because we know we don't have to resize the list,
+				// and we do not care about zeroing the memory.
+				data->mem.m_length = requiredSize;
+				*(Header*)(data->mem.Ptr + headerStart) = new Header { length = (uint)nElements | UsedBit | AllocatedBit };
+				return headerStart + sizeof(Header);
+			}
+		}
+
+		/// <summary>Frees a single allocation</summary>
+		public void Free (int allocatedIndex) {
+			CheckDisposed();
+			if (allocatedIndex == ZeroLengthArray) return;
+			unsafe {
+#if ENABLE_UNITY_COLLECTIONS_CHECKS
+				if (allocatedIndex < sizeof(Header) || allocatedIndex >= data->mem.Length) throw new System.IndexOutOfRangeException();
+#endif
+				var ptr = data->mem.Ptr;
+				var header = (Header*)(ptr + allocatedIndex - sizeof(Header));
+				var length = (int)(header->length & LengthMask);
+#if ENABLE_UNITY_COLLECTIONS_CHECKS
+				if (length < 0 || length > SizeIndexToElements(MaxAllocationSizeIndex)) throw new System.Exception("Invalid index");
+				if ((header->length & AllocatedBit) == 0) throw new System.Exception("Trying to free an already freed index");
+#endif
+
+				var sizeIndex = ElementsToSizeIndex(length);
+
+				*(NextBlock*)(ptr + allocatedIndex) = new NextBlock {
+					next = data->freeHeads[sizeIndex]
+				};
+				data->freeHeads[sizeIndex] = allocatedIndex;
+				// Mark as not allocated
+				header->length &= ~(AllocatedBit | UsedBit);
+			}
+		}
+
+		public void CopyTo (SlabAllocator<T> other) {
+			CheckDisposed();
+			other.CheckDisposed();
+			unsafe {
+				other.data->mem.CopyFrom(data->mem);
+				for (int i = 0; i < MaxAllocationSizeIndex + 1; i++) {
+					other.data->freeHeads[i] = data->freeHeads[i];
+				}
+			}
+		}
+
+		[System.Runtime.CompilerServices.MethodImpl(System.Runtime.CompilerServices.MethodImplOptions.AggressiveInlining)]
+		void CheckDisposed () {
+#if ENABLE_UNITY_COLLECTIONS_CHECKS
+			unsafe {
+				if (data == null) throw new System.InvalidOperationException("SlabAllocator is already disposed or not initialized");
+			}
+#endif
+		}
+
+		/// <summary>Frees all unmanaged memory associated with this container</summary>
+		public void Dispose () {
+			unsafe {
+				if (data == null) return;
+				var allocator = data->mem.Allocator;
+				data->mem.Dispose();
+				AllocatorManager.Free(allocator, data);
+				data = null;
+			}
+		}
+
+		public ref struct List {
+			public UnsafeSpan<T> span;
+			SlabAllocator<T> allocator;
+			// TODO: Can be derived from span
+			public int allocationIndex;
+
+			public List(SlabAllocator<T> allocator, int allocationIndex) {
+				this.span = allocator.GetSpan(allocationIndex);
+				this.allocator = allocator;
+				this.allocationIndex = allocationIndex;
+			}
+
+			public void Add (T value) {
+				allocator.Realloc(ref allocationIndex, span.Length + 1);
+				span = allocator.GetSpan(allocationIndex);
+				span[span.Length - 1] = value;
+			}
+
+			public void RemoveAt (int index) {
+				span.Slice(index + 1).CopyTo(span.Slice(index, span.Length - index - 1));
+				allocator.Realloc(ref allocationIndex, span.Length - 1);
+				span = allocator.GetSpan(allocationIndex);
+			}
+
+			public void Clear () {
+				allocator.Realloc(ref allocationIndex, 0);
+				span = allocator.GetSpan(allocationIndex);
+			}
+
+			public int Length => span.Length;
+
+			public ref T this[int index] {
+				[System.Runtime.CompilerServices.MethodImpl(System.Runtime.CompilerServices.MethodImplOptions.AggressiveInlining)]
+				get {
+					return ref span[index];
+				}
+			}
+		}
+	}
+
+	public static class SlabListExtensions {
+		public static void Remove<T>(ref this SlabAllocator<T>.List list, T value) where T : unmanaged, System.IEquatable<T> {
+			int idx = list.span.IndexOf(value);
+			if (idx != -1) list.RemoveAt(idx);
+		}
+	}
+}
diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Core/Collections/SlabAllocator.cs.meta b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Core/Collections/SlabAllocator.cs.meta
new file mode 100644
index 0000000..b317b73
--- /dev/null
+++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Core/Collections/SlabAllocator.cs.meta
@@ -0,0 +1,11 @@
+fileFormatVersion: 2
+guid: 020cb204e780440f8987b23cd21c02d2
+MonoImporter:
+  externalObjects: {}
+  serializedVersion: 2
+  defaultReferences: []
+  executionOrder: 0
+  icon: {instanceID: 0}
+  userData: 
+  assetBundleName: 
+  assetBundleVariant: 
diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Core/Collections/Span.cs b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Core/Collections/Span.cs
new file mode 100644
index 0000000..da9976a
--- /dev/null
+++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Core/Collections/Span.cs
@@ -0,0 +1,384 @@
+using Unity.Mathematics;
+using Unity.Burst;
+using Unity.Collections;
+using Unity.Collections.LowLevel.Unsafe;
+using System.Runtime.CompilerServices;
+using System.Collections.Generic;
+
+namespace Pathfinding.Util {
+	/// <summary>
+	/// Replacement for System.Span which is compatible with earlier versions of C#.
+	///
+	/// Warning: These spans do not in any way guarantee that the memory they refer to is valid. It is up to the user to make sure
+	/// the memory is not deallocated before usage. It should never be used to refer to managed heap memory without pinning it, since unpinned managed memory can be moved by some runtimes.
+	///
+	/// This has several benefits over e.g. UnsafeList:
+	/// - It is faster to index into a span than into an UnsafeList, especially from C#. In fact, indexing into an UnsafeSpan is as fast as indexing into a native C# array.
+	///    - As a comparison, indexing into a NativeArray can easily be 10x slower, and indexing into an UnsafeList is at least a few times slower.
+	/// - You can create a UnsafeSpan from a C# array by pinning it.
+	/// - It can be sliced efficiently.
+	/// - It supports ref returns for the indexing operations.
+	/// </summary>
+	public readonly struct UnsafeSpan<T> where T : unmanaged {
+		[NativeDisableUnsafePtrRestriction]
+		internal readonly unsafe T* ptr;
+		internal readonly uint length;
+
+		/// <summary>Number of elements in this span</summary>
+		public int Length => (int)length;
+
+		[MethodImpl(MethodImplOptions.AggressiveInlining)]
+		public unsafe UnsafeSpan(void* ptr, int length) {
+			if (length < 0) throw new System.ArgumentOutOfRangeException();
+			if (length > 0 && ptr == null) throw new System.ArgumentNullException();
+			this.ptr = (T*)ptr;
+			this.length = (uint)length;
+		}
+
+		/// <summary>
+		/// Creates a new UnsafeSpan from a C# array.
+		/// The array is pinned to ensure it does not move while the span is in use.
+		///
+		/// You must unpin the pinned memory using UnsafeUtility.ReleaseGCObject when you are done with the span.
+		/// </summary>
+		public unsafe UnsafeSpan(T[] data, out ulong gcHandle) {
+			unsafe {
+				this.ptr = (T*)UnsafeUtility.PinGCArrayAndGetDataAddress(data, out gcHandle);
+			}
+			this.length = (uint)data.Length;
+		}
+
+		/// <summary>
+		/// Allocates a new UnsafeSpan with the specified length.
+		/// The memory is not initialized.
+		///
+		/// You are responsible for freeing the memory using the same allocator when you are done with it.
+		/// </summary>
+		public UnsafeSpan(Allocator allocator, int length) {
+			unsafe {
+				if (length < 0) throw new System.ArgumentOutOfRangeException();
+				if (length > 0) this.ptr = AllocatorManager.Allocate<T>(allocator, length);
+				else this.ptr = null;
+				this.length = (uint)length;
+			}
+		}
+
+		public ref T this[int index] {
+			// With aggressive inlining the performance of indexing is essentially the same as indexing into a native C# array
+			[MethodImpl(MethodImplOptions.AggressiveInlining)]
+			get {
+				unsafe {
+					if ((uint)index >= length) throw new System.IndexOutOfRangeException();
+					Unity.Burst.CompilerServices.Hint.Assume(ptr != null);
+					return ref *(ptr + index);
+				}
+			}
+		}
+
+		public ref T this[uint index] {
+			// With aggressive inlining the performance of indexing is essentially the same as indexing into a native C# array
+			[MethodImpl(MethodImplOptions.AggressiveInlining)]
+			get {
+				unsafe {
+					if (index >= length) throw new System.IndexOutOfRangeException();
+					Unity.Burst.CompilerServices.Hint.Assume(ptr != null);
+					Unity.Burst.CompilerServices.Hint.Assume(ptr + index != null);
+					return ref *(ptr + index);
+				}
+			}
+		}
+
+		/// <summary>
+		/// Returns a copy of this span, but with a different data-type.
+		/// The new data-type must have the same size as the old one.
+		///
+		/// In burst, this should effectively be a no-op, except possibly a branch.
+		/// </summary>
+		[MethodImpl(MethodImplOptions.AggressiveInlining)]
+		public UnsafeSpan<U> Reinterpret<U> () where U : unmanaged {
+			unsafe {
+				if (sizeof(T) != sizeof(U)) throw new System.InvalidOperationException("Cannot reinterpret span because the size of the types do not match");
+				return new UnsafeSpan<U>(ptr, (int)length);
+			}
+		}
+
+		/// <summary>
+		/// Creates a new span which is a slice of this span.
+		/// The new span will start at the specified index and have the specified length.
+		/// </summary>
+		public UnsafeSpan<T> Slice (int start, int length) {
+			if (start < 0 || length < 0 || start + length > this.length) throw new System.ArgumentOutOfRangeException();
+			unsafe {
+				return new UnsafeSpan<T>(ptr + start, length);
+			}
+		}
+
+		/// <summary>
+		/// Creates a new span which is a slice of this span.
+		/// The new span will start at the specified index and continue to the end of this span.
+		/// </summary>
+		public UnsafeSpan<T> Slice (int start) {
+			return Slice(start, (int)this.length - start);
+		}
+
+		/// <summary>Copy the range [startIndex,startIndex+count) to [toIndex,toIndex+count)</summary>
+		public void Move (int startIndex, int toIndex, int count) {
+			unsafe {
+				if (count < 0) throw new System.ArgumentOutOfRangeException();
+				if (startIndex < 0 || startIndex + count > length) throw new System.ArgumentOutOfRangeException();
+				if (toIndex < 0 || toIndex + count > length) throw new System.ArgumentOutOfRangeException();
+				// If length is zero, the pointers may be null, which is technically undefined behavior (but in practice usually fine)
+				if (count == 0) return;
+				UnsafeUtility.MemMove(ptr + toIndex, ptr + startIndex, (long)sizeof(T) * (long)count);
+			}
+		}
+
+		/// <summary>
+		/// Copies the memory of this span to another span.
+		/// The other span must be large enough to hold the contents of this span.
+		///
+		/// Note: Assumes the other span does not alias this one.
+		/// </summary>
+		public void CopyTo (UnsafeSpan<T> other) {
+			if (other.length < length) throw new System.ArgumentException();
+			unsafe {
+				// If length is zero, the pointers may be null, which is technically undefined behavior (but in practice usually fine)
+				if (length > 0) UnsafeUtility.MemCpy(other.ptr, ptr, (long)sizeof(T) * (long)length);
+			}
+		}
+
+		/// <summary>Appends all elements in this span to the given list</summary>
+		public void CopyTo (List<T> buffer) {
+			if (buffer.Capacity < buffer.Count + Length) buffer.Capacity = buffer.Count + Length;
+			for (int i = 0; i < Length; i++) buffer.Add(this[i]);
+		}
+
+		/// <summary>
+		/// Creates a new copy of the span allocated using the given allocator.
+		///
+		/// You are responsible for freeing this memory using the same allocator when you are done with it.
+		/// </summary>
+		public UnsafeSpan<T> Clone (Allocator allocator) {
+			unsafe {
+				var clone = new UnsafeSpan<T>(allocator, (int)length);
+				CopyTo(clone);
+				return clone;
+			}
+		}
+
+		/// <summary>Converts the span to a managed array</summary>
+		public T[] ToArray () {
+			var arr = new T[length];
+			if (length > 0) {
+				unsafe {
+					fixed (T* ptr = arr) {
+						UnsafeUtility.MemCpy(ptr, this.ptr, (long)sizeof(T) * (long)length);
+					}
+				}
+			}
+			return arr;
+		}
+
+		/// <summary>
+		/// Frees the underlaying memory.
+		///
+		/// Warning: The span must have been allocated using the specified allocator.
+		///
+		/// Warning: You must never use this span (or any other span referencing the same memory) again after calling this method.
+		/// </summary>
+		public unsafe void Free (Allocator allocator) {
+			if (length > 0) AllocatorManager.Free<T>(allocator, ptr, (int)length);
+		}
+	}
+
+	public static class SpanExtensions {
+		public static void FillZeros<T>(this UnsafeSpan<T> span) where T : unmanaged {
+			unsafe {
+				if (span.length > 0) UnsafeUtility.MemSet(span.ptr, 0, (long)sizeof(T) * (long)span.length);
+			}
+		}
+
+		public static void Fill<T>(this UnsafeSpan<T> span, T value) where T : unmanaged {
+			unsafe {
+				// This is wayy faster than a C# for loop (easily 10x faster).
+				// It is also faster than a burst loop (at least as long as the span is reasonably large).
+				// It also generates a lot less code than a burst for loop.
+				if (span.length > 0) {
+					// If this is too big, unity seems to overflow and crash internally
+					if ((long)sizeof(T) * (long)span.length > (long)int.MaxValue) throw new System.ArgumentException("Span is too large to fill");
+					UnsafeUtility.MemCpyReplicate(span.ptr, &value, sizeof(T), (int)span.length);
+				}
+			}
+		}
+
+		/// <summary>
+		/// Copies the contents of a NativeArray to this span.
+		/// The span must be large enough to hold the contents of the array.
+		/// </summary>
+		public static void CopyFrom<T>(this UnsafeSpan<T> span, NativeArray<T> array) where T : unmanaged {
+			CopyFrom(span, array.AsUnsafeReadOnlySpan());
+		}
+
+		/// <summary>
+		/// Copies the contents of another span to this span.
+		/// The span must be large enough to hold the contents of the array.
+		/// </summary>
+		public static void CopyFrom<T>(this UnsafeSpan<T> span, UnsafeSpan<T> other) where T : unmanaged {
+			if (other.Length > span.Length) throw new System.InvalidOperationException();
+			if (other.Length == 0) return;
+			unsafe {
+				UnsafeUtility.MemCpy(span.ptr, other.ptr, (long)sizeof(T) * (long)other.Length);
+			}
+		}
+
+		/// <summary>
+		/// Copies the contents of an array to this span.
+		/// The span must be large enough to hold the contents of the array.
+		/// </summary>
+		public static void CopyFrom<T>(this UnsafeSpan<T> span, T[] array) where T : unmanaged {
+			if (array.Length > span.Length) throw new System.InvalidOperationException();
+			if (array.Length == 0) return;
+			unsafe {
+				var ptr = UnsafeUtility.PinGCArrayAndGetDataAddress(array, out var gcHandle);
+				UnsafeUtility.MemCpy(span.ptr, ptr, (long)sizeof(T) * (long)array.Length);
+				UnsafeUtility.ReleaseGCObject(gcHandle);
+			}
+		}
+
+		/// <summary>
+		/// Converts an UnsafeAppendBuffer to a span.
+		/// The buffer must be a multiple of the element size.
+		///
+		/// The span is a view of the buffer memory, so do not dispose the buffer while the span is in use.
+		/// </summary>
+		[MethodImpl(MethodImplOptions.AggressiveInlining)]
+		public static UnsafeSpan<T> AsUnsafeSpan<T>(this UnsafeAppendBuffer buffer) where T : unmanaged {
+			unsafe {
+				var items = buffer.Length / UnsafeUtility.SizeOf<T>();
+				if (items * UnsafeUtility.SizeOf<T>() != buffer.Length) throw new System.ArgumentException("Buffer length is not a multiple of the element size");
+				return new UnsafeSpan<T>(buffer.Ptr, items);
+			}
+		}
+
+		/// <summary>
+		/// Converts a NativeList to a span.
+		///
+		/// The span is a view of the list memory, so do not dispose the list while the span is in use.
+		/// </summary>
+		[MethodImpl(MethodImplOptions.AggressiveInlining)]
+		public static UnsafeSpan<T> AsUnsafeSpan<T>(this NativeList<T> list) where T : unmanaged {
+			unsafe {
+				return new UnsafeSpan<T>(list.GetUnsafePtr(), list.Length);
+			}
+		}
+
+		/// <summary>
+		/// Converts a NativeArray to a span.
+		///
+		/// The span is a view of the array memory, so do not dispose the array while the span is in use.
+		/// </summary>
+		[MethodImpl(MethodImplOptions.AggressiveInlining)]
+		public static UnsafeSpan<T> AsUnsafeSpan<T>(this NativeArray<T> arr) where T : unmanaged {
+			unsafe {
+				return new UnsafeSpan<T>(arr.GetUnsafePtr(), arr.Length);
+			}
+		}
+
+		/// <summary>
+		/// Converts a NativeArray to a span without performing any checks.
+		///
+		/// The span is a view of the array memory, so do not dispose the array while the span is in use.
+		/// This method does not perform any checks to ensure that the array is safe to write to or read from.
+		/// </summary>
+		[MethodImpl(MethodImplOptions.AggressiveInlining)]
+		public static UnsafeSpan<T> AsUnsafeSpanNoChecks<T>(this NativeArray<T> arr) where T : unmanaged {
+			unsafe {
+				return new UnsafeSpan<T>(NativeArrayUnsafeUtility.GetUnsafeBufferPointerWithoutChecks(arr), arr.Length);
+			}
+		}
+
+		/// <summary>
+		/// Converts a NativeArray to a span, assuming it will only be read.
+		///
+		/// The span is a view of the array memory, so do not dispose the array while the span is in use.
+		///
+		/// Warning: No checks are done to ensure that you only read from the array. You are responsible for ensuring that you do not write to the span.
+		/// </summary>
+		[MethodImpl(MethodImplOptions.AggressiveInlining)]
+		public static UnsafeSpan<T> AsUnsafeReadOnlySpan<T>(this NativeArray<T> arr) where T : unmanaged {
+			unsafe {
+				return new UnsafeSpan<T>(arr.GetUnsafeReadOnlyPtr(), arr.Length);
+			}
+		}
+
+		/// <summary>
+		/// Converts an UnsafeList to a span.
+		///
+		/// The span is a view of the list memory, so do not dispose the list while the span is in use.
+		/// </summary>
+		[MethodImpl(MethodImplOptions.AggressiveInlining)]
+		public static UnsafeSpan<T> AsUnsafeSpan<T>(this UnsafeList<T> arr) where T : unmanaged {
+			unsafe {
+				return new UnsafeSpan<T>(arr.Ptr, arr.Length);
+			}
+		}
+
+		/// <summary>
+		/// Converts a NativeSlice to a span.
+		///
+		/// The span is a view of the slice memory, so do not dispose the underlaying memory allocation while the span is in use.
+		/// </summary>
+		[MethodImpl(MethodImplOptions.AggressiveInlining)]
+		public static UnsafeSpan<T> AsUnsafeSpan<T>(this NativeSlice<T> slice) where T : unmanaged {
+			unsafe {
+				return new UnsafeSpan<T>(slice.GetUnsafePtr(), slice.Length);
+			}
+		}
+
+		/// <summary>Returns true if the value exists in the span</summary>
+		public static bool Contains<T>(this UnsafeSpan<T> span, T value) where T : unmanaged, System.IEquatable<T> {
+			return IndexOf(span, value) != -1;
+		}
+
+		/// <summary>
+		/// Returns the index of the first occurrence of a value in the span.
+		/// If the value is not found, -1 is returned.
+		/// </summary>
+		public static int IndexOf<T>(this UnsafeSpan<T> span, T value) where T : unmanaged, System.IEquatable<T> {
+			unsafe {
+				return System.MemoryExtensions.IndexOf(new System.ReadOnlySpan<T>(span.ptr, (int)span.length), value);
+			}
+		}
+
+		/// <summary>Sorts the span in ascending order</summary>
+		public static void Sort<T>(this UnsafeSpan<T> span) where T : unmanaged, System.IComparable<T> {
+			unsafe {
+				NativeSortExtension.Sort<T>(span.ptr, span.Length);
+			}
+		}
+
+		/// <summary>Sorts the span in ascending order</summary>
+		public static void Sort<T, U>(this UnsafeSpan<T> span, U comp) where T : unmanaged where U : System.Collections.Generic.IComparer<T> {
+			unsafe {
+				NativeSortExtension.Sort<T, U>(span.ptr, span.Length, comp);
+			}
+		}
+
+#if !MODULE_COLLECTIONS_2_4_0_OR_NEWER
+		/// <summary>Shifts elements toward the end of this list, increasing its length</summary>
+		public static void InsertRange<T>(this NativeList<T> list, int index, int count) where T : unmanaged {
+			list.ResizeUninitialized(list.Length + count);
+			list.AsUnsafeSpan().Move(index, index + count, list.Length - (index + count));
+		}
+#endif
+
+#if !MODULE_COLLECTIONS_2_1_0_OR_NEWER
+		/// <summary>Appends value count times to the end of this list</summary>
+		public static void AddReplicate<T>(this NativeList<T> list, T value, int count) where T : unmanaged {
+			var origLength = list.Length;
+			list.ResizeUninitialized(origLength + count);
+			list.AsUnsafeSpan().Slice(origLength).Fill(value);
+		}
+#endif
+	}
+}
diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Core/Collections/Span.cs.meta b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Core/Collections/Span.cs.meta
new file mode 100644
index 0000000..de2fb18
--- /dev/null
+++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Core/Collections/Span.cs.meta
@@ -0,0 +1,11 @@
+fileFormatVersion: 2
+guid: fa5a1e493f0bf8946bc5fe477ef4710b
+MonoImporter:
+  externalObjects: {}
+  serializedVersion: 2
+  defaultReferences: []
+  executionOrder: 0
+  icon: {instanceID: 0}
+  userData: 
+  assetBundleName: 
+  assetBundleVariant: