Sign in to follow this  
kalixxx

space algorithm problem

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
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?


Share this post


Link to post
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 above
distance2 = diff.x*diff.x + diff.y*diff.y + diff.z*diff.z; // same as above
// skip the sqrt() and compare squared values
if( distance2 < minDistance*minDistance ) collision();

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

Share this post


Link to post
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?

Share this post


Link to post
Share on other sites
Quote:
Original post by ArikwexHow do you handle collisions (or whatever) if two items are placed in adjacent partitions near the boundary?


If you have a fixed partitioning scheme then mobile objects will often be in more than partition (when they are on a line). In a grid for example, nothing special has to be done, the object on the boundary is simply collided with other objects in both partitions.

Share this post


Link to post
Share on other sites
ok first, gabereiser did you just say your game runs 120000 objects in space in real time?!?!
noway there all on screen but even if not you are moving them by a frame by frame basis?

second, i now get what you 2 meant buy not using sqer its a nice idea.

and last, i looked at the octree and i did not get how it will work on a large scale...
i meen the very idea of space is that its infinite so dividing it to a grid didnt relay cut it.

so after several weeks of brain pain... last night i came up with a simpler idea!
and since its an original it will be from here on call as the Kalix Onion.
basically instead of dividing space into bricks i did it in to onion layers!

and here it is (well the first draft...)
you start by making a list of all your collidebl objects(no shots go in here!)
then you sort the list by distance from origin(0,0)
now each of you moving object(ships,shots,missiles,ect...) checks the list from his range minus his detection/collision range to the detection/collision plus his range.
and you get this info into a the object list of "who can i see"
now! you only have to check the "who can i see" list every frame and the total list only every second or so(depending on how fast things in your game go)

depending on how the ships are spread in your universe this algorithm can be very effective! (well i think so anyway)
me ? my game will be spread over galaxies and relay big distances.
i tested it with 10000 ships and found out that if every ship only needs to see 3-4 ships i only need like 700 iteration per frame!
and 700 is a long LONG way from the million i started with (for 1000 ships!)
and the one hundred million i wold have needed for the 10000 ships!

now the only thing that will slow you is how far your ships need to see!!!

ok people we got us a new algorithm to rip apart! nuke it and tell me what you think!





Share this post


Link to post
Share on other sites
>>and last, i looked at the octree and i did not get how it will work on a large scale...
>>i meen the very idea of space is that its infinite so dividing it to a grid didnt relay cut it.

Uhm I'm sorry, but your game can not have "infinite" space because your computer has FINITE memory... :D


>>basically instead of dividing space into bricks i did it in to onion layers!
Were you watching Shrek? lol.


>>ok people we got us a new algorithm to rip apart! nuke it and tell me what you think!


NICE. Simple, elegant, and effective.
Each frame requires a re-partitioning of all ships (lets say N ships)
so that algorithm operates in O(N) time which is good.

The next step is to iterate through each ship individually and compare its layer with other nearby layers. Given a radius R of search area (measured in # of onion layers) and a total of T onion partitions, you are handling approximately 2R/T*N checks (assuming uniform density of ships per layer). Since you're performing the check for EACH SHIP this means approximately 2R/T*N^2 checks. So this is still an N^2 algorithm at best due to the nature of the problem. HOWEVER, You have a nice 2R/T coefficient in front of the N^2 which was not always there!

You might want to experiment with the width of the onion regions and examine the efficiency of the system (in terms of time). Very interesting algorithm concept. I'll probably be using it in the future :) If I can think of any problems with it I'll be sure to post.

Share this post


Link to post
Share on other sites
Seems to be a variation of a method in one of the Game Programming Gems, except he's not sorting by distance to origin, but has 2-3 seperate lists sorted by x/y/z coordinate.

Your approach has the advantage of using only one list, but the disadvantage that theoretically you end up comparing objects that are far away but just happen to have the same distance to the origin.

And here I see one (very minor catch): when do you abort your tests? When the first object thats a neighbor in your list turns out to be too far away? Won't work. You'd still have to stick with the difference in distance to origin. Considering the vastness of space that shouldn't happen often enough to worry about.

So your test (each object only tests to the right in the list):
if (pre- or recalculated distance to origin - my distance to origin > threshold) abort

Their test (also only to the right):

if (his x - my x < threshold)
if (his y - my y < threshold)
if (his z - my z < threshold)


One requires more work keeping your lists (and uses more memory), but the test is easier, the other is less maintenance, but a little more testing.

I think for games happening in a smaller area I'd prefer their method, but for huge space yours might be preferable (less if's are always good and you could store the determined distance for each object and the squared threshold).



