Can this algorithm be done with the Jobs System?

I am prototyping a game in Unity. It involves building a randomly generated grid. The first phase is the most resource-consuming and involves creating an initial "tree" grid of nodes.
I build the initial tree by "spawning" nodes (I am not really spawning GameObjects, but only generating random positions and comparing to existing positions positions, I use "spawning" below just to be clearer and more graphical). I spawn the nodes randomly on a unit sphere from their parent and discarding them if they are too close to any other node, generating another random on unit sphere position, gradually relaxing the distance threshold.
As the spawning happens, I put the nodes in a flat array to operate on them later.
It is important that each new spawn has to check its distance to all existing spawns, including the spawns that have just occurred at the previous iteration.
To explain better, If I have one parent that has to spawn 2 children, when the first child spawns, it checks its distance only with regard to the parent, but when the second child spawns, it checks its distance to both the parent and the first child.
However, it is not important whether the first child is spawned before the second one, as long as they are checked against each other by the one that is spawning the later.
I have read about the Unity's C# Job system and I have doubts whether the above algorithm could be implemented with the IJobParallelFor, because all parallel iterations (corresponding to each child that should be spawned) should be able to write and read the array of existing "accepted" spawn positions, while the other iterations are also doing so. As I wrote, for the proper operation of the algorithm, it does not matter in which order they write and read from the array of existing "accepted" spawn positions.
It would be really great if I could parallelise that process, since the generation of the "tree" grid takes around 7-8 seconds for a grid of 1000 nodes and more importantly freezes the game in the meantime.
Is there a hope?

 

I'm very surprised it takes 7-8 seconds to do this as all you need is a distance check between two Vector3's. Have you deep profiled this to see what is causing the problem?

I suspect that your distance threshold is too large and the algorithm is spending lots of time trying to grow outward.

Have you considered a different generation approach, e.g. you could randomly generate a point offset by a rotation along a vector from the original point, then limit future random rotations to be > 45* degrees away from any existing points therefore ensuring the minimum distance is maintained and the node tree will grow with minimal pruning needed.

*The angle could be any number of degrees that at one unit matches the minimum distance threshold you have set.

 

I am not sure whether I understood that, sorry. What do you mean by "rotation along a vector from the original point"? I cannot visualise that...
I have been thinking that my approach is not a very smart one and many random on unit shpere generations go to waste.
I actually managed to put the generation down from 15 sec to 7 sec simply by comparing thr sqrMagnitude instead of the distance.
I also probably start with a too high threshold.
But what about the job system? Would I be able to speed up things that way?

 

You are generating a new random point in a sphere however worst case is the half that space would be too close to your last point(s) and as your point cloud grows even more of that space becomes blocked.

If you moved that sphere away from your original point, so that the old point was outside of the sphere this could guarantee that early expansion would never be too close to the last point.

Or if you use Random.OnUnitSphere, you are guaranteed the point is not within range of it's parent point, you can then randomize this value by scaling the vector a random amount e.g. 1.0 to 2.0

All you are doing is a distance calculation between all the existing points and a new point, the hierarchy does not matter to the testing aspect of the program batching and jobifying this would massively speed things up, however I don't think it will solve what I think is an underlying problem with your algorithm.

So please profile your code and/or share it with the community so we can help you to the best of our abilities.

Idea: If you think of this as a plant growing then you could use the growth vectors like branches and generate child angle offsets e.g. take the parents offset vector or branch and use it to make the next child offset with a limited rotation and safe scale (< limit).

 

Here is the zip with the Deep Profiler data https://drive.google.com/file/d/1ZAOcw8gzAve4BoDel8m1HVkXFD1ACbPx/view?usp=sharing
Here is my code:

Code (CSharp):

1. while (foundNodePos == false)
2.                 {
3.                     foundNodePos = true;
4.                     float minDist = minDistNode * scaleGrid - extraDecrease;
5.                     for (int i = 0; i < allLvlArrayNum; i++)
6.                     {
7.                         //Discards the new node position if it is too close to other existing nodes. This might make it difficult to put into a job, since there is a dependency
8.                         Vector3 newNodeToAllNodes = NodePositions[i] - newNodePos;
9.                         if (Vector3.SqrMagnitude(newNodeToAllNodes) < minDist*minDist)
10.                         {
11.                             foundNodePos = false;
12.                             newNodePos = NodePositions[parentNodeNum] + Random.onUnitSphere * lineLength * scaleGrid;
13.                             //i = allLvlArrayNum;
14.                             break;
15.                         }
16.                     }
17.                     randomLoops++;
18.                     if (randomLoops > maxRandomLoops)
19.                     {
20.                         extraDecrease += (extraDecreaseStep * scaleGrid);
21.                         randomLoops = 0;
22.                     }
23.                     //Debug.Log ("foundNodePos="+foundNodePos);
24.                 }

And here are the 3 most resource intensive operations, from what I could gather:
https://i.imgur.com/gnGY5la.jpg

https://i.imgur.com/H3ujuAn.jpg

https://i.imgur.com/UM9rywu.jpg

I agree that most of the loops go to waste...

 

not jobs related, but some micro-optimizations,
- can calculate this outside for-loop minDist*minDist, same for lineLength * scaleGrid
- and looks like this can be outside while-loop minDistNode * scaleGrid
- use floats or vector3 components directly (v.x = v.x*some, v.y = v.y*some, v.z = v.z*some, is faster than v = v*some)
- test calculating SqrMagnitude manually from floats or vector components http://answers.unity.com/answers/384974/view.html
- could move Vector3 newNodeToAllNodes; outside while loop, then just assign xyz values to it in loop

in any case,
could search for some algorithm that evenly places points on sphere surface,
they work without having to loop all points and checking distances (which gets slower the more points you have)

 

Thanks, I agree there was no need to recompute some of that in the for loop or the while loop. I tried with the changed text, but I am again at 7sec. It is the algorithm that discards too many random on unit spheres (6 million for 350 nodes).
Arowx above suggested another approach by moving the center of the OnUnitSphere outside the parent node and away from existing nodes.

 

Trying to use IJobParallelFor is NOT the first step in optimizing your code. There's a bunch of other optimizations and restructurings that are going to get you to your goal faster. But first, let's take a step back and look at your real problem:

The algorithm is freezing the game for 7 seconds.

There's two ways to solve this:
1) Make the algorithm waaaaaaay faster
2) Make the algorithm not freeze the game while it is running

I'm willing to walk you through a bunch of tips and tricks to get this thing under control, but I'll need you to answer a couple of questions just to make sure this is feasible within your game's constraints.

A) Assuming that it is possible for this algorithm to run across multiple frames without freezing the game, does this algorithm need to run in a single frame?

B) How long (milliseconds or frame count) can you afford this algorithm to run given the same assumption as A?

C) Would you be willing to upload a more complete version of this algorithm which includes the outer loops and all variables this algorithm uses?

 

No, I can show the player some tutorial tips in the meantime

2-3 seconds ideally

Here is a shorter version of the CreateLevel() function

Code (CSharp):

1. //parentNode is the GameObject of the parent that has to spawn the children
2. //childrenNum is the child index that the parent has to spawn at this iteration of this function
3. void CreateLevel(GameObject parentNode, int childrenNum)
4.     {
5.         //allLvlArrayNum is the int that describes the index in the GameObject[] AllLvlArray that when the grid is finished should contain all nodes;
6.         //allLvlArrayLength is the int that describes the maximum number of nodes allowed in the grid;
7.         if (allLvlArrayNum < allArrayLength)
8.         {
9.             //We get the index of the parent node in order to find its position in the array that holds the node positions
10.             parentNodeNum = int.Parse(parentNode.name);
11.             //We generate a random location around the parent node float lineLength = 0.5f;
12.             newNodePos = NodePositions[parentNodeNum] + Random.onUnitSphere * lineLength;
13.             //This is sort of a safety fuse system to enable the while loop to actually complete, that compares the current loop number with the int maxRandomLoops = 30; and if we reached maxRandomLoops, relaxes the threshold by float extraDecreaseStep = 0.1f;
14.             randomLoops = 0;
15.             //Everytime that the safety fuse system reaches the maxRandomLoops = 30 the extraDecrease is increased by float extraDecreaseStep = 0.1f;
16.             extraDecrease = 0;
17.             while (foundNodePos == false)
18.             {
19.                 //At each new while loop iteration we set the condition for exiting the while loop to true and if the potential position for the new child node does not pass the threshold (i.e. is too close to other existing nodes), we set the foundNodePos = false; thus triggering another iteration of the while loop
20.                 foundNodePos = true;
21.                 //the minimum distance starts probably too high at float minDistNode = 1f; which is double the radius of the Random.onUnitSphere (for reference float lineLength = 0.5f;) and every 30 loops gets decreased by float extraDecreaseStep = 0.1f; Maybe a potential optimisation could be to have faster extraDecreaseStep first and slower later
22.                 float minDist = minDistNode - extraDecrease;
23.                 //we calculate the square of minDist for faster comparison with the distance between the potential position of the child node and the positions of all existing nodes
24.                 float minDistSq = minDist * minDist;
25.                 //check the distance to all existing nodes allLvlArrayNum in a for loop.
26.                 for (int i = 0; i < allLvlArrayNum; i++)
27.                 {
28.                     //Discards the new node position if it is too close to other existing nodes.
29.                     Vector3 newNodeToAllNodes = NodePositions[i] - newNodePos;
30.                     if (Vector3.SqrMagnitude(newNodeToAllNodes) < minDistSq)
31.                     {
32.                         //Discards the current potential position for the child node, preparing the next interation of the while loop
33.                         foundNodePos = false;
34.                         //Generates a new potential child node position for the next while loop iteration and breaks from the for loop
35.                         newNodePos = NodePositions[parentNodeNum] + Random.onUnitSphere * lineLength;
36.                         break;
37.                     }
38.                 }
39.                 randomLoops++;
40.                 //If no new position was found with 30 iterations, relax the threshold by float extraDecreaseStep = 0.1f;
41.                 if (randomLoops > maxRandomLoops)
42.                 {
43.                     extraDecrease += (extraDecreaseStep);
44.                     randomLoops = 0;
45.                 }
46.            }
47.             //Instantiates and sets up (orients and scales) the new node,
48.             AllLvlArray[allLvlArrayNum] = Instantiate(node, newNodePos, Quaternion.identity, grid);
49.             AllLvlArray[allLvlArrayNum].name = allLvlArrayNum.ToString();
50.             //Immediately fills in the new confirmed child node position into the array of node position so that the next child will check its potential position against that new position too. I think this might be problematic for a IJobParallelFor, since if all children's CreateLevel functions run in parallel, they would have to read and write to NodePositions[] simultaneously
51.             NodePositions[allLvlArrayNum] = newNodePos;
52.             //k=linksContainerArray[i,j] describes which adjacent node number k is at which link number j coming from the current node i
53.             // the 0 link (j=0) of each node always refers to its parent node
54.             linksContainerArray[allLvlArrayNum, 0] = parentNodeNum;
55.             // The j = childrenNum + 1 refers to the current child that was just spawned
56.             linksContainerArray[parentNodeNum, childrenNum + 1] = allLvlArrayNum;
57.             //increments int allLvlArrayNum in order to prepare the next iteration of CreateLevel();
58.             allLvlArrayNum++;
59.             //Sets the bool foundNodePos in order to enable the while loop for the next iteration of CreateLevel();
60.             foundNodePos = false;
61.         }
62.     }

And here is the function that creates the successive tree levels (I put only 3 levels, but you get the idea):

Code (CSharp):

