- Home /
Speeding up nested for loop of structs and calculations
Hello, I have a project where I’m essentially comparing a set of points against itself to find the best pair of points. Each point has a “score” by calculating the number of points in a different set - let’s call them ground points and the original set wall points for simplicity - it can linecast to, however things get a bit more complex than just taking the top two scoring wall points because for each ground point that both wall points can see, the score for that particular point is dependent on the angle difference between the two line casts or rather the amount of coverage that point could see. For example: Wall point A can cast to ground point 1,2, and 3, Wall point B can see 2, 3, and 4, and Wall point C can see 1, 2, 3, and 4. The scoring for A alone would be 3*180, B would be 3*180, and C would be 4*180. However, let’s say B is on the opposite wall of A and C is on the neighboring wall. Then the score of the AB pair would be 3*180+3*180, whereas AC would get a score of 4*180 + 3*90.
I’ve gotten that all to work, however it currently is very slow as I have a for loop going through each wall point, with another for loop for each wall point, looping through the ground points each one can cast to, checking if it’s seen by both or just one of the points, then if it’s both calculating the angle offset, and finally adding the score for that pair. It works, but it’s slow as heck (I believe it might be O(n^2) or O(n^3)? It’s been a bit since I’ve used big-O notation ha). I was wondering if anyone may have some insight into how to either A) optimize my calculations, or B) get them to work without freezing up the program for such a long time.
Here’s an example of the code I’m using:
for (int i = 0; i < wallSpots.Count; i++){
for (int j = i + 1; j < wallSpots.Count; j++){
int sharedPoints = 0
for each (point in wallSpots[i].seenPoints){
if (wallSpots[j].seenPoints.ContainsKey(point)){
sharedPoints++;
score += 180 + Vector3.Angle(wallSpots[i].seenPoints[point], wallSpots[j].seenPoints[point])
}
}
score += 180 * ( (wallSpots[i].seenPoints.Count - sharedPoints) + (wallSpots[j].seenPoints.Count - sharedPoints) )
}
}
A picture might help, btw. Also, do be careful as this isn't really a Unity question and folks can get testy about that.
How many elements are usually in wallSpots
? Your bottleneck might be the number of things being considered and them all needing that angle calculation. I don't know much about your situation, but that iteration setup feels suspect. What does the angle do here, considering that those seem to be points and not directions?
There's usually at least 50 spots in wallSpots. I'm basically trying to deter$$anonymous$$e the best placement of a pair of VR sensor cameras in a room, so angle is to track if the cameras can see the player at any given angle at that point, avoiding dead spots if your back is towards one camera or something