Edit:

Did you consider really huge objects? Say objects that are so large you don't want to use the largest objects size as threshold for collision tests, yet dont want to a seperate approach for them?

For the other method I think it's pretty simple. Sort by "low" edge and always compare upper edge to neighbours lower edge. In your approach you'd probably need to calculate min and max distance to origin and always compare max to neighbours min.

[Edited by - Trienco on August 20, 2009 12:58:22 AM]

Share this post


Link to post
Share on other sites
>>i looked at the octree and i did not get how it will work on a large scale

you could have multiple octrees
(eg 3)
one with 100,000 km3 // spaceships, planets etc
one with 100 au3 // planets etc
one with 100 light year // stars, galaxys etc

>>And here I see one (very minor catch): when do you abort your tests? When the first object thats a neighbor in your list turns out to be too far away? Won't work. You'd still have to stick with the difference in distance to origin. Considering the vastness of space that shouldn't happen often enough to worry about.<<

a better method (in 2d at least, perhaps it works in 3d)
start in the desired node, then test each node in a loop outwards (if u find a hit u will still need to carry on another loop)

Share this post


Link to post
Share on other sites
Quote:
Original post by zedz
a better method (in 2d at least, perhaps it works in 3d)
start in the desired node, then test each node in a loop outwards (if u find a hit u will still need to carry on another loop)


But since he's based on distance to origin, a ship might be very close in the list, yet very far away. So you can't do

while(hit) keepTesting

as an object further away in the list might be literally infinitely closer (and actually colliding, unlike the 5 nodes you tested before). The only reliable test I can think of is that the other node must be further away from the origin than some threshold (based on the largest object in the list).

As some objects might be pretty big (stations, planets) I don't think sorting by object center and using "hugest object size" as threshold would be as efficient as it could be with a min/max distance and testing this->max vs next->min approach. Depends on number of objects, overhead for the additional calculations and how many unneccessary tests would be done on average.

Share this post


Link to post
Share on other sites
ok first the master list is sorted!
first is always closes to origin(0,0),
so you only have to test from the first object in you range to the last one in it.
and object size is NOT relevant since you do a second distance check(between the 2 objects) to look for collisions! you can just add the object size to the distance!

now remember the master list is only there to tell the objects whats close to them and only need to be updated depending your game speed(in my game evry 60 frames or so)
THEN every object on its own look for whats close to him AND DOSE NOT HAVE TO BE IN THE SAME FRAME!
i give every object a random(1-59) number when i make it.
the master list runs on frame 0.
then every ship updates its "close to me" list at its desgnted frame!
this way they shear the pain!
the only thing you need to do is tell each ship what range it needs to look for collisions. by the speed its going plus a minimum. or what ever you need!

p.s.
problem one: yes i know that a ship from the other side of the universe can be the same distance as the ship next to you(in the master list)
and depending on how you spared it can be very likely to happen...
i still say its an exeptble loss.
if any1 has a way to fix it be my gust! BUT consider if the fix wont be slower.

problem two: each ship dosent have the same range for collisions(well at lis in my game). so if you can see a ship it dosent mean it sees you!
so there can be duel checks. thats bad yes BUT if you get a hit you die/ bonce off/ect... then the check ends so its not so bad at the end.

well i am very surprised i made this algorithm even more that it works(i think)
and even MORE that none nuked it!
keep posting!

Share this post


Link to post
Share on other sites
I don't see a problem with using an octree or a kd-tree.

For instance, using something like a kd-tree, in every frame you take your list of objects, find the maximum and minimum values for x, y and z. Let's say x spans the largest range. Then find the median of the x values and divide the space into objects under the median x and objects above the median x. If an object intersects x=median_x, put it in both sets. Now recursively repeat the process with each set, until the sets have few objects or are small. This process takes O(n*log(n)) steps, and it results in a structure in which you can query for intersections of one object versus all the other objects in time O(log(n)). Since will be doing this n times, this part of the algorithm also takes O(n*log(n)) steps, so the total running time is O(n*log(n)), which is way better than O(n^2).

In practice, instead of finding the true median x value, you can use something like the median of the x values for 5 random objects.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this