Still having BIG problems with corner collisions!

Basically I've got a game scren containing lots of square blocks and a ball which is fired from a starting point and needs to bounce off the blocks realistically.

I've got most of it working but I'm having real trouble with corners. Check out the pic and I'll explain.



Firstly as all of the blocks have vertical and horizontal sides I'm not using any fancy maths to rebound a ball off an angled wall. I'm simply saying: If ball hits a vertical wall reverse the X coord; and If ball hits a horizontal wall reverse the Y coord. This works fine for the blocks and for the outer wall surrounding the game area.

I'm also doing a little extra thing to make it better and this is where my problems come in...

Look at the top three pictures. Say a ball is moving at an angle like in the first one, you can see how it should rebound. I do this by:

1) moving the ball to it's new position based on it's X and Y speeds.
2) checking the ball against the vertical line with a "circle and line intersect function" which returns True if there is a collision.
3) if there is a collision this means that the balls new coordinates have placed it slightly in the wall. Well sure I can reverse the X Speed but I can't leave the ball at those coordinates because it's in the wall!
4) So what I do is I find out how much it has gone into the wall by looking at the ball centre + ball radius (it's far right edge) and seeing how far into the wall it is (this distance is depicted by the red line in the second picture).
5) Then I set the ball's new X coordinate to be that calculated distance BACK from the wall (see 3rd picture where red line is that distance applied). This means that it still travelled the SAME distance. Get it? I hope so as that's where my problems come in...

The same technique is applied for hitting a horizontal wall (see pic 4)

Anyway, this works fine and is nice and realistic UNTIL I get to corners. Why? I'll explain...

Look at the bottom left pic. If the collision is detected and the ball is well into the corner, that's fine because my red lines (distance from wall edge to edge of ball which has a blue dot on) can be subtracted from the ball x/y coords and the ball is in a good position after the bounce.

Now look at the bottom right picture. A collision has occured but the ball is not very far into the corner. Note how neither the bottom or the right edge have actually touched the corner yet. Instead the ball has collided at about 4 and 5 o'clock roughly. So if I use my code before which gets the (vert and horiz) distance from the edge of the ball to the wall and uses it to reset the ball coords, the ball will be moved back TOO FAR. Really I need to calculate the SMALLER distances shown by the GREEN lines and use that to move the ball back from the wall. This will be accurate.

But how can I do that without loads of crazy vector maths, dot products, angles etc? I.e. simply. Maybe it's not possible OR maybe there's a different approach that will yield the same result that is not a "bodge" or an "ignore" if you see what I mean.

Basically I'm thinking that I need to know the coordinates of those 4 and 5 o'clock collisions, then I can work out the green distances. Perhaps I need to modify the cirlce/line insect code to return those coords...but that won't be easy with my current maths skills because I don't even understand how the circle/line intersect code works!

I'd really appreciate any feedback on this as I'm like a zombie today due to lots of late nights and early starts and my brain has ceased to function and I'm not seeing clearly any more, thanks! :-)

Personally I would check collisions based on where the ball will be next cycle and therefore you don't need to worry about things getting stuck in walls.

ie.. check the collision for x+xs before you actually move the ball... if there's no collision then do x=x+xs otherwise xs=-xs and don't move the ball, or move the ball enough so it's against the wall, this way you won't ever get the stuck in the wall syndrome.

Of course dealing with x and y at the same time becomes marginally more complex as if you reduce the amount you're going to move the x, you need to proportionally decrease the ys before you check the Y collision.

ie.
XS = 5
X+XS = Collision
Wall = X+3
Therefore move ball X=X+3 = 3/5ths Of the movement, therefore the ball needs to be checked for Y collision ( 3/5 of YS ) + Y. Otherwise the ball will be changing direction slightly.

Of course.. If you don't do the positioning of the ball against the wall for a collision you'll never have to worry about that.

I would suggest replacing the new dir calculation through a vector based one as it will work consistently with any surface of which you know its normal vector.
The new direction is just

