# space algorithm problem

This topic is 3323 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

hi there. im new here so bear with me. lets say i have 1000 ship in the vastness of space! now i need to know whats each ship distance if from any other ship(for collsions, ai,ect...) now just doing a loop of 1000 ship looking for 1000 ship is not an option! thats one million iterations of a loop each "just" checking distance! thats more resources then the 1000 ship in my 3D engine! im trying to think of a way to relay shrink that! i been trying to do it for weeks with nothing effective to show... here is some of the ways i was thinking will help: splitting the space into virtual sectors or galaxies - dose save a lot but not enough and what happens on the borders of the sector? if someone is sitting on the edge of the next sector i cant see him? an organized list (by distance) i dont think it will save anything coz of the high operating cost of a list like that. so thats where i need help or if anyone knows how a big game handles it.

##### Share on other sites
octree's

If your scene is inside an octree than all your ships will fill 1 or a few octree nodes. You know when to do collisions if any other objects are inside that objects node.

Do some research on octree's and you'll quickly see this is the solution you need.

In my game I have over 120,000 objects (asteroids, ships, planets, rings, stations, etc) loaded into an octreed scene. I only calculate collisions for objects that have other objects in the node. Before I do collision, I say...

Object 1's node has 10 other objects, loop through checking distance from Object 1. If distance is less than Object 1's bounding sphere diameter than check for collision.

The tough part is when an object moves, you have to check to make sure its still in the same octree node and it can belong to multiple nodes if it partially intersects them.

##### Share on other sites
tnx ill go try googleing it now

##### Share on other sites
Any spatial partitioning scheme will help. The most basic one is dividing your space into a grid of cells (I guess this is what you mean by sectors). For each object, you test collisions against objects in the same cell as well as neighboring cells (for the edge case). The smaller the grid cells the fewer collision tests will occur; one limitation is that an object must never be larger than half the width of a cell, and of course a super high number of cells will have some overhead.

##### Share on other sites
>>now just doing a loop of 1000 ship looking for 1000 ship is not an option!
thats one million iterations of a loop each "just" checking distance!<<

as others have said
but I just wanna point out its only 1,000,000 if youre checking distances twice
i.e. if u check A->B u dont need to also check B->A

##### Share on other sites
Also, make sure to use the square of the distance if at all possible (it should be in your case), because it's much faster to compute.

##### Share on other sites
Quote:
 Original post by alvaroAlso, make sure to use the square of the distance if at all possible (it should be in your case), because it's much faster to compute.

i dont get what you meenby that?

##### Share on other sites
What alvaro is talking about is avoiding the use of square roots to compare distances.

Normally, to determine the distance between two points, each point represented by a vector, you'd do something like this:
vector diff = vector(position1.x-position2.x, position1.y-position2.y, position1.z-position2.z);distance = sqrt(diff.x*diff.x + diff.y*diff.y + diff.z*diff.z);if( distance < minDistance ) collision();

Square-roots are computationally expensive when you can do the same thing this way:
vector diff = vector(position1.x-position2.x, position1.y-position2.y, position1.z-position2.z); // same as abovedistance2 = diff.x*diff.x + diff.y*diff.y + diff.z*diff.z; // same as above// skip the sqrt() and compare squared valuesif( distance2 < minDistance*minDistance ) collision();

The second method results in the same collision detection but is faster.

##### Share on other sites
Ok, now I'm curious.
I understand the concept of an octree.
All it's doing is partitioning a space recursively to whatever accuracy you want.
However, the original problem statement suggested that he was concerned with partition-boundary interfaces. How do you handle collisions (or whatever) if two items are placed in adjacent partitions near the boundary?

1. 1
2. 2
3. 3
Rutin
16
4. 4
5. 5

• 10
• 11
• 14
• 10
• 25
• ### Forum Statistics

• Total Topics
632650
• Total Posts
3007645
• ### Who's Online (See full list)

There are no registered users currently online

×