#12818 - shunyata - Thu Nov 27, 2003 6:44 pm
?cause I?m working on two different very fast detection-algorithms intruducing some concepts I havn?t seen anyone else implement..
is it worth investing my precious time in completing these or should I move on to arbitrary bounding-shapes?
#12819 - sajiimori - Thu Nov 27, 2003 6:52 pm
Of course, lots of people use collision rects. What's your idea?
#12820 - shunyata - Thu Nov 27, 2003 7:29 pm
well one is simple, it expands the sector method. instead of registering the sector in which an object resides, it keeps track of the sectors where bounding points reside;
| Code: |
struct bound_point
{
byte x;
byte y;
byte type;
byte filler;
};
// values of type
enum {TOP_LEFT, TOP_RIGHT, BOTTOM_LEFT, BOTTOM_RIGHT};
// each collidable object includes a bounding point array
// which is indexed with the same enumeration
bound_point bounds[4]; |
I?m using a sector size of 30 x 20 pixels so that 4 levels of binary exclusion can be used when determining which sectors contain points. Objects with larger bounds than the sector size use multiple aligned point arrays. the containment algorithm switches on the type of its point arguments and can then determine whether the objects the points belong to have collided. using this technique we elliminate the shores of making sure objects are checked for collision in all sectors they overlap.
i just started developing this, and I havn?t yet determined wheather it will be too space-intensive.
#12821 - tepples - Thu Nov 27, 2003 7:39 pm
Conceptually, a typical collision detection routine will go like this:
1. Axis sorting (1D extent test), to reject the most sprites that do not possibly overlap. Some engines use a sector method.
2. Bounding rectangle test, to reject more sprites that do not overlap.
3. More complicated tests, sometimes.
It seems you're replacing step 1 with what amounts to a bitmap test, scaling each sprite's bounding rectangle down by a factor and checking it against all other sprites that have been drawn in that cell. I'd like to see how this technique's speed fares against that of sorting at various densities of sprites in a playfield.
If you're worried about space, develop it on a PC first, where you get 32+ MiB of space to roam in. Complicated algorithms with complicated data structures are a very good candidate for PC based prototyping.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#12822 - shunyata - Thu Nov 27, 2003 7:40 pm
we can make it smaller by using bounds instead of points
| Code: |
struct bound
{
byte value;
byte type;
};
// values for type
enum {LEFT, TOP, BOTTOM, RIGHT}; |
but that makes it slower...
#12823 - shunyata - Thu Nov 27, 2003 7:56 pm
well, you might see it as partitioning the bounding rectangle into 1-4 segments each bounded by a point and two sector edges (which are determined by the 'type' variable of the point) of the sector. the special cases where 2 or 4 bounding points from one object reside in the same sector are quite easy to take care of (by keeping track of the diagonal direction from which an object has been determined to be contained)
#12828 - col - Fri Nov 28, 2003 2:58 pm
[quote="shunyata"]...using this technique we elliminate the shores of making sure objects are checked for collision in all sectors they overlap.
quote]
Hi Shunyata
From your description, it sounds to me like you are not elliminating any shores(chores?). More like you are moving the work around a bit so it seems that there is less?
Also, there seem to be some problems with the logic of your system...
Maybe i don't fully understand what you are doing?
but is sounds like in trying to simplify the actual box overlap test by turning it into 4 point tests- 1 for each corner, you are actually going to increase the workload - with many extra conditionals and special cases...
a couple of examples :
| Code: |
-------------------------------------------------------
|1 |2 |3 |
| boxA | | |
| ------|-----------------|------ |
| | | | | |
-------------------------------------------------------
|4 | |5 boxB |6 | |
| | | ------- | | |
| | | | | | | |
| | | ------- | | |
-------------------------------------------------------
|7 | |8 |9 | |
| | | | | |
| ------|-----------------|------ |
| | | |
-------------------------------------------------------
|
what if you have 1 bounding box (boxA) with corners in sectors 1, 3, 7 & 9 (with your sector size, this could happen with any box greater than 31x21) - and another (boxA) that has all its points in sector 5?
Ok, so usually, a collision would be detected before boxB got inside of boxA, but not always...
| Code: |
-------------------------------------------------------
|1 |2 |3 |
| boxA | | |
| ------|-----------------|--- |
| | | | | |
-------------------------------------------------------
|4 | |5 |6 | |
| | | boxB | | |
| | | --|---|-------------|---
| | | | | | | |
-------------------------------------------------------
|7 | |8 | |9 | | |
| ------|--------------|--|--- | |
| | | | | |
| | | | | |
------------------------------------------------------- |
| |
------------------------
|
The above example is possibly more worrying. The two boxes overlap, but none of the corner points from boxA share sectors with any of boxBs corner points !
Still probably uncommon, but if you don't 'catch' this special case, you will have to be constantly aware when designing levels etc. or you might create game situations where this happens every time !
The standard 2d collision box test methods described by tepples are very efficient - its going to be pretty difficult to improve on them unless you have some very 'custom' situations in your game.
If I have misunderstood your technique, and your system deals gracefully with the situations that i have described - please explain the system again.
cheers
Col
#12831 - shunyata - Fri Nov 28, 2003 4:26 pm
| Quote: |
| I?m using a sector size of 30 x 20 pixels so that 4 levels of binary exclusion can be used when determining which sectors contain points. Objects with larger bounds than the sector size use multiple aligned point arrays. |
this means that there are no boxes larger than the sector size, so none of your situations can arise. also concerning the point tests, I hope you realize the importance of the type variable in the point structure. it makes the containment test faster than rect vs rect, ofcource you have to do 4 of them, but if you use a traditional sector-method (sorting the positions of objects into sectors), you have to either
1) test 3 sorrounding sectors in addition to the sector where the object registered, because you cant be sure if it extends into them without testing
2) make 4 different displaced sector sorts
and both of these metods require a sector size larger than the largest object boundary
as for the special cases where 2 or 4 points from the same object boundary reside in the same sector, I will post the code once i?ve done it, it is perhaps not entirely intuitive to see. my computer works very poorly so I?m not sure when I can get to it.
and yes; 'chores' is what I was trying to spell..:) i?m from sweden and currently hostage under a foreign language..i can assure you that you would be wining a lot more if i posed in swedish :p
holler if you want me to explain further.
#12838 - col - Fri Nov 28, 2003 6:04 pm
| Quote: |
[quote="shunyata"] | Quote: | | I?m using a sector size of 30 x 20 pixels so that 4 levels of binary exclusion can be used when determining which sectors contain points. Objects with larger bounds than the sector size use multiple aligned point arrays. |
this means that there are no boxes larger than the sector size, so none of your situations can arise. also concerning the point tests,
|
I'm not sure what you mean by '4 levels' of binary exclusion?
Also, I've never read or heard of 'aligned point arrays', so maybe you could explain what they are - and how they will help
| Quote: |
I hope you realize the importance of the type variable in the point structure.
|
yes - it is very clear.
| Quote: |
it makes the containment test faster than rect vs rect, ofcource you have to do 4 of them
|
rect vs rect uses up to 4 comparisons - if you use an early termination test, then when you average out over many tests it works out at 2.5 comparisons per test !
your point test uses 3 comparisons just to deal with the type info, then it uses 0 to 2(0 for internal points) to do the actual test.
it looks to me as though with any box > 30x20, you are potentially going to need at least 9 not 4 tests - unless your 'aligned point arrays' help in this situation (and result in an overall cpu saving)
| Quote: |
...but if you use a traditional sector-method (sorting the positions of objects into sectors), you have to either
1) test 3 sorrounding sectors in addition to the sector where the object registered, because you cant be sure if it extends into them without testing
2) make 4 different displaced sector sorts
and both of these metods require a sector size larger than the largest object boundary
|
yes
| Quote: |
as for the special cases where 2 or 4 points from the same object boundary reside in the same sector, I will post the code once i?ve done it, it is perhaps not entirely intuitive to see. my computer works very poorly so I?m not sure when I can get to it.
|
I'm sure there are many ways you could process your special cases - thats not the issue. The issue is that you have to test for each case - its this testing that is the real danger to efficiency
| Quote: |
holler if you want me to explain further.
|
:)
I really hope you have discovered a 'better way' to do collision detection. My worry is all the tricks you use to get around the problems with traditional methods might take more cpu time that the original problems did.
I guess I will just have to wait and see :)
cheers
Col
#12848 - shunyata - Fri Nov 28, 2003 7:33 pm
hey col, what does your rect-vs-rect code look like?
#12855 - col - Fri Nov 28, 2003 10:05 pm
| shunyata wrote: |
| hey col, what does your rect-vs-rect code look like? |
It's a bog standard rectangle overlap check.
roughly:
| Code: |
if( boxB.x1 > boxA.x2
|| boxA.x2 < boxB.x1
|| boxB.y1 > boxA.y2
|| boxA.y2 < boxB.y1 ){
return NO_COLLISION;
}
return COLLISION;
|
cheers
Col
#12857 - shunyata - Fri Nov 28, 2003 11:45 pm
yeah, that?s the bare basics, but I need a test that returns the direction of collision
| Code: |
/* ______________
|7 |6 |5 |4 |3 |
|__|__|__|__|__|
|8 | | | |2 |
|__|__|__|__|__|
|9 | |or| |1 |
|__|__|ig|__|__|
|10| | | |16|
|__|__|__|__|__|
|11|12|13|14|15|
|__|__|__|__|__|
*/
sbyte col_detect(byte* box_1, byte* box_2)
{
if (box_1[TOP] >= box_2[TOP] && box_1[TOP] <= box_2[BOTTOM])
{
/* _ _ _
|2 _|_ _
|_ _|_| |
|_ _ 1| |
v */
if (box_1[LEFT] >= box_2[LEFT] && box_1[LEFT] <= box_2[RIGHT])
{
return (7);
}
/* _ _ _
_|2 _ _|_
| |_ _ _| |
| |
|_ _ _ _ 1| |
v */
else if (box_1[LEFT] < box_2[LEFT] && box_1[RIGHT] > box_2[RIGHT])
{
return (5);
}
}
if (box_1[RIGHT] >= box_2[LEFT] && box_1[RIGHT] <= box_2[RIGHT])
{
/* _ _ _
_ _|_ 2|
| |_|_ _|
|1 _ _| |
v */
if (box_1[TOP] >= box_2[TOP] && box_1[TOP] <= box_2[BOTTOM])
{
return (3);
}
/* _ _ _ _ _ _
| _|_ _
| | | 2|
| |_|_ _|
|1 _ _ _ _ _| |
v */
else if(box_1[TOP] < box_2[TOP] && box_1[BOTTOM] > box_2[BOTTOM])
{
return (1);
}
}
if (box_1[BOTTOM] >= box_2[TOP] && box_1[BOTTOM] <= box_2[BOTTOM])
{
/* _ _ _
|1 _|_ _
|_ _|_| |
|_ _ 2| |
v */
if (box_1[RIGHT] >= box_2[LEFT] && box_1[RIGHT] <= box_2[RIGHT])
{
return (15);
}
/* _ _ _ _ _
|1 |
| _ _ _ |
|_|_ _ _|_|
|_ _ 2| |
v */
else if (box_1[RIGHT] > box_2[RIGHT] && box_1[LEFT] < box_2[LEFT])
{
return (13);
}
}
if (box_1[LEFT] >= box_2[LEFT] && box_1[LEFT] <= box_2[RIGHT])
{
/* _ _ _
_ _|_ 1|
| |_|_ _|
|2 _ _| |
v */
if (box_1[BOTTOM] >= box_2[TOP] && box_1[BOTTOM] <= box_2[BOTTOM])
{
return (11);
}
/* _ _ _ _ _ _
_ |_ 1|
| | | |
|2 _|_| |
|_ _ _ _ _ _| |
v */
else if (box_1[BOTTOM] > box_2[BOTTOM] && box_1[TOP] < box_2[TOP])
{
return (9);
}
}
return (0);
} |
that?s where the sector-point algorithm comes into play
to clarify everything else i?ll just post the code when (and if) it?s done. i do believe this sector-point algorithm would be faster for this type of collision detection, but i realize it might be a bit of an overkill for the gba. in the worst case we?ll need dynamic datastructures and i?m not up for writing my own heap implementation and all that stuff.
how fast is malloc() / new, pretty awful right?
well maybe i?ll just settle for the bare-bones rect-outside-rect method with 1d sorting.
#12858 - crossraleigh - Sat Nov 29, 2003 12:01 am
On several different topics now, tepples has kindly suggested using axis-sorting collision detection, and I have come to favor it over using sectors. The GBA screen is pretty small for full fledged screen sectoring anyway.
If you keep a list of all the sprites sorted by Y coordinate, you can just move backwards or forwards in the list until you find a sprite that is higher than the top or lower than the bottom of the sprite you want to test. While X-sorting is usually better for collision detection (the locations should be spread out more), Y-sorting takes care of Z-ordering as well; you just loop through and apply the list to OAM.
To save memory you'll keep sprites in a list anyway, right? So you might as well keep them sorted. Unless you're doing a linear side-scroller, like Mario, where almost all the Y coordindates match up, I think this sorting is quicker. And in games like mario, Z-ordering isn't that important, so you can use X-sorting.
#12859 - poslundc - Sat Nov 29, 2003 12:25 am
| crossraleigh wrote: |
| While X-sorting is usually better for collision detection (the locations should be spread out more), Y-sorting takes care of Z-ordering as well; you just loop through and apply the list to OAM. |
Hey now, that's a very good point! <makes a mental note for when it comes time to write collision-detection code>
Nothing I love more than killing multiple birds with single projectiles.
Dan.
#12863 - yaustar - Sat Nov 29, 2003 12:48 am
may I ask for an example of x/y ordering and ask what is z-ordering
_________________
[Blog] [Portfolio]
#12864 - shunyata - Sat Nov 29, 2003 12:58 am
well, I agree with you crossraleigh, in most cases 1d-sorting would be enough (and the z-order trick ain?t half bad either). but i?m writing a spaceshooter with quite a lot of objects, that?s why i bother (and also for the sense of completeness). and remember, the faster the col-det the more time over for cool software-effects ;D
#12899 - crossraleigh - Sun Nov 30, 2003 5:10 am
yaustar, I'll try explaining:
Z-ordering is simple. The GBA draws sprites that have the same priority in the order they are placed in OAM; sprites lowest in memory are drawn first. Usually you want objects furthest away (from the 'camera') to be drawn first, so you need to keep them ordered in OAM by their 'Z coordinate'.
To be kept sorted by their X or Y values, sprites need to be in a doubly linked list. Every time you move a sprite, just make sure you move it in the list. When they are Y sorted, you don't need to worry about changes in X values, and for changes in Y values, here is some pseudocode:
| Code: |
if sprite.direction == UP
while sprite.y - sprite.speed > i.y
i = i.prev
sprite.insert_before i
if sprite.direction == DOWN
while sprite.y + sprite.speed < i.y
i = i.next
sprite.insert_after i
|
tepples has also suggested using a Shellsort to reorder the sprites, but I think that is overkill unless you have some really hyperactive sprites and the list will drasticly change each frame.
#12914 - yaustar - Sun Nov 30, 2003 4:15 pm
ok, but how does keeping the y-coords sorted help with the collision detection?
| Code: |
for(i=0; i < no of sprites; i++)
{
//do y checking here
if(sprites[i].y + SPRITE_HEIGHT < sprites[i+1].y)
{
break;
}
}
|
Something like this maybe?
_________________
[Blog] [Portfolio]
#12918 - sajiimori - Sun Nov 30, 2003 6:51 pm
Yup, just like that. :-)
#13290 - haduken - Wed Dec 10, 2003 8:22 pm
And what's wrong with rectangular collision detection? It works just fine for most sidescrolling games.
#13292 - yaustar - Wed Dec 10, 2003 8:40 pm
This is still a variation of the rectangle collision detection but making it quicker by not comparing all the sprites with each other.
_________________
[Blog] [Portfolio]