space algorithm problem
Author
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.
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.
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.
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.
>>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
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
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.
Author
Quote:Original post by alvaro
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.
i dont get what you meenby that?
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:
Square-roots are computationally expensive when you can do the same thing this way:
The second method results in the same collision detection but is faster.
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.
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?
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?
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
