private struct AStarJob : IJobChunk
        {
            [NativeDisableParallelForRestriction] public BufferFromEntity<PathNodeEntry> PathNodeBuffer;
//            public EntityCommandBuffer.Concurrent CommandBuffer;
            public ArchetypeChunkComponentType<AStarData> AStarDataType;
            public ArchetypeChunkComponentType<Translation> TranslateDataType;
            public ArchetypeChunkComponentType<MovementData> MovementDataType;

            [ReadOnly] public uint RandomSeed;
            [ReadOnly] public ArchetypeChunkEntityType EntityType;

            [ReadOnly] public DynamicBuffer<Edge> pathsBetweenNodes;
            [ReadOnly] public DynamicBuffer<NodeOctreeCell> childCells;
            [ReadOnly] public DynamicBuffer<IntBufferData> nodeIdsSortedByCellIds;
            [ReadOnly] public int parentCellId;
//            [ReadOnly] public Entity GraphEntity;

            [ReadOnly] public DynamicBuffer<Node> Nodes;

            public void Execute(ArchetypeChunk chunk, int chunkIndex, int firstEntityIndex)
            {
                var chunkMovementData = chunk.GetNativeArray(MovementDataType);
                var chunkAStarData = chunk.GetNativeArray(AStarDataType);
                var chunkTranslate = chunk.GetNativeArray(TranslateDataType);
                var chunkEntities = chunk.GetNativeArray(EntityType);

//                Nodes = CommandBuffer.SetBuffer<Node>(chunkIndex, GraphEntity);

                for (int i = 0; i < chunk.Count; i++)
                {
                    AStarData aStarData = chunkAStarData[i];
                    MovementData movementData = chunkMovementData[i];
                    Translation translation = chunkTranslate[i];
                    Entity entity = chunkEntities[i];

                    if (!aStarData.IsSearchingPath && movementData.hasArrived)
                    {
                        Random random = new Random((uint) chunkIndex + (uint) i + RandomSeed);
                        float3 randomTarget = new float3(random.NextFloat(movementData.minX, movementData.maxX), movementData.y,
                            random.NextFloat(movementData.minZ, movementData.maxZ));

                        if (TryGetClosestNodeToPoint(randomTarget, out Node targetGraphNode) &&
                            TryGetClosestNodeToPoint(translation.Value, out Node startGraphNode))
                        {
                            aStarData.IsSearchingPath = true;
                            aStarData.HasFoundPath = false;
                            AStarPathNode startNode = new AStarPathNode
                            {
                                GCost = 0,
                                HCost = Utils.GetHeuristicLengthOf(targetGraphNode.Position - startGraphNode.Position),
                                Index = startGraphNode.Id,
                                PreviousNodeId = -1,
                                Position = startGraphNode.Position,
                            };
                            startNode.CalculateFCost();

                            NativeList<AStarPathNode> sortedNodes = new NativeList<AStarPathNode>(Allocator.Temp);
                            sortedNodes.Add(startNode);
                            NativeHashMap<int, AStarPathNode> openList = new NativeHashMap<int, AStarPathNode>(15, Allocator.Temp);
                            openList.Add(startNode.Index, startNode);
                            NativeHashMap<int, AStarPathNode> closedList = new NativeHashMap<int, AStarPathNode>(15, Allocator.Temp);

                            bool isPathFound = false;
                            while (openList.Length > 0 && !isPathFound)
                            {
                                int currentIndex = sortedNodes[0].Index;
                                Node currentNode = Nodes[currentIndex];
                                AStarPathNode currentSearchNode = openList[currentIndex];
                                closedList.Add(currentIndex, currentSearchNode);

                                var newSorted = Utils.RemoveAt(sortedNodes, 0);
                                sortedNodes.Dispose();
                                sortedNodes = newSorted;

                                openList.Remove(currentIndex);

                                if (currentSearchNode.Index == targetGraphNode.Id)
                                {
                                    int pathIndex = currentSearchNode.Index;
                                    NativeList<int> pathToTarget = new NativeList<int>(Allocator.Temp);
                                    while (pathIndex >= 0)
                                    {
                                        pathToTarget.Add(pathIndex);
                                        pathIndex = closedList[pathIndex].PreviousNodeId;
                                    }
                                    isPathFound = true;

                                    DynamicBuffer<PathNodeEntry> pathNodes = PathNodeBuffer[entity]; // CommandBuffer.SetBuffer<PathNodeEntry>(chunkIndex, entity);
                                    pathNodes.Clear();
                                    for (int pathIndexId = pathToTarget.Length - 1; pathIndexId >= 0; pathIndexId--)
                                    {
                                        pathNodes.Add(new PathNodeEntry {node = Nodes[pathToTarget[pathIndexId]]});
                                    }

                                    pathToTarget.Dispose();

                                    movementData.ResetPath();
                                    chunkMovementData[i] = movementData;

                                    aStarData.HasFoundPath = true;
                                    break;
                                }

                                for (int neighbourId = 0; neighbourId < currentNode.NumberOfEdges; neighbourId++)
                                {
                                    Edge nextEdge = pathsBetweenNodes[currentNode.FirstEdgeId + neighbourId];
                                    if (!closedList.ContainsKey(nextEdge.TargetNodeId))
                                    {
                                        Node nextNode = Nodes[nextEdge.TargetNodeId];
                                        AStarPathNode nextSearchNode = new AStarPathNode
                                        {
                                            GCost = currentSearchNode.GCost + nextEdge.Cost,
                                            HCost = Utils.GetHeuristicLengthOf(targetGraphNode.Position - nextNode.Position),
                                            Index = nextNode.Id,
                                            PreviousNodeId = currentNode.Id,
                                            Position = nextNode.Position
                                        };
                                        nextSearchNode.CalculateFCost();

                                        if (openList.ContainsKey(nextSearchNode.Index))
                                        {
                                            if (nextSearchNode.FCost < openList[nextSearchNode.Index].FCost)
                                            {
                                                openList[nextSearchNode.Index] = nextSearchNode;

                                                // Sort the IDs to reflect the new FCost
                                                int removeId = -1;
                                                for (int sortedListId = 0; sortedListId < sortedNodes.Length; sortedListId++)
                                                {
                                                    if (nextSearchNode.Index == sortedNodes[sortedListId].Index)
                                                    {
                                                        removeId = sortedListId;
                                                        break;
                                                    }
                                                }

                                                if (removeId >= 0)
                                                {
                                                    var newSortedInside = Utils.RemoveAt(sortedNodes, removeId);
                                                    sortedNodes.Dispose();
                                                    sortedNodes = newSortedInside;
                                                }

                                                int insertId = -1;
                                                for (int sortedListId = 0; sortedListId < sortedNodes.Length; sortedListId++)
                                                {
                                                    if (nextSearchNode.FCost < openList[sortedNodes[sortedListId].Index].FCost)
                                                    {
                                                        insertId = sortedListId;
                                                        break;
                                                    }
                                                }
                                                if (insertId < 0)
                                                {
                                                    sortedNodes.Add(nextSearchNode);
                                                }
                                                else
                                                {
                                                    NativeList<AStarPathNode> newSortedNodes = Utils.InsertIntoNativeList(sortedNodes, nextSearchNode, insertId);
                                                    sortedNodes.Dispose();
                                                    sortedNodes = newSortedNodes;
                                                }
                                            }
                                        }
                                        else
                                        {
                                            openList.Add(nextSearchNode.Index, nextSearchNode);
                                            int insertId = -1;
                                            for (int sortedListId = 0; sortedListId < sortedNodes.Length; sortedListId++)
                                            {
                                                if (nextSearchNode.FCost < openList[sortedNodes[sortedListId].Index].FCost)
                                                {
                                                    insertId = sortedListId;
                                                    break;
                                                }
                                            }

                                            if (insertId < 0)
                                            {
                                                sortedNodes.Add(nextSearchNode);
                                            }
                                            else
                                            {
                                                NativeList<AStarPathNode> newSortedNodes = Utils.InsertIntoNativeList(sortedNodes, nextSearchNode, insertId);
                                                sortedNodes.Dispose();
                                                sortedNodes = newSortedNodes;
                                            }
                                        }
                                    }
                                }
                            }
                            aStarData.IsSearchingPath = false;
                            chunkAStarData[i] = aStarData;
                            openList.Dispose();
                            closedList.Dispose();
                            sortedNodes.Dispose();
                        }
                    }
                }
            }


            private bool TryGetClosestNodeToPoint(float3 point, out Node result)
            {
                NativeList<int> cellIdsToIterate = new NativeList<int>(Allocator.Temp);
                cellIdsToIterate.Add(parentCellId);

                NodeOctreeCell lastParent = new NodeOctreeCell();
                bool isLastParentSet = false;
                bool foundNode = false;
                result = new Node();

                while (!foundNode && cellIdsToIterate.Length > 0)
                {
                    NodeOctreeCell currentCell = childCells[cellIdsToIterate[0]];
                    if (currentCell.DoesContain(point))
                    {
                        NativeList<int> subCellList = GetOctreeCellIds(currentCell);
                        if (subCellList.Length > 0)
                        {
                            lastParent = currentCell;
                            isLastParentSet = true;
                            cellIdsToIterate.Dispose();
                            cellIdsToIterate = new NativeList<int>(Allocator.Temp);
                            cellIdsToIterate.AddRange(subCellList);
                        }
                        else
                        {
                            if (currentCell.NumberOfChildNodes > 0)
                            {
                                NativeArray<Node> childNodes = GetChildNodes(currentCell);
                                Node closest = childNodes[0];
                                float closestSqrDist = math.distancesq(point, closest.Position);
                                for (int n = 1; n < childNodes.Length; n++)
                                {
                                    float sqrDist = math.distancesq(point, childNodes[n].Position);
                                    if (sqrDist < closestSqrDist)
                                    {
                                        closestSqrDist = sqrDist;
                                        closest = childNodes[n];
                                    }
                                }

                                childNodes.Dispose();

                                foundNode = true;
                                result = closest;
                            }
                            else if (isLastParentSet)
                            {
                                NativeList<Node> allNodesInLastParent = new NativeList<Node>(Allocator.Temp);
                                NativeArray<Node> childNodesOfLastParent = GetChildNodes(lastParent);
                                if (childNodesOfLastParent.Length > 0)
                                {
                                    allNodesInLastParent.AddRange(childNodesOfLastParent);
                                }
                                else
                                {
                                    var childCellsOfLastParent = GetOctreeCellIds(lastParent);
                                    // ReSharper disable once ForCanBeConvertedToForeach - No foreach in burst jobs
                                    for (int i = 0; i < childCellsOfLastParent.Length; i++)
                                    {
                                        NativeArray<Node> cellChildNodes = GetChildNodes(childCells[childCellsOfLastParent[i]]);
                                        if (cellChildNodes.Length > 0)
                                        {
                                            allNodesInLastParent.AddRange(cellChildNodes);
                                        }

                                        cellChildNodes.Dispose();
                                    }

                                    childCellsOfLastParent.Dispose();
                                }

                                childNodesOfLastParent.Dispose();

                                if (allNodesInLastParent.Length > 0)
                                {
                                    Node closest = allNodesInLastParent[0];
                                    float closestSqrDist = math.distancesq(point, closest.Position);
                                    for (int n = 1; n < allNodesInLastParent.Length; n++)
                                    {
                                        float sqrDist = math.distancesq(point, allNodesInLastParent[n].Position);
                                        if (sqrDist < closestSqrDist)
                                        {
                                            closestSqrDist = sqrDist;
                                            closest = allNodesInLastParent[n];
                                        }
                                    }

                                    foundNode = true;
                                    result = closest;
                                }
                                else
                                {
                                    // A cell was hit, that has no way points. No close point can be found.
                                    cellIdsToIterate.Clear();
                                }

                                allNodesInLastParent.Dispose();
                            }
                            else
                            {
                                cellIdsToIterate.Clear();
                            }
                        }

                        subCellList.Dispose();
                    }
                    else
                    {
                        cellIdsToIterate.RemoveAtSwapBack(0);
                    }
                }

                return foundNode;
            }

            /// <summary>
            /// Returns a the child cells for a certain parent cell.
            /// </summary>
            /// <param name="parentCell"> The parent cell. </param>
            /// <returns> The child cells you wanted to retrieve. </returns>
            private NativeList<int> GetOctreeCellIds(NodeOctreeCell parentCell)
            {
                return GetOctreeCellIds(parentCell.FirstChildCellId, parentCell.NumberOfChildCells);
            }

            /// <summary>
            /// Returns a sub-array of child cells for a range of number of cells, starting with a given cell ID.
            /// </summary>
            /// <param name="firstChildCellId"> ID of the first cell. </param>
            /// <param name="numberOfChildCells"> Total number of cells. </param>
            /// <returns> The child cells you wanted to retrieve. </returns>
            private NativeList<int> GetOctreeCellIds(int firstChildCellId, int numberOfChildCells)
            {
                if (firstChildCellId == -1 || numberOfChildCells == 0)
                {
                    return new NativeList<int>(Allocator.Temp);
                }

                NativeList<int> cellIds = new NativeList<int>(Allocator.Temp);
                NativeList<NodeOctreeCell> subList = Utils.GetSubList(childCells, firstChildCellId, numberOfChildCells);
                for (int i = 0; i < subList.Length; i++)
                {
                    cellIds.Add(subList[i].Id);
                }

                return cellIds;
            }

            private NativeArray<Node> GetChildNodes(NodeOctreeCell parentCell)
            {
                return GetChildNodes(parentCell.FirstSortedNodeId, parentCell.NumberOfChildNodes);
            }

            private NativeArray<Node> GetChildNodes(int firstSortedNodeId, int numberOfNodes)
            {
                NativeArray<int> cellChildNodeIds = Utils.GetIntDataSubArray(nodeIdsSortedByCellIds, firstSortedNodeId, numberOfNodes);
                NativeArray<Node> cellChildNodes = new NativeArray<Node>(cellChildNodeIds.Length, Allocator.Temp);
                for (int i = 0; i < cellChildNodeIds.Length; i++)
                {
                    cellChildNodes[i] = Nodes[cellChildNodeIds[i]];
                }

                cellChildNodeIds.Dispose();

                return cellChildNodes;
            }
        }