OldDirection - 2*ScalarProduct(OldDirection, SurfaceNormal)

ScalarProduct(a,b) in 2D simple means a.x*b.x + a.y*b.y

Thanks Rob:

This is what I'm doing. I'm modifying my BallX/Y coords just for the check, and then if it's not safe I'm changing them so that the ball is in an accurate rebounded position, so it's never stuck.

Yeah I tried that but it's basically inaccurate as the ball reverses course BEFORE it hits the wall. It's only accurate if the ballspeed is exactly double the distance from the wall. If it's close to the wall, it should be position further away after rebound, or if it's far away it should be positioned close to the wall after rebound. OR if I position the ball against the wall as you also suggest, a portion of the distance travelled has been lost because the ball should have bounced some distance from the wall. This brings me back to the way I was doing things.

I see where you were going with this though, but both methods are not 100% accurate in the rebound amount. I had considered "regressing" the ball back from it's collision point (diagonally) until there was no collision (I did this sort of thing in a platform game for a guy landing on/in a platform after falling). But basically it's still not accurate as there is no rebound. I have to know how much to rebound by and that is hard to work out on corners.

Thank for your suggestions though, they confirm a path I already considered unless I'm misunderstanding you.

Dreamora: OK, Scalar Product = Dot Product. I have made some vector classes and should be able to try this out. I'm still wondering what happens on corners... Anyway, I presume you mean a Right Hand surface normal?

Dreamora: Something in that formula of yours is messed up or needs more explaining. The dot product of a couple of vectors is a pretty big number which I'm multiplying by two. Then if I simply "subtract" that from the x and y components of OldDirection, it will shoot off miles in the wrong direction. Do I have to do a square root on the dot product first or maybe apply the subtract in a different manner? Thanks for any help.

Args there is an error, forgot to add the direction vector. Scalar product gets the projected length of the original direction onto the surface normal and returns only a scalar, not a vector


vecOldDirection - 2*ScalarProduct(vecOldDirection, vecSurfaceNormal)*vecSurfaceNormal

I figured it out. Basically the Normal has to be NORMALISED into a unit vector and then multiplied by the NormalVector as you have done above. Here's my code:

Strict
Graphics 800,600,0

Global offsetX=400
Global offsetY=200

Global line:TVector = TVector.Create(100,200)
Global linein:TVector = TVector.Create(100,50)
Global lineout:TVector = linein.CreateCopy()
lineout.rebound(line)

Global Normal:TVector = line.CalcNormal() 'for display only

While Not KeyHit(KEY_ESCAPE)
	Cls
	line.draw(offsetX,offsetY)
	SetColor 0,255,0
	linein.draw(offsetX+line.x/2-linein.x,offsetY+line.y/2-linein.y)
	SetColor 0,0,255
	lineout.draw(offsetX+line.x/2,offsetY+line.y/2)
	SetColor 255,255,255
	normal.draw(offsetX+line.x/2,offsetY+line.y/2)
	Flip
Wend 

