#60472 - Ultima2876 - Thu Nov 10, 2005 8:18 pm
I'm working on a 2D side crolling shooter, and I've got pretty much everything in except walls - well, fully anyway. The game is correctly detecting collisions with these walls, but I need to now make the walls bounce the player when the player hits them.
Problem is, how do I work out which way to bounce the player? Bearing in mind it will detect a collision with a tile, effectively, I need some way to work out which direction to bounce the player in. Two factors to take into account are that the player can move in 8 directions (and thus only needs to bounce in one of these 8 directions) and that the background moves at any angle 0-359 degrees (however, as said before, the player only needs to move in one of 8 directions after the bounce).
Any ideas of how to work out which way to bounce? (one of the problems that stops me from simply inverting the player's direction is that the player can be moving up or down while the wall moves left into the player - the player would invert direction and go down, if he was going up - problem.)
Final factor to take into account is that the walls can be hit from any side - the player could back into them from the right, go straight into them from the left, hit them from the top or the bottom..
Thanks for any help :P
#60503 - LOst? - Fri Nov 11, 2005 4:52 am
Is this system of yours used in any other game? I haven't seen advanced bouncing in any game.
Simply invert the player when hitting the wall. Remember that the wall isn't moving. It is your player that is. Scrolling the walls isn't the same as moving the walls. Your player knows the speed and should act on it only.
If your walls really move, and that is not based on the player's speed, the collision will require heavy math. maybe redesigning your game will help?
About the math... Do the walls have any angle data? If so, then get the slope of your player by using atan2 LUT. Seriously, I have stepped over my math grade now, so I better shut up before I mess things up.
EDIT: I have had the math for it for 3 years now, and I still can't understand it propperly. And even if that math works, it can't be applied to moving walls. Only the player must move. Anyways it requires angle data for your walls.
_________________
Exceptions are fun
#60511 - DekuTree64 - Fri Nov 11, 2005 6:57 am
It would probably be easiest to do with vector math, rather than angles. The formula for vector reflection is
vReflected = v - 2 * wallNormal * (wallNormal DOT v)
Then you can round the result to one of your 8 directions.
How to get the normal of the wall depends on how your level data is stored.
Can you give a bit more explanation of what you have to work with? Like, are walls defined as 2 endpoints of a line, or something tile based like a point and an angle within each tile? Or maybe a bitmap :)? (that would be scary)
Also, a screenshot might help to get a better idea what the goal is. I would agree with LOst that your design probably needs some chopping :)
_________________
___________
The best optimization is to do nothing at all.
Therefore a fully optimized program doesn't exist.
-Deku
#60531 - Ultima2876 - Fri Nov 11, 2005 1:46 pm
The walls use 1-bit per pixel collision masks. However, the bouncing doesn't need to be that accurate. Once it detects a collision, you can treat the tile as if it was a solid 8x8 square.
LOst - I tried inverting the player, but I didn't think of it this way... this gives me another idea to try... hopefully it'll be sucessful :P
Oh yeah, and most scrolling shooters I've seen have one-hit death with walls. I've yet to see one which doesn't do that =P
Thanks.
#60550 - thegamefreak0134 - Fri Nov 11, 2005 6:04 pm
You still haven't answered one important question. Are your walls moving or not? If not, you're set with the solutions here. If so, I might just have the formulas to help you, considering that that's what I'm studying right now.
Are you working in an area with gravity? If so, and you want to bounce along the ground, remember that you shouldn't simply invert the y speed as this will result in exactly the same hight, and the fall/bounce loop will never end. To combat this, you must reduce the speed upon the bounce. Of course, if you won't be bouncing along the ground, don't worry about it, as side bounces should not need to account for this.
_________________
What if the hokey-pokey really is what it's all about?
[url=http:/www.darknovagames.com/index.php?action=recruit&clanid=1]Support Zeta on DarkNova![/url]
#60565 - Ultima2876 - Fri Nov 11, 2005 8:32 pm
There's no gravity, and the walls scroll past the player. No, they don't actually move on the map, however, the illusion is that they move.
Not sure how you define "move" - they move on the screen. Anyways, as I said, I've got a plan, and I think it might work =P
#60592 - SittingDuck - Sat Nov 12, 2005 10:51 am
I'd like to point out that if the collision test doesn't have to be that accurate, scrap the collision mask and just use rectangle to rectangle collision testing. It'll be faster.
First check which side of the object the character has hit. If it's on the left or right, invert the xspeed. If it's on the top or bottom, invert the yspeed.
Also to avoid the character falling through the edge of the object, allow the character to stand on a small amount of empty space either side of the object. Although this seems strange many games have this and it's quite aesthetically pleasing.
#60602 - tepples - Sat Nov 12, 2005 4:10 pm
| LOst? wrote: |
| Is this system of yours used in any other game? I haven't seen advanced bouncing in any game. |
Pinball? Pinbot? High Speed? Metroid Prime Pinball?
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#60608 - LOst? - Sat Nov 12, 2005 5:51 pm
| tepples wrote: |
| LOst? wrote: | | Is this system of yours used in any other game? I haven't seen advanced bouncing in any game. |
Pinball? Pinbot? High Speed? Metroid Prime Pinball? |
What I meant is I have never seen collision between a ball and a moving wall (such as a moving level). In pinball, the walls and bumpers are static and not moving.
_________________
Exceptions are fun
#60611 - tepples - Sat Nov 12, 2005 6:12 pm
| LOst? wrote: |
| In pinball, the walls and bumpers are static and not moving. |
What are the flippers?
Galactic Pinball for Virtual Boy has several different kinds of moving platforms.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#60614 - Ultima2876 - Sat Nov 12, 2005 7:34 pm
The collision mask system is as accurate as I want it to be, and as fast as I need it to be ;P
Lets not turn this into a debate about what the best method of handling collisions is - there's enough of those around and I've chosen the one I think is best for my game. Thanks for the tip though ^_^
Note this is a space shooter, not a platformer. There's no gravity, and the palyer doesn't stand on anything =P
And yeah - SittingDuck, you're getting close to the solution I'm working with at the moment - the only thing is, how do I work out (accurately) which side of the object the player hit? I'm thinking of using if Xmax > TileXmin then it's a left hit etc, but the problem here is if both the X and Y overlaps - which it can, quite easily, given that the tiles are 8x8... it causes a diagonal bounce, which is not always correct. Anyway, I'm still fiddling with this, so any input is appreciated.
Thanks everyone =P
#60616 - SittingDuck - Sat Nov 12, 2005 10:13 pm
if (charLeft > objLeft) and (charRight < objRight) and (charBottom <= objTop) then the character is above the object.
Just change this slightly for each side.
Alternatively, if you want extra bouncing a little off the side of the object it is like this:
if (charRight > objLeft) and (charLeft < objRight) and (charBottom <= objTop) then the character is above the object or slightly off to one side.
At least I think that's how it is. There's a small amount of information about this right in the middle of a big fat book somewhere. It's just a matter of spending a few hours trying to find it! Also note that if the character is already overlapping with the object then the character will pass straight through it.
Just use some logic and experiment.
#60620 - LOst? - Sun Nov 13, 2005 12:14 am
| SittingDuck wrote: |
| There's a small amount of information about this right in the middle of a big fat book somewhere. It's just a matter of spending a few hours trying to find it! |
I want that book!
| Quote: |
What are the flippers?
Galactic Pinball for Virtual Boy has several different kinds of moving platforms. |
Player against objects is one thing. But when the whole level is treated like an object, that will be too much info to handle.
_________________
Exceptions are fun
#60622 - Ultima2876 - Sun Nov 13, 2005 12:47 am
I dunno LOst, I say it's down to how you handle it..
#60642 - LOst? - Sun Nov 13, 2005 5:25 am
| Ultima2876 wrote: |
| I dunno LOst, I say it's down to how you handle it.. |
I can't even spell bounc. What do you expect of me?
_________________
Exceptions are fun
#60652 - SittingDuck - Sun Nov 13, 2005 9:49 am
Jobe Makar's Flash MX Game Programming Demystified.
Yes, I know that we're doing GBA programming right now, but some quite complex physics/collision reaction stuff is in there. That's where I learnt from. There's probably a book out there for collision reactions on the GBA, or some similar platform.
Just think, before I had that book my collision detection consisted of looping through all the pixels in one square, and for each of these pixels I looped through all the pixels in the other square. If two pixel coordinates were the same, the two rectangles were touching. The code took a few seconds to check all 3 rectangles.
I'm certainly much wiser now!
Amazon
Safari.Peachpit - you can actually read parts of it for 14 days here!
#60675 - LOst? - Sun Nov 13, 2005 5:31 pm
| SittingDuck wrote: |
Jobe Makar's Flash MX Game Programming Demystified.
Yes, I know that we're doing GBA programming right now, but some quite complex physics/collision reaction stuff is in there. That's where I learnt from. There's probably a book out there for collision reactions on the GBA, or some similar platform.
Just think, before I had that book my collision detection consisted of looping through all the pixels in one square, and for each of these pixels I looped through all the pixels in the other square. If two pixel coordinates were the same, the two rectangles were touching. The code took a few seconds to check all 3 rectangles.
I'm certainly much wiser now!
Amazon
Safari.Peachpit - you can actually read parts of it for 14 days here! |
Well, that book is where my knowledge come from, actually. It's still too much square root and floating point to be GBA friendly, but without it I would be blind.
_________________
Exceptions are fun
#60689 - SittingDuck - Sun Nov 13, 2005 9:52 pm
| LOst? wrote: |
| Well, that book is where my knowledge come from, actually. It's still too much square root and floating point to be GBA friendly, but without it I would be blind. |
Wow, really? That's a coincidence.
#60702 - LOst? - Sun Nov 13, 2005 11:51 pm
| SittingDuck wrote: |
| LOst? wrote: | | Well, that book is where my knowledge come from, actually. It's still too much square root and floating point to be GBA friendly, but without it I would be blind. |
Wow, really? That's a coincidence. |
That's why I asked :P
I had a feeling there was only one book.
_________________
Exceptions are fun
#60769 - SittingDuck - Mon Nov 14, 2005 6:17 pm
| LOst? wrote: |
I had a feeling there was only one book. |
lol!
#60807 - Miked0801 - Mon Nov 14, 2005 11:49 pm
Relative velocities people. It doesn't matter if the wall hits the ball or the ball hits the wall - it's the relative velocity between the 2 objects the affects the collision. Now onto diagonal bouncing. A couple ways to do this. 1 - See if top edge collided before the side edge and bounce that way. On a tie or very close, bounce diagonally. This just requires a couple of dot products and compares - very quick. 2. Check the pixel location in the object of the collision. Bounce according to the angle to the center (treat like a round object), or based on a table of locations per pixel.
I'd go for the vector based solution - it is works for any velocity, is 100% accurate, works for all angles, and is probably faster than a mask check system. What happens to your collision system right now if the relative velocities of the objects colliding is higher than the size of your collision area? Bad things more than likely :)
#60821 - LOst? - Tue Nov 15, 2005 4:15 am
| Miked0801 wrote: |
Relative velocities people.
I'd go for the vector based solution - it is works for any velocity, is 100% accurate, works for all angles, and is probably faster than a mask check system. What happens to your collision system right now if the relative velocities of the objects colliding is higher than the size of your collision area? Bad things more than likely :) |
Please teach me vector collisions! Please! (I don't have time for 8 years of school)
When having two object moving against eachother, there is a bigger risk of falling through because of the combined speed. Since I don't know vector math, I say it is impossible to have a moving level (walls) and a moving object (player) and make them collide perfectly.
_________________
Exceptions are fun
#60926 - tepples - Wed Nov 16, 2005 3:04 am
| LOst? wrote: |
| When having two object moving against eachother, there is a bigger risk of falling through because of the combined speed. Since I don't know vector math, I say it is impossible to have a moving level (walls) and a moving object (player) and make them collide perfectly. |
As long as the player's motion relative to the walls isn't bigger than the size of a metatile you shouldn't have too much of a problem. Super Mario Bros. for NES used 16 pixel metatiles and probably didn't use vector collision.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#60985 - sgeos - Wed Nov 16, 2005 3:03 pm
| tepples wrote: |
| As long as the player's motion relative to the walls isn't bigger than the size of a metatile you shouldn't have too much of a problem. Super Mario Bros. for NES used 16 pixel metatiles and probably didn't use vector collision. |
What if I represent my stages using lines and circles? I can't move faster than my radius or I risk fall through lines.
-Brendan
#61001 - Miked0801 - Wed Nov 16, 2005 6:07 pm
| Quote: |
What if I represent my stages using lines and circles? I can't move faster than my radius or I risk fall through lines |
Not true. Vector math allows you to detect quickly which side of a line (vector) a given point resides. Here's the collision routine in a nut-shell:
1. If needed, cull out other lines on the level to reduce checks. For smaller levels, not needed. I'll assume 2D, but the process is very similiar for 3D.
for(i=0; i<number of lines to check; i++)
{
Form a vector from the last tic's position to the base point of the pontential colliding line. Calculate only the Z component of the cross product between this vector and the line vector. We only care about the sign of result - though a 0 means directly on the line.
Form a vector from the current tic's position to the base point of the line and do the same math.
If(the sign of the first result is different from the sign of the second (one positive, one negative), you have crossed this collision line and a potential collision has occured)
else go to next line
Now, we need to check to see if the collision point was within the bounds of the line. I take a shortcut and just use the new position for this check, but you could calculate the actual intersection if you wished.
To check for inclusion on the line segment, take the same curpos vector formed above and do a dot product against the line vector.
If(the value is less than zero or greater than the magnitude of the linevector * magnitude of the velocity vector (unit vectors for the line segment help here) it is outside the edges of the line and no collision has occured)
else
a collision has occured. Do what you will. If you decide to reflect, you have a nice line vector already to work with.
}
As you can see, this solution is velocity independant. If the walls were moving as well, then you'd just use the previous tic's wall position against the current tic's wall position for the collision check. The only issue with this is quickly calculating the point of intersection between the wall and the hero if you need to place them "on the ground".
#61069 - LOst? - Thu Nov 17, 2005 4:14 am
Okay Miked0801. You make it sound very easy.
What we need is dot product and cross product.
I have a line from point 10,10 to 90,30. I have a circle at coordinate 5,5, with a x speed of 3 and a y speed of 17. The circle has a radius of 4 pixels.
Now what is a vector? How do I define a vector? How do I know what angle the circle is moving, and the angle of the line? From my book, a vector is something "great" and has a "direction" (very helpful). I still don't know how you can do this without using trigonometry. And in the end, square root must be used which will kill the game speed. And don't forget, if the circle is colliding on two lines at the same time.... yea, at this point I gave up that form of collision handling.
_________________
Exceptions are fun
#61076 - tepples - Thu Nov 17, 2005 4:35 am
| LOst? wrote: |
What we need is dot product and cross product.
I have a line from point 10,10 to 90,30. I have a circle at coordinate 5,5, with a x speed of 3 and a y speed of 17. The circle has a radius of 4 pixels.
Now what is a vector? How do I define a vector? |
You may have asked: "What is the matrix?" First we have to explain the prequel: "What is the vector?" This Wikipedia article gives an introduction.
The line segment is an origin (10,10) and a displacement vector (80,20) from the origin. Equivalently, it is an origin (90,30) and a displacement vector (-80,-20) from the origin. The difference is that one is a floor and the other is a ceiling; one popular convention is that floors are stored with positive X displacements and ceilings are stored with negative X displacements.
| Quote: |
| How do I know what angle the circle is moving, and the angle of the line? From my book, a vector is something "great" and has a "direction" (very helpful). I still don't know how you can do this without using trigonometry. |
Projection onto the normal line using dot products help the trigonometry cancel out.
| Quote: |
| And in the end, square root must be used which will kill the game speed. |
Unless you cache the reciprocal of the line segment's length ((Δx?+Δy?)^(-0.5); there are fast ways to compute this) when you compile or load the level. Then you multiply the displacement vector by this reciprocal to get a unit vector along the wall. (A "unit vector" is a vector of length 1, generally stored in a fixed-point or floating-point format.) Rotating this unit vector by 90 degrees (the poor man's cross product) gives you the unit normal vector, which a lot of the collision detection and response algorithms use heavily. (A "normal vector" is a vector perpendicular to a given line or plane.)
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#61086 - LOst? - Thu Nov 17, 2005 6:29 am
Tried to find more info about cross product in 2D space. "The cross product is really a 3D thingy, which do not have sense in a 2D world."
So that means, we can't use it in GBA programming. Trigonometry is the only way unless you can prove differently.
_________________
Exceptions are fun
#61087 - gladius - Thu Nov 17, 2005 6:35 am
The 2D cross product is well defined. You rotate one vector counter-clockwise by 90 degrees and take the dot product.
It ends up looking like this:
cp2d = v1x * v2y - v1y * v2x;
#61145 - tepples - Thu Nov 17, 2005 5:43 pm
| LOst? wrote: |
Tried to find more info about cross product in 2D space. "The cross product is really a 3D thingy, which do not have sense in a 2D world."
So that means, we can't use it in GBA programming. Trigonometry is the only way unless you can prove differently. |
Cross product is really just a way to get normal vectors. But in 2D you can just rotate a vector by 90 degrees to get a normal vector.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#61211 - Miked0801 - Thu Nov 17, 2005 11:17 pm
| LOst? wrote: |
Okay Miked0801. You make it sound very easy.
What we need is dot product and cross product.
I have a line from point 10,10 to 90,30. I have a circle at coordinate 5,5, with a x speed of 3 and a y speed of 17. The circle has a radius of 4 pixels.
Now what is a vector? How do I define a vector? How do I know what angle the circle is moving, and the angle of the line? From my book, a vector is something "great" and has a "direction" (very helpful). I still don't know how you can do this without using trigonometry. And in the end, square root must be used which will kill the game speed. And don't forget, if the circle is colliding on two lines at the same time.... yea, at this point I gave up that form of collision handling. |
Ok, let's ansewr a few basic questions. What is a vector? It is a direction with magnitude. It also can represent a single point of space or a few other things as well.
A vector is defined (in 2D space) as 2 numbers - usually an X and Y value.
"What angle is my circle moving... " Stop - if you do this correctly, you don't care what angle your circle is moving. Vector math eliminates all the sin/cos/tan/etc stuff and replaces them with simple operations. If you really need to know angles, there are a couple identities than translate vectors to angles, but are very rarely needed.
"and in the end a square root" - the above solution I have for you does not need a normalized vector. It would work fine as long as you knew the magnitude of your velocity and the wall's length. It simplifies the math a bit to have normalized vectors, but these can can pre-calculated and stored as long as your walls aren't rotating.
"and if the circle is colliding with 2 lines" then you choose the collision that occured first. The magnitude of the Cross product value is proportional to the closest point between the line and end point of your movement. You just take the smaller value of the 2 line checks and go from there.
Now to your problem
I have a line from point 10,10 to 90,30. I have a circle at coordinate 5,5, with a x speed of 3 and a y speed of 17. The circle has a radius of 4 pixels.
Your line would be stored as the vector (90 - 10), (30 - 10) or [80,20]. It's origin is 10,10. Your circle begins at 5,5 and next tic will be at 13,22. To check for a collision, we do the following as per my post:
" Form a vector from the last tic's position to the base point of the pontential colliding line. Calculate only the Z component of the cross product between this vector and the line vector. We only care about the sign of result - though a 0 means directly on the line. "
The vector from the base of the line to the last tic is (5 - 10, 5 - 10) or [-5, -5]
The Z component of the cross product between this value and the line's vector is [-5, -5] X [80, 20] = -5 * 20 - -5 * 80 = -100 + 400 = 300
From the current tic's position we get [13 - 10, 22 - 10] = [3, 12]. The Z cross of this is [3, 12] X [80,20] = 3*20 - 12*20 = -180.
The signs of the 2 values differ, we crossed the line this tic.
Now, see if the collision happened within the line as per my email:
[3, 12] dot [ 80,20] = 3 * 80 + 12 * 20 = 240+240 = 480. The number is positive so we know we're not off one side. Now if we didn't want to store magnitudes, we could form vectors from the cur pos and the other end of the line, but I'll follow my own advice and assume we know that (pre-calculated) the line has a magnitude of 82.5. Our velocity has a magnitude of (9 + 144)^.5 = 12,4. Multiplying them together gives 10,230. 480 is much less than 10,230 so we have a collision.
If I had wanted to avoid the magnitude check, I could have formed them vector [-80, -20] for the wall and (13-90, 22-30) = [-77, -8] The dot product of this is -80 * -77 + -20 * -8 = 6320 which is positive so it is also on the line and therefore a collision as occured.
Throwing a radius in here instead of a point check just adds a couple of extra additions/subtractions. That's the beauty of circles with vectors - they work very well together.
All these calculations are very quick to execute and scale very well. You don't need to do any angles, and sins, and trig whatsoever. They work will fixed/float math and in many instances are much more accurate than the geometric side do to less roundoff. Vectors also scale to 3D/4D/nD without much difference in the math. Imagine trying to do 3D collision detection with angles and trig. Yuck. This is why I advocate the use of vectors whenever possible. This is why anyone who is serious about computer programming should have a strong grasp of vector math.
BTW, some (2D) identities for you
A dot B = A.x * B.x + A.y * B.y. Adding Z just adds + A.z * B.z.
A cross B = a whole bunch of terms that turn to 0 + A.x * B.y - A.y - B.x
A dot B = (Magnitude of A) * (Magnitude of B) * Cos(Angle between the vectors) can be used to find the angle between 2 vectors
A cross B = (Magnitude of A) * (Magnitude of B) * Sin(Smaller of the 2 Angles between the A and B)
One final note. Vectors are actually nX1 matrixes and therefore obey all matrix math laws. This becomes very important later on when doing other "fun" 3D math.
#61364 - LOst? - Sat Nov 19, 2005 8:21 am
Miked0801, thank you very much!
I applied your z cross check to my collision test project. It worked. But the circle will only detect a collision between the previous tick and this tick, so how can I put the circle on top of the line so it won't fall through next time?
Well, I don't understand your magnitude stuff at all. Do I need it? I need to detect multiple lines, and so that the circle will fall when an edge of a line has reached.
[quote]^.5[quote]
The power of .5? You got to be kidding here. Sure if you make a LUT table for every line, it will work, but still. As I said above, magnitude?
_________________
Exceptions are fun
#61387 - tepples - Sat Nov 19, 2005 6:24 pm
"Power of .5" is a square root. "Power of -.5" is a reciprocal square root. There is a BIOS call that computes a square root, and there are ARM assembly language functions that you can put in IWRAM if you need it to be even faster.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#61520 - LOst? - Mon Nov 21, 2005 4:09 am
Still I don't get where he gets the number 144?
| Quote: |
| (9 + 144)^.5 = 12,4 |
_________________
Exceptions are fun
#61524 - tepples - Mon Nov 21, 2005 4:52 am
3*3 + 12*12 = 9 + 144
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#61687 - Miked0801 - Tue Nov 22, 2005 6:52 pm
Hey lost, your quoteline is not correct. A function calling itself is very legal and allows for some neat algorithms. Look up Recursion sometime :)
Also, look at the paragraph below the magnitude calc if you don't want to bother with magnitudes at all.
How to place the circle directly on the line? That's a bit more involved. Easier to either back up the circle to the previous tic's position or "bounce" the ball like the title of the thread. Deku's post should make a bit more sense now in how a reflection about any line is calculated :)
#61699 - tepples - Tue Nov 22, 2005 8:02 pm
| Miked0801 wrote: |
| Hey lost, your quoteline is not correct. A function calling itself is very legal and allows for some neat algorithms. Look up Recursion sometime :) |
Scheme allows recursion. C allows limited recursion (limited in that the standard does not require implementations to handle tail recursion in O(1) space). Fortran and possibly other languages of the olden days may not have allowed any recursion at all.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#61770 - LOst? - Wed Nov 23, 2005 4:42 am
| Miked0801 wrote: |
Hey lost, your quoteline is not correct. A function calling itself is very legal and allows for some neat algorithms. Look up Recursion sometime :)
Also, look at the paragraph below the magnitude calc if you don't want to bother with magnitudes at all.
How to place the circle directly on the line? That's a bit more involved. Easier to either back up the circle to the previous tic's position or "bounce" the ball like the title of the thread. Deku's post should make a bit more sense now in how a reflection about any line is calculated :) |
I know about recursion. I am using it in a few of my programs.
As for the circle... well pixel right now in my current test project, I really need it to be placed on top of the line really. If you know how to do it, please try to explain.
I tried the stuff you said below your magnitude explaination, and it sometimes work, but a lot of times, the pixel is falling through the inside of the line. I don't know why?
EDIT: One frame, I get 1360 and 100 as cross product answers, and the next frame I get -480 and -2320. For some reason it want through the line with no differ in sign!
I am going to try out the magnitude formula like tepples said. if the pixel still falls through the inside of the line, I will give up this form of collision detection.
I want my pixel to ride the line rather than bouncing on it. Imagine two lines drawn as a V shape, where the pixel has fallen into, at one point the pixel has touched both lines, and it will kinda get stuck. That's what I want. All other circle-line collision detections I have tried fall through the two lines.
Now when the pixel is bounching, I don't know what will happen if it gets into the V shaped lines.
_________________
Exceptions are fun
#61804 - Miked0801 - Wed Nov 23, 2005 7:56 pm
Your cross product answers should line up better than that between frames - as a matter of fact the newPos cross product should equal your old pos cross product. Either something else in the engine is playing with your positions outside of your collision check, you are having some nasty round-off in your calcs, or you've got some sort of error in your math. Please double check :) If your collision vectors enclose a convex area, you could also assume a negative number is always colliding (if within the line segment) in you wish. Be careful on how you create your vectors though if you go this route.
BTW, a quick shortcut for checking sign difference is to xor your 2 cross results and check the top bit. If the bit is set, the signs are different.
On the circle on line thing, it involves having a unit vector for each line segment to make things work well. You dot the position vector with the line unit vector which gives you a scalar. Multiply that number by each component of the unit vector and add the the base point. This returns the closest point along the wall to the center of your circle. Move outwards perpendicular to the wall the radius of your circle and that's the point you want. You could also directly solve for this with a cross product, but it's a bit messy as well.
In your V collision case, you would need to solve for the collision point on each vector, create a new temporary wall vector from these 2 points, and bounce off it - or just stop the movement completely on a double collide depending on your environ.
#65117 - sgeos - Fri Dec 30, 2005 10:30 am
Is there a simple way to get all this to work with fat lines?
I find myself tempted to draw lines from the tops and bottoms of one circle to another. Using lines with a thickness I could just draw a line from the center of one circle to another. I don't care if the ends of the lines behave strangely because I plan to cap them with circles anyway.
(ASCII diagrams would have been really cool, but they take too long to make. =)
-Brendan
#65526 - Miked0801 - Tue Jan 03, 2006 8:36 pm
Could work - here's how I would do it.
Create 2 lines - one for the top, on for the bottom of the fat line. Check to see if the vector crossed either of the lines and was between the shared end-points.
#65735 - sgeos - Thu Jan 05, 2006 10:28 am
If a circle is a fat point, than the circle/line collision test is a modified point/line collision test. If I add the width of the line to circle's radius and use the same test, is there any reason the results will not be accurate? (I'm hoping to give it a shot in the next couple of weeks... until then I'll blab here =)
-Brendan
#65789 - Miked0801 - Thu Jan 05, 2006 7:30 pm
Sounds good to me - give it a shot.
#66625 - sgeos - Thu Jan 12, 2006 3:28 pm
| Miked0801 wrote: |
| Throwing a radius in here instead of a point check just adds a couple of extra additions/subtractions. That's the beauty of circles with vectors - they work very well together. |
Where exactly?
This is what I have so far, does anything look silly?
| Code: |
// http://freespace.virgin.net/hugo.elias/routines/r_dot.htm
// http://freespace.virgin.net/hugo.elias/routines/r_cross.htm
typedef signed long s32;
typedef s32 vinternal_t;
typedef struct vector_t
{
vinternal_t x;
vinternal_t y;
vinternal_t z;
} vector_t;
typedef struct collision_t
{
vector_t o; // orgin
vector_t m; // magnitude
vinternal_t r; // thickness; "radius" in the case of a circle
} collision_t;
vinternal_t vectorDot2D(vector_t *pA, vector_t *pB)
{
return pA->x * pB->x + pA->y * pB->y;
}
vinternal_t vectorDot3D(vector_t *pA, vector_t *pB)
{
return pA->x * pB->x + pA->y * pB->y + pA->z * pB->z;
}
vinternal_t vectorCrossZ(vector_t *pA, vector_t *pB)
{
return pA->x * pB->y - pA->y * pB->x;
}
void vectorCross(vector_t *pResult, vector_t *pA, vector_t *pB)
{
pResult->x = pA->y * pB->z - pA->z * pB->y;
pResult->y = pA->z * pB->x - pA->x * pB->z;
pResult->z = pA->x * pB->y - pA->y * pB->x;
}
void vectorAdd(vector_t *pResult, vector_t *pA, vector_t *pB)
{
pResult->x = pA->x + pB->x;
pResult->y = pA->y + pB->y;
pResult->z = pA->z + pB->z;
}
void vectorSubtract(vector_t *pResult, vector_t *pA, vector_t *pB)
{
pResult->x = pA->x - pB->x;
pResult->y = pA->y - pB->y;
pResult->z = pA->z - pB->z;
}
void vectorCopy(vector_t *pResult, vector_t *pA)
{
pResult->x = pA->x;
pResult->y = pA->y;
pResult->z = pA->z;
}
int doesCollide(collision_t *pA, collision_t *pB)
{
vector_t curr = {pA->o.x, pA->o.y, pA->o.z};
vector_t next =
{
curr.x + pA->m.x,
curr.y + pA->m.y,
curr.z + pA->m.z
};
vectorCopy(current, &(pA->o));
vectorCopy(next, current);
vectorAdd(next, next, &(pA->m));
// TODO: Finish routine
} |
-Brendan
#66665 - Miked0801 - Thu Jan 12, 2006 8:12 pm
Alpha push happening here - I haven't forgot you :)
#66783 - sgeos - Fri Jan 13, 2006 2:49 pm
| Miked0801 wrote: |
I have a line from point 10,10 to 90,30. I have a circle at coordinate 5,5, with a x speed of 3 and a y speed of 17. The circle has a radius of 4 pixels. | LOst? wrote: | | Your circle begins at 5,5 and next tic will be at 13,22. |
|
Should not the next tic be (8, 22)?
| Miked0801 wrote: |
| Alpha push happening here - I haven't forgot you :) |
Reply as time permits.
This is my current best effort. It compiles without errors, but is untested. The FIXMEs above the main routine detail what I want to know how to do.
| Code: |
/*** Compile Options
*
gcc -Wall -c -o vector.o vector.c
*/
/*** References
*/
// http://forum.gbadev.org/viewtopic.php?t=7453
// http://freespace.virgin.net/hugo.elias/routines/r_dot.htm
// http://freespace.virgin.net/hugo.elias/routines/r_cross.htm
/*** Headers
*/
#include <math.h> // For the default sqrt()
/*** Macros
*/
// If the signs of the 2 values differ, we will cross the line next tic.
//
// A shortcut for checking sign difference is to xor the 2 cross results
// and check the sign bit. If the bit is set, the signs are different.
//
#define VINTERNAL_T_SIGN_BIT (1 << 31)
#define VINTERNAL_T_SIGN_DIFF(pA,pB) \
(((pA) ^ (pB)) & ~VINTERNAL_T_SIGN_BIT)
// Replace this with a function of your choice that works.
// This macro should return a vinternal_t.
//
#define VECTOR_SQRT(pA) ( (vinternal_t)sqrtf( (float)pA ) ) /* someSqrtFunc(pA) */
/*** Types
*/
typedef signed long s32;
typedef s32 vinternal_t;
typedef struct vector_t
{
vinternal_t x;
vinternal_t y;
vinternal_t z;
vinternal_t l; // precalculated length
} vector_t;
typedef struct collision_t
{
vector_t o; // orgin vector
vector_t m; // magnitude vector
vector_t v; // velocity vector
vinternal_t r; // thickness; "radius" in the case of a circle
} collision_t;
/*** Code
*/
vinternal_t vectorDot2D(vector_t *pA, vector_t *pB)
{
return pA->x * pB->x + pA->y * pB->y;
}
vinternal_t vectorDot3D(vector_t *pA, vector_t *pB)
{
return pA->x * pB->x + pA->y * pB->y + pA->z * pB->z;
}
vinternal_t vectorCrossZ(vector_t *pA, vector_t *pB)
{
return pA->x * pB->y - pA->y * pB->x;
}
void vectorSetLength(vector_t *pA)
{
vinternal_t x = pA->x;
vinternal_t y = pA->y;
vinternal_t z = pA->z;
vinternal_t lengthSq = x * x + y * y + z * z;
pA->l = VECTOR_SQRT(lengthSq);
}
void vectorCross(vector_t *pResult, vector_t *pA, vector_t *pB)
{
pResult->x = pA->y * pB->z - pA->z * pB->y;
pResult->y = pA->z * pB->x - pA->x * pB->z;
pResult->z = pA->x * pB->y - pA->y * pB->x;
vectorSetLength(pResult);
}
void vectorAdd(vector_t *pResult, vector_t *pA, vector_t *pB)
{
pResult->x = pA->x + pB->x;
pResult->y = pA->y + pB->y;
pResult->z = pA->z + pB->z;
vectorSetLength(pResult);
}
void vectorSubtract(vector_t *pResult, vector_t *pA, vector_t *pB)
{
pResult->x = pA->x - pB->x;
pResult->y = pA->y - pB->y;
pResult->z = pA->z - pB->z;
vectorSetLength(pResult);
}
void vectorCopy(vector_t *pResult, vector_t *pA)
{
pResult->x = pA->x;
pResult->y = pA->y;
pResult->z = pA->z;
pResult->l = pA->l;
}
// FIXME: pA is assumed to be a point. Should correctly handle lines for pA.
// FIXME: pB is assumed not to move. Should correctly handle movement for pB.
// FIXME: Does not take collision_t thickness into account.
//
// RETURNS:
// 0 = no collision
// 1 = collision
//
int doesCollide2D(collision_t *pA, collision_t *pB)
{
vector_t workVector; // current tick to base of line
s32 currentZ; // Z = crossZ(currentTic, lineBase)
s32 nextZ; // Z = crossZ(nextTic, lineBase)
s32 hitDist; // distance from base of line
// Form a vector from the current tic's position to the base point
// of the pontential colliding line.
//
vectorSubtract(&workVector, &(pA->o), &(pB->o));
// Calculate only the Z component of the cross product between this
// vector and the line vector.
//
currentZ = vectorCrossZ(&workVector, &(pB->m));
// Z of the next tic and the line vector.
//
vectorAdd(&workVector, &workVector, &(pA->v));
nextZ = vectorCrossZ(&workVector, &(pB->m));
// A Z result of 0 is on the line. That is a collision.
//
// BUG: Does not take last frame into account.
//
if (0 == nextZ)
return 0;
// If the signs of the Z values are the same, we have not crossed
// the line this tic.
//
if ( !VINTERNAL_T_SIGN_DIFF(currentZ, nextZ) )
return 0;
// To check for inclusion on the line segment, take the same
// curpos vector formed above and do a dot product against the
// line vector.
//
hitDist = vectorDot2D(&workVector, &(pB->m));
// If(the value is less than zero or greater than the magnitude
// of the linevector * magnitude of the velocity vector (unit
// vectors for the line segment help here) it is outside the edges
// of the line and no collision has occured)
//
if (hitDist < 0)
return 0;
if ( (pA->v.l * pB->m.l) < hitDist )
return 0;
// else a collision has occured.
//
return 1;
} |
Is anything silly?
-Brendan
#66871 - crossraleigh - Sat Jan 14, 2006 1:10 am
Thanks Miked0801; I've been learning even if I haven't been posting.
| sgeos wrote: |
| I find myself tempted to draw lines from the tops and bottoms of one circle to another. Using lines with a thickness I could just draw a line from the center of one circle to another. I don't care if the ends of the lines behave strangely because I plan to cap them with circles anyway. |
I think that would cause a problem when one circle is below the other.
| sgeos wrote: |
| Miked0801 wrote: | | Throwing a radius in here instead of a point check just adds a couple of extra additions/subtractions. That's the beauty of circles with vectors - they work very well together. |
Where exactly? |
I don't know if this is what he meant, but here's how I understood it: If you take the line the object might collide with, along with the velocity of the object, and think of them both as parametric lines,* then the goal of the collision test as it stands is to determine if there is a point where the t values are equal. With circles, the goal would be to find the points where the lines are closest to one another, form a vector using them, then see if the vector's magnitude is less than the sum of the two radii.
It turns out that that's not a very expensive thing to do. Browsing around, I found this page very helpful.
* I'm not sure how common this term is. What I mean is a line segment that is defined by an origin and a vector. That way you can move along the line using single parameter t in the range [0, 1].
#66892 - sgeos - Sat Jan 14, 2006 4:06 am
| crossraleigh wrote: |
| sgeos wrote: | | I find myself tempted to draw lines from the tops and bottoms of one circle to another. Using lines with a thickness I could just draw a line from the center of one circle to another. I don't care if the ends of the lines behave strangely because I plan to cap them with circles anyway. |
I think that would cause a problem when one circle is below the other. |
What kind of a problem? The internal data looks something like this. The green shape is the player. The red shapes are the collision map. The text lists how this is stored in the program. I have working prototype, but the math is completely different. Vector math seems better.
| crossraleigh wrote: |
| sgeos wrote: | | Miked0801 wrote: | | Throwing a radius in here instead of a point check just adds a couple of extra additions/subtractions. |
Where exactly? |
I don't know if this is what he meant, but here's how I understood it: If you take the line the object might collide with, along with the velocity of the object, and think of them both as parametric lines,* then the goal...
*SNIP details* |
I suspect that there is either a simpler solution or a simpler way of wording the solution.
My primary goal is to detect collision between circles and wide lines. The current vector routine only handles points and lines. A circle to wide line algorithm will handle 98% of what I want to do. 98% is happy. Happy enough that when I get there I should probably work on something else. =)
Circle to wide line is a special case of wide line to wide line collision. Wide line to wide line collision could be really useful, so I want the general algorithm. In general, walls will not move. A moving wide line to unmoving wide line algorithm will handle 99.9% of what I will ever want to do.
Moving walls are really cool even if unecessary. Given the ability to correctly detect moving walls, I might change the stage design specification. If it can be easily done, fantasitic. If not, I'll skip it.
-Brendan
#66900 - LOst? - Sat Jan 14, 2006 6:19 am
| sgeos wrote: |
| Miked0801 wrote: | I have a line from point 10,10 to 90,30. I have a circle at coordinate 5,5, with a x speed of 3 and a y speed of 17. The circle has a radius of 4 pixels. | LOst? wrote: | | Your circle begins at 5,5 and next tic will be at 13,22. |
|
Should not the next tic be (8, 22)? |
Yea ;.;
This is why I can't get my formulas right. The speed of the ball is wrong, and when I use the right speeds, the formulas that Miked0801 explained will not be of any help.
_________________
Exceptions are fun
#66909 - sgeos - Sat Jan 14, 2006 9:38 am
| LOst? wrote: |
| This is why I can't get my formulas right. The speed of the ball is wrong, and when I use the right speeds, the formulas that Miked0801 explained will not be of any help. |
The formulas should be fine. Just replace all instances of the next tice location (13, 22) with (8, 22). I posted my attempt above. It compiles but remains untested.
Did Miked0801 tell you how to factor factor the radius into the collision detection routine? He made a "by email" comment a while back.
BTW, how is your collision detection/bouncing coming along?
-Brendan
#66947 - crossraleigh - Sat Jan 14, 2006 5:15 pm
| sgeos wrote: |
| What kind of a problem? The internal data looks something like this. The green shape is the player. The red shapes are the collision map. The text lists how this is stored in the program. I have working prototype, but the math is completely different. Vector math seems better. |
Sorry, I wasn't clear. I was talking about drawing lines from the actual tops and bottoms of the circles, without taking into account the slope of the lines. Doing that won't give the effect of a thick line when the circles are lined-up vertically. Does that make any sense?
#67201 - LOst? - Mon Jan 16, 2006 5:11 am
| sgeos wrote: |
| LOst? wrote: | | This is why I can't get my formulas right. The speed of the ball is wrong, and when I use the right speeds, the formulas that Miked0801 explained will not be of any help. |
The formulas should be fine. Just replace all instances of the next tice location (13, 22) with (8, 22). I posted my attempt above. It compiles but remains untested.
Did Miked0801 tell you how to factor factor the radius into the collision detection routine? He made a "by email" comment a while back.
BTW, how is your collision detection/bouncing coming along?
-Brendan |
I never got any e-mail, so I am as interested as you what that e-mail was all about.
I haven't worked on my test project mainly because I can't get it to work with only one example using wrong wrong speed. I am waiting for more info and maybe someday I will work it out. Right now I am into normal collision detection since it works better (normal = not vector math based). Remember that I want more than just bouncing. I want to run over the line.
The more I work with angles and other trig stuff, the more I see how fast and easy and fast +/- math is compared to those cross product multiplies. +/- is much faster than mul/div/sqrt.
_________________
Exceptions are fun
#67256 - sgeos - Mon Jan 16, 2006 2:47 pm
| crossraleigh wrote: |
| Sorry, I wasn't clear. I was talking about drawing lines from the actual tops and bottoms of the circles, without taking into account the slope of the lines. Doing that won't give the effect of a thick line when the circles are lined-up vertically. Does that make any sense? |
The PC side tool does all that. It can use floats and run as slow as my CPU is fast, so drawing lines from the tops and bottoms of circles isn't a big deal. If I get wide lines working I can replace 2 lines and 2 circles with one wide line, assuming the circles are of the same size. Thats a GBA side optimisation. (Lets me make bigger stages or not optimise somewhere else.)
-Brendan
#67292 - crossraleigh - Mon Jan 16, 2006 7:30 pm
How long does it take to test a collision with your method? Over the weekend I tried the technique I linked earlier and it was taking about 1 scanline per test. (I was using THUMB executing from ROM.)
I suspect most of that time was spent in the 2 divides that must be performed. (I had it return the distance squared to remove the square root.)
#67357 - sgeos - Tue Jan 17, 2006 10:40 am
| crossraleigh wrote: |
| How long does it take to test a collision with your method? Over the weekend I tried the technique I linked earlier and it was taking about 1 scanline per test. (I was using THUMB executing from ROM.) |
My code is untested. Rereading it I don't see any divides, but I might be blind. It's probably fast enough. It can be optimised if it needs to be.
| Quote: |
| I suspect most of that time was spent in the 2 divides that must be performed. (I had it return the distance squared to remove the square root.) |
Distance squared is the obvious optimisation.
-Brendan
#67378 - Miked0801 - Tue Jan 17, 2006 5:45 pm
I'm still here - but still dying in our alpha push. Keep the faith and I'll spend a half our or so going back over the code again :)
#67440 - sgeos - Wed Jan 18, 2006 3:41 am
| Miked0801 wrote: |
| I'm still here - but still dying in our alpha push. Keep the faith and I'll spend a half our or so going back over the code again :) |
Good luck with the alpha push! Don't die... I wan't to know how to turn a point into a circle. =)
-Brendan
#67474 - keldon - Wed Jan 18, 2006 10:10 am
Not sure how fast/slow this is but one way to do circle/line collision is to turn this into a line/line collision. Create a line from the centre of the circle the length of its radius perpendicular to the line your are checking it with. In 3d the cross product of the line with (0,0,1) will create a line in the correct direction but in the length of the line. This needs to be scaled to the length of the circles radius, which might make this slow because of the divide.
Well I'm sure there's a much quicker tried and tested way.
EDIT: You do not need to create a scale for each line. For each line do the cross product with (0,0, 1/lineLength) and then multiply by the radius of the circle. So each line would have 1/lineLength stored. This will at first create a line in the correct direction with a magnitude of 1, which you are then multiplying by the radius of the circle. No divides either, just 6 multiplies for the cross product (in 3d anyway) and another multiply to make it the length of the circle. If your object is not rotating then this stays constant and is therefore only one multiply. Well actually 2 multiplies for the cross product since you have two zero values so you do not need to multiply these at all.
EDIT 2: Another thing is that your line is from (circle.point - theVector). And then the vectors magnitude is doubled to become the length of the circles diameter.
EDIT 3: This does not like testing the collision between the end of the line and the circle. For this you do a circle / point collision test, which adds 4 multiplies to this (for testing the circle with the two vertices of the edge).
#67588 - LOst? - Thu Jan 19, 2006 5:30 am
I worked a little on vectors yesterday. I have everything working except this part:
| Code: |
// If(the value is less than zero or greater than the magnitude
// of the linevector * magnitude of the velocity vector (unit
// vectors for the line segment help here) it is outside the edges
// of the line and no collision has occured)
//
if (hitDist < 0)
return 0;
if ( (pA->v.l * pB->m.l) < hitDist )
return 0;
// else a collision has occured.
//
return 1; |
sgeos code is useful for me. I tried to make exactly as Miked0801 said, but neither his examples or sgeos code work.
I am using integers for all results including square root. Still that's not the real problem. The actual velocity length is not big enough to work in that function. Also I thought the use of vector math would be a way to skip square roots. Well, I guess i will get more info later in this thread to fix my problems.
_________________
Exceptions are fun
#67604 - sgeos - Thu Jan 19, 2006 10:59 am
If you can't get ints to work, use floats and link to the standard math library. This will horriblely slow down your system. Thats not a problem because you can remove the floats after everything works.
If you are not using source control back up your code before changing to floats.
-Brendan
#67620 - keldon - Thu Jan 19, 2006 2:58 pm
Brendan. Does that method I spoke of deal with the line / circle or collision for you. You should be able to test a circle against a fat line by adding the thickness of the line to the radius of the circle.
#67689 - crossraleigh - Thu Jan 19, 2006 10:13 pm
keldon, like you noted in an edit, the line drawn from the circle's center isn't necessarily perpendicular to the line segment. More importantly, circle-line intersection doesn't address circles with velocity, which was the problem sgeos had back on page 2.
When the circle has a velocity, there isn't a single center you can draw the line from. Once you've taken that into account, the page I linked works on the same idea as you.
Alas, sgeos didn't like it. :'(
#67706 - keldon - Thu Jan 19, 2006 11:55 pm
Can't a moving circle be represented as a parallelogram with the two diagonal edges derrived from like the method I spoke of (only that the direction is found using the direction of the circles movement and not the line), and the base derrived from the movement velocity of the circle? And of course the other collision test with the circle at both its start and end position against the two vertices of the line must be carried out too.
Although I know nothing line / polygon collision. These may be much more complicated.
EDIT: However I know that a line collides with a polygon if the line collides with any of the lines in the polygon OR one of the vertices of the line is contained within the polygon.
And testing whether a point is contained within a parallelogram can be done by testing whether an infinite line from the point in any one direction collides with any line of the polygon an odd number of times. If we assume the infinite line is facing directly up then the infinite line crosses any line if the point [from which the infinite line begins] is below the line AND point.x is between line.head.x and line.tail.x. Although there may be much simpler ways to test this.
#67745 - sgeos - Fri Jan 20, 2006 2:44 am
| keldon wrote: |
| Does that method I spoke of deal with the line / circle or collision for you. |
Testing it is on the todo list. It looks like it would detect a collision. It's probably better than the solution I came up with. (Rotate the point into the line's space and compare the radius to the distance above the line.) My solution doesn't handle fall through.
| crossraleigh wrote: |
| Alas, sgeos didn't like it. :'( |
The page looks fine. It just seems that there is probably a simpler explanation.
-Brendan
#67787 - keldon - Fri Jan 20, 2006 10:55 am
| Quote: |
| Testing it is on the todo list. It looks like it would detect a collision. It's probably better than the solution I came up with. (Rotate the point into the line's space and compare the radius to the distance above the line.) My solution doesn't handle fall through. |
The first solution I wrote does not handle fallthrough, but the second solution does.
| Code: |
/*
* Returns twice the area of the triangle a, b, c positive if a, b, c are ccw, and negative clockwise
*/
int area (Point a, Point b, Point c) {
return ((b.x - a.x)*(c.y - a.y)) - ((c.x- a.x) *(b.y - a.y));
}
|
For the poly contains method, first find the two edges in the polygon created where the points y value is between the y values in the edges (excluding vertical edges). You will now have 2 edges ab and cd. abcd will also be your 4 vertices in clockwise / anticlockwise. Point 'e' is contained in the polygon abcd if the sign for area(a,b,e) and area(c,d,e) are the same. So to recap, the first step is to iterate through the edges of your polygon (either clockwise or anticlockwise). Either 0 or 2 of these edges will collide with the line x = point.x. The first one you find makes ab, and the second becomes cd.
So long as this ball does not move too far within each frame and you don't have too many of them it should not be too much computation. The poly contains method I gave is 8 multiplies. Plus the 4 multiplies for each line in the line collision test(using CCW, not sure about mikes way). In short testing for parallelogram/line collision in my method takes 28 multiplies - is that a lot.
EDIT: I changed the algo from the traditional polygon contains method to remove 8 of the multiplies. It was 36 multiplies before.
#70430 - keldon - Mon Feb 06, 2006 11:45 am
Does anyone know a faster way to the way which I just posted. Not that I'm going to need it now, as we're going to use this in java on a PC - but it would be useful to know of the faster way.
#70440 - sgeos - Mon Feb 06, 2006 2:43 pm
I'm still wondering where the guru, Miked0801, puts his adds and subtracts to do circle to line collision. =)
I'm in no hurry, getting back to this is a few calls up the on the stack.
-Brendan
#70659 - Miked0801 - Wed Feb 08, 2006 1:21 am
And I'm still wondering how the &^$* I'm going to make our Alpha build a less than 2 weeks :)
I have time for quick chirps, but not the hour or so the dive and and see what's what with that code. I haven't forgotten...
#70669 - sgeos - Wed Feb 08, 2006 2:41 am
| Miked0801 wrote: |
| And I'm still wondering how the &^$* I'm going to make our Alpha build a less than 2 weeks :) |
We have until the end of the month to master over here. =)
-Brendan
#70906 - beckn - Thu Feb 09, 2006 2:21 pm
Interestinig post!!!
I guess i found what he meant by adds/subs:
I used Chasles to get this, it comes with 2/3 lignes of maths:
With O the center of the circle, H the point on the circle the closet to the line nd AB the segment:
AH dot AB = (AO + OH) dot AB
= AO dot AB + OH dot AB
and because OH orthogonal to AB
= AO dot AB
=> the dot part won't change if you consider the center of the circle or the closet point...
For the z part of the rot:
AH rot AB = (AO + OH) rot AB
= AO rot AB + OH rot AB
and because OH orthogonal to AB
= AO rot AB + ||OH|| x ||AB||x vector u (i will explain with it means later)
=AO rot AB + Radius x AB x vector u
vector u is a vector with a length of 1. u is orthogonal to AB and OH. H is closer to AB than O, so the abs(rot ) is lower.
=> AH rot AB = AO rot AB - Radius x AB if AO rot AB > 0
=> AH rot AB = AO rot AB + Radius x AB if AO rot AB < 0
if the guru could confirm that would be great ;)
i hope my english was ckear enough
#70948 - crossraleigh - Thu Feb 09, 2006 5:17 pm
Well, but, AB is a segment. OH is not always orthogonal to AB.
And there's still the problem of fall-through, right?
#71001 - beckn - Thu Feb 09, 2006 10:57 pm
H is the the closest point of the circle from AB, so OH is always orthogonal to AB, AB is parallel to the tangent at H
For the fallthrough, if i understood what it means, you just have to know that you cross one segment (with the dot)
#71182 - crossraleigh - Fri Feb 10, 2006 9:09 pm
Let me give an example.
If a circle has a center at (0, 0) and a radius of 1, and a line segment has one endpoint at (2, 2) and the other at (2, 4), then what point on the circle is closest to the segment? Is it not (0.707, 0.707)?
#71201 - beckn - Fri Feb 10, 2006 11:30 pm
well i was speaking of the closest point from the line, not from the segment, so in your example (0,1). But you're right, my solution doesn't work :(. I just check if this point cut the segment and that's definitly not waht we have to do. I have some other solutions that will solve the problem and i will post them when they won't be too shitty...
#82744 - keldon - Tue May 09, 2006 7:10 am
Wait, I think I have something [for fixed line / moving circle], but I have an exam in a while so when I've finished I'll get back to it - providing I can understand what I've just jotted.
EDIT: wait it might be almost the same as before. So far it is conceptually 4xCircle/Point test + 1xParallelogram/point test. I'm seeing whether part of this can be done with just adds or subtracts, or very few multiplies.
EDIT 2: a parallelogram/point test [in this case] can be reduced to a line/line test. Okay really must go.
EDIT 3: Nope, I see a case in which this doesn't work; and the fix leaves me back to my original solution. Maybe I need to think outside the box, because what I am doing at the moment is converting the problem into different geometric problems which have a viable divideless solution. Maybe it is a divide solution which equates to an addition and subtraction using a special case or something - will check this out later.
#110657 - keldon - Thu Nov 30, 2006 3:45 am
| sgeos wrote: |
I'm still wondering where the guru, Miked0801, puts his adds and subtracts to do circle to line collision. =)
I'm in no hurry, getting back to this is a few calls up the on the stack.
-Brendan |
Noooo, I've awoken the thread. I should be going to bed, but now I will have to convince myself I cannot figure it out tonight otherwise I will not be able to sleep.
Now I understand a few things but let me sleep and hope I remember what I think I understood!
#110677 - keldon - Thu Nov 30, 2006 10:06 am
Ok, here's what I've got.
A circle/line can be converted to a point/fat line(edit) by doing exactly what mike0801 said. And a point/fat line can be converted to a circle/line, therefore a circle/fat point can be converted into a point/fat line.
You start of with a unit vector for the cross of the line and multiply this by the radius of the circle you wish check it with to create your two offset vectors for your fat line. If the point is within this then there is a collision.
Only problem is checking wither the point is within this bound as this looks like an area contains method. To fix this you can multiply the unit's cross by half of the circles radius to determine the thickness of the fat line. You then use the same vector created from the unit of the cross with half of the circles radius to create a vector from the point in the opposite direction and check for collision with either of the edges of the fat line.
For a moving point you need (a) can go back to the first thing I said so you create a single vector using the unit cross*radius and check for collision against the vector of the moving point on either of the two outer lines for the fat line.
Last edited by keldon on Mon Feb 05, 2007 2:18 am; edited 1 time in total
#110679 - keldon - Thu Nov 30, 2006 10:38 am
Actually forget that 'halving' of the fat line, there is another way to test whether the point is within the square/bounds (of the fat line).
Point P collides with a vector pair vp on plane p if a line projected along plane p from point P collides with both vectors within vp (about 4 if statements). Point P is contained within vp on plane p if found to be contained within both vectors in vp via two CCW's.
So in our case we have point P, and four line segments.
| Code: |
bool collision(P, segments[] ){
VectorPair vp;
for ( i = 0; i < 4; i ++ ) {
if ( segment[i].contains(P)) {
vp.a = segment[i];
break;
}
}
for (; i<4; i++)
if ( segment[i].contains(P)) {
vp.b = segment[i];
return vp.contains (P);
}
}
} |
Plus a range test with the radius of the circle against the two points of the original line and we're fine. But I've just realised that this is what I have already said!!!
Last edited by keldon on Thu Nov 30, 2006 12:37 pm; edited 1 time in total
#110682 - keldon - Thu Nov 30, 2006 11:47 am
VectorPair.collides (along x plane) is simply checking whether the point is contained within the y bounds of two line segments, so is basically two bounds checks. VectorPair.contains is basically two CCW operations (4 multiplies in total).
If we want to do this with a moving line then you can convert the fat line (square) into a 6 sided polygon/point collision (3xVectorPair.collides() + 4 multiplies from 1xVectorPair.contains()) with 4xcircle.within(point P) methods. Along with tests for another 2 fat lines, but the polygon contains method (for a polygon with no reflex angles) only requires one VectorPair.contains method for a polygon of any size. Altogether the worst you could have for a movingCircle/line collision (or a vector/fatLine collision) is 12 multiplies!!!