1.     void CreateGrid()
2.     {
3.         //Creates the central node, it cannot use the CreateLevel() function, since it has no parents
4.         CreateCenterNode();
5.         //I think this will be difficult to parallelise since we want in the creation of each level the new child nodes to consider also already created nodes from the same CreateLevel() function
6.         //We don't use fully nested for loops since this way we are building the tree gradually level by level, which makes it more evenly spread
7.         //Level 1 - Node # = linksPerNode
8.         for (int i = 0; i < linksPerNode; i++)
9.         {
10.             //Builds the first level directly off the central node as a parent
11.             CreateLevel(AllLvlArray[0], i);
12.         }
13.         //Level 2 - Node # = linksPerNode^2
14.         if (branchingLevels >= 2 && allLvlArrayNum < allArrayLength)
15.         {
16.             for (int i = 0; i < linksPerNode; i++)
17.             {
18.                 for (int j = 0; j < linksPerNode; j++)
19.                 {
20.                     //Creates the second level by finding all children from level 1 and assigning them as a parent  for the creation of level 2
21.                     CreateLevel(AllLvlArray[linksContainerArray[0, i + 1]], j);
22.                 }
23.             }
24.         }
25.         //Level 3 - Node # = linksPerNode^3
26.         if (branchingLevels >= 3 && allLvlArrayNum < allArrayLength)
27.         {
28.             for (int i = 0; i < linksPerNode; i++)
29.             {
30.                 for (int j = 0; j < linksPerNode; j++)
31.                 {
32.                     for (int k = 0; k < linksPerNode; k++)
33.                     {
34.                         //Creates the third level by finding all children from level 2 and assigning them as a parent for the creation of level 3
35.                         CreateLevel(AllLvlArray[linksContainerArray[linksContainerArray[0, i + 1], j + 1]], k);
36.                     }
37.                 }
38.             }
39.         }
40.  

I hope that is helpful.
I also thought of ways to optimise my algorithms, it is creating too many iterations of the while loop.
There should be a way to have a more guided/biased random point generation that should rely on a "LookAway()" function that returns a vector that points in the opposite direction from a group of nearby existing nodes.
I thought of this simple approach:
https://i.imgur.com/dS3ZTc7.gif

But it is only an idea now and for 2d and would not work if nodes 2, 3 and 6 are surrounding the parent node 1 from all sides.
I also thought that another point where my algorithm is not optimised is that I discard forever the already generated potential child node positions if they fail the distance test, while they might pass a later relaxed distance test without the need to create new random positions.
Thanks for any pointers
Edit: Here is a new version of the while loop that does no lose "the closest to the threshold that did not pass" and every time when the threshold is relaxed checks that "best candidate" against the new relaxed threshold:

Code (CSharp):

1.  
2. randomLoops = 0;
3. extraDecrease = 0;
4. float minDistScaled = minDistNode * scaleGrid;
5. float lineLengthScaled = lineLength * scaleGrid;
6. float maxSqrMagnitude = 0f;
7. float minUnderThresholdSq=100f;
8. int maxi = 0;
9. while (foundNodePos == false)
10. {
11.     foundNodePos = true;
12.     float minDist = minDistScaled - extraDecrease;
13.     float minDistSq = minDist * minDist;
14.     for (int i = 0; i < allLvlArrayNum; i++)
15.     {
16.         //Discards the new node position if it is too close to other existing nodes. This might make it difficult to put into a job, since there is a dependency
17.         Vector3 newNodeToAllNodes = NodePositions[i] - newNodePos;
18.         float curSqrMagnitude = Vector3.SqrMagnitude(newNodeToAllNodes);
19.         float underThresholdSq = minDistSq - curSqrMagnitude;
20.         if (curSqrMagnitude < minDistSq)
21.         {
22.             if (underThresholdSq < minUnderThresholdSq && i > maxi)
23.             {
24.                 minUnderThresholdSq = underThresholdSq;
25.                 maxSqrMagnitude = curSqrMagnitude;
26.                 furtherstNewNodePos = newNodePos;
27.                 maxi = i;
28.             }
29.             foundNodePos = false;
30.             newNodePos = NodePositions[parentNodeNum] + Random.onUnitSphere * lineLengthScaled;
31.             //i = allLvlArrayNum;
32.             break;
33.         }
34.     }
35.     randomLoops++;
36.     if (randomLoops > maxRandomLoops)
37.     {
38.         //foundNodePos = true;
39.         extraDecrease += (extraDecreaseStep * scaleGrid);
40.         randomLoops = 0;
41.         minDist = minDistScaled - extraDecrease;
42.         minDistSq = minDist * minDist;
43.         if (maxSqrMagnitude> minDistSq) {
44.             foundNodePos = true;
45.             for (int i = 0; i < allLvlArrayNum; i++)
46.             {
47.                 //Checks the node that was closest to the threshold so far against the new threshold
48.                 newNodePos= furtherstNewNodePos;
49.                 Vector3 newNodeToAllNodes = NodePositions[i] - newNodePos;
50.                 float curSqrMagnitude = Vector3.SqrMagnitude(newNodeToAllNodes);
51.                 float underThresholdSq = minDistSq - curSqrMagnitude;
52.                 if (curSqrMagnitude < minDistSq)
53.                 {
54.                     if (underThresholdSq < minUnderThresholdSq && i > maxi)
55.                     {
56.                         minUnderThresholdSq = underThresholdSq;
57.                         maxSqrMagnitude = curSqrMagnitude;
58.                         maxi = i;
59.                     }
60.                     foundNodePos = false;
61.                     newNodePos = NodePositions[parentNodeNum] + Random.onUnitSphere * lineLengthScaled;
62.                     break;
63.                 }
64.             }
65.         }
66.     }
67.     //Debug.Log ("foundNodePos="+foundNodePos);
68. }

Edit2: I tested the above addition to the algorithm, which I call "second chance" The "second chance" bit generates around 15% of all nodes, provides around 10% speed-up and creates slightly more evenly distributed grids.

 

Alright! So some good news, this is totally achievable, and we probably won't even need IJobParallelFor to pull it off.

But there's also some bad news. I was specifically asking for all the variables used in the algorithm (and by algorithm that includes both CreateGrid and CreateLevel because the first step is to get rid of all the reference types like GameObject.name. This does not include arrays 2D arrays, or lists, but does include arrays of lists and lists of lists.

You are allowed to have patch-up steps before and after the main algorithm that can use all the reference types you want. But you have to make sure these patch-up steps take very little time as they will freeze your game. Though I think you should be able to get those steps down to under a frame.

Unfortunately I can't help you with refactoring out those patch-up processes because your algorithm is using variables in class scope and I don't fully know those data types. But if you get stuck anywhere with this refactoring, feel free to ask.

 

Oh, I see now what you wanted, sorry, did not get you the first time. You want a self-containing class with the functions and variables for the algorithm. Also, that passing the whole GameObject of the parent and then getting its number with int.Parse() was such a flop. I actually don't need it since all my positions, rotations and scales are in arrays, so I can pass an int with the parent's index instead.
Hese is a link to the .cs file
https://drive.google.com/file/d/1nt7GCn3Ea2szM0DA3QvAVnF6_S8kcqby/view?usp=sharing
And here is the whole class:

Code (CSharp):

1.  
2. using System.Collections;
3. using System.Collections.Generic;
4. using UnityEngine;
5.  
6. public class New : MonoBehaviour
7. {
8.  
9.     int allLvlArrayNum = 0;
10.     int allArrayLength = 2000;
11.     Vector3 newNodePos;
12.     float lineLength = 0.5f;
13.     float scaleGrid = 1f;
14.     int randomLoops;
15.     float extraDecrease;
16.     float minDistNode = 1f;
17.     float extraDecreaseStep = 0.1f;
18.     bool foundNodePos = false;
19.     Vector3 furtherstNewNodePos;
20.     int maxRandomLoops = 30;
21.     Vector3 camPos = new Vector3(0, 0, 5);
22.     Vector3[] NodePositions;
23.     Quaternion[] NodeRotations;
24.     Vector3[] NodeScales;
25.     Vector3 camUp = new Vector3(0, 1, 0);
26.     Vector3 fixedNormalScale = new Vector3(1f, 1f, 1f);
27.     int[,] linksContainerArray;
28.     int maxLinksPerLinkedNode = 9;
29.     int branchingLevels = 6;
30.     int linksPerNode = 3;
31.  
32.     void AssignValues()
33.     {
34.         NodePositions = new Vector3[allArrayLength];
35.         NodeRotations = new Quaternion[allArrayLength];
36.         NodeScales = new Vector3[allArrayLength];
37.         linksContainerArray = new int[allArrayLength, maxLinksPerLinkedNode];
38.     }
39.  
40.     void CreateLevel(int parentNodeNum, int childrenNum)
41.     {
42.         if (allLvlArrayNum < allArrayLength)
43.         {
44.             newNodePos = NodePositions[parentNodeNum] + Random.onUnitSphere * lineLength * scaleGrid;
45.             randomLoops = 0;
46.             extraDecrease = 0;
47.             float minDistScaled = minDistNode * scaleGrid;
48.             float lineLengthScaled = lineLength * scaleGrid;
49.             float extraDecreaseStepScaled = extraDecreaseStep * scaleGrid;
50.             float maxSqrMagnitude = 0f;
51.             float minUnderThresholdSq = 100f;
52.             int maxi = 0;
53.             //This inner loop checks the distance between the new node and all other nodes and ensures that the new nodes are no too close to existing nodes, gradually lowering the threshold from 1 unit by 0.1 units every 30 attempts
54.             while (foundNodePos == false)
55.             {
56.                 foundNodePos = true;
57.                 float minDist = minDistScaled - extraDecrease;
58.                 float minDistSq = minDist * minDist;
59.                 for (int i = 0; i < allLvlArrayNum; i++)
60.                 {
61.                     //Discards the new node position if it is too close to other existing nodes. This might make it difficult to put into a job, since there is a dependency
62.                     Vector3 newNodeToAllNodes = NodePositions[i] - newNodePos;
63.                     float curSqrMagnitude = Vector3.SqrMagnitude(newNodeToAllNodes);
64.                     float underThresholdSq = minDistSq - curSqrMagnitude;
65.                     if (curSqrMagnitude < minDistSq)
66.                     {
67.                         //Debug.Log(underThresholdSq);
68.                         //if (underThresholdSq < minUnderThresholdSq && i > maxi)
69.                         if (underThresholdSq < minUnderThresholdSq)
70.                         {
71.                             minUnderThresholdSq = underThresholdSq;
72.                             maxSqrMagnitude = curSqrMagnitude;
73.                             furtherstNewNodePos = newNodePos;
74.                             maxi = i;
75.                         }
76.                         foundNodePos = false;
77.                         newNodePos = NodePositions[parentNodeNum] + Random.onUnitSphere * lineLengthScaled;
78.                         break;
79.                     }
80.                 }
81.                 randomLoops++;
82.                 if (randomLoops > maxRandomLoops)
83.                 {
84.                     extraDecrease += extraDecreaseStepScaled;
85.                     randomLoops = 0;
86.                     minDist = minDistScaled - extraDecrease;
87.                     minDistSq = minDist * minDist;
88.                     if (maxSqrMagnitude > minDistSq)
89.                     {
90.                         foundNodePos = true;
91.                         for (int i = 0; i < allLvlArrayNum; i++)
92.                         {
93.                             //Checks the node that was closest to the threshold so far against the new threshold
94.                             newNodePos = furtherstNewNodePos;
95.                             Vector3 newNodeToAllNodes = NodePositions[i] - newNodePos;
96.                             float curSqrMagnitude = Vector3.SqrMagnitude(newNodeToAllNodes);
97.                             float underThresholdSq = minDistSq - curSqrMagnitude;
98.                             if (curSqrMagnitude < minDistSq)
99.                             {
100.                                 if (underThresholdSq < minUnderThresholdSq && i > maxi)
101.                                 {
102.                                     minUnderThresholdSq = underThresholdSq;
103.                                     maxSqrMagnitude = curSqrMagnitude;
104.                                     maxi = i;
105.                                 }
106.                                 foundNodePos = false;
107.                                 newNodePos = NodePositions[parentNodeNum] + Random.onUnitSphere * lineLengthScaled;
108.                                 break;
109.                             }
110.                         }
111.                     }
112.                 }
113.             }
114.             NodePositions[allLvlArrayNum] = newNodePos;
115.             Vector3 nodeToCam = camPos - NodePositions[allLvlArrayNum];
116.             NodeRotations[allLvlArrayNum] = Quaternion.LookRotation(nodeToCam, camUp);
117.             NodeScales[allLvlArrayNum] = fixedNormalScale;
118.             linksContainerArray[parentNodeNum, childrenNum + 1] = allLvlArrayNum;
119.             linksContainerArray[allLvlArrayNum, 0] = parentNodeNum;
120.             allLvlArrayNum++;
121.             foundNodePos = false;
122.         }
123.     }
124.  
125.     void CreateCenterNode()
126.     {
127.         NodePositions[0] = Vector3.zero;
128.         Vector3 nodeToCam = camPos - NodePositions[0];
129.         NodeRotations[allLvlArrayNum] = Quaternion.LookRotation(nodeToCam, camUp);
130.         NodeScales[allLvlArrayNum] = fixedNormalScale;
131.         linksContainerArray[0, 0] = 0;
132.         allLvlArrayNum++;
133.     }
134.  
135.     void CreateGrid()
136.     {
137.         CreateCenterNode();
138.         //We don't use fully nested for loops since this way we are building the tree gradually, which makes it more evenly spread
139.         //Level 1 - Node # = linksPerNode
140.         for (int i = 0; i < linksPerNode; i++)
141.         {
142.             CreateLevel(0, i);
143.         }
144.         //Level 2 - Node # = linksPerNode^2
145.         if (branchingLevels >= 2 && allLvlArrayNum < allArrayLength)
146.         {
147.             for (int i = 0; i < linksPerNode; i++)
148.             {
149.                 for (int j = 0; j < linksPerNode; j++)
150.                 {
151.                     CreateLevel(linksContainerArray[0, i + 1], j);
152.                 }
153.             }
154.         }
155.         //Level 3 - Node # = linksPerNode^3
156.         if (branchingLevels >= 3 && allLvlArrayNum < allArrayLength)
157.         {
158.             for (int i = 0; i < linksPerNode; i++)
159.             {
160.                 for (int j = 0; j < linksPerNode; j++)
161.                 {
162.                     for (int k = 0; k < linksPerNode; k++)
163.                     {
164.                         CreateLevel(linksContainerArray[linksContainerArray[0, i + 1], j + 1], k);
165.                     }
166.                 }
167.             }
168.         }
169.  
170.         //Level 4 - Node # = linksPerNode^4
171.         if (branchingLevels >= 4 && allLvlArrayNum < allArrayLength)
172.         {
173.             for (int i = 0; i < linksPerNode; i++)
174.             {
175.                 for (int j = 0; j < linksPerNode; j++)
176.                 {
177.                     for (int k = 0; k < linksPerNode; k++)
178.                     {
179.                         for (int l = 0; l < linksPerNode; l++)
180.                         {
181.                             CreateLevel(linksContainerArray[linksContainerArray[linksContainerArray[0, i + 1], j + 1], k + 1], l);
182.                         }
183.                     }
184.                 }
185.             }
186.         }
187.         //Level 5 - Node # = linksPerNode^5
188.         if (branchingLevels >= 5 && allLvlArrayNum < allArrayLength)
189.         {
190.             for (int i = 0; i < linksPerNode; i++)
191.             {
192.                 for (int j = 0; j < linksPerNode; j++)
193.                 {
194.                     for (int k = 0; k < linksPerNode; k++)
195.                     {
196.                         for (int l = 0; l < linksPerNode; l++)
197.                         {
198.                             for (int m = 0; m < linksPerNode; m++)
199.                             {
200.                                 CreateLevel(linksContainerArray[linksContainerArray[linksContainerArray[linksContainerArray[0, i + 1], j + 1], k + 1], l + 1], m);
201.                             }
202.                         }
203.                     }
204.                 }
205.             }
206.         }
207.  
208.         //Level 6 - Node # = linksPerNode^6
209.         if (branchingLevels >= 6 && allLvlArrayNum < allArrayLength)
210.         {
211.             for (int i = 0; i < linksPerNode; i++)
212.             {
213.                 for (int j = 0; j < linksPerNode; j++)
214.                 {
215.                     for (int k = 0; k < linksPerNode; k++)
216.                     {
217.                         for (int l = 0; l < linksPerNode; l++)
218.                         {
219.                             for (int m = 0; m < linksPerNode; m++)
220.                             {
221.                                 for (int n = 0; n < linksPerNode; n++)
222.                                 {
223.                                     CreateLevel(linksContainerArray[linksContainerArray[linksContainerArray[linksContainerArray[linksContainerArray[0, i + 1], j + 1], k + 1], l + 1], m + 1], n);
224.                                 }
225.                             }
226.                         }
227.                     }
228.                 }
229.             }
230.         }
231.     }
232. }

I hope that is better.
I should mention that my target is Android and I get the 7 sec loading time on Android.

 

Perfect!

So our next step is we are going to turn this class you named "New" into a job struct. It no longer needs to be on a MonoBehaviour (you can have a MonoBehaviour create and populate the struct). The struct should implement the interface IJob, and the Execute method will just be a simple call to CreateGrid.

We also need to get the remaining managed types to Job-safe types.

For our random number generator, we will create a math.Random field in our struct. This is using Unity.Mathematics. Instead of the onUnitSphere property, we will use the NextFloat3Direction method from our math.Random. We can also change all usages of Vector3 to float3. There's implicit conversions between the two, so you shouldn't have any compatibility issues with the rest of the code, but the float3 will give you a good speedup later.

Next, we need to convert our Arrays into NativeArrays. We'll allocate them using Allocator.TempJob. The 2D array is a little more involved, so I whipped up something for you quick.

Code (CSharp):

1. public struct NativeArray2D<T> : IDisposable where T : struct
2.     {
3.         private int xDim, yDim;
4.         private NativeArray<T> data;
5.  
6.         public NativeArray2D(int x, int y, Allocator allocator)
7.         {
8.             xDim = x;
9.             yDim = y;
10.             data = new NativeArray<T>(x * y, allocator);
11.         }
12.  
13.         public int CountX { get { return xDim; } }
14.         public int CountY { get { return yDim; } }
15.  
16.         public T this[int x, int y]
17.         {
18.             get
19.             {
20.                 return data[yDim * x + y];
21.             }
22.             set
23.             {
24.                 data[yDim * x + y] = value;
25.             }
26.         }
27.  
28.         public void Dispose()
29.         {
30.             data.Dispose();
31.         }
32.     }

By this point, we are pretty close to having something heavily optimizable, but we need to test some things to make sure they aren't broken. To ensure everything works, run the job and complete it immediately using .Schedule().Complete() and then copy the data out of the NativeArrays into the arrays that the rest of your game uses. First, make sure you get results on screen that you like. Second, make sure that the final copy step runs fast enough for your liking assuming that that little bit of code will freeze your game. If it takes too long, we'll have to do some additional gymnastics to speed that up.

Assuming everything is checking out, the next step is to add [BurstCompile] on top of the job and see how much faster it runs. It might actually be fast enough that you don't need to do anything else, but if not, we can keep going.

To get this thing running asynchronous, we can use a code snippet like this inside a coroutine:

Code (CSharp):

1. var jh = ourJobStructInstance.Schedule(this);
2.             while (!jh.IsCompleted)
3.             {
4.                 yield return null;
5.             }
6.             jh.Complete();

See how close that gets you to what you want. And if there's still some problems, we can work them out!

 

Can I ask what your algorithm is trying to do, why do you need a group of random points with a minimum distance between them?

 

Hi, Thanks for all the tips. This is quite new for me so it took some time to figure it out, but it was interesting.
I decided to test everything in a new project to be sure that I am working on a clean basis with only 2 scripts:
JobCaller.cs that is a MonoBehaviour and that starts the job upon pressing the space key:
https://drive.google.com/file/d/1b_8PPa51ewFVwT1iK6jCMnBhX-cxzp2O/view?usp=sharing
CreateGridStruct.cs that contains the IJob struct and the NativeArray2D struct:
https://drive.google.com/file/d/1_gKGUTzuKKbALFMJ51c6fUglorwOVu6Z/view?usp=sharing
I finally managed to compile the scripts, but I get this error message when I start the createGridJob:

Code (CSharp):

1. ArgumentException: Invalid state 0. Random object has not been properly initialized
2. Unity.Mathematics.Random.CheckState () (at Library/PackageCache/com.unity.mathematics@1.0.1/Unity.Mathematics/random.cs:535)
3. Unity.Mathematics.Random.NextState () (at Library/PackageCache/com.unity.mathematics@1.0.1/Unity.Mathematics/random.cs:513)
4. Unity.Mathematics.Random.NextFloat2 () (at Library/PackageCache/com.unity.mathematics@1.0.1/Unity.Mathematics/random.cs:314)
5. Unity.Mathematics.Random.NextFloat3Direction () (at Library/PackageCache/com.unity.mathematics@1.0.1/Unity.Mathematics/random.cs:469)
6. CreateGridJob.CreateLevel (System.Int32 parentNodeNum, System.Int32 childrenNum) (at Assets/Scripts/CreateGridStruct.cs:91)
7. CreateGridJob.CreateGrid () (at Assets/Scripts/CreateGridStruct.cs:232)
8. CreateGridJob.Execute () (at Assets/Scripts/CreateGridStruct.cs:84)
9. Unity.Jobs.IJobExtensions+JobStruct`1[T].Execute (T& data, System.IntPtr additionalPtr, System.IntPtr bufferRangePatchData, Unity.Jobs.LowLevel.Unsafe.JobRanges& ranges, System.Int32 jobIndex) (at C:/buildslave/unity/build/Runtime/Jobs/Managed/IJob.cs:30)
10. Unity.Jobs.JobHandle:ScheduleBatchedJobsAndComplete(JobHandle&)
11. Unity.Jobs.JobHandle:Complete() (at C:/buildslave/unity/build/Runtime/Jobs/ScriptBindings/JobHandle.bindings.cs:20)
12. JobCaller:CallCreateGridJob() (at Assets/Scripts/JobCaller.cs:156)
13. JobCaller:Update() (at Assets/Scripts/JobCaller.cs:222)

It says I have not properly initialized the Random object. For reference, this is what I did:

Code (CSharp):

1. using Rand = Unity.Mathematics.Random;
2. ...
3. public static Rand rand;
4. ...
5. public float3 randVector3;
6. ...
7. randVector3 = rand.NextFloat3Direction();

It also spits the following message:

Code (CSharp):

1. Internal: JobTempAlloc has allocations that are more than 4 frames old - this is not allowed and likely a leak
2. -----------------------------
3. To Debug, enable the define: TLA_DEBUG_STACK_LEAK in ThreadsafeLinearAllocator.cpp. This will output the callstacks of the leaked allocations
4.  

In the job struct I also resorted to the Unity method for getting a Quaternion from a direction vector and up vector, because I did not know of any similar method in the new math library:

Code (CSharp):

1. longCubesRotNA[numberOfLinks] = Quaternion.LookRotation(nodeToNode, Vector3.up);

I also don't know whether we should dispose of the NativeArrays...
BTW, once I get this done, I plan to continue with converting to the job system the building of the secondary grid, but let's first get this done
Here is the JobCaller.cs

Code (CSharp):

1. using System.Collections;
2. using System.Collections.Generic;
3. using UnityEngine;
4. using UnityEngine.UI;
5. using Unity.Collections;
6. using TMPro;
7. using UnityEngine.SceneManagement;
8. using UnityEngine.EventSystems;
9. using Unity.Jobs;
10. using UnityEngine.Jobs;
11. using Unity.Mathematics;
12.  
13. public class JobCaller : MonoBehaviour
14. {
15.     public int allLvlArrayNum=0;
16.     public int allArrayLength;
17.     public Vector3 newNodePos;
18.     public float lineLength;
19.     public float scaleGrid;
20.     public int randomLoops=0;
21.     public float extraDecrease=0f;
22.     public float minDistNode;
23.     public float extraDecreaseStep;
24.     public bool foundNodePos=false;
25.     public Vector3 furtherstNewNodePos;
26.     public int maxRandomLoops;
27.     public Vector3 camPos;
28.     public Vector3[] NodePositions;
29.     public Quaternion[] NodeRotations;
30.     public Vector3[] NodeScales;
31.     public Vector3 camUp;
32.     public Vector3 fixedNormalScale;
33.     public int[,] linksContainerArray;
34.     public int[] linksContainerArrayLength;
35.     public int[,] lineToNodes;
36.     public int numberOfLinks=0;
37.     public Vector3[] longCubesPos;
38.     public Quaternion[] longCubesRot;
39.     public Vector3[] longCubesScale;
40.     public bool[,] currentLinkedToTarget;
41.     public int[,] instLongCubesNum;
42.     public float[,] DistanceBetweenNodesArraySq;
43.     public float linkWidth;
44.     public int maxLinksPerLinkedNode;
45.     public int branchingLevels;
46.     public int linksPerNode;
47.     public int secondChance;
48.     public int maxLinks;
49.  
50.     void AssignValues()
51.     {
52.         allArrayLength = 2000;
53.         maxLinksPerLinkedNode = 9;
54.         lineLength = 0.5f;
55.         scaleGrid = 1f;
56.         minDistNode = 1f;
57.         extraDecreaseStep = 0.1f;
58.         maxRandomLoops = 30;
59.         linkWidth = 0.01f;
60.         branchingLevels = 6;
61.         linksPerNode = 3;
62.         NodePositions = new Vector3[allArrayLength];
63.         NodeRotations = new Quaternion[allArrayLength];
64.         NodeScales = new Vector3[allArrayLength];
65.         maxLinks = allArrayLength * maxLinksPerLinkedNode;
66.         instLongCubesNum = new int[allArrayLength, maxLinksPerLinkedNode];
67.         linksContainerArray = new int[allArrayLength, maxLinksPerLinkedNode];
68.         currentLinkedToTarget = new bool[allArrayLength, allArrayLength];
69.         DistanceBetweenNodesArraySq = new float[allArrayLength, allArrayLength];
70.         for (int i = 0; i < allArrayLength; i++)
71.         {
72.             for (int j = 0; j < allArrayLength; j++)
73.             {
74.                 currentLinkedToTarget[i, j] = false;
75.             }
76.         }
77.         linksContainerArrayLength = new int[allArrayLength];
78.         longCubesPos = new Vector3[maxLinks];
79.         longCubesRot = new Quaternion[maxLinks];
80.         longCubesScale = new Vector3[maxLinks];
81.         lineToNodes = new int[maxLinks, 2];
82.         fixedNormalScale = new Vector3(5f, 5f, 5f);
83.         linkWidth = 0.01f;
84.         camPos = new Vector3(0f, 0f, -3f);
85.         camUp = new Vector3(0f, 1f, 0f);
86.     }
87.  
88.  
89.     void CallCreateGridJob()
90.     {
91.         var createGridJob = new CreateGridJob()
92.         {
93.             allLvlArrayNum = allLvlArrayNum,
94.             allArrayLength = allArrayLength,
95.             newNodePos = newNodePos,
96.             lineLength = lineLength,
97.             scaleGrid = scaleGrid,
98.             randomLoops = randomLoops,
99.             extraDecrease = extraDecrease,
100.             minDistNode = minDistNode,
101.             extraDecreaseStep = extraDecreaseStep,
102.             foundNodePos = foundNodePos,
103.             furtherstNewNodePos = furtherstNewNodePos,
104.             maxRandomLoops = maxRandomLoops,
105.             camPos = camPos,
106.             NodePositionsNA = new NativeArray<float3>(allArrayLength, Allocator.TempJob),
107.             NodeRotationsNA = new NativeArray<Quaternion>(NodeRotations, Allocator.TempJob),
108.             NodeScalesNA = new NativeArray<float3>(allArrayLength, Allocator.TempJob),
109.             camUp = camUp,
110.             fixedNormalScale = fixedNormalScale,
111.             linksContainerArrayNA = new NativeArray2D<int>(allArrayLength, maxLinksPerLinkedNode, Allocator.TempJob),
112.             linksContainerArrayLengthNA = new NativeArray<int>(linksContainerArrayLength, Allocator.TempJob),
113.             lineToNodesNA = new NativeArray2D<int>(maxLinks, 2, Allocator.TempJob),
114.             numberOfLinks = numberOfLinks,
115.             longCubesScaleNA = new NativeArray<float3>(maxLinks, Allocator.TempJob),
116.             longCubesPosNA = new NativeArray<float3>(maxLinks, Allocator.TempJob),
117.             longCubesRotNA = new NativeArray<Quaternion>(longCubesRot, Allocator.TempJob),
118.             currentLinkedToTargetNA = new NativeArray2D<bool>(allArrayLength, allArrayLength, Allocator.TempJob),
119.             instLongCubesNumNA = new NativeArray2D<int>(allArrayLength, maxLinksPerLinkedNode, Allocator.TempJob),
120.             DistanceBetweenNodesArraySqNA = new NativeArray2D<float>(allArrayLength, allArrayLength, Allocator.TempJob),
121.             linkWidth = linkWidth,
122.             maxLinksPerLinkedNode = maxLinksPerLinkedNode,
123.             branchingLevels = branchingLevels,
124.             linksPerNode = linksPerNode,
125.             secondChance = secondChance,
126.         };
127.  
128.         for (int i = 0; i < allArrayLength; i++)
129.         {
130.             createGridJob.NodePositionsNA[i] = NodePositions[i];
131.             createGridJob.NodeScalesNA[i] = NodeScales[i];
132.             for (int j = 0; j < maxLinksPerLinkedNode; j++)
133.             {
134.                 createGridJob.linksContainerArrayNA[i, j] = linksContainerArray[i, j];
135.                 createGridJob.instLongCubesNumNA[i, j] = instLongCubesNum[i, j];
136.             }
137.             for (int k = 0; k < allArrayLength; k++)
138.             {
139.                 createGridJob.currentLinkedToTargetNA[i, k] = currentLinkedToTarget[i, k];
140.                 createGridJob.DistanceBetweenNodesArraySqNA[i, k] = DistanceBetweenNodesArraySq[i, k];
141.             }
142.         }
143.  
144.         for (int i = 0; i < maxLinks; i++)
145.         {
146.             createGridJob.lineToNodesNA[i, 0] = lineToNodes[i, 0];
147.             createGridJob.lineToNodesNA[i, 1] = lineToNodes[i, 1];
148.             createGridJob.longCubesScaleNA[i] = longCubesScale[i];
149.             createGridJob.longCubesPosNA[i] = longCubesPos[i];
150.             createGridJob.longCubesRotNA[i] = longCubesRot[i];
151.         }
152.  
153.         JobHandle createGridJobHandle = createGridJob.Schedule();
154.         createGridJobHandle.Complete();
155.  
156.         NodeRotations = createGridJob.NodeRotationsNA.ToArray();
157.         linksContainerArrayLength = createGridJob.linksContainerArrayLengthNA.ToArray();
158.         longCubesRot = createGridJob.longCubesRotNA.ToArray();
159.         for (int i = 0; i < allArrayLength; i++)
160.         {
161.             NodePositions[i] = createGridJob.NodePositionsNA[i];
162.             NodeScales[i] = createGridJob.NodeScalesNA[i];
163.             for (int j = 0; j < maxLinksPerLinkedNode; j++)
164.             {
165.                 linksContainerArray[i, j] = createGridJob.linksContainerArrayNA[i, j];
166.                 instLongCubesNum[i, j] = createGridJob.instLongCubesNumNA[i, j];
167.             }
168.             for (int k = 0; k < allArrayLength; k++)
169.             {
170.                 currentLinkedToTarget[i, k] = createGridJob.currentLinkedToTargetNA[i, k];
171.                 DistanceBetweenNodesArraySq[i, k] = createGridJob.DistanceBetweenNodesArraySqNA[i, k];
172.             }
173.         }
174.  
175.         for (int i = 0; i < maxLinks; i++)
176.         {
177.             lineToNodes[i, 0] = createGridJob.lineToNodesNA[i, 0];
178.             lineToNodes[i, 1] = createGridJob.lineToNodesNA[i, 1];
179.             longCubesScale[i] = createGridJob.longCubesScaleNA[i];
180.             longCubesPos[i] = createGridJob.longCubesPosNA[i];
181.             longCubesRot[i] = createGridJob.longCubesRotNA[i];
182.         }
183.  
184.         if (createGridJob.NodePositionsNA != null)
185.         {
186.             createGridJob.NodePositionsNA.Dispose();
187.         }
188.  
189.         if (createGridJob.NodeRotationsNA != null)
190.         {
191.             createGridJob.NodeRotationsNA.Dispose();
192.         }
193.  
194.         if (createGridJob.NodeScalesNA != null)
195.         {
196.             createGridJob.NodeScalesNA.Dispose();
197.         }
198.  
199.         //if (createGridJob.linksContainerArrayNA != null)
200.         //{
201.         createGridJob.linksContainerArrayNA.Dispose();
202.         //}
203.  
204.         createGridJob.allLvlArrayNum = allLvlArrayNum;
205.         createGridJob.numberOfLinks = numberOfLinks;
206.         createGridJob.secondChance = secondChance;
207.     }
208.  
209.     // Start is called before the first frame update
210.     void Start()
211.     {
212.         AssignValues();
213.     }
214.  
215.     // Update is called once per frame
216.     void Update()
217.     {
218.         if (Input.GetKeyDown("space"))
219.         {
220.             CallCreateGridJob();
221.         }
222.         //Debug.LogError(allArrayLength);
223.     }
224. }
225.  

and the CreateGridStruct.cs:

Code (CSharp):

1. using System.Collections;
2. using System.Collections.Generic;
3. using UnityEngine;
4. using Unity.Collections;
5. using Unity.Jobs;
6. using UnityEngine.Jobs;
7. using Unity.Mathematics;
8. using Rand = Unity.Mathematics.Random;
9. using System;
10.  
11. public struct NativeArray2D<T> : IDisposable where T : struct
12. {
13.     private int xDim, yDim;
14.     private NativeArray<T> data;
15.  
16.     public NativeArray2D(int x, int y, Allocator allocator)
17.     {
18.         xDim = x;
19.         yDim = y;
20.         data = new NativeArray<T>(x * y, allocator);
21.     }
22.  
23.     public int CountX { get { return xDim; } }
24.     public int CountY { get { return yDim; } }
25.  
26.     public T this[int x, int y]
27.     {
28.         get
29.         {
30.             return data[yDim * x + y];
31.         }
32.         set
33.         {
34.             data[yDim * x + y] = value;
35.         }
36.     }
37.  
38.     public void Dispose()
39.     {
40.         data.Dispose();
41.     }
42. }
43.  
44. public struct CreateGridJob : IJob
45. {
46.     public int allLvlArrayNum;
47.     public int allArrayLength;
48.     public float3 newNodePos;
49.     public float lineLength;
50.     public float scaleGrid;
51.     public int randomLoops;
52.     public float extraDecrease;
53.     public float minDistNode;
54.     public float extraDecreaseStep;
55.     public bool foundNodePos;
56.     public float3 furtherstNewNodePos;
57.     public int maxRandomLoops;
58.     public float3 camPos;
59.     public NativeArray<float3> NodePositionsNA;
60.     public NativeArray<Quaternion> NodeRotationsNA;
61.     public NativeArray<float3> NodeScalesNA;
62.     public float3 camUp;
63.     public float3 fixedNormalScale;
64.     public NativeArray2D<int> linksContainerArrayNA;
65.     public NativeArray<int> linksContainerArrayLengthNA;
66.     public NativeArray2D<int> lineToNodesNA;
67.     public int numberOfLinks;
68.     public NativeArray<float3> longCubesScaleNA;
69.     public NativeArray<float3> longCubesPosNA;
70.     public NativeArray<Quaternion> longCubesRotNA;
71.     public NativeArray2D<bool> currentLinkedToTargetNA;
72.     public NativeArray2D<int> instLongCubesNumNA;
73.     public float linkWidth;
74.     public int maxLinksPerLinkedNode;
75.     public int branchingLevels;
76.     public int linksPerNode;
77.     public float3 randVector3;
78.     public static Rand rand;
79.     public int secondChance;
80.     public NativeArray2D<float> DistanceBetweenNodesArraySqNA;
81.  
82.     public void Execute()
83.     {
84.         CreateGrid();
85.     }
86.  
87.     void CreateLevel(int parentNodeNum, int childrenNum)
88.     {
89.         if (allLvlArrayNum < allArrayLength)
90.         {
91.             randVector3 = rand.NextFloat3Direction();
92.             float lineLengthScaled = lineLength * scaleGrid;
93.             newNodePos = NodePositionsNA[parentNodeNum] + randVector3 * lineLengthScaled;
94.             randomLoops = 0;
95.             extraDecrease = 0;
96.             float minDistScaled = minDistNode * scaleGrid;
97.             float extraDecreaseStepScaled = extraDecreaseStep * scaleGrid;
98.             float maxSqrMagnitude = 0f;
99.             float minUnderThresholdSq = 100f;
100.             int maxi = 0;
101.             while (foundNodePos == false)
102.             {
103.                 foundNodePos = true;
104.                 float minDist = minDistScaled - extraDecrease;
105.                 float minDistSq = minDist * minDist;
106.                 for (int i = 0; i < allLvlArrayNum; i++)
107.                 {
108.                     //Discards the new node position if it is too close to other existing nodes.
109.                     float3 newNodeToAllNodes = NodePositionsNA[i] - newNodePos;
110.                     float curSqrMagnitude = newNodeToAllNodes.x* newNodeToAllNodes.x+ newNodeToAllNodes.y * newNodeToAllNodes.y+ newNodeToAllNodes.z * newNodeToAllNodes.z;
111.                     float underThresholdSq = minDistSq - curSqrMagnitude;
112.                     if (curSqrMagnitude < minDistSq)
113.                     {
114.                         if (underThresholdSq < minUnderThresholdSq && i > maxi)
115.                         //if (underThresholdSq < minUnderThresholdSq)
116.                         {
117.                             minUnderThresholdSq = underThresholdSq;
118.                             maxSqrMagnitude = curSqrMagnitude;
119.                             furtherstNewNodePos = newNodePos;
120.                             maxi = i;
121.                         }
122.                         foundNodePos = false;
123.                         float3 randVector3 = rand.NextFloat3Direction();
124.                         newNodePos = NodePositionsNA[parentNodeNum] + randVector3 * lineLengthScaled;
125.                         break;
126.                     }
127.                 }
128.                 randomLoops++;
129.                 if (randomLoops > maxRandomLoops && foundNodePos==false)
130.                 {
131.                     extraDecrease += extraDecreaseStepScaled;
132.                     randomLoops = 0;
133.                     minDist = minDistScaled - extraDecrease;
134.                     minDistSq = minDist * minDist;
135.                     if (maxSqrMagnitude > minDistSq)
136.                     {
137.                         foundNodePos = true;
138.                         for (int i = 0; i < allLvlArrayNum; i++)
139.                         {
140.                             //Checks the node that was closest to the threshold so far against the new threshold
141.                             newNodePos = furtherstNewNodePos;
142.                             float3 newNodeToAllNodes = NodePositionsNA[i] - newNodePos;
143.                             float curSqrMagnitude = newNodeToAllNodes.x * newNodeToAllNodes.x + newNodeToAllNodes.y * newNodeToAllNodes.y + newNodeToAllNodes.z * newNodeToAllNodes.z;
144.                             float underThresholdSq = minDistSq - curSqrMagnitude;
145.                             if (curSqrMagnitude < minDistSq)
146.                             {
147.                                 if (underThresholdSq < minUnderThresholdSq && i > maxi)
148.                                 {
149.                                     minUnderThresholdSq = underThresholdSq;
150.                                     maxSqrMagnitude = curSqrMagnitude;
151.                                     maxi = i;
152.                                 }
153.                                 foundNodePos = false;
154.                                 float3 randVector3 = rand.NextFloat3Direction();
155.                                 newNodePos = NodePositionsNA[parentNodeNum] + randVector3 * lineLengthScaled;
156.                                 break;
157.                             }
158.                         }
159.                     }
160.                     if (foundNodePos)
161.                     {
162.                         secondChance++;
163.                     }
164.                 }
165.             }
166.             NodePositionsNA[allLvlArrayNum] = newNodePos;
167.             float3 nodeToCam = camPos - NodePositionsNA[allLvlArrayNum];
168.             NodeRotationsNA[allLvlArrayNum] = Quaternion.LookRotation(nodeToCam, camUp);
169.             NodeScalesNA[allLvlArrayNum] = fixedNormalScale;
170.             float3 nodeToNode = NodePositionsNA[parentNodeNum] - NodePositionsNA[allLvlArrayNum];
171.             float distBetweenNodes = math.sqrt(nodeToNode.x* nodeToNode.x+nodeToNode.y* nodeToNode.y+nodeToNode.z* nodeToNode.z);
172.             float3 nodeMidPoint = NodePositionsNA[allLvlArrayNum] + nodeToNode * 0.5f;
173.             longCubesScaleNA[numberOfLinks] = new float3(linkWidth, linkWidth, distBetweenNodes);
174.             longCubesPosNA[numberOfLinks] = nodeMidPoint;
175.             //How is this lookrotation implemented in the new math library?
176.             longCubesRotNA[numberOfLinks] = Quaternion.LookRotation(nodeToNode, Vector3.up);
177.             linksContainerArrayNA[parentNodeNum, childrenNum + 1] = allLvlArrayNum;
178.             linksContainerArrayLengthNA[parentNodeNum]++;
179.             currentLinkedToTargetNA[parentNodeNum, allLvlArrayNum] = true;
180.             instLongCubesNumNA[parentNodeNum, childrenNum + 1] = numberOfLinks;
181.             lineToNodesNA[numberOfLinks, 0] = parentNodeNum;
182.             lineToNodesNA[numberOfLinks, 1] = allLvlArrayNum;
183.             linksContainerArrayNA[allLvlArrayNum, 0] = parentNodeNum;
184.             linksContainerArrayLengthNA[allLvlArrayNum]++;
185.             currentLinkedToTargetNA[allLvlArrayNum, parentNodeNum] = true;
186.             instLongCubesNumNA[allLvlArrayNum, 0] = numberOfLinks;
187.             allLvlArrayNum++;
188.             foundNodePos = false;
189.             numberOfLinks++;
190.         }
191.     }
192.  
193.     void CreateCenterNode()
194.     {
195.         NodePositionsNA[0] = new float3(0f,0f,0f);
196.         float3 nodeToCam = camPos - NodePositionsNA[0];
197.         //can we use the math analogue to Quaternion.LookRotation?
198.         NodeRotationsNA[allLvlArrayNum] = Quaternion.LookRotation(nodeToCam, camUp);
199.         NodeScalesNA[allLvlArrayNum] = fixedNormalScale;
200.         linksContainerArrayNA[0, 0] = 0;
201.         linksContainerArrayLengthNA[allLvlArrayNum]=1;
202.         currentLinkedToTargetNA[0, 0] = true;
203.         longCubesScaleNA[0] = new float3(0f, 0f, 0f);
204.         longCubesPosNA[0] = new float3(0f, 0f, 0f);
205.         longCubesRotNA[0] = Quaternion.identity;
206.         instLongCubesNumNA[0, 0] = 0;
207.         lineToNodesNA[0, 0] = 0;
208.         lineToNodesNA[0, 1] = 0;
209.         numberOfLinks++;
210.         allLvlArrayNum++;
211.     }
212.  
213.     void FillDistanceArray()
214.     {
215.         for (int i = 0; i < allLvlArrayNum; i++)
216.         {
217.             for (int j = 0; j < allLvlArrayNum; j++)
218.             {
219.                 float3 NodeItoJ = NodePositionsNA[j] - NodePositionsNA[i];
220.                 DistanceBetweenNodesArraySqNA[i, j] = NodeItoJ.x*NodeItoJ.x+ NodeItoJ.y * NodeItoJ.y+ NodeItoJ.z * NodeItoJ.z;
221.             }
222.         }
223.     }
224.  
225.     void CreateGrid()
226.     {
227.         CreateCenterNode();
228.         //We don't use fully nested for loops since this way we are building the tree gradually, which makes it more evenly spread
229.         //Level 1 - Node # = linksPerNode
230.         for (int i = 0; i < linksPerNode; i++)
231.         {
232.             CreateLevel(0, i);
233.         }
234.         //Level 2 - Node # = linksPerNode^2
235.         if (branchingLevels >= 2 && allLvlArrayNum < allArrayLength)
236.         {
237.             for (int i = 0; i < linksPerNode; i++)
238.             {
239.                 for (int j = 0; j < linksPerNode; j++)
240.                 {
241.                     CreateLevel(linksContainerArrayNA[0, i + 1], j);
242.                 }
243.             }
244.         }
245.         //Level 3 - Node # = linksPerNode^3
246.         if (branchingLevels >= 3 && allLvlArrayNum < allArrayLength)
247.         {
248.             for (int i = 0; i < linksPerNode; i++)
249.             {
250.                 for (int j = 0; j < linksPerNode; j++)
251.                 {
252.                     for (int k = 0; k < linksPerNode; k++)
253.                     {
254.                         CreateLevel(linksContainerArrayNA[linksContainerArrayNA[0, i + 1], j + 1], k);
255.                     }
256.                 }
257.             }
258.         }
259.  
260.         //Level 4 - Node # = linksPerNode^4
261.         if (branchingLevels >= 4 && allLvlArrayNum < allArrayLength)
262.         {
263.             for (int i = 0; i < linksPerNode; i++)
264.             {
265.                 for (int j = 0; j < linksPerNode; j++)
266.                 {
267.                     for (int k = 0; k < linksPerNode; k++)
268.                     {
269.                         for (int l = 0; l < linksPerNode; l++)
270.                         {
271.                             CreateLevel(linksContainerArrayNA[linksContainerArrayNA[linksContainerArrayNA[0, i + 1], j + 1], k + 1], l);
272.                         }
273.                     }
274.                 }
275.             }
276.         }
277.         //Level 5 - Node # = linksPerNode^5
278.         if (branchingLevels >= 5 && allLvlArrayNum < allArrayLength)
279.         {
280.             for (int i = 0; i < linksPerNode; i++)
281.             {
282.                 for (int j = 0; j < linksPerNode; j++)
283.                 {
284.                     for (int k = 0; k < linksPerNode; k++)
285.                     {
286.                         for (int l = 0; l < linksPerNode; l++)
287.                         {
288.                             for (int m = 0; m < linksPerNode; m++)
289.                             {
290.                                 CreateLevel(linksContainerArrayNA[linksContainerArrayNA[linksContainerArrayNA[linksContainerArrayNA[0, i + 1], j + 1], k + 1], l + 1], m);
291.                             }
292.                         }
293.                     }
294.                 }
295.             }
296.         }
297.  
298.         //Level 6 - Node # = linksPerNode^6
299.         if (branchingLevels >= 6 && allLvlArrayNum < allArrayLength)
300.         {
301.             for (int i = 0; i < linksPerNode; i++)
302.             {
303.                 for (int j = 0; j < linksPerNode; j++)
304.                 {
305.                     for (int k = 0; k < linksPerNode; k++)
306.                     {
307.                         for (int l = 0; l < linksPerNode; l++)
308.                         {
309.                             for (int m = 0; m < linksPerNode; m++)
310.                             {
311.                                 for (int n = 0; n < linksPerNode; n++)
312.                                 {
313.                                     CreateLevel(linksContainerArrayNA[linksContainerArrayNA[linksContainerArrayNA[linksContainerArrayNA[linksContainerArrayNA[0, i + 1], j + 1], k + 1], l + 1], m + 1], n);
314.                                 }
315.                             }
316.                         }
317.                     }
318.                 }
319.             }
320.         }
321.  
322.         //Level 7 - Node # = linksPerNode^7
323.         if (branchingLevels >= 7 && allLvlArrayNum < allArrayLength)
324.         {
325.             for (int i = 0; i < linksPerNode; i++)
326.             {
327.                 for (int j = 0; j < linksPerNode; j++)
328.                 {
329.                     for (int k = 0; k < linksPerNode; k++)
330.                     {
331.                         for (int l = 0; l < linksPerNode; l++)
332.                         {
333.                             for (int m = 0; m < linksPerNode; m++)
334.                             {
335.                                 for (int n = 0; n < linksPerNode; n++)
336.                                 {
337.                                     for (int o = 0; o < linksPerNode; o++)
338.                                     {
339.                                         CreateLevel(linksContainerArrayNA[linksContainerArrayNA[linksContainerArrayNA[linksContainerArrayNA[linksContainerArrayNA[linksContainerArrayNA[0, i + 1], j + 1], k + 1], l + 1], m + 1], n + 1], o);
340.                                     }
341.                                 }
342.                             }
343.                         }
344.                     }
345.                 }
346.             }
347.         }
348.  
349.         //Level 8 - Node # = linksPerNode^8
350.         if (branchingLevels >= 8 && allLvlArrayNum < allArrayLength)
351.         {
352.             for (int i = 0; i < linksPerNode; i++)
353.             {
354.                 for (int j = 0; j < linksPerNode; j++)
355.                 {
356.                     for (int k = 0; k < linksPerNode; k++)
357.                     {
358.                         for (int l = 0; l < linksPerNode; l++)
359.                         {
360.                             for (int m = 0; m < linksPerNode; m++)
361.                             {
362.                                 for (int n = 0; n < linksPerNode; n++)
363.                                 {
364.                                     for (int o = 0; o < linksPerNode; o++)
365.                                     {
366.                                         for (int p = 0; p < linksPerNode; p++)
367.                                         {
368.                                             CreateLevel(linksContainerArrayNA[linksContainerArrayNA[linksContainerArrayNA[linksContainerArrayNA[linksContainerArrayNA[linksContainerArrayNA[linksContainerArrayNA[0, i + 1], j + 1], k + 1], l + 1], m + 1], n + 1], o + 1], p);
369.                                         }
370.                                     }
371.                                 }
372.                             }
373.                         }
374.                     }
375.                 }
376.             }
377.         }
378.  
379.         //Level 9 - Node # = linksPerNode^9
380.         if (branchingLevels >= 9 && allLvlArrayNum < allArrayLength)
381.         {
382.             for (int i = 0; i < linksPerNode; i++)
383.             {
384.                 for (int j = 0; j < linksPerNode; j++)
385.                 {
386.                     for (int k = 0; k < linksPerNode; k++)
387.                     {
388.                         for (int l = 0; l < linksPerNode; l++)
389.                         {
390.                             for (int m = 0; m < linksPerNode; m++)
391.                             {
392.                                 for (int n = 0; n < linksPerNode; n++)
393.                                 {
394.                                     for (int o = 0; o < linksPerNode; o++)
395.                                     {
396.                                         for (int p = 0; p < linksPerNode; p++)
397.                                         {
398.                                             for (int q = 0; q < linksPerNode; q++)
399.                                             {
400.                                                 CreateLevel(linksContainerArrayNA[linksContainerArrayNA[linksContainerArrayNA[linksContainerArrayNA[linksContainerArrayNA[linksContainerArrayNA[linksContainerArrayNA[linksContainerArrayNA[0, i + 1], j + 1], k + 1], l + 1], m + 1], n + 1], o + 1], p + 1], q);
401.                                             }
402.                                         }
403.                                     }
404.                                 }
405.                             }
406.                         }
407.                     }
408.                 }
409.             }
410.         }
411.         FillDistanceArray();
412.     }
413. }
414.  

Thanks in advance.

 

Alright. First, let's address that Random issue.

So in classical Unity, Unity provides a Random number generator singleton that generates a new value every time you call for a value. That works well in the single-threaded paradigm of classical Unity. However, it falls flat on its face when multithreading in job system enters the game. So instead of creating a static math.Random, we want our Random to be another variable in the CreateGridJob. And then we initialize it with a new math.Random(seed).

Now there's this magic "seed" variable that we have to deal with. Every random number generator needs a seed, and since we are creating a new generator for our job, we need a new one. There are many ways to generate them. We can either use UnityEngine.Random or we can use the current time.

Code (CSharp):

1. uint seed  = (uint)(System.DateTime.Now.Ticks & 0x00000000FFFFFFFF);
2. uint seed2 = math.asuint(Random.Range(float.MinValue, float.MaxValue));

For the quaternion, you want math.quaternion.LookRotationSafe(nodeToNode, Vector3.up)

And yes, you should call Dispose() when you are done with the NativeContainers at the end of your generation. Unfortunately there is a bug in Unity where if you encounter an exception after allocating a NativeContainer Unity will keep issuing that warning message until you restart Unity. I have learned to just ignore it until I get my algorithm stable, and then restart Unity when it is convenient.

There's still a ton of headroom for optimization, but let's get this code running first!

 

Ugh, that was underwhelming... I got it to work now, but it actually made the grid creation time 2-3 times slower (i.e. around 18 sec). I even used the burst compiler. I don't know why and I have to go to bed now. Here is how the Profiler looks like at 1000 nodes https://drive.google.com/file/d/1l3zF76rFVqiusuEzKwIKDsEjYIrYSmFj/view?usp=sharing
I also had an idea how to use IJobParallelFor to create the nodes for all children per level at the same time: have the existing grid for the positions of all parents that should spawn nodes at this level and all their parents' positions in a read-only array. Then have another read/write array for all the child nodes that should be created this level pre-populated with very distant positions and have the IJobParallelFor iterate through all the positions in the read-only array and the read/write array.
Here is how the working struct looks like

Code (CSharp):

1. using System.Collections;
2. using System.Collections.Generic;
3. using UnityEngine;
4. using Unity.Collections;
5. using Unity.Jobs;
6. using UnityEngine.Jobs;
7. using Unity.Mathematics;
8. using Rand = Unity.Mathematics.Random;
9. using System;
10. using Unity.Burst;
11.  
12. public struct NativeArray2D<T> : IDisposable where T : struct
13. {
14.     private int xDim, yDim;
15.     private NativeArray<T> data;
16.  
17.     public NativeArray2D(int x, int y, Allocator allocator)
18.     {
19.         xDim = x;
20.         yDim = y;
21.         data = new NativeArray<T>(x * y, allocator);
22.     }
23.  
24.     public int CountX { get { return xDim; } }
25.     public int CountY { get { return yDim; } }
26.  
27.     public T this[int x, int y]
28.     {
29.         get
30.         {
31.             return data[yDim * x + y];
32.         }
33.         set
34.         {
35.             data[yDim * x + y] = value;
36.         }
37.     }
38.  
39.     public void Dispose()
40.     {
41.         data.Dispose();
42.     }
43. }
44.  
45. [BurstCompile]
46. public struct CreateGridJob : IJob
47. {
48.     public NativeArray<int> allLvlArrayNumNA;
49.     public int allArrayLength;
50.     public float3 newNodePos;
51.     public float lineLength;
52.     public float scaleGrid;
53.     public int randomLoops;
54.     public float extraDecrease;
55.     public float minDistNode;
56.     public float extraDecreaseStep;
57.     public bool foundNodePos;
58.     public float3 furtherstNewNodePos;
59.     public int maxRandomLoops;
60.     public float3 camPos;
61.     public NativeArray<float3> NodePositionsNA;
62.     public NativeArray<Quaternion> NodeRotationsNA;
63.     public NativeArray<float3> NodeScalesNA;
64.     public float3 camUp;
65.     public float3 fixedNormalScale;
66.     public NativeArray2D<int> linksContainerArrayNA;
67.     public NativeArray<int> linksContainerArrayLengthNA;
68.     public NativeArray2D<int> lineToNodesNA;
69.     public NativeArray<int> numberOfLinksNA;
70.     public NativeArray<float3> longCubesScaleNA;
71.     public NativeArray<float3> longCubesPosNA;
72.     public NativeArray<Quaternion> longCubesRotNA;
73.     public NativeArray2D<int> currentLinkedToTargetNA;
74.     public NativeArray2D<int> instLongCubesNumNA;
75.     public float linkWidth;
76.     public int maxLinksPerLinkedNode;
77.     public int branchingLevels;
78.     public int linksPerNode;
79.     public float3 randVector3;
80.     //static Rand rand;
81.     public Rand rand;
82.     public NativeArray<int> secondChanceNA;
83.     public NativeArray2D<float> DistanceBetweenNodesArraySqNA;
84.  
85.     public void Execute()
86.     {
87.         CreateGrid();
88.     }
89.  
90.     void CreateLevel(int parentNodeNum, int childrenNum)
91.     {
92.         if (allLvlArrayNumNA[0] < allArrayLength)
93.         {
94.             uint seed = (uint)(System.DateTime.Now.Ticks & 0x00000000FFFFFFFF);
95.             rand = new Rand(seed);
96.             randVector3 = rand.NextFloat3Direction();
97.             float lineLengthScaled = lineLength * scaleGrid;
98.             newNodePos = NodePositionsNA[parentNodeNum] + randVector3 * lineLengthScaled;
99.             randomLoops = 0;
100.             extraDecrease = 0;
101.             float minDistScaled = minDistNode * scaleGrid;
102.             float extraDecreaseStepScaled = extraDecreaseStep * scaleGrid;
103.             float maxSqrMagnitude = 0f;
104.             float minUnderThresholdSq = 100f;
105.             int maxi = 0;
106.             while (foundNodePos == false)
107.             {
108.                 foundNodePos = true;
109.                 float minDist = minDistScaled - extraDecrease;
110.                 float minDistSq = minDist * minDist;
111.                 for (int i = 0; i < allLvlArrayNumNA[0]; i++)
112.                 {
113.                     //Discards the new node position if it is too close to other existing nodes.
114.                     float3 newNodeToAllNodes = NodePositionsNA[i] - newNodePos;
115.                     float curSqrMagnitude = newNodeToAllNodes.x* newNodeToAllNodes.x+ newNodeToAllNodes.y * newNodeToAllNodes.y+ newNodeToAllNodes.z * newNodeToAllNodes.z;
116.                     float underThresholdSq = minDistSq - curSqrMagnitude;
117.                     if (curSqrMagnitude < minDistSq)
118.                     {
119.                         if (underThresholdSq < minUnderThresholdSq && i > maxi)
120.                         //if (underThresholdSq < minUnderThresholdSq)
121.                         {
122.                             minUnderThresholdSq = underThresholdSq;
123.                             maxSqrMagnitude = curSqrMagnitude;
124.                             furtherstNewNodePos = newNodePos;
125.                             maxi = i;
126.                         }
127.                         foundNodePos = false;
128.                         uint seed1 = (uint)(System.DateTime.Now.Ticks & 0x00000000FFFFFFFF);
129.                         rand = new Rand(seed1);
130.                         randVector3 = rand.NextFloat3Direction();
131.                         newNodePos = NodePositionsNA[parentNodeNum] + randVector3 * lineLengthScaled;
132.                         break;
133.                     }
134.                 }
135.                 randomLoops++;
136.                 if (randomLoops > maxRandomLoops && foundNodePos==false)
137.                 {
138.                     extraDecrease += extraDecreaseStepScaled;
139.                     randomLoops = 0;
140.                     minDist = minDistScaled - extraDecrease;
141.                     minDistSq = minDist * minDist;
142.                     if (maxSqrMagnitude > minDistSq)
143.                     {
144.                         foundNodePos = true;
145.                         for (int i = 0; i < allLvlArrayNumNA[0]; i++)
146.                         {
147.                             //Checks the node that was closest to the threshold so far against the new threshold
148.                             newNodePos = furtherstNewNodePos;
149.                             float3 newNodeToAllNodes = NodePositionsNA[i] - newNodePos;
150.                             float curSqrMagnitude = newNodeToAllNodes.x * newNodeToAllNodes.x + newNodeToAllNodes.y * newNodeToAllNodes.y + newNodeToAllNodes.z * newNodeToAllNodes.z;
151.                             float underThresholdSq = minDistSq - curSqrMagnitude;
152.                             if (curSqrMagnitude < minDistSq)
153.                             {
154.                                 if (underThresholdSq < minUnderThresholdSq && i > maxi)
155.                                 {
156.                                     minUnderThresholdSq = underThresholdSq;
157.                                     maxSqrMagnitude = curSqrMagnitude;
158.                                     maxi = i;
159.                                 }
160.                                 foundNodePos = false;
161.                                 uint seed2 = (uint)(System.DateTime.Now.Ticks & 0x00000000FFFFFFFF);
162.                                 rand = new Rand(seed2);
163.                                 randVector3 = rand.NextFloat3Direction();
164.                                 newNodePos = NodePositionsNA[parentNodeNum] + randVector3 * lineLengthScaled;
165.                                 break;
166.                             }
167.                         }
168.                     }
169.                     if (foundNodePos)
170.                     {
171.                         secondChanceNA[0]++;
172.                     }
173.                 }
174.             }
175.             NodePositionsNA[allLvlArrayNumNA[0]] = newNodePos;
176.             float3 nodeToCam = camPos - NodePositionsNA[allLvlArrayNumNA[0]];
177.             NodeRotationsNA[allLvlArrayNumNA[0]] = quaternion.LookRotationSafe(nodeToCam, camUp);
178.             NodeScalesNA[allLvlArrayNumNA[0]] = fixedNormalScale;
179.             float3 nodeToNode = NodePositionsNA[parentNodeNum] - NodePositionsNA[allLvlArrayNumNA[0]];
180.             float distBetweenNodes = math.sqrt(nodeToNode.x* nodeToNode.x+nodeToNode.y* nodeToNode.y+nodeToNode.z* nodeToNode.z);
181.             float3 nodeMidPoint = NodePositionsNA[allLvlArrayNumNA[0]] + nodeToNode * 0.5f;
182.             longCubesScaleNA[numberOfLinksNA[0]] = new float3(linkWidth, linkWidth, distBetweenNodes);
183.             longCubesPosNA[numberOfLinksNA[0]] = nodeMidPoint;
184.             //How is this lookrotation implemented in the new math library?
185.             longCubesRotNA[numberOfLinksNA[0]] = quaternion.LookRotationSafe(nodeToNode, Vector3.up);
186.             linksContainerArrayNA[parentNodeNum, childrenNum + 1] = allLvlArrayNumNA[0];
187.             linksContainerArrayLengthNA[parentNodeNum]++;
188.             currentLinkedToTargetNA[parentNodeNum, allLvlArrayNumNA[0]] = 1;
189.             instLongCubesNumNA[parentNodeNum, childrenNum + 1] = numberOfLinksNA[0];
190.             lineToNodesNA[numberOfLinksNA[0], 0] = parentNodeNum;
191.             lineToNodesNA[numberOfLinksNA[0], 1] = allLvlArrayNumNA[0];
192.             linksContainerArrayNA[allLvlArrayNumNA[0], 0] = parentNodeNum;
193.             linksContainerArrayLengthNA[allLvlArrayNumNA[0]]++;
194.             currentLinkedToTargetNA[allLvlArrayNumNA[0], parentNodeNum] = 1;
195.             instLongCubesNumNA[allLvlArrayNumNA[0], 0] = numberOfLinksNA[0];
196.             allLvlArrayNumNA[0]++;
197.             foundNodePos = false;
198.             numberOfLinksNA[0]++;
199.         }
200.     }
201.  
202.     void CreateCenterNode()
203.     {
204.         NodePositionsNA[0] = new float3(0f,0f,0f);
205.         float3 nodeToCam = camPos - NodePositionsNA[0];
206.         //can we use the math analogue to Quaternion.LookRotation?
207.         NodeRotationsNA[allLvlArrayNumNA[0]] = quaternion.LookRotationSafe(nodeToCam, camUp);
208.         NodeScalesNA[allLvlArrayNumNA[0]] = fixedNormalScale;
209.         linksContainerArrayNA[0, 0] = 0;
210.         linksContainerArrayLengthNA[allLvlArrayNumNA[0]]=1;
211.         currentLinkedToTargetNA[0, 0] = 1;
212.         longCubesScaleNA[0] = new float3(0f, 0f, 0f);
213.         longCubesPosNA[0] = new float3(0f, 0f, 0f);
214.         longCubesRotNA[0] = Quaternion.identity;
215.         instLongCubesNumNA[0, 0] = 0;
216.         lineToNodesNA[0, 0] = 0;
217.         lineToNodesNA[0, 1] = 0;
218.         numberOfLinksNA[0]++;
219.         allLvlArrayNumNA[0]++;
220.     }
221.  
222.     void FillDistanceArray()
223.     {
224.         for (int i = 0; i < allLvlArrayNumNA[0]; i++)
225.         {
226.             for (int j = 0; j < allLvlArrayNumNA[0]; j++)
227.             {
228.                 float3 NodeItoJ = NodePositionsNA[j] - NodePositionsNA[i];
229.                 DistanceBetweenNodesArraySqNA[i, j] = NodeItoJ.x*NodeItoJ.x+ NodeItoJ.y * NodeItoJ.y+ NodeItoJ.z * NodeItoJ.z;
230.             }
231.         }
232.     }
233.  
234.     void CreateGrid()
235.     {
236.         CreateCenterNode();
237.         //We don't use fully nested for loops since this way we are building the tree gradually, which makes it more evenly spread
238.         //Level 1 - Node # = linksPerNode
239.         for (int i = 0; i < linksPerNode; i++)
240.         {
241.             CreateLevel(0, i);
242.         }
243.         //Level 2 - Node # = linksPerNode^2
244.         if (branchingLevels >= 2 && allLvlArrayNumNA[0] < allArrayLength)
245.         {
246.             for (int i = 0; i < linksPerNode; i++)
247.             {
248.                 for (int j = 0; j < linksPerNode; j++)
249.                 {
250.                     CreateLevel(linksContainerArrayNA[0, i + 1], j);
251.                 }
252.             }
253.         }
254.         //Level 3 - Node # = linksPerNode^3
255.         if (branchingLevels >= 3 && allLvlArrayNumNA[0] < allArrayLength)
256.         {
257.             for (int i = 0; i < linksPerNode; i++)
258.             {
259.                 for (int j = 0; j < linksPerNode; j++)
260.                 {
261.                     for (int k = 0; k < linksPerNode; k++)
262.                     {
263.                         CreateLevel(linksContainerArrayNA[linksContainerArrayNA[0, i + 1], j + 1], k);
264.                     }
265.                 }
266.             }
267.         }
268.  
269.         //Level 4 - Node # = linksPerNode^4
270.         if (branchingLevels >= 4 && allLvlArrayNumNA[0] < allArrayLength)
271.         {
272.             for (int i = 0; i < linksPerNode; i++)
273.             {
274.                 for (int j = 0; j < linksPerNode; j++)
275.                 {
276.                     for (int k = 0; k < linksPerNode; k++)
277.                     {
278.                         for (int l = 0; l < linksPerNode; l++)
279.                         {
280.                             CreateLevel(linksContainerArrayNA[linksContainerArrayNA[linksContainerArrayNA[0, i + 1], j + 1], k + 1], l);
281.                         }
282.                     }
283.                 }
284.             }
285.         }
286.         //Level 5 - Node # = linksPerNode^5
287.         if (branchingLevels >= 5 && allLvlArrayNumNA[0] < allArrayLength)
288.         {
289.             for (int i = 0; i < linksPerNode; i++)
290.             {
291.                 for (int j = 0; j < linksPerNode; j++)
292.                 {
293.                     for (int k = 0; k < linksPerNode; k++)
294.                     {
295.                         for (int l = 0; l < linksPerNode; l++)
296.                         {
297.                             for (int m = 0; m < linksPerNode; m++)
298.                             {
299.                                 CreateLevel(linksContainerArrayNA[linksContainerArrayNA[linksContainerArrayNA[linksContainerArrayNA[0, i + 1], j + 1], k + 1], l + 1], m);
300.                             }
301.                         }
302.                     }
303.                 }
304.             }
305.         }
306.  
307.         //Level 6 - Node # = linksPerNode^6
308.         if (branchingLevels >= 6 && allLvlArrayNumNA[0] < allArrayLength)
309.         {
310.             for (int i = 0; i < linksPerNode; i++)
311.             {
312.                 for (int j = 0; j < linksPerNode; j++)
313.                 {
314.                     for (int k = 0; k < linksPerNode; k++)
315.                     {
316.                         for (int l = 0; l < linksPerNode; l++)
317.                         {
318.                             for (int m = 0; m < linksPerNode; m++)
319.                             {
320.                                 for (int n = 0; n < linksPerNode; n++)
321.                                 {
322.                                     CreateLevel(linksContainerArrayNA[linksContainerArrayNA[linksContainerArrayNA[linksContainerArrayNA[linksContainerArrayNA[0, i + 1], j + 1], k + 1], l + 1], m + 1], n);
323.                                 }
324.                             }
325.                         }
326.                     }
327.                 }
328.             }
329.         }
330.  
331.         //Level 7 - Node # = linksPerNode^7
332.         if (branchingLevels >= 7 && allLvlArrayNumNA[0] < allArrayLength)
333.         {
334.             for (int i = 0; i < linksPerNode; i++)
335.             {
336.                 for (int j = 0; j < linksPerNode; j++)
337.                 {
338.                     for (int k = 0; k < linksPerNode; k++)
339.                     {
340.                         for (int l = 0; l < linksPerNode; l++)
341.                         {
342.                             for (int m = 0; m < linksPerNode; m++)
343.                             {
344.                                 for (int n = 0; n < linksPerNode; n++)
345.                                 {
346.                                     for (int o = 0; o < linksPerNode; o++)
347.                                     {
348.                                         CreateLevel(linksContainerArrayNA[linksContainerArrayNA[linksContainerArrayNA[linksContainerArrayNA[linksContainerArrayNA[linksContainerArrayNA[0, i + 1], j + 1], k + 1], l + 1], m + 1], n + 1], o);
349.                                     }
350.                                 }
351.                             }
352.                         }
353.                     }
354.                 }
355.             }
356.         }
357.  
358.         //Level 8 - Node # = linksPerNode^8
359.         if (branchingLevels >= 8 && allLvlArrayNumNA[0] < allArrayLength)
360.         {
361.             for (int i = 0; i < linksPerNode; i++)
362.             {
363.                 for (int j = 0; j < linksPerNode; j++)
364.                 {
365.                     for (int k = 0; k < linksPerNode; k++)
366.                     {
367.                         for (int l = 0; l < linksPerNode; l++)
368.                         {
369.                             for (int m = 0; m < linksPerNode; m++)
370.                             {
371.                                 for (int n = 0; n < linksPerNode; n++)
372.                                 {
373.                                     for (int o = 0; o < linksPerNode; o++)
374.                                     {
375.                                         for (int p = 0; p < linksPerNode; p++)
376.                                         {
377.                                             CreateLevel(linksContainerArrayNA[linksContainerArrayNA[linksContainerArrayNA[linksContainerArrayNA[linksContainerArrayNA[linksContainerArrayNA[linksContainerArrayNA[0, i + 1], j + 1], k + 1], l + 1], m + 1], n + 1], o + 1], p);
378.                                         }
379.                                     }
380.                                 }
381.                             }
382.                         }
383.                     }
384.                 }
385.             }
386.         }
387.  
388.         //Level 9 - Node # = linksPerNode^9
389.         if (branchingLevels >= 9 && allLvlArrayNumNA[0] < allArrayLength)
390.         {
391.             for (int i = 0; i < linksPerNode; i++)
392.             {
393.                 for (int j = 0; j < linksPerNode; j++)
394.                 {
395.                     for (int k = 0; k < linksPerNode; k++)
396.                     {
397.                         for (int l = 0; l < linksPerNode; l++)
398.                         {
399.                             for (int m = 0; m < linksPerNode; m++)
400.                             {
401.                                 for (int n = 0; n < linksPerNode; n++)
402.                                 {
403.                                     for (int o = 0; o < linksPerNode; o++)
404.                                     {
405.                                         for (int p = 0; p < linksPerNode; p++)
406.                                         {
407.                                             for (int q = 0; q < linksPerNode; q++)
408.                                             {
409.                                                 CreateLevel(linksContainerArrayNA[linksContainerArrayNA[linksContainerArrayNA[linksContainerArrayNA[linksContainerArrayNA[linksContainerArrayNA[linksContainerArrayNA[linksContainerArrayNA[0, i + 1], j + 1], k + 1], l + 1], m + 1], n + 1], o + 1], p + 1], q);
410.                                             }
411.                                         }
412.                                     }
413.                                 }
414.                             }
415.                         }
416.                     }
417.                 }
418.             }
419.         }
420.         FillDistanceArray();
421.     }
422. }
423.  

And here is how the function that calls it looks like:

Code (CSharp):

1.     void CallCreateGridJob()
2.     {
3.         var createGridJob = new CreateGridJob()
4.         {
5.             allArrayLength = allArrayLength,
6.             newNodePos = newNodePos,
7.             lineLength = lineLength,
8.             scaleGrid = scaleGrid,
9.             randomLoops = randomLoops,
10.             extraDecrease = extraDecrease,
11.             minDistNode = minDistNode,
12.             extraDecreaseStep = extraDecreaseStep,
13.             foundNodePos = foundNodePos,
14.             furtherstNewNodePos = furtherstNewNodePos,
15.             maxRandomLoops = maxRandomLoops,
16.             camPos = camPos,
17.             NodePositionsNA = new NativeArray<float3>(allArrayLength, Allocator.TempJob),
18.             NodeRotationsNA = new NativeArray<Quaternion>(NodeRotations, Allocator.TempJob),
19.             NodeScalesNA = new NativeArray<float3>(allArrayLength, Allocator.TempJob),
20.             camUp = camUp,
21.             fixedNormalScale = fixedNormalScale,
22.             linksContainerArrayNA = new NativeArray2D<int>(allArrayLength, maxLinksPerLinkedNode, Allocator.TempJob),
23.             linksContainerArrayLengthNA = new NativeArray<int>(linksContainerArrayLength, Allocator.TempJob),
24.             lineToNodesNA = new NativeArray2D<int>(maxLinks, 2, Allocator.TempJob),
25.             numberOfLinksNA = new NativeArray<int>(1, Allocator.TempJob),
26.             longCubesScaleNA = new NativeArray<float3>(maxLinks, Allocator.TempJob),
27.             longCubesPosNA = new NativeArray<float3>(maxLinks, Allocator.TempJob),
28.             longCubesRotNA = new NativeArray<Quaternion>(longCubesRot, Allocator.TempJob),
29.             currentLinkedToTargetNA = new NativeArray2D<int>(allArrayLength, allArrayLength, Allocator.TempJob),
30.             instLongCubesNumNA = new NativeArray2D<int>(allArrayLength, maxLinksPerLinkedNode, Allocator.TempJob),
31.             DistanceBetweenNodesArraySqNA = new NativeArray2D<float>(allArrayLength, allArrayLength, Allocator.TempJob),
32.             allLvlArrayNumNA = new NativeArray<int>(1, Allocator.TempJob),
33.             linkWidth = linkWidth,
34.             maxLinksPerLinkedNode = maxLinksPerLinkedNode,
35.             branchingLevels = branchingLevels,
36.             linksPerNode = linksPerNode,
37.             secondChanceNA = new NativeArray<int>(1, Allocator.TempJob),
38.         };
39.  
40.         createGridJob.allLvlArrayNumNA[0] = allLvlArrayNum;
41.  
42.         for (int i = 0; i < allArrayLength; i++)
43.         {
44.             createGridJob.NodePositionsNA[i] = NodePositions[i];
45.             createGridJob.NodeScalesNA[i] = NodeScales[i];
46.             for (int j = 0; j < maxLinksPerLinkedNode; j++)
47.             {
48.                 createGridJob.linksContainerArrayNA[i, j] = linksContainerArray[i, j];
49.                 createGridJob.instLongCubesNumNA[i, j] = instLongCubesNum[i, j];
50.             }
51.             for (int k = 0; k < allArrayLength; k++)
52.             {
53.                 createGridJob.currentLinkedToTargetNA[i, k] = currentLinkedToTarget[i, k] == false ? 0 : 1;
54.                 createGridJob.DistanceBetweenNodesArraySqNA[i, k] = DistanceBetweenNodesArraySq[i, k];
55.             }
56.         }
57.  
58.         for (int i = 0; i < maxLinks; i++)
59.         {
60.             createGridJob.lineToNodesNA[i, 0] = lineToNodes[i, 0];
61.             createGridJob.lineToNodesNA[i, 1] = lineToNodes[i, 1];
62.             createGridJob.longCubesScaleNA[i] = longCubesScale[i];
63.             createGridJob.longCubesPosNA[i] = longCubesPos[i];
64.             createGridJob.longCubesRotNA[i] = longCubesRot[i];
65.         }
66.  
67.         JobHandle createGridJobHandle = createGridJob.Schedule();
68.  
69.         createGridJobHandle.Complete();
70.  
71.         NodeRotations = createGridJob.NodeRotationsNA.ToArray();
72.         linksContainerArrayLength = createGridJob.linksContainerArrayLengthNA.ToArray();
73.         longCubesRot = createGridJob.longCubesRotNA.ToArray();
74.         for (int i = 0; i < allArrayLength; i++)
75.         {
76.             NodePositions[i] = createGridJob.NodePositionsNA[i];
77.             NodeScales[i] = createGridJob.NodeScalesNA[i];
78.             for (int j = 0; j < maxLinksPerLinkedNode; j++)
79.             {
80.                 linksContainerArray[i, j] = createGridJob.linksContainerArrayNA[i, j];
81.                 instLongCubesNum[i, j] = createGridJob.instLongCubesNumNA[i, j];
82.             }
83.             for (int k = 0; k < allArrayLength; k++)
84.             {
85.                 currentLinkedToTarget[i, k] = createGridJob.currentLinkedToTargetNA[i, k] == 0 ? false : true;
86.                 DistanceBetweenNodesArraySq[i, k] = createGridJob.DistanceBetweenNodesArraySqNA[i, k];
87.             }
88.         }
89.  
90.         for (int i = 0; i < maxLinks; i++)
91.         {
92.             lineToNodes[i, 0] = createGridJob.lineToNodesNA[i, 0];
93.             lineToNodes[i, 1] = createGridJob.lineToNodesNA[i, 1];
94.             longCubesScale[i] = createGridJob.longCubesScaleNA[i];
95.             longCubesPos[i] = createGridJob.longCubesPosNA[i];
96.             longCubesRot[i] = createGridJob.longCubesRotNA[i];
97.         }
98.  
99.         allLvlArrayNum = createGridJob.allLvlArrayNumNA[0];
100.         numberOfLinks = createGridJob.numberOfLinksNA[0];
101.         secondChance = createGridJob.secondChanceNA[0];
102.  
103.         createGridJob.NodePositionsNA.Dispose();
104.         createGridJob.NodeRotationsNA.Dispose();
105.         createGridJob.NodeScalesNA.Dispose();
106.         createGridJob.linksContainerArrayNA.Dispose();
107.         createGridJob.linksContainerArrayLengthNA.Dispose();
108.         createGridJob.instLongCubesNumNA.Dispose();
109.         createGridJob.currentLinkedToTargetNA.Dispose();
110.         createGridJob.DistanceBetweenNodesArraySqNA.Dispose();
111.         createGridJob.lineToNodesNA.Dispose();
112.         createGridJob.longCubesPosNA.Dispose();
113.         createGridJob.longCubesScaleNA.Dispose();
114.         createGridJob.longCubesRotNA.Dispose();
115.         createGridJob.allLvlArrayNumNA.Dispose();
116.         createGridJob.numberOfLinksNA.Dispose();
117.         createGridJob.secondChanceNA.Dispose();
118.     }
119.  

As I said, I think what I will try next is IJobParallelFor for all children per level.
Regardless, even if I did not manage to improve the code's performance, I would have learned something new