Type TVector
	Field x!
	Field y!

	Function Create:TVector(x!,y!)
		Local v:TVector = New TVector
		v.x=x
		v.y=y
		Return v
	End Function
	
	Function CreateFromPoints:TVector(x!,y!,x2!,y2!)
		'Point x2,y2 will be the end point so x,y is subtracted from it.
		'This is useful for creating a Distance vector.
		Local v:TVector = New TVector
		v.x=x2-x
		v.y=y2-y
		Return v
	End Function

	Function CreateFromVectorsAdded:TVector(v1:TVector,v2:TVector)
		Local newv:TVector = v1.CreateCopy()		
		newv.AddVector(v2)
		Return newv
	End Function

	Function CreateFromVectorScaled:TVector(v1:TVector, Multiplier:Double)
		Local newv:TVector = v1.CreateCopy()		
		newv.Multiply(Multiplier)
		Return newv
	End Function
		
	Function CreateFromVectorsSubtracted:TVector(v1:TVector,v2:TVector)
		'v2 will be the end point so v1 is subtracted from it.
		'This is useful for creating a Distance vector.
		Local newv:TVector = v2.CreateCopy()
		newv.SubtractVector(v1)
		Return newv
	End Function
	
	Method AddVector(v:TVector)
		x:+v.x
		y:+v.y
	End Method

	Method CalcLength!()
		'Calc the hypotenuese using the Pythagorean Formula.
		'(can also use square root of dot product of itself, which is the same formula)
		Return Sqr(x*x+y*y)
	End Method

	Method CalcNormal:TVector()
		'Returns a right hand normal
		Local v:TVector = New TVector
		v.x = 0-y
		v.y = x
		Return v
	End Method
	
	Method CalcSlope!()
		'Slope is change in y over change in x
		'Warning, if x is 0 this will return infinite.
		Return y/x
	End Method

	Method CreateCopy:TVector()
		Local v:TVector = New TVector
		v.x=x
		v.y=y
		Return v
	End Method
	
	Method CopyFrom(source:TVector)
		x=source.x
		y=source.y
	End Method
	
	Method DotProduct!(v2:TVector)
		Return x*v2.x + y*v2.y
	End Method

	Method Draw(StartX!,StartY!,DrawLastPixel=True)	
		DrawLine StartX,StartY,StartX+x,StartY+y,DrawLastPixel
	End Method
	
	Method Multiply(multiplier!)
		x:*multiplier
		y:*multiplier
	End Method

	Method Normalise()
		'Nomalises x and y components into range -1 to 1
		Local length!=CalcLength()
		x:/length
		y:/length
	End Method

	Method Rebound(Surface: TVector)	
		'Takes the current vector as the Old Direction and bounces
		'it off of a surface vector using angle of incidence = angle of reflection rule
		
		'First calc a normal to the surface.
		Local Normal:TVector = Surface.CalcNormal()
		'Make the normal into a unit vector.
		Normal.Normalise()
		'Now turn the normal vector into a projection vector.
		'and subtract twice from the old direction (this vector)
		Local dot! = Normal.DotProduct(Self)
		Normal.Multiply(dot*2)
		Self.SubtractVector(Normal)
	End Method
	
	Method Reverse()
		x=0-x
		y=0-y	
	End Method
	
	Method Rotate(angle!) 'clockwise
		Local tx# = (x * Cos(angle)) - (y * Sin(angle))
		Local ty# = (x * Sin(angle)) + (y * Cos(angle))	
		x=tx
		y=ty
	End Method
	
	Method Scale(multiplier!)
		x:*multiplier
		y:*multiplier
	End Method
	
	Method SubtractVector(v:TVector)
		x:-v.x
		y:-v.y
	End Method
End Type

Works very nicely thanks. Try changing the coords of the line vector to whatever.

Hopefully this will prove useful to others. Now I have to apply it to my ball code and see if it works on corners, fingers crossed!

Balls have one very usefull attribute: their normal direction is always collision point - center of sphere :) For two spheres this means vecCenter1 - vecCenter2 and then normalize it (just in case you ever do or need a circle circle bounce)

OK thanks. Anyway this new method rebounding works nicely at any angle but it still doesn't solve my corner problem.

Even with the new method I still have to reposition the ball after the circle/line intersection test so that the ball is OUTSIDE of the wall by the correct amount as if it bounced and travelled the same distance in the timeslice.

So if (in the example in the picture) I take the collision point to be the right edge and use that to work out how much to move the ball outside of the wall, that's fine for vertical walls but on a corner it's not fine as per the bottom picture. This problem has NOTHING to do with the code used for the rebound ANGLE - that's all fine. The problem is to do with where to reposition it after the rebound.

Now taking into account what you have said about the ball's normal direction and if I know the collision point I wonder if something can be worked out. But my brain has faded again, I need food...

isnt it just ...

you know the ditance the ball was going to move. (moveDistance)
you know the point of collision.
you therefore know the distance travelled to the collision point. (distanceToCollision)

the distance the ball will travel after the bounce would be
moveDistance-distanceToCollision


