Best way to go about many objects checking array for data?

Performance Tuning
#1

I am currently working on a two-dimensional space simulation game. Every object will have a gravitational force that pulls on everything else. The issue I have run into is finding an efficient way for every object to find the position of every other object so that its gravity may act on those that are within its gravitational pull. My first thought was to put all objects into an ArrayList and looping through all objects in the ArrayList for every object. Obviously this would be extremely slow, so I didn’t even try to do this. What would you guys suggest as an optimal way to do this?

In layman’s terms:

  • Many objects with x and y position
  • Each object needs to find x and y position of all other objects in order to check if their x and y coordinates are within a certain parameter
#2

for 2D a uniform-grid-partition can be handy. random google result : http://gameprogrammingpatterns.com/spatial-partition.html

the idea is very simple :

  • divide space into cells.
  • store objects inside cells.
    – to find the cell in which to store you can test a point, like the object center (easy)
    – or you can test which cells overlap with the object. (bit more complex)
  • once stored - “select” or “query” objects from cell-partition with a geometric shape, in your case a circle.

this works as long as you do not group up too many objects in one cell. worst case is - all objects are in the same cell, what renders the cell-partitioning useless.

now, gravity itself is not going to well with that idea. eventually everything collapses into a singular point. this works better with “negative gravity”, things that seperate, like water.

if you still want to do a “all-pairs” simulation (test every object with every other object) you could use a quad-tree and store the mass and center of mass for each quadrant/child and use this information to approximate the simulation. this is just a coarse description. read more here : http://en.wikipedia.org/wiki/Barnes–Hut_simulation

this is not as easy as cell-partition anymore tho’.

#3

As your rule is “every object influences every other object” then there is only one way to do what you want which is to loop through the entire array of objects (O(n2). Yes, it’s slow, but that’s physics if you want to do it right.

Cas :slight_smile:

#4

Like Cas hinted at, you’re contradicting yourself a bit here: should every object impact every other object? Or should they only impact objects within a certain range?

If every object should impact every other object, then by definition you’re pretty much stuck with looping through every object. Even that is an oversimplification. Recommended reading: http://en.wikipedia.org/wiki/N-body_problem

However, if each object should only impact neighbors within a certain range, then you could use a quadtree: http://en.wikipedia.org/wiki/Quadtree (or some similar data structure that partitions your space)

You could also just use your 2D array as the partition: for each object, only consider other objects within a certain range of cells?

#5

that’s what i had on mind.

#6

If you NEED all object, no matter what distance to each other, to have a gravimetric pull to each other,
then considder lumping object, wich are further way into a “area gravity” number.

For example, have a grid, add the mass of all objects within it to that grid-part.

If objects are too far (number of gridpoints) away, only considder the mass of the combines grid to calculate the pull.

Newton considdered the earth (and the apple) also just like a single mass point in his calculations.
Not each atom.

if you happen to create a nice simulation of a galaxy, post some pictures. :wink:

#7

If your simulation doesn’t need to be very exact and you have lots of objects, you might be able to get away with grid partitioning and calculating the gravitational forces acting on each cell (excluding the most adjacent cells); so when you calculate the pull for each object, you apply the cached pull and only check the most immediate cells. You can also split the gravity calculations over 2 frames to shave off some extra cycles.

I did this in a pet/play project and it worked quite well.

edit: Damocles beat me to it.

#8

Come on, own up … the reason you didn’t do it was cos it would be boring!

(Sensible voice says you could get the thing up and running fine for 100 objects in half an hour and tune it later if you need to!)

#9

First off, how many objects would be typical?
Less than a 1000? Probably not a problem to take the naive route.
Try/test before lest you needlessly optimize.

#10

Space scales are so large that most gravitational interactions do not take place in real time. A good simulation of this galaxy is all the stars in their current position, not moving. Printed astronomical maps are only updated every few years (50 years if I recall correctly). Even if you speed up time so much that the stars move in a measurable way, their motions are not really influenced by local gravity as the gravitational pull of nearby stars largely cancels itself out. You could just have the stars moving in random directions and be pretty accurate.

At a smaller scale, such as planetary system, a good approximation is that the stars have gravitational influence and everything else doesn’t. Even Jupiter only has a minuscule effect on the orbits of other planets - if it had a larger effect then the other orbit would be unstable. The same applies for planets and their moons, only the planet’s gravity needs to be taken into account.

At an event smaller scale (spaceships) you can just ignore gravity altogether.

#11

That might not make for the interesting gravity-based game/simulation the OP is looking for, of course :wink:

Cas :slight_smile:

#12

Hey everyone, thanks for all the help. In the end I decided to just iterate through every objects in the game, for every object in the game, so that the gravitational pulls are accurate. It will be slow when I increase the amount of objects, but accuracy comes at a price. I’m sure I’ll optimize later anyway. Currently making pretty good progress, and I’m working on the gravity itself right now. (Lots of trigonometry, fun!). I’ll eventually have a screen-cap for everyone to preview. Soon. :slight_smile:

#13

FYI: you don’t need trig for gravity.

#14

But the Force vectors need to be used in some way…

#15

Yup. Still no trig. You take the vector from one mass to the other, normalize it, and you have your directional vector, which you can multiply with F/m (from: F=m*a) to get the (directional) acceleration.