Better way for calculate too much iterations

Unity Engine
1

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:

for (int i = 0; i < atomPositionList.Count; i++)
        {
            atomContainer.transform.GetChild(i).transform.position = atomPositionList[i];
            atomContainer.transform.GetChild(i).name = atomList[i].atomName;

            SetLines(i, atomList[i].elementSymbol); //BOTTLENECK HERE
        }

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).

private void SetLines(int currentAtom, string element)
    {
        Vector3 currentPosition = atomPositionList[currentAtom];

        //SET RADIUS CONNECTION
        if (element == "N")
        {
            radiusConnection = radiusDefault;
        }
        else if (element == "S")
        {
            radiusConnection = radiusMedium;
        }
        else
        {
            radiusConnection = radiusDefault;
        }


        var atoms = atomPositionList.Where(atom => Vector3.Distance(atom, currentPosition) <= radiusConnection && currentPosition != atom && !CheckIfLineExist(currentPosition, atom));

        foreach (var atom in atoms)
        {       
           SetLine(currentPosition, atom);
        }
    }

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 :eyes:

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.-

2

did you check the profiler or are these just stopwatched?

3

I used System.Diagnostics.Stopwatch, Environment.TickCount and the profiler.

1 Like
4

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.

  • 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.

  • Have a ‘close enough’ threshold. Stop searching if you find another atom that is so close that there is no need to look further.

I just realized that #2 won't help you much; atom can have multiple bonds, not just one.
5

Also

You’re checking every Atom in a list against every other atom in the list.

for( int i = 0 ; i < list.count ; i++)
{
    for( int u = 0 ; u < list.count ; u++ )
    {
        if( listt[u] != list[i] )
            compare distances
    }
}

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

for( int i = 0 ; i < list.count - 1 ; i++)
{
    for( int u = i + 1 ; u < list.count ; u++ )
    {
        compare distances
    }
}

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.

6

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

Did you try the Vector3.sqrMagnitude instead of Distance?

8

Yep.

var targetDif = target - currentPosition;
var distance = Vector3.SqrMagnitude(targetDif);

But with this i gain 100 to 125 ms. This not generate a high impact in the process.

9

I’d say break out the profiler again and let us know what your longest/most common function calls are.

10

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

There’s lots of solutions for finding nearest neighbour, I’d find a more efficient algorithm Nearest neighbor search - Wikipedia

A quick search found this: c++ - In 2D, how do I efficiently find the nearest object to a point? - Game Development Stack Exchange