Hey there, i am fairly new to the whole ecs/job system/burst environment, and im currenlty working on a project make a 3D A* algorithm, which scans the environment dynamically. The issue is that im having trouble optimizing, as i think that i cant optimize some loops. Any ideas how i can increase performance on this script? I would appreciate as much feedback/ideas as possible.
#Any ideas on what i can optimize here?
odd mist
steel shell
looks like grid based path finding but 3d version
if you really want to optimize it, use another spatial partition and rewrite the code
branch factor is at most 18 (b^d, d=18 in your case), which is too large
and you should write or copy and paste native minheap for the open set
btw your code cannot be used in job since you use dictionary
odd mist
I thought about using a NativeMultiHashMap for it, since a key can have multiple values, but can i also iterate through those values?
Also is there a way to increase performance on the MoveToTarget function? Maybe even handle it with jobs? (Im already implementing a Heap, but i just want to know if there is other stuff i can optimize aswell)
steel shell
i remember there is native hashmap
idk what the version of your packet is so i cant say there must be native hash map
steel shell
still, the heap cannot be used in job since it is managed
and i suggest you to get rid of lambda expression, this maybe fine in other codes, but for those "low level" operations you should avoid function as much as possible to reduce the performance drawback, you know that the critical parts of a star is push/pop operations to the min heap and they should be fast (even inline the function call by aggressivelining)
and your heap is not resizable
and i highly discourage floating point value as dictionary key
odd mist
But is it even possible to Sort or does it make sense to sort in jobs?
Also there is no way to execute this in jobs right?
private void MoveToTarget()
{
int neighbor;
float cost;
while (openCells.Size > 0)
{
currentPoint = openCells.Peek();
if (currentPoint == endPoint)
break;
closedCells.Add(cells[currentPoint].Index);
openCells.Pop();
for (int i = 0; i < cellNeighbors[cells[currentPoint].Index].Length; i++)
{
neighbor = cellNeighbors[cells[currentPoint].Index][i];
if (cells[neighbor].FCost > -1 || closedCells.Contains(cells[neighbor].Index))
continue;
cost = (math.distance(cells[neighbor].CellPos, cells[startingPoint].CellPos) +
math.distance(cells[neighbor].CellPos, targetPos) * 10);
cells[neighbor] = new Cell(cells[neighbor].CellPos, cells[neighbor].Index, cells[currentPoint].Index, cost);
openCells.Add(cells[neighbor].Index);
}
}
SearchOrigin();
}
sorting is n log n while push pop is log n
you wont see any of the a star implementations sort the openset
you need to know what is IJob (or IJobXXX) interfaces first and implement the corresponding Execute method
odd mist
So i reworked my code, and i was at ~ 0.3ms execution time of the MoveToTarget method, now i reworked the Dictionary and turned it into a NativeParallelMultiHashMap, and now im at ~0.8ms execution. I know that its normal cause right now im not making use of burst and the Job System, but is the "overhead" worth the cost?
This is my reworked code, im not sure what else i can execute through jobs
steel shell
https://docs.unity3d.com/ScriptReference/Unity.Jobs.IJob.html
there is an example.....
wait, you already used job...
odd mist
i mean yeah i used it for generating the grid, but thats just for initialization, and i used the job system for finding the closest cell for a player. But i want to use it in the MoveToTarget Method, as 0.8ms is still too long for me, and i wanna get the max performance out of it
steel shell
actually the FindNearestCell(playerPos) is obviously no need to multithreads (or ever not suggested to be) in your current implementation, you still stuck the main thread and wait for the result, you can handle many requests at once but not one by one
and in InitializeGrid you dont need to allocate a new buffer and copy it to the class property, just allocate the class property and pass it into job
you can run the algorithm in job
Other optimization is (if you really want to keep adjacency list) to give up the hashmap and use array since the index is always in the range [0, number of vertices)
and the element is some struct likes:
unsafe struct A{
fixed ushort neighbors[6];
int neighborsCount;
}
```keep the neighbors in this structBtw where you reset the graph after the algorithm is finished?
odd mist
Currently im not resetting the graph, also when a make a struct with a array in it , can i still use it in jobs? As it is managed?
steel shell
create a new NativeArray<A>
odd mist
So its better to have a array with all the <A>, or do i need a variable of A in the struct itself?
steel shell
and i dont understand
currentPoint = openCells.Elements[0];
currentCellIndex = cells[currentPoint].Index;
```the currentCellIndex should be equal to currentPoint and no need to access the cells array?do you know what is adjacency list?
the native hash map acts as adjacency list and you can optimize it
odd mist
and i dont understand
```cs
currentPoint = openCells.Elements[0];
currentCellInd...
Correct, there was a unnessesary redundance i just removed.
odd mist
do you know what is adjacency list?
Isnt it a collection of lists i believe?
steel shell
odd mist
Other optimization is (if you really want to keep adjacency list) to give up the...
Do i need to set the members and the value by constructor only then?
odd mist
Currently i change my code, and made a similar approach, which heavily increased performance, but with the consequence in using a managed array
public unsafe struct A
{
public int NeighborsCount;
public int[] Neighbors;
public A(int[] size)
{
Neighbors = size;
NeighborsCount = size.Length;
}
}
Also i decided to dynamic set the size of the array, as there are chances that the size of the array can vary, depending on how many neighbors are accessible
steel shell
You only have 6 directions==the maximum possible number of neighbors is 6, and fixed size array is different from managed array
odd mist
do you know what else i can do to fix floating point precision in my dictionary? to get the neighbor cells? im afraid i might have to make a 3d int array, but im trying to find another solution without making a huge reworking
The Instantiate Grid is just a test of making a grid with subgrids, but it seems i got floating point precision issues now
steel shell
I have said I highly discourage using floating point as dictionary key
odd mist
What would be a good approach? Cause 3D int arrays seems like the only alternative i personally know.
Also, is there a way to not go through the read write acces check of a NativeArray? I just profiled my code and this seems pretty heavy. Maybe wirh direkt pointers?
steel shell
unsafe list
silver jewel
What would be a good approach? Cause 3D int arrays seems like the only alternative i personally know.
Why do you needfloat3instead ofint3for 3D index? In case your 3D indices are always whole numbers, you should useint3. And better if your grid size never changes, you can convert anint3to anint(1D index) to use as the key.
Even better, from the purpose of your cellData hash map, you can remove cellData, and only use cells. Since grid size never changes, an int3 index always equals to an int index. Supposely your total indices won't exceed int.MaxValue.
steel shell
you new an array every frame....
odd mist
So far i removed the cellNeighbors hashmap, and i added a reset function for clearing the path, also i removed unnessesary calculations (no sqrt calculations). But now i got a small issue that i want to make a NativeArray of "GridCores". The Purpose of this is to make a spatial grid, to speed up the search. So far it already boosted performance, but i want it to use in Jobs so it speeds up even more, but i dont know how i need to structure the GridCore struct, to make it work. I tried doing it with fixed arrays, but the problem is that a user should be able to dynamically set the cells amount. Also when i make fixed array , i cant access them from outside, any ideas?
using System.Collections;
using System.Collections.Generic;
using Unity.Mathematics;
using UnityEngine;
public struct GridCore
{
public float3 CorePos;
public List<Cell> SubCells;
public GridCore(float3 corePos, List<Cell> subCells)
{
CorePos = corePos;
SubCells = subCells;
}
}
steel shell
I remember i met the same error but i forgot, can you show the error when you try to access the fixed size array
odd mist
i made a little workaround, what i did now is i turned the MoveToTarget method into a job, i reached now 0.07ms, but i dont know how i get lower.
Also my goal is to have custom "flying agents", which should be able to path symultanously, any ideas what would be a good approach?
using System.Collections;
using System.Collections.Generic;
using Unity.Burst;
using Unity.Collections;
using Unity.Jobs;
using Unity.Mathematics;
using UnityEngine;
[BurstCompile]
public unsafe struct MoveToTargetJob : IJob
{
public float3 TargetPos;
public NativeArray<int> CurrentPoint;
public NativeArray<int> EndPoint;
public int OpenCellsCount;
public NativeList<Cell> Cells;
public NativeList<int> OpenCells;
public NativeArray<TempData> TempData;
public NativeArray<NeighborData> CellNeighbors;
public void Execute()
{
int neighborIndex;
NeighborData neighborData;
while (CurrentPoint != EndPoint && OpenCellsCount > 0)
{
CurrentPoint[0] = OpenCells[0];
neighborData = CellNeighbors[CurrentPoint[0]];
OpenCells.RemoveAt(0);
OpenCellsCount--;
for (int i = 0; i < 6; i++)
{
neighborIndex = neighborData.Neighbors[i];
if (neighborIndex < 0 || TempData[neighborIndex].FCost > 0)
continue;
TempData[neighborIndex] = new TempData(CurrentPoint[0], CalculationHelper.CalculateSquaredDistance(Cells[neighborIndex].CellPos, TargetPos));
OpenCells.Add(neighborIndex);
OpenCellsCount++;
}
}
}
}
I am also not sure how to turn the cores into a burst compatible code, as i still have a managed type on this struct, but the problem is, its supposed to be a future tool where people can decide how many cells a each corecell has
using System.Collections;
using System.Collections.Generic;
using Unity.Mathematics;
using UnityEngine;
public struct GridCore
{
public float3 CorePos;
public int[] SubCells;
public GridCore(float3 corePos, int[] subCells)
{
CorePos = corePos;
SubCells = subCells;
}
}
weak bolt
what would be an upper limit of number of subscells
odd mist
so the user should be able to go from 3 (333 = 27), to 8 (512)
weak bolt
so 512 elements?
i was thinking of suggesting a fixedlist but that'd likely be too large to be practical
odd mist
right now i have 40 cores, with each of them 125 subcells
Im not really sure what else would be a good approach to make it more perfomant, except optimizing the FindNearestCell method. I just profiled and this isnt even close to the most expensive methods.
The most problematic things are the NativeArray´1.CheckElementReadAccess() method, and a lot of ArrayGet methods
weak bolt
NativeArray´1.CheckElementReadAccess()
this is just safety check, it wont exist in build
and you can turn it off in burst in editor to profile
odd mist
Oh, good to know, also what would be a good approach when i want to have multiple pathfinding agents? Revert the movetotarget job to a regular method, and turn the whole AStar into a parallelfor?
I thought about a system where agents can subscribe to the manager, and then i can parallelfor through a list of all subscribed referenzes
weak bolt
i haven't read this thread so i'm not familiar with your implementation however i personally have a very complicated work pooling system for my pathfinding
- objects send a request into a work pool
- each thread reads from the queue to do work each frame
- each thread can execute X iterations/frame from as many pooled elements as it can complete in these iterations
- once X iterations are hit, work is stopped and resumed the next frame - there is no requirement for a path request to be finished in a frame and for really long range stuff it could take multiple frames
- objects query to check if work is done each frame