Java-Gaming.org Hi !
 Featured games (90) games approved by the League of Dukes Games in Showcase (753) Games in Android Showcase (228) games submitted by our members Games in WIP (842) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
Pages: [1]
 ignore  |  Print
 Best way to go about many objects checking array for data?  (Read 12007 times) 0 Members and 1 Guest are viewing this topic.
 « Posted 2014-09-17 02:13:16 »

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
basil_

« JGO Bitwise Duke »

Medals: 418
Exp: 13 years

 « Reply #1 - Posted 2014-09-17 11:37:14 »

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%E2%80%93Hut_simulation

this is not as easy as cell-partition anymore tho'.
princec

« JGO Spiffy Duke »

Medals: 1012
Projects: 3
Exp: 20 years

Eh? Who? What? ... Me?

 « Reply #2 - Posted 2014-09-17 11:53:55 »

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

KevinWorkman

« JGO Plugged Duke »

Medals: 283
Projects: 12
Exp: 12 years

HappyCoding.io - Coding Tutorials!

 « Reply #3 - Posted 2014-09-17 13:12:33 »

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?

HappyCoding.io - Coding Tutorials!
Happy Coding forum - Come say hello!
basil_

« JGO Bitwise Duke »

Medals: 418
Exp: 13 years

 « Reply #4 - Posted 2014-09-17 13:26:54 »

that's what i had on mind.
Damocles
 « Reply #5 - Posted 2014-09-17 13:39:12 »

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.
junkdog
 « Reply #6 - Posted 2014-09-17 13:47:05 »

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.

artemis-odb: bugfixing and performance optimized fork of artemis ECS
richierich
 « Reply #7 - Posted 2014-09-17 15:34:53 »

Obviously this would be extremely slow, so I didn't do this

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!)
BurntPizza

« JGO Bitwise Duke »

Medals: 485
Exp: 7 years

 « Reply #8 - Posted 2014-09-17 15:52:54 »

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

JGO Kernel

Medals: 363
Projects: 7

Make code not war!

 « Reply #9 - Posted 2014-09-18 10:30:50 »

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.

princec

« JGO Spiffy Duke »

Medals: 1012
Projects: 3
Exp: 20 years

Eh? Who? What? ... Me?

 « Reply #10 - Posted 2014-09-18 10:53:10 »

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

Cas

 « Reply #11 - Posted 2014-09-22 01:34:36 »

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

« JGO Overlord »

Medals: 1336
Projects: 4
Exp: 16 years

 « Reply #12 - Posted 2014-09-22 05:31:45 »

FYI: you don't need trig for gravity.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings!
Damocles
 « Reply #13 - Posted 2014-09-22 05:37:16 »

But the Force vectors need to be used in some way...
Riven

« JGO Overlord »

Medals: 1336
Projects: 4
Exp: 16 years

 « Reply #14 - Posted 2014-09-22 05:42:38 »

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.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings!
Pages: [1]
 ignore  |  Print

 ivj94 (583 views) 2018-03-24 14:47:39 ivj94 (48 views) 2018-03-24 14:46:31 ivj94 (374 views) 2018-03-24 14:43:53 Solater (61 views) 2018-03-17 05:04:08 nelsongames (109 views) 2018-03-05 17:56:34 Gornova (151 views) 2018-03-02 22:15:33 buddyBro (693 views) 2018-02-28 16:59:18 buddyBro (91 views) 2018-02-28 16:45:17 xxMrPHDxx (493 views) 2017-12-31 17:17:51 xxMrPHDxx (733 views) 2017-12-31 17:15:51
 SHC 10x NuclearPixels 10x Zemlaynin 10x KaiHH 10x ByerN 7x Spasi 6x Damocles 6x Guerra2442 6x VaTTeRGeR 5x ags1 4x orangepascal 4x philfrei 4x princec 3x ndnwarrior15 3x mesterh 3x Phased 2x
 Java Gaming Resourcesby philfrei2017-12-05 19:38:37Java Gaming Resourcesby philfrei2017-12-05 19:37:39Java Gaming Resourcesby philfrei2017-12-05 19:36:10Java Gaming Resourcesby philfrei2017-12-05 19:33:10List of Learning Resourcesby elect2017-03-13 14:05:44List of Learning Resourcesby elect2017-03-13 14:04:45SF/X Librariesby philfrei2017-03-02 08:45:19SF/X Librariesby philfrei2017-03-02 08:44:05
 java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org