Help: Jobifying existing "Find Nearest Enemies for Each Agent" code

Hi everyone!

I need help Jobifying this situation below. I’m stuck in figuring how to do it with a ParallelforTransform since I only have one Transform list, and need two. My attempts to do this have been so bad, that It’s probably easier for you to not even look at my jobbed code. Help please! I’m just trying to understand HOW this can be done.


Context:
So I have two teams, say 200 vs 200. Each agent needs to make a list of ascending order of enemies closest to itself.

Using NON JOBS - I’m limiting processing to MAX 15 agents scanning per frame, with each agent scanning every 3 seconds, and frames randomized, so spread out the load evenly across those 3 seconds… I get about .8 to 2 milliseconds for this. This performance is fine, but I want to learn JOBs and this is my first use case and man, I’m sucking large. I just can’t grasp this.

pseudo code warning as my current code too long without context

List <int> ListOfAgentsThatScanThisFrame  // each element is the INDEX of the agent in the "ListOfAllAliveAgents" that need to scan

public struct structNearestAgents
{
    public float distance;
    public int index;
}

List <structNearestAgents> tempListOfNearestAgentsForSorting = new .. ();

for (int i, i < listOfAgentsThatScanThisFrame, i++)
{
  currentIndex = ListOfAgentsThatScanThisFrame[i];
 
    for(int j, j <ListOfAllAliveAgents, j++)
    {


     if(AllAliveAgents[currentIndex].team == AllAliveAgents[j].team) continue //skip my own team
     

     float tempDistance = Vector3.Distance ( ListOfAllAliveAgents[currentIndex].transform.position - ListOfAllAliveAgents[j].transform.position]

         new StructNearestAgent tempStruct;
         tempStruct.index = j;
         tempStruct.distance = tempDistance;
         tempListOfNearestAgentsForSorting.add(tempStruct);

    } 

  //Sort the final assembled calculated list
  tempListNearestAgentsForSorting.Sort((a, b) => a.distance.CompareTo(b.distance));  
  
  //Assign it to the right agent
  ListOfAllAliveAgents[CurrentIndex].listNearestEnemies = tempListNearestAgentsForSorting;
}

When I try jobifying it, I’m having trouble with a iJobParallelTransform with doing the second iteration of all agents inside the job. I just can’t seem to grasp it and my code is garbage here.

Can someone help?

I would suggest splitting this up into multiple jobs.

Here’s a pair of jobs that will get you there. This is far from optimal, but it will serve as a good starting point from which you can study and further optimize.

[BurstCompile]
struct CopyPositionsJob : IJobParallelForTransform
{
    public NativeArray<float3> positions; // Sized to number in a given faction

    public void Execute(int index, TransformAccess transform)
    {
        positions[index] = transform.position;
    }
}

// When scheduling, set indicesPerJobCount to otherFactionPositions.Length
[BurstCompile]
struct FindClosestsByFactionJob : IJobParallelForBatch
{
    [ReadOnly] public NativeArray<float3> thisFactionPositions;
    [ReadOnly] public NativeArray<float3> otherFactionPositions;
    public NativeArray<int> orderedEnemyIndicesPerThisFactionAgent; // Length should be thisFactionPositions.Length * otherFactionPositions.Length

    public void Execute(int startIndex, int count)
    {
        var thisAgentIndex = startIndex / otherFactionPositions.Length;
        var thisPosition = thisFactionPositions[thisAgentIndex];
        var distanceIndexPairArray = new NativeArray<DistanceIndexPair>(otherFactionPositions.Length, Allocator.Temp, NativeArrayOptions.UninitializedMemory);
        
        for (int i = 0; i < otherFactionPositions.Length; i++)
        {
            distanceIndexPairArray[i] = new DistanceIndexPair
            {
                distance = math.distancesq(thisPosition, otherFactionPositions[i]),
                index = i
            };
        }
        
        distanceIndexPairArray.Sort();

        var outputSubArray = orderedEnemyIndicesPerThisFactionAgent.GetSubArray(startIndex, count);
        for (int i = 0; i < outputSubArray.Length; i++)
        {
            outputSubArray[i] = distanceIndexPairArray[i].index;
        }
    }

    struct DistanceIndexPair : IComparable<DistanceIndexPair>
    {
        public float distance;
        public int index;

        public int CompareTo(DistanceIndexPair other)
        {
            return distance.CompareTo(other.distance);
        }
    }
}
2 Likes