Of course you better hope you dont have a wall/corner too close otherwise the ball might end up inside another wall/corner.

When I wrote a simple billiards game what I ended up doing was something like this :

1. take Snapshot of all the balls.
2. subTimeSlice = timeSlice.
3. Repeat
4. Repeat each subTimeSlice until totalSubSlices = timeSlice
5. Move each ball by distance of SubtimeSlice
6. If ball collides with something and overlap > TOLERANCE
6.1 then restore balls, divide subtimeslice by 2 and start again from step 3
6.2 else calculate the new velocity vectors for the colliding objects.
7. EndLoop
8. EndLoop

Basically if I overlapped anywhere by an amount > acceptable amount of overlap ( 1 pixel for example ) then I would halve the timeslice and try again.
When the balls collided with anything the collision occured right on a subtimeslice so I only had to calculate the new velocities for the colliding objects. The next subtimeslice(s) would then move the ball and also cater for any other collisions that may occur.

This worked great and meant that even whacking the balls from a break all balls would bounce properly. Of course if things got really busy the game might just visibly slow down slightly but surprisingly it didnt happen often.

Of course the simple way round this problem is to make it so that the max speed of the ball is 1 pixel at a time and just increase your game core speed to compensate.

You could simplify corner collisions by moving the ball out of the collision by either the horizontal overlap or verticle overlap ONLY ( not both ) depending on which overlap is the smaller. Then only reflect the velocity based on that lines normal.

Alternatively, upon collision with 2 lines create a helper line perpendicular to the corner which crosses the corner and has an normal which is the average of both lines ( basically a diagonal which goes through the corner ). Then calculate penetration depth on this line to work out how much to move the ball out of collision.

Stevie

QuietBloke: Yep that does sound like the answer. I have now found a way to calculate the collision point (I didn't have it before, only the fact that there was a collision). Also your timeslicing info was very interesting thanks.

Rob: HAHA good one :-D

StevieG: Interesting ideas like the corner one, thanks.

Everyone writing an Arkanoid clone hits this problem. I even hit it when I wrote it in BASIC on the C64 ;)

I hit it again on the Amiga using AMOS Pro. Solved it by updating the ball position at 200Hz, the ball only ever moved one pixel at a time and my rebounds worked fine. Previously, the ball could hit a corner and get stuck in the y-plane, wiping out a whole row of blocks. Very frustrating :D

yeah that's what I was thinking, maybe detect a collision so got back and step through it.

My thought process when solving it on the Amiga was:

The ball is going to be at position fx:fy on the next move.

Will it hit a collision on 1 hitpoint? yes = hit a straight edge.
Will it hit a collision on 2 adjacent hitpoints? yes = we are bumping into a corner and we need to figure out if it was dead-on or off-centre and deal with that appropriately.
Will it hit a collision on 3 adjacent hitpoints? yes = we are almost managing to squeeze between two rows or columns of blocks, but we can use almost the same logic as if we hit a corner.

I do remember that I got it working to the standard of Amegas (best Amiga Arkanoid clone ever).

actually thinking about it.. detect a collision then go back and step through is probably not a good idea as it could actually miss a glancing blow.

if the ball is moving faster than 1pixel per update and it passes close to the corner it may end up not detecting that it had actually collided with the corner halfway through the move.

You'd be better off on every update to find the fastest moving object and then use that to determine how timeslices are required to ensure nothing moves more than 1 pixel per slice.

My way, the ball cannot possibly move more than one pixel per update. I remember that the speed of compiled AMOS Pro on an unexpanded A600 did limit me to 200Hz and therefore a max ball speed of 4 pixels per screen refresh.

That was plenty fast enough though ;)

I remember Amegas, and Crystal Hammer. Anyway, I've temporarily had to stop working on this because it was consiming FAR too much of my time. I was addicted to solving it and wanted to solve it but I everytime I seemed to be getting anywhere it would either fail or my head would go all fuzzy and distracted :-) I'll come back to it though as it MUST be possible, but no one has some definitive easy solution ... so far.