Quote: I'm also not sure if the solutions you posted solve another problem: some objects that are very large or very long will occupy more than 2 sectors at a time. Some objects may span 3 or more. My system allows for this, but it's somewhat dependent on the game your are making.
Easy enough to change I suppose, thought I never actually prepared for it in my implementation. But what I would do is just create a "clone" of the object in every grid it exists in. So objects will check that grid and check back at its actual locatin and size.
Also, calculating an objects location on a grid, unlike in a quadtree, is much simpler.
Good points from Hybrid and visage. I've thought of those but am willing to take the potential performance hit.
The alternative is to clone the object into the other sectors like visage said. So if an object exists in two nodes i would have to check that object against all objects in both nodes. That also decreases performance.
there is an article in one of the graphics gems (#3? can't remember), called dynamic sphere tree. I like the concept a lot. It's like clustering objects together in a loose sphere tree. Very dynamic, and adaptable. Unfortunately, the code was a bit of a mess, and the article was very short.
I think for that kind of stuff, it's got to be anything loose. like a loose quadtree, a KDtree. Static partitioning (grid, voxels, quadtrees) for that amount of objects would impact the memory.
Sweep and prune is nice, as long as objects are well distributed. When they start to cluster a lot, or they are very large, there are lots of redundancies.
Anyway, I think I should read those discussions before posting... I'll be back.
Thanks for the posts. I'm still a little confused though as it seems nobody agrees on the most efficient method. I guess it depends on the specific scenario.
The quadtree solution seems best to me, but in a world with 1000 guarenteed objects is this likely to slow down too much?
Oliii you mentioned the sweep and prune method, any chance you could explain how it works?
that spanish hanging moss is nothing more than a 2D gridcell map. I can't believe the guy claimed he 'invented' it, anybody with a bit of sense would come up with the same thing on his own. [/rant]
about the second post, it's the same as the gridbased algo, but for sprites that can cover several squares.
About the redundant tests, That shifting method is insane :) I used a collision ID counter, that I increment for every object I test, and I store it into the objects I test against it. Then I avoid duplication of tests. no big deal really. You just have to remember to reset the counters and stored ID once in a while (using ints, reset it when one counter reaches 0xFFFFFFFF, which would be, ... every 10 or so days?!).
In the case of doing Collide(ObjectA, ObjectB), another thing is to make sure that ObjectB's physical address is greater than ObjectA's address. That way, you also perform the test only once per pair (you do A vs. B, and not B vs. A).
I wasn't too satisfied with it though, since it's not exactly efficient, as you do a proximity query stab for each objects, which also seems not very efficient.
So I used a gridmap like that for static objects, which aren't tested against anything, and used a sweep and prune algo for all mobile objects. Sweep-and-prune is performed as usual (mobile vs. mobile list trasversal), and mobiles are tested against the statics in the grid. Maybe I should not have bothered, but it was a good learning experience.
There is also another intriguing strategy that a friend of mine uses for his virtual city and autonomous agents PHD research. He is using a delaunay trianglulation. The whole City is mapped and trianglulated into a hierarchy of convex sectors, that's for the environment. It's used for navigation, path planning, traffic lights (set a portal as being 'blocking', 'forbidden', and other funky stuff like that). Much better than waypoints, since it's a lot more 'fuzzy'.
Then all the agents (cars, people, dogs, rats, ...) are stored into a delaunay/voronoi diagram. So each agent knows the closest agents to it, and can do avoidance by itself. The way the delaunay map is re-shaped every frame is quite complicated, but it's done localy for each agent as they move. Clever stuff, but way OTT (He is researching after all).
Back on the subject, for an RTS, I might contradict myself, but a grid-based approach would actually make sense. And it depends what you mean by collision entity. Could be a whole platoon, where the whole platoon is treated as a single collision block, and the little guys inside would not really collide with each other, or use some special faster and simpler collision code.
So in the end, the gridbased model, using a fast collision rejection algo.
Sphere Trees (page 384) and Recursive Dimensional Clustering (228).
Sphere Trees work as such: Each object is encompassed in a bounding sphere. While bounding spheres are generally known for holding extra space, the author insists that its actually good in some respects because it allows for all animations, etc for that object.
Whenever an object changes positions, it checks its distance from the center of its parent sphere. If it no longer is within the "skin" of its parent sphere, it is remove and placed into the root node of the tree. It is also placed in a FIFO queue. The parent is also placed in the queue. At each frame, all FIFOs are recomputed and reintegrated into the tree.
Unlike quadtrees and octrees, no sphere can over belong to more than one node on a tree. What is true for a SuperShere is true for its children (if it is outside the viewing range, so are its children.)
Recursive Dimensional Clustering is quite different. It claims, by the way, do be able to do collsion detection between 10,000 objects it 478 ms on a Pentium II 400Mhz machine. So, this might be something you want to check out. Here is how it works. First, it lines each object up by their first axis. You create a "bounding list", with each objects "open" and "close" location. Using something like quicksort, you order this list by axis location, lowest to highest. Next, we go through and create groups based on bracketed units.
A would be in group 1. B, C and D would be in group 2. Because A is a single unit, it can be tossed.
These groups are then passed to the Y-axis sort. In our case, B, C, and D must be analyzed in the Y case. Again, A doesn't need to be. So lets then say that when analyzed in the Y case, B becomes its own group and C and D get grouped again.
B gets tossed, C and D move on.
C and D are sent to the Z access, and do the same thing.
However, for any units to collide, they must be a group for all three steps. So the final steps for RDC are:
1) Start with the X axis 2) Construct a linked list of object bounderies in this dimension 3) Sort that list by boundry position, from lowest to highest 4) Find groups using the open/close bracket method 5) For each group found, repeat steps 2-5 in the other dimension(s) until the group no longer gets subdivided and all dimensions have been analyzed for that unique group.
Okay, so that should be plenty of methods to choose from. Rock on.
About the redundant tests, That shifting method is insane :) I used a collision ID counter, that I increment for every object I test, and I store it into the objects I test against it. Then I avoid duplication of tests. no big deal really. You just have to remember to reset the counters and stored ID once in a while (using ints, reset it when one counter reaches 0xFFFFFFFF, which would be, ... every 10 or so days?!).
Insane in a good way ;) Did you look at the math the guy did? I mean...it works. I personally wouldn't have even thought of it!
As for your method...I dont really like having to store those extra variables and keep track of them. Too much possibility for error I guess. I mean, what if you do forget to reset the counters and stored IDs? That would get pretty messy after a while (even if it is 10 days!) :D
Anyway, I dont know whats up with that guy claiming he invented the Hanging Moss Algorithm. I was doing it without even knowing it was actually a thing. I mean...it is just common sense.
I really like your friends method there though. Really, really impressive. But a word to the wise...when nobody knows that your friend exists, claim it as your own [wink]
True, it's clever, But I would never try to do such thing, as there is always a simpler solution for that kind of problems. But, kudos...
If you don't like that ID storing thing, which may looks hacky in a way but works really well, you can always store the objects tested in a bucket, and add new objects you test to that bucket. If alreay in there, don't test. That was the first solution I used, but it was far from optimal.
Anyway, if it is fast, and you understand the method he describes, you can try it.
about that dimensional clustering, that's another flavor of sweep and prune, in a complicated word. That's almost what I used for my mobiles in the world, with the hanging gardens of Babylon for the statics.
I used a 2D clustering, along X and Z. Enough for a racing game. It's quite cool and works well, as I said for nice, well distributed small objects, like spaceships, cars, humans and projectiles. And I suspect that particular method would aso work well if large objects were introduced. The special method I used would not cope well with that.
It's also particularly good if objects move relatively slowly. All you have to do is shift the object along the sorted lists, and recompute the touched groups.
Well worth a try. And I don't believe the 500ms (1/2 second?!?). It must be much faster than that with good optimisations, even on a pentium II, and for 10,000 objects.
The disadvantage of it is that it is not suited for very long ray-tracing (for things like A.I. vision), whereas the sphere tree and the hanging shrubs are much better at it.
I am just telling you what the article said. Dont kill the messenger ;)
As for your two possible methods: what about the wasted memory? Also, if you use the object bucket method (which I know you said yuo werent...), dont you find that about 8000th object that the bucket is gettnig enormous, and searching through it is almost as costly as just running through the entire list?
As for the IDs: Dont you need to run through the IDs for the object you are checking the IDs of the object it "may" be colliding with to check if one has the other in their ID list? Again, doesn't this create major slow down once the number of objects increases and you are getting down to your last few objects? Though, it is probably only true for the initial test: once the game gets going these ID checks only need to be done when a unit moves. But what happens when me and my allies move our 1000 unit army across a map to battle another 1000 unit army. Thats a lot of unit IDs being tracked.
I'm not intending to kill anyone. If I sounded grumpy, it was probably my usual monday morning strop.
"As for the IDs: Dont you need to run through the IDs for the object you are checking the IDs of the object it "may" be colliding with to check if one has the other in their ID list?"
I just can't make up that sentence :)))
I stopped using the bucket anyway. As you pointed out, it's pointless when objects tend to cluster.
the collision counter is a global variable. in short, it falls down to this...
bool CCollisionGrid::GetCellsCoveredByObject(CObject& ObjA, int& xmin, int& ymin, int& xmax, int& ymax){ // whatever you fancy //....}bool CCollisionGrid::TestObjectAgainstGrid(CObject& ObjA){ int iCounter = IncrementGlobalCollisionCounter(); if (iCounter == 0) ResetAllObjectsCollCounters(0xFFFFFFFF); ObjA.SetCollCounter(iCounter); int xmin, ymin, xmax, ymax; if (!GetCellsCoveredByObject(ObjA, xmin, ymin, xmax, ymax)) return false; bool bCollided = false; for(int i = xmin; i <= xmax; i ++) { for(int j = ymin; j <= ymax; j ++) { bCollided |= TestObjectAgainstCell(ObjA, i, j); } } return bCollided;}void CCollisionGrid::TestObjectAgainstCell(CObject& ObjA, int x, int y){ bCollided = false; CObjList& xList = *(GetCell(x, y).GetObjList()); for(int i = 0; i < pxList->NumElements(); i ++) { CObj& ObjB = *(xList.GetObject(i)); int ObjCollCounter = ObjB.GetCollCounter(); if (ObjB.GetCollCounter() == ObjA.GetCollCounter()) continue; if (&ObjB <= &ObjA) continue; ObjB.SetCollCounter(ObjA.GetCollCounter()); bCollided |= TestForCollisions(ObjA, ObjB); } return bCollided;}
can't be any simpler.
The ID is just like flagging the objects as "tested already", but you don't have to reset the flags every tests. Only every couple of hour or so (0xFFFFFFFF / (10,000 objects * 60 fps_per_sec * 3600 seconds_per_hour);
the cells covered by the object can also be pre-processed and stored in the object itself. It's like a double book-keeping.
