[quote="deadeye":3nuys7g6]Welp, I found a post where the creator of the original game explained how he made the asteroids...
[quote:3nuys7g6]Each asteroid affects each other, which is an O(n^2). This should be really slow for 1000 asteroids. Should be 1,000,000 gravity calculations. So... I use a coarse grid and calculate the mass contained in each grid segment. Gravity is calculated accurately for near by asteroids and the grid is used for distant asteroids.[/quote:3nuys7g6]
I don't know what that means
I am not sure myself, but I'll try to explain anyway
... First it initializes an array, a grid which has wide segments, like 1000 pixels or something like that. Then it calculates the amount of the mass in each segment... it kind of "rounds" the "gravitational map", or "scales down the resolution", if you get it that way. Then it starts to loop through each asteroid and calculating the forces affecting them. If there were... let's say about 10 asteroids on each segment, it calculates the forces of asteroids on its own segment and the neighbour segments, the forces of, say, 90 asteroids. Then it calculates the more distant ones, but it doesn't calculate asteroids, it calculates the combined gravitational forces of segments. If there is 1000 asteroids, like in your quote, and there is 10 asteroids per segment, then there would be totally 100 segments, so, there would be a 10 x 10 segment grid. So, the forces affecting a single asteroid would be forces of 89 asteroids and 100 - 9 (9 is the amount of neighbour segments whose forces are calculated accurately) = 91 segments, so there would be only 180 forces to calculate per asteroid, instead of 999. So, it's over five times faster.
And I think it can be optimised further. For example, the forces of the distant segments are the same for every asteroid in a segment, so these forces need to be calculated only once per ten asteroids, assuming we have that ten asteroids in a segment... so, averagely 89 + 9.1 = 98.1 force calculations per an asteroid. That's already TEN times faster
Of course, updating the mass grid takes some calculating, but it's not necessary to do every tick, since the positions of the asteroids don't change that fast.
I think this wouldn't be too hard to implement with Construct... But of course, cannot say surely yet. I would try to make this myself unless I had so little time :I