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.

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!

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

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

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!

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.

so if octree is so good is my algorithm of any use to any1?
or dose any1 wana help me make it better?