Objects in List problem?

Newbie & Debugging Questions
#1

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

#2

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.

#3

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.

#4

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
}
}

#5

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.

#6

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.

#7

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