Java-Gaming.org Hi !
Featured games (91)
games approved by the League of Dukes
Games in Showcase (761)
Games in Android Showcase (229)
games submitted by our members
Games in WIP (845)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Best way to go about many objects checking array for data?  (Read 12451 times)
0 Members and 1 Guest are viewing this topic.
Offline shadowstryker
« 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
Offline 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'.
Offline princec

« JGO Spiffy Duke »


Medals: 1037
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 Smiley

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline 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!
Offline 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.
Offline 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. Wink
Offline 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
Offline 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!)
Offline 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.
Offline ags1

JGO Kernel


Medals: 367
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.

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline princec

« JGO Spiffy Duke »


Medals: 1037
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 Wink

Cas Smiley

Offline shadowstryker
« 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. Smiley
Offline Riven
Administrator

« JGO Overlord »


Medals: 1341
Projects: 4
Exp: 16 years


Hand over your head.


« 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!
Offline Damocles
« Reply #13 - Posted 2014-09-22 05:37:16 »

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

« JGO Overlord »


Medals: 1341
Projects: 4
Exp: 16 years


Hand over your head.


« 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  
 
 

 
EgonOlsen (347 views)
2018-06-10 19:43:48

EgonOlsen (337 views)
2018-06-10 19:43:44

EgonOlsen (290 views)
2018-06-10 19:43:20

DesertCoockie (514 views)
2018-05-13 18:23:11

nelsongames (779 views)
2018-04-24 18:15:36

nelsongames (762 views)
2018-04-24 18:14:32

ivj94 (1229 views)
2018-03-24 14:47:39

ivj94 (385 views)
2018-03-24 14:46:31

ivj94 (1054 views)
2018-03-24 14:43:53

Solater (410 views)
2018-03-17 05:04:08
Java Gaming Resources
by philfrei
2017-12-05 19:38:37

Java Gaming Resources
by philfrei
2017-12-05 19:37:39

Java Gaming Resources
by philfrei
2017-12-05 19:36:10

Java Gaming Resources
by philfrei
2017-12-05 19:33:10

List of Learning Resources
by elect
2017-03-13 14:05:44

List of Learning Resources
by elect
2017-03-13 14:04:45

SF/X Libraries
by philfrei
2017-03-02 08:45:19

SF/X Libraries
by philfrei
2017-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
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!