gbadev.org forum archive

This is a read-only mirror of the content originally found on forum.gbadev.org (now offline), salvaged from Wayback machine copies. A new forum can be found here.

Coding > Binary Search

#11795 - crossraleigh - Sun Oct 19, 2003 2:21 am

In collision detection on sorted data, is it more efficient to use a binary search instead of a normal loop? Or how do you usually narrow down the points?

A binary search seems particularly suited to tile collisions where there are lots of 'hot tiles' to test against. Would it also be the way to find sprite collisions if you sort them first as tepples describes? I'm just a little confused about how to test the coordinates once they are sorted.

#11797 - tepples - Sun Oct 19, 2003 3:11 am

I don't think a binary search would be straightforwardly applicable here. A binary search is good for finding a single needle in a well-ordered haystack, and any needle matching the needle you hold in your hand will do. Collision detection, on the other hand, is a different sort of search problem, as you're looking for any two needles that touch. You need to find needles matching each of the needles already in a haystack, which means you're going to have to loop through all the needles. The sort guarantees that the needles that match x will be close to x in the array, and the set will be somewhat dense (x's candidates much smaller than the entire haystack).

If you have so many objects packed into such a tight space that the sorting method isn't fast enough for your app, investigate the sector method. It's sort of like the sorting method (no pun intended) but can be applied in two or more dimensions.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.

#11799 - Gopher - Sun Oct 19, 2003 3:02 pm

It's probably not the optimal solution, but a binary tree could be applied to improve linear x- or y- sorting. If an x-sorted list is stored in a tree such that each node, not only the leaves, has a min and max x/y value stored in it that is the min and max from it's leaves. The main problem is that the non-leaf nodes would take up more memory, but if you use a static pool of nodes and 16-bit indexing the structure could be only 8 bytes per node

Code:

typedef struct CollisionTreeNode_tag {
    hword MinX, MaxX;
    hword LeftIndex, RightIndex;
} CollisionTreeNode;


Then just define your static tree so that index 0 is the root node and you can use 0 as null to mark the terminal points just as you would with pointers, and you can have up to a 65k node tree and 32k leaf nodes (and therefore collidable objects)

As I said, probably not an optimal solution, but should be a slight improvement in speed (at the cost of memory) over a testing against a sorted list, especially if you update a node's position and test that new pos for collisions in the same traversal of the tree.

Thinking about it more, this not be the best idea after all, since you could end up having an added node actually span between seperate branches, requiring those two branches to be lumped together. Nodes would only be able to be seperated into branches where there is a spot with no overlap on the sorted axis. This is a fatal flaw in my initial logic.

Ah, well. That's what I get for trying to be clever when I've only been awake for 15 minutes. I guess ultimately I'm back to agreeing with Tepples, probably not a straightford way to apply a binary tree to this problem. I concidered not posting this little thought-journey at all, but I've decided to post it anyway.
_________________
"Only two things are infinite: the universe, and human stupidity. The first is debatable." -Albert Einstein

#11813 - crossraleigh - Mon Oct 20, 2003 2:46 am

Wow, it's amazing what just a few extra terms can do for an otherwise fruitless search. I found a great article on (2D) collison detection: http://www.ddj.com/documents/s=983/ddj9513a/.

I almost had collisions down just from reading GBA forum and group posts when I deciding to give it one last Google'ing. Before, searching for collision detection yielded various 3D stuff, no 2D; but when I looked this last time, I found some 2D information.

I have been looking for something like that article for a while. Thanks guys! I'm pretty happy now :)