Search Unity

  1. Megacity Metro Demo now available. Download now.
    Dismiss Notice
  2. Unity support for visionOS is now available. Learn more in our blog post.
    Dismiss Notice

Better way for calculate too much iterations

Discussion in 'Scripting' started by Onsterion, Jun 10, 2016.

  1. Onsterion

    Onsterion

    Joined:
    Feb 21, 2014
    Posts:
    215
    Hi all,

    Unity Version: 5.4.0b18-HTP

    I have to create a molecule with 8550 atoms so 8550 spheres and then create lines for connect this atoms.

    Steps:

    1- I instantiated 8550 atoms (gameobjects - prefabs) and 9000 lines (gameobjects - prefabs) for object pooling method.

    2- Parse a text for get the positions of the 8550 atoms in a list. Takes 2 and 3 seconds

    3- Re position of the 8550 atoms with the 8550 records in the list:

    Code (CSharp):
    1.  
    2. for (int i = 0; i < atomPositionList.Count; i++)
    3.         {
    4.             atomContainer.transform.GetChild(i).transform.position = atomPositionList[i];
    5.             atomContainer.transform.GetChild(i).name = atomList[i].atomName;
    6.  
    7.             SetLines(i, atomList[i].elementSymbol); //BOTTLENECK HERE
    8.         }
    9.  
    If i don't use SetLines method Takes 1 and 2 seconds

    4- The problem (bottleneck) started when i have to calculate the position of the lines (i don't have this data, so i have to calculate this).

    Code (CSharp):
    1.  
    2. private void SetLines(int currentAtom, string element)
    3.     {
    4.         Vector3 currentPosition = atomPositionList[currentAtom];
    5.  
    6.         //SET RADIUS CONNECTION
    7.         if (element == "N")
    8.         {
    9.             radiusConnection = radiusDefault;
    10.         }
    11.         else if (element == "S")
    12.         {
    13.             radiusConnection = radiusMedium;
    14.         }
    15.         else
    16.         {
    17.             radiusConnection = radiusDefault;
    18.         }
    19.  
    20.  
    21.         var atoms = atomPositionList.Where(atom => Vector3.Distance(atom, currentPosition) <= radiusConnection && currentPosition != atom && !CheckIfLineExist(currentPosition, atom));
    22.  
    23.         foreach (var atom in atoms)
    24.         {      
    25.            SetLine(currentPosition, atom);
    26.         }
    27.     }
    28.  
    The problem here is for every atom (8550) i have to loop another 8550 times for every one for calculate the closest atom for create the line. Takes 10 a 12 seconds. Too much iterations o_O

    P.D: Before someone says don't use 'string' for compare the element, use a enum (yes i know it, but this is not the problem).

    5- Then group and split the atoms and lines for create combined meshes for boost the performance. Takes 150 and 30 Milliseconds




    Any advice for a better way to calculate the lines?
    Can i pass the complete calculation of all lines in the GPU for reduce calculation time?



    Sorry for my english is not my native lenguaje.



    Greetings.-
     
    Last edited: Jun 10, 2016
  2. LeftyRighty

    LeftyRighty

    Joined:
    Nov 2, 2012
    Posts:
    5,148
  3. Onsterion

    Onsterion

    Joined:
    Feb 21, 2014
    Posts:
    215
    LeftyRighty likes this.
  4. Mycroft

    Mycroft

    Joined:
    Aug 29, 2012
    Posts:
    160
    I have a similar problem in AI decision making (finding the closest precomputed location node) and I have a few 'hacks' that allow for less searching.

    1. instead of Vector3.Distance use Vector3.sqrMagnitude; There is no need to get the exact distance (which requires a sqr root calculation), so just find the lowest sqrMagnitude.
    2. Have a 'close enough' threshold. Stop searching if you find another atom that is so close that there is no need to look further.

    <Edit>
    I just realized that #2 won't help you much; atom can have multiple bonds, not just one.
     
    Last edited: Jun 10, 2016
  5. Mycroft

    Mycroft

    Joined:
    Aug 29, 2012
    Posts:
    160
    Also

    You're checking every Atom in a list against every other atom in the list.
    Code (CSharp):
    1. for( int i = 0 ; i < list.count ; i++)
    2. {
    3.     for( int u = 0 ; u < list.count ; u++ )
    4.     {
    5.         if( listt[u] != list[i] )
    6.             compare distances
    7.     }
    8. }
    Is this what you're doing in effect?

    Is there any reason that comparing list[10] vs list[100] will result in any differences than list[100] vs list[10]?

    You could do this instead

    Code (CSharp):
    1. for( int i = 0 ; i < list.count - 1 ; i++)
    2. {
    3.     for( int u = i + 1 ; u < list.count ; u++ )
    4.     {
    5.         compare distances
    6.     }
    7. }
    Only compare an Atom against Atoms further in the list.

    You also wouldn't need to check to see if a line exists, because that can't happen in this setup.
     
    Last edited: Jun 10, 2016
  6. Onsterion

    Onsterion

    Joined:
    Feb 21, 2014
    Posts:
    215
    Hi,

    If i use list.count - 1 i lost the comparation with the last gameobject previously instanciated.

    But with the int u = i +1 it's a "Gauss and the sum of the first n" with this approach this calculation are reduced to 4 or 6 seconds of 10 or 12. So very good!

    Thanks.



    Another suggestion?
     
  7. Mycroft

    Mycroft

    Joined:
    Aug 29, 2012
    Posts:
    160
    Did you try the Vector3.sqrMagnitude instead of Distance?
     
  8. Onsterion

    Onsterion

    Joined:
    Feb 21, 2014
    Posts:
    215
    Yep.

    Code (CSharp):
    1.  
    2. var targetDif = target - currentPosition;
    3. var distance = Vector3.SqrMagnitude(targetDif);
    4.  
    But with this i gain 100 to 125 ms. This not generate a high impact in the process.
     
  9. Mycroft

    Mycroft

    Joined:
    Aug 29, 2012
    Posts:
    160
    I'd say break out the profiler again and let us know what your longest/most common function calls are.
     
  10. jimroberts

    jimroberts

    Joined:
    Sep 4, 2014
    Posts:
    560
    This is the problem.

    You're essentially iterating over 73,093,950 elements and checking their distances. Distance checks are, as you probably have realized by now, quite slow. Considering you know the position of each atom. There is a very simple optimization you can implement to speed things up. Create a 3D grid to contain all of the atoms and add them to a list in their respective grid cubes. Then you can iterate over the atoms in the current grid cube. If no other atoms are found, keep expanding the search to surrounding grid cubes until you find at least one atom.
     
  11. larku

    larku

    Joined:
    Mar 14, 2013
    Posts:
    1,422