Bounding Box
Pixel based movement is getting to my head. I can get the basic movement working but the collision is confusing me quite a bit, maybe because this is my first time around.
Anyway, I was referred to the "bounding box" method of detection, I was slightly confused. I looked around to see on what it was, I see the pros and cons, one con being that it's difficult to work with shapes that aren't fully square and leave spaces which usually let off the Collision checker to return a collision detected, anyway, that isn't the problem.
I found the main problem for me to actually write it in terms of BYOND. Here is my base movement system:
So this is where you all come in, I've searched all of BYOND for the bounding box, in the forums, libs/demos, everywhere. I need help creating a simple bounding box collision detection system. I was thinking something modular would be fine, Calus Corps's LineWalk demo helped a bit, but not enough for me to potentially write my own. So lead me to my first pixel based collision system :)
A small demo would be nice :)
Thank you all in advance.
Haywire
Anyway, I was referred to the "bounding box" method of detection, I was slightly confused. I looked around to see on what it was, I see the pros and cons, one con being that it's difficult to work with shapes that aren't fully square and leave spaces which usually let off the Collision checker to return a collision detected, anyway, that isn't the problem.
I found the main problem for me to actually write it in terms of BYOND. Here is my base movement system:
#define PX_STEP 8 mob animate_movement = 0 proc px_step(var/dir). if(NORTH&dir) pixel_y+=PX_STEP if(SOUTH&dir) pixel_y-=PX_STEP if(EAST&dir) pixel_x+=PX_STEP if(WEST&dir) pixel_x-=PX_STEP while(pixel_x>=32) pixel_x-=32 x++ while(pixel_x<=-32) pixel_x+=32 x-- while(pixel_y>=32) pixel_y-=32 y++ while(pixel_x<=-32) pixel_y+=32 y-- |
So this is where you all come in, I've searched all of BYOND for the bounding box, in the forums, libs/demos, everywhere. I need help creating a simple bounding box collision detection system. I was thinking something modular would be fine, Calus Corps's LineWalk demo helped a bit, but not enough for me to potentially write my own. So lead me to my first pixel based collision system :)
A small demo would be nice :)
Thank you all in advance.
Haywire
Posted by Haywire on Thursday, May 28, 2009 11:52AM
- 12 comments
(link)
/
(Edited on Thursday, May 28, 2009 12:27PM)
Login to post a comment.
#12 Kingstone99:
Haywire wrote:
> Kingstone99 wrote:
> > What happen to your CSS. This whole blue nothingness seems haywire to me :(
>
> I'm not bothered with writing myself a CSS anymore, too troublesome.
>
Haywire how can you be Haywire without a CSS!
Tuesday, June 09, 2009 06:07PM
#11 Haywire:
Kingstone99 wrote:
> What happen to your CSS. This whole blue nothingness seems haywire to me :(
I'm not bothered with writing myself a CSS anymore, too troublesome.
Tuesday, June 09, 2009 10:39AM
#10 Kingstone99:
What happen to your CSS. This whole blue nothingness seems haywire to me :(
Tuesday, June 09, 2009 02:44AM
#9 Haywire:
Jeff8500 wrote:
> I'd recommend the pythagorean theorem algorithm (IanPeregrine wrong a Dream Makers article with it), or the algorithm you find on gamedev.net when you google "Rectangle collision algorithm" (it's written in C++, but I was able to write it in DM months ago without any prior knowledge of C++).
Wait, he wrote the article using pythagorean theorem? :O
Friday, May 29, 2009 09:54AM
#8 Haywire:
Thank you everyone, I think I get the gist of it, let's hope I do when I get home :)
Friday, May 29, 2009 03:53AM
#7 Jeff8500:
I'd recommend the pythagorean theorem algorithm (IanPeregrine wrong a Dream Makers article with it), or the algorithm you find on gamedev.net when you google "Rectangle collision algorithm" (it's written in C++, but I was able to write it in DM months ago without any prior knowledge of C++).
Thursday, May 28, 2009 08:17PM
#6 Alathon:
If the bounding boxes are always aligned with the grid (i.e. no rotated sprites), then its quite easy. Bounding sphere (in 2D) is still easier.
Consider the bounding box to have the following properties: x and y coordinate of the bottom left corner, as well as a width and a height. This gives you a minX, maxX, minY and maxY for each bounding box.
Testing intersection between two bounding boxes:
if(r1.minX > r2.maxX || r2.minX > r1.maxX || r1.minY > r2.maxY || r2.minY > r1.maxY) return false
proc/Intersects(mob/A, mob/B)
var
A_min_x = (A.x*32) - 32 + A.pixel_x
A_max_x = A_min_x + 32
A_min_y = (A.y*32) - 32 + A.pixel_y
A_max_y = A_min_y + 32
B_min_x = (B.x*32) - 32 + B.pixel_x
B_max_x = B_min_x + 32
B_min_y = (B.y*32) - 32 + B.pixel_y
B_max_y = B_min_y + 32
return !(A_min_x > B_max_x || B_min_x > A_max_x || A_min_y > B_max_y || B_min_y > A_max_y)
Totally untested, theoretically should work.
Thursday, May 28, 2009 03:09PM
(Edited on Thursday, May 28, 2009 03:19PM)
#5 Foomer:
For using circular collision:
Use a true get distance proc, such as the one from AbyssDragon's BasicMath library:
distance(atom/M,atom/N)
return sqrt((N.x-M.x)**2 + (N.y-M.y)**2)
Give each object a radius variable which determines the radius of the object's collision detection. A typical 32x32 circle would have a radius of 16. Typically a radius is about half the size of the object's icon.
Then use the distance proc to get the distance between two objects, subtract each object's radius var, and if the value is less than 0, they collide.
Depending on how large your your radius vars can get, I usually just check for objects in range(src, 1) and see if the object collides with any of those.
Thursday, May 28, 2009 03:06PM
#4 Haywire:
SuperSaiyanGokuX wrote:
> Using circles is actually not as complicated as it sounds... Really the only "complex" math needed is the Pythagorean theorem...
>
> You just need to keep track of each object's pixel center, which can be done via the following simple calculations:
>
> atom.PixelCenterX=atom.x*32+atom.pixel_x
> atom.PixelCenterY=atom.y*32+atom.pixel_y
>
> Then, you just plug those coordinates into a simple a^2+b^2=c^2 formula (the Pythagorean Theorem), where a=(atom1.PixelCenterX-atom2.PixelCenterX) and b=(atom1.PixelCenterY-atom2.PixelCenterY), and c will be the length of the hypotenuse of the triangle, IE the distance in pixels between their center points...
>
> Then, you just check to see if c is <= (atom1.PixelRadius+atom2.PixelRadius) where PixelRadius is simply a variable you define for each object that is equal to/approximately half the width of that object (so an object that is only 6 pixels wide will have a PixelRadius of 3, and object that is an entire 32 pixels wide will have a PixelRadius of 16, etc.)
>
> you also need a check to make sure that the objects are actually traveling towards each other before you trigger a collision with this method...
>
> Hmmm, I guess when you write it out, it sounds even more complicated, but it's really not, I swear...lol
Still finding it quite complicated :S.
Remember, first time round, also I've never had to use any formula when programming (I don't have much experience), so I find it difficult to apply maths, especially the pythagorean theorem, to programming.
I think I need to work with a square shape because it seems easier to understand mentally, if you could just explain the bounding "box" (instead of circle) in the DM-sense, then it would be most appreciated :)
Thursday, May 28, 2009 02:46PM
#3 SuperSaiyanGokuX:
Using circles is actually not as complicated as it sounds... Really the only "complex" math needed is the Pythagorean theorem...
You just need to keep track of each object's pixel center, which can be done via the following simple calculations:
atom.PixelCenterX=atom.x*32+atom.pixel_x
atom.PixelCenterY=atom.y*32+atom.pixel_y
Then, you just plug those coordinates into a simple a^2+b^2=c^2 formula (the Pythagorean Theorem), where a=(atom1.PixelCenterX-atom2.PixelCenterX) and b=(atom1.PixelCenterY-atom2.PixelCenterY), and c will be the length of the hypotenuse of the triangle, IE the distance in pixels between their center points...
Then, you just check to see if c is <= (atom1.PixelRadius+atom2.PixelRadius) where PixelRadius is simply a variable you define for each object that is equal to/approximately half the width of that object (so an object that is only 6 pixels wide will have a PixelRadius of 3, and object that is an entire 32 pixels wide will have a PixelRadius of 16, etc.)
you also need a check to make sure that the objects are actually traveling towards each other before you trigger a collision with this method...
Hmmm, I guess when you write it out, it sounds even more complicated, but it's really not, I swear...lol
Thursday, May 28, 2009 02:13PM
#2 Haywire:
SuperSaiyanGokuX wrote:
> It's always seemed to me that a circle was the best all-around shape (har!) for a collision detection algorithm...
>
> It's not quite perfect, either, but I think it matches most object shapes better than a box with corners sticking out...
>
> And the best part about using circles for collisons is that all you need to do is keep track of the radius of each object's boundary circle, and use a pixel distance check between their centers, and if that distance is ever less than or equal to the total of their boundary radii (and they're traveling towards each other, of course) then there's a collision...
>
> I only played around with this a long, long time ago on a side-project I started that never got off the ground, and I don't think I ever had it working quite right, but that's due to my own shortcomings of the time (I should revisit it sometime)
Yeah, although using it would be simple enough, building it would be difficult as it needs a more advanced mathematical algorithm than the bounding box. I want to start simple as this is my first time round and I want to get hold of the simple bits, the bounding box. Although simple compared to other algorithms, I still find it difficult.
So, do you have any idea of how I should come into this?
Thursday, May 28, 2009 01:48PM
#1 SuperSaiyanGokuX:
It's always seemed to me that a circle was the best all-around shape (har!) for a collision detection algorithm...
It's not quite perfect, either, but I think it matches most object shapes better than a box with corners sticking out...
And the best part about using circles for collisons is that all you need to do is keep track of the radius of each object's boundary circle, and use a pixel distance check between their centers, and if that distance is ever less than or equal to the total of their boundary radii (and they're traveling towards each other, of course) then there's a collision...
I only played around with this a long, long time ago on a side-project I started that never got off the ground, and I don't think I ever had it working quite right, but that's due to my own shortcomings of the time (I should revisit it sometime)
Thursday, May 28, 2009 01:30PM