Java-Gaming.org    
Featured games (91)
games approved by the League of Dukes
Games in Showcase (576)
games submitted by our members
Games in WIP (497)
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  
  Objects in List problem?  (Read 1147 times)
0 Members and 1 Guest are viewing this topic.
Offline kappa
« League of Dukes »

JGO Kernel


Medals: 70
Projects: 15


★★★★★


« Posted 2006-06-11 03:18:20 »

i have a List of Objects,

each Object contains a List of the neighbouring Objects,

distance(float) from Object to all neighbour Objects are calculated at startup,

i need a good way to store this so that i can  just do search for (object1, object2) and get a return (float) distance.
are there any built in structures i can use? or whats a good method to achieve this?

thanks
Offline Herko_ter_Horst

Senior Newbie




Java games rock!


« Reply #1 - Posted 2006-06-11 09:54:20 »

Should your game Objects really be responsible for having that knowledge? It's hard to say without knowing more specifics, but I would probably create some kind of "Board" or "World" class that holds a list of your game Objects and their "locations". It would be this class that is able to answer "distance" questions.
Offline cylab

JGO Knight


Medals: 34



« Reply #2 - Posted 2006-06-11 17:57:49 »

If you really want to precalculate this in the way you have described, you can use a HashMap for this. Use the neighbouring object as key and the distance as value. Make sure you implement the hashCode() and equals()-methods in your objects to allow for using them as keys in a HashMap.

But like Herko_ter_Horst pointet out, this may not be the best solution to your problem. Since it is very easy and cheap to calculate the distance between two points, just give your objects a location property, so your "object1.distance(object2)" method just calculates the distance on the fly by substracting the two locations.

The real problem is to find the two objects you need to calculate the exact distance for. In the first place you have to reduce the amount of objects to test, like grouping them in neighbouring clusters. If this is what you are after, Google for "space partitioning trees" like BSP trees, quadtrees and octrees.

Mathias - I Know What [you] Did Last Summer!
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline CommanderKeith
« Reply #3 - Posted 2006-06-12 04:02:12 »

But like Herko_ter_Horst pointet out, this may not be the best solution to your problem. Since it is very easy and cheap to calculate the distance between two points, just give your objects a location property, so your "object1.distance(object2)" method just calculates the distance on the fly by substracting the two locations.

The real problem is to find the two objects you need to calculate the exact distance for. In the first place you have to reduce the amount of objects to test, like grouping them in neighbouring clusters. If this is what you are after, Google for "space partitioning trees" like BSP trees, quadtrees and octrees.

You may not need to do any partitioning at all.  Testing distance from 1 object to n-1 others is really quick even for hundreds of objects (it scales by (n^2)/2 ).  To make it quicker you could even leave out the square root from the distance calculation so you are only computing subtractions.  If you store the objects in a list, loop through them like this:

for (int i = 0; i < objects.size(); i++){
            for (int j = i+1; j < objects.size(); j++){
                // distance test here between i & j
            }
         }

Offline Jeff

JGO Coder




Got any cats?


« Reply #4 - Posted 2006-06-12 23:27:08 »

Its also very possible you dont really need to repcompute this.

The expesnive part of distance calculation is the square root.

If you can arrange your code so you can do all your comparisons in distance-squared space then you can eliminate all square roots.
Then the distance between two points is calculated with a few adds and multiplies.

Got a question about Java and game programming?  Just new to the Java Game Development Community?  Try my FAQ.  Its likely you'll learn something!

http://wiki.java.net/bin/view/Games/JeffFAQ
Offline kappa
« League of Dukes »

JGO Kernel


Medals: 70
Projects: 15


★★★★★


« Reply #5 - Posted 2006-06-13 02:03:21 »

thx for all the tips, as for not needing to precaluclate, in this case i need to since its for a pathfinder, the distance is for special nodes for an abstract map, so they could be anywhere, the position on the nodes isn't really needed just the distance from one to another so a path can be calculated.
Offline Jeff

JGO Coder




Got any cats?


« Reply #6 - Posted 2006-06-15 03:10:32 »

Then I would organize this based on the best data structure for your particualr path-finding algorithym.

Got a question about Java and game programming?  Just new to the Java Game Development Community?  Try my FAQ.  Its likely you'll learn something!

http://wiki.java.net/bin/view/Games/JeffFAQ
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

xsi3rr4x (14 views)
2014-04-15 18:08:23

BurntPizza (12 views)
2014-04-15 03:46:01

UprightPath (25 views)
2014-04-14 17:39:50

UprightPath (11 views)
2014-04-14 17:35:47

Porlus (28 views)
2014-04-14 15:48:38

tom_mai78101 (50 views)
2014-04-10 04:04:31

BurntPizza (109 views)
2014-04-08 23:06:04

tom_mai78101 (209 views)
2014-04-05 13:34:39

trollwarrior1 (177 views)
2014-04-04 12:06:45

CJLetsGame (184 views)
2014-04-01 02:16:10
List of Learning Resources
by Longarmx
2014-04-08 03:14:44

Good Examples
by matheus23
2014-04-05 13:51:37

Good Examples
by Grunnt
2014-04-03 15:48:46

Good Examples
by Grunnt
2014-04-03 15:48:37

Good Examples
by matheus23
2014-04-01 18:40:51

Good Examples
by matheus23
2014-04-01 18:40:34

Anonymous/Local/Inner class gotchas
by Roquen
2014-03-11 15:22:30

Anonymous/Local/Inner class gotchas
by Roquen
2014-03-11 15:05:20
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!