Note that you cannot use C# managed types. List<> needs to be replaced with NativeArray<> or NativeList<>.

Don’t forget the [BurstCompile] attribute or else you’re forfeiting potential speedups by factors of 10-100 (or even more in some cases)!

Use the Burst Debugger to view how your job is converted to machine instructions. This may be overwhelming at first, and admittedly, even at second, third and henceforth. Nevertheless there are key indicators whether a job performs vectorized operations or not. You’ll find these bits of info in the Burst manual and by searching.

I also recommend to set up TestRunner with the PerformanceTesting package so that you can run your job on (artificial) data at any time and compare its performance metrics against a previous version after making a change.

1 Like

Thank you!!! I’ll take a look tomorrow night and try to understand this. Thank you! I appreciate you taking the time out of your day to help me learn the job system!

Great advice! I’ll make sure to do that as I’m working away at this. Thank you!

Hi Hi! Follow up question if that’s OK!

So finally had a chance to sit down - it’s 11:30pm so maybe I’m just sleep deprived on top of being not smart.

  1. var thisAgentIndex = startIndex / otherFactionPositions.Length;

startIndex is the literal index of the agent in the “AllAliveAgentsforBothFactions” array that we use to built positions, correct? (e.g.: an integer like “53”), NOT the element number where that value is stored (element 0 has the value of 53)- So if anything, it would be:

ThisAgentIndex = otherFactionPositions[startIndex]

Right? I just don’t understand the division there, but I am also very dumb so.

  1. For actually executing this, I couldn’t find any official documentation on the syntax here, but I found this - this is right?
    // The first parameter specifies the total number of indices, the second one the
    // size of a batch. The Execute function specified in the job will be called with
    // a count of that number, usually, unless you are in the last batch.
    job.ScheduleBatch(n, x);

where n is thisFactionPositions.Length * otherFactionPositions.Length as you mentioned, and the size of the batch is just the enemyfactionPositions.count, right, because it’s how many enemies you are comparing size to and thus the number of iterations aka the batch size?

Thank you, my brain is fried at the moment, so I apologize for asking basic questions here.

No. It is actual an index into the array sized n as you call out here. A “batch” in this context is 1 agent and all the enemies. Thus you have as many batches as you have agents. I highly suggest drawing it out, with 3 agents and 4 enemies.

1 Like

OK got it I think So:

There are 3 agents and 4 enemies, so total indices is 12 (12 individual calculations). 3 Batches since I am iterating through 3 agents to find their enemies, with total of 12 calculations in total (4 calculations per batch).

OK, that makes total sense. (If I’m wrong, I apologize up front)

Thank you! Do you have a “buy me a coffee/beer” links or anything I can show my appreciation with?

Nope!

If you ever get into ECS, I have a lot more to share and then maybe you can learn what I’m all about. But otherwise or until then, just focus on learning and don’t hesitate to ask more questions here!

Thank you! I DO have one more question here:

public NativeArray orderedEnemyIndicesPerThisFactionAgent; // Length should be thisFactionPositions.Length * otherFactionPositions.Length

So in this part - what am I exactly populating in this INT array? Given it’s used here:

var outputSubArray = orderedEnemyIndicesPerThisFactionAgent.GetSubArray(startIndex, count);

It looks like it is storing the results of the closest enemies for each agent in one array. So if the scenario is:

-3 agents, 2 enemies

the end result of “orderedEnemyIndicesPerThisFactionAgent” will be:

[agent1_1stClosestEnemyIndex, Agent1_2ndClosestEnemyIndex, Agent1_3rdClosestEnemyIndex, Agent2_1stClosestEnemyIndex, Agent2_2ndClosestEnemyIndex…etc]

Do I understand that correctly?

If I wanted to return the ordered list of indexes, AND according distances, I would create a native array “DistanceIndexPairArray” in the struct instead of in the Execute. I can then reference this array after the job finishes to get the index AND distance, which are already ordered. Correct?

Thank you again for your time here!!

If you only have two enemies, there’s no such thing as a third-closest enemy. But otherwise, you have the right idea.

That is correct. Just watch out because I used math.distancesq instead of math.distance, so you might want to change that.

1 Like

It looks like you are doing distance tests between each enemy. The most important thing you can do is replace this with a bursted acceleration structure, such as a kdtree, octree, or quadtree. You can then issue queries to find neighbours for each point, and this should be much faster.

Work around the constraints of Burst so that you can use it in as many places as possible. Try to structure this into several Burst jobs.

1 Like