Overlaps & Collision Detection
Overlaps & Collision Detection
Overlaps & Collision Detection
Overlaps & Collision Detection
Overlaps & Collision Detection
Overlaps & Collision Detection Overlaps & Collision Detection Overlaps & Collision Detection Overlaps & Collision Detection Overlaps & Collision Detection Overlaps & Collision Detection Overlaps & Collision Detection Overlaps & Collision Detection
Overlaps & Collision Detection Overlaps & Collision Detection
Overlaps & Collision Detection
Go Back  Xtreme Visual Basic Talk > > > > Overlaps & Collision Detection


Reply
 
Thread Tools Display Modes
  #1  
Old 12-23-2002, 05:21 PM
Iceplug's Avatar
IceplugOverlaps & Collision Detection Iceplug is offline
MetaCenturion

Retired Moderator
* Guru *
 
Join Date: Aug 2001
Location: Iowa, USA
Posts: 16,583
Default Overlaps & Collision Detection


Here is a little program that shows you what many different kinds of collision detection there is... (the BreakOut game is buggy... so don't get your hopes up).

The regular one, Function Contact(Control, Control) determines if two rectangular controls overlap.
It is important to use rectangular controls (i.e. no Lines, Timers, etc.)
The second Function QuadContact(Control, Control) determines what quadrant an object falls into (left, top, right, or bottom)... it returns a 1, 2, 3, 4, or 0.
The third Function LineContact(Line, Line) determines if two line controls cross. Again, note that they are lines.
The fourth (or whatever) Function Containment(Control, Control) determines if a control lies inside of another control.
The fifth Function LSContact(Line, Control) determines if a line goes through (somewhat) a control (I think there's a bug in it, though).
And I've included a sample of using the IntersectRect API to determine if two objects overlap.
This should be enough to help anyone figure out collision detection.
Attached Files
File Type: zip collisiondetect.zip (12.7 KB, 1594 views)
Reply With Quote
  #2  
Old 12-24-2002, 12:23 PM
Iceplug's Avatar
IceplugOverlaps & Collision Detection Iceplug is offline
MetaCenturion

Retired Moderator
* Guru *
 
Join Date: Aug 2001
Location: Iowa, USA
Posts: 16,583
Default Other files

And here is the explanation of how to do these collision tests.
Attached Files
File Type: zip cd2.zip (34.1 KB, 889 views)
__________________

Iceplug, USN
Quadrill 1 Quadrill 2 (full) Quadrill 3 JumpCross .NET Website is ALIVE! - DL Platform Tour for VB.NET! Posting Guidelines Hint: Specify your location in your user cp profile if you want compassion!
Reply With Quote
  #3  
Old 06-18-2003, 06:30 AM
Iceplug's Avatar
IceplugOverlaps & Collision Detection Iceplug is offline
MetaCenturion

Retired Moderator
* Guru *
 
Join Date: Aug 2001
Location: Iowa, USA
Posts: 16,583
Default

Updated module: I fixed the LSContact function so that it works 100% correctly.
Attached Files
File Type: bas CollisionDetection.bas (4.7 KB, 413 views)
__________________

Iceplug, USN
Quadrill 1 Quadrill 2 (full) Quadrill 3 JumpCross .NET Website is ALIVE! - DL Platform Tour for VB.NET! Posting Guidelines Hint: Specify your location in your user cp profile if you want compassion!
Reply With Quote
  #4  
Old 12-09-2003, 10:08 AM
Iceplug's Avatar
IceplugOverlaps & Collision Detection Iceplug is offline
MetaCenturion

Retired Moderator
* Guru *
 
Join Date: Aug 2001
Location: Iowa, USA
Posts: 16,583
Wink Getting Collision Detection to work for you

As in the module's function Contact, there is a function that determines if two controls overlap.

The idea is to determine if an object (let's call it an apple) and another object (let's call it an orange) are touching (touching is the same as colliding and the same as overlapping to the computer). I use the syntax below to determine if they have collided.
Code:
If Apple.Left < Orange.Left + Orange.Width And Orange.Left < Apple.Left + Apple.Width Then If Apple.Top < Orange.Top + Orange.Height And Orange.Top < Apple.Top + Apple.Height Then 'collision! End If End If
Note that this only checks collision upon execution, and does not check for collision even while it isn't running. This also does not apply to controls that do not have the Left, Top, Width, and Height properties (Line controls, for example, don't).
For continuous checks of collision, these If statements must be called after everytime the orange moves or everytime the apple moves, whether they move on the KeyDown event (they'd go into the KeyDown event), by Timer (they'd go into the timer), or by any other means (the If statements will have to tag along with the movement code).

To check collision between multiple objects in a control array, (let's say that there was a control array of oranges) the if statement must be inside of the For Loop.
Code:
For LV = Orange.LBound To Orange.UBound 'If the control array is contiguous. If Apple.Left < Orange(LV).Left + Orange(LV).Width And Orange(LV).Left < Apple.Left + Apple.Width Then If Apple.Top < Orange(LV).Top + Orange(LV).Height And Orange(LV).Top < Apple.Top + Apple.Height Then 'collision with orange LV! End If End If Next
What you do in the If statements is your business . Most tests for collisions in a control array are of three types:
1. Collectibles
2. Hazards
3. Barriers
In the case of collectibles (if you like oranges), then you'll just *collect* the orange:
Code:
Orange.Visible = False 'Eat it. OrangesEaten = OrangesEaten + 1 'Increment some counter of 'how many oranges you have eaten.
In the case of hazards, you may not really want to check *all* of them but only if the apple is touching any oranges (if you don't like oranges).
Code:
Apple.Visible = False 'Or however you want to denote 'that something bad has happened. LV = Orange.UBound + 1 'Exit the loop
Third case will be explained in next post.
Check out the simple example attached - it determines if Charmander is touching the Statue.
Good luck!
Attached Files
File Type: zip Touching.zip (3.1 KB, 423 views)
__________________

Iceplug, USN
Quadrill 1 Quadrill 2 (full) Quadrill 3 JumpCross .NET Website is ALIVE! - DL Platform Tour for VB.NET! Posting Guidelines Hint: Specify your location in your user cp profile if you want compassion!

Last edited by Iceplug; 12-10-2003 at 10:50 AM. Reason: Added a vb tag
Reply With Quote
  #5  
Old 12-10-2003, 12:52 PM
Iceplug's Avatar
IceplugOverlaps &amp; Collision Detection Iceplug is offline
MetaCenturion

Retired Moderator
* Guru *
 
Join Date: Aug 2001
Location: Iowa, USA
Posts: 16,583
Unhappy Running into the Walls

The third case above, Collision with Barriers, should be handled a little differently than the other two.
One method: Before the movement, alter the values that are being checked in the collision If statements so that collision is detected before the movement.
This method is excellent when using the RECT structure, because I can call the OffsetRect API to move the rectangle and then check for collision with IntersectRect API.
With controls however I'll end up with four collision detection statements in each case block.
More info on using RECTs to come .
Another method: Immediately after the movement.
(If you are using RECTs, I recommend the first method; this method should be used if you are using controls). After I have moved the 'apple', I will want to check if it has collided with any walls. Of course, I can use the good old collision formula:
Code:
If Apple.Left < Orange.Left + Orange.Width And Orange.Left < Apple.Left + Apple.Width Then If Apple.Top < Orange.Top + Orange.Height And Orange.Top < Apple.Top + Apple.Height Then 'collision! End If End If
In this case, I will not do anything to a control inside of the If statement (unless you want to--it gets messy, but the same principles as in Hazard collision can be applied), I just want to check if it has collided with any object.
In the collision If statement, I will only set a boolean variable to True:
Collision = True
and I will add a definition for Collision at the top of the procedure:
Dim Collision As Boolean
as it is in the example attached.

Now, what to do if this 'apple' has collided with any 'oranges'?
I only have to move the apple back in the direction that it moved originally.

Check out this attachment for Collectible Control Array and Barrier Control Array collisions.
Attached Files
File Type: zip Touching.zip (20.0 KB, 361 views)
__________________

Iceplug, USN
Quadrill 1 Quadrill 2 (full) Quadrill 3 JumpCross .NET Website is ALIVE! - DL Platform Tour for VB.NET! Posting Guidelines Hint: Specify your location in your user cp profile if you want compassion!
Reply With Quote
  #6  
Old 01-08-2004, 08:34 AM
Iceplug's Avatar
IceplugOverlaps &amp; Collision Detection Iceplug is offline
MetaCenturion

Retired Moderator
* Guru *
 
Join Date: Aug 2001
Location: Iowa, USA
Posts: 16,583
Default Collision using RECT structures.

Collision checking with a RECT structure is fairly simple if you use these three API functions:
IntersectRect, OffsetRect, SetRect.
Each has a role in the collision, movement, and placement of the apples and oranges.

For example:
You can start off by placing your objects into a rect structure with SetRect.
SetRect MyRect, 0, 0, 32, 32

You can move this RECT with OffsetRect.
OffsetRect MyRect, 8, 0
This will move it forward by 8 pixels.

To do collision detection with rects is easy. IntersectRect returns 1 if the RECTs specified as the 2nd and 3rd parameter intersect.
If IntersectRect(BufferRect, AppleRect, OrangeRect) Then
'they have collided.
End If
BufferRect is a dummy rect with nothing in it... you can have one for the whole project.

Check out the attachment. It uses RECTs for collision detection and BitBlt for drawing.
Attached Files
File Type: zip bltcollide.zip (10.3 KB, 371 views)
__________________

Iceplug, USN
Quadrill 1 Quadrill 2 (full) Quadrill 3 JumpCross .NET Website is ALIVE! - DL Platform Tour for VB.NET! Posting Guidelines Hint: Specify your location in your user cp profile if you want compassion!

Last edited by Iceplug; 01-31-2004 at 02:18 PM.
Reply With Quote
  #7  
Old 01-13-2004, 09:14 AM
Iceplug's Avatar
IceplugOverlaps &amp; Collision Detection Iceplug is offline
MetaCenturion

Retired Moderator
* Guru *
 
Join Date: Aug 2001
Location: Iowa, USA
Posts: 16,583
Smile Detecting Collision in a Tile Map

If you are making a tile based game, then there is an easier way (easier than the rectangular collisions above) of detecting a collision with a certain type of tile.

If you can access the tiles that you have from an array, then, you only need to check the tile that you are moving to against the tiles that you do not want to be walked on. If you have only one tile that you wish to keep the main character away from, then you check for that specific tile with an If statement.
Code:
If MapArr(MyX, MyY) = 1 Then Collided = True
where MyX and MyY are the coordinates of the player (sometimes, they need to be manipulated)

But, most of the time, you'll want to have more than one tile that you want to block (like a house, or a large rock, or maybe even a pool of water).
You can use a loop to iterate through the set of all the tiles that you don't want the main character to walk on.
Code:
Collided = False For LV = LBound(BlockedSet) To UBound(BlockedSet) If MapArr(MyX, MyY) = BlockedSet(LV) Then Collided = True End If Next
Note that there are many different ways to implement a tile based game.

In the attachment, I used the BitBlt API and a 2D array of Integers to make the map.
Attached Files
File Type: zip MapBlt.zip (45.4 KB, 347 views)
__________________

Iceplug, USN
Quadrill 1 Quadrill 2 (full) Quadrill 3 JumpCross .NET Website is ALIVE! - DL Platform Tour for VB.NET! Posting Guidelines Hint: Specify your location in your user cp profile if you want compassion!
Reply With Quote
  #8  
Old 01-29-2004, 06:27 PM
Iceplug's Avatar
IceplugOverlaps &amp; Collision Detection Iceplug is offline
MetaCenturion

Retired Moderator
* Guru *
 
Join Date: Aug 2001
Location: Iowa, USA
Posts: 16,583
Angry Inter-tile Collision in a Tile Map

In some cases, you may want your main character to move casually along your map (similar to the way the main character moves in the IntersectRect example).
This requires a bit more work, but it does let you get away with a little bit more, and if you're at this point, you've probably thought about using a non-tile based map, since you can probably do something similar with RECTs, ...
but a tile map is somewhat easier to store to file and to interact with than a RECT based map.

There are a few things that you'd have to change to existing map code to do this:
Code:
Private MyX As Currency, MyY As Currency 'Declared as currency to allow smooth stepping
You have to allow you character to actually move between a tile...
for instance, MyX = 6 and MyY = 3.25 means that the character is on column 6, 1/4 of the way to column 4 from column 3.
Your existing drawing code should allow you to draw at this point, since you are probably multiplying by 16 or 32 anyway.

Code:
Private Const TILESTEPDECIMAL As Currency = 0.25 'How much we step into the tile on each keystroke.
This is how much the player moves on each key press. You will probably want to make this number of some value 2^-n... the higher n is, the more steps the character takes to go between tiles. You'll also want to avoid making your steps too small
(say, if you were trying to make the character step 64 times, when your tiles are only 32 pixels wide)... it also may make your game boring because it takes forever to get from one tile to the next .

Now, about the collision detection:
Consider your character's location to be x=3.25, y=2.75.
At this location, you'd have to check for collision against (3,2), (3,3), (4,2), and (4,3).
You can easily generate these numbers with a ceiling function and a floor function...
Int in VB6 will perform a Floor operation for you... Floor(3.25) = 3
The Ceiling operation will require a bit more work, but you can use this function:
Code:
Private Function Celg(Number As Currency) As Integer Celg = -Int(-Number) End Function
Where Celg(3.25) = 4

Now, with these functions, you could implement your collision detection by doing this everytime:
Code:
If MapArr(Int(MyX), Int(MyY)) = BlockedSet(LV) Or MapArr(Celg(MyX), Celg(MyY)) = BlockedSet(LV) Then Collided = True ElseIf MapArr(Celg(MyX), Int(MyY)) = BlockedSet(LV) Or MapArr(Int(MyX), Celg(MyY)) = BlockedSet(LV) Then Collided = True End If
Each if statement checks the four tiles that the player could be on for collision.

In the first attachment, I went a few steps further and checked if it is necessary to check all four of these cases by inspecting the values of MyX and MyY to determine if they were integer values (5.0, 7.0).
The comments should explain what I was up to .
The second attachment is the implementation of the above article.
Attached Files
File Type: zip MapBlt.zip (46.7 KB, 244 views)
File Type: zip SimplerVersion.zip (46.2 KB, 280 views)
__________________

Iceplug, USN
Quadrill 1 Quadrill 2 (full) Quadrill 3 JumpCross .NET Website is ALIVE! - DL Platform Tour for VB.NET! Posting Guidelines Hint: Specify your location in your user cp profile if you want compassion!

Last edited by Iceplug; 01-31-2004 at 02:17 PM. Reason: Added old version with implementation of this article
Reply With Quote
  #9  
Old 02-22-2004, 06:33 PM
Iceplug's Avatar
IceplugOverlaps &amp; Collision Detection Iceplug is offline
MetaCenturion

Retired Moderator
* Guru *
 
Join Date: Aug 2001
Location: Iowa, USA
Posts: 16,583
Default

There's also a function in the module, Container, that determines if an object is "inside" of another object.

Usually, in a game, you will want to keep the character within some outer boundary, and this is what my bound-exit detection does.
This is not the same thing as the regular collision detection in the post #3. In collision detection, we are checking if the object is even slightly touching another rectangular object... here we are checking if the object is even slightly touching an area outside of another rectangular object.

Let's pretend we have an open backyard and a dog (on the form)... to determine if the dog is not totally within the backyard (if any hair of the dog is too far over):
Code:
If Dog.Left < Backyard.Left Or Dog.Left + Dog.Width > Backyard.Left + Backyard.Width _ Or Dog.Top < Backyard.Top Or Dog.Top + Dog.Height > Backyard.Top + Backyard.Height Then OutofBound = True End If 'It looks a little like the collision detection 'Except it uses ors and I am comparing left with left, 'top with top, etc.
Of course if OutOfBound is True, then you can do something to the dog... give it a treat or throw it in the sea, whatever.

You can apply this just like the collision detection code.

Something else to note: You may want to experiment with the inequalities (switch <, > with <=, >=) to get it to work differently.

In my example below, I use < and >... and this allows me to keep my Squirtle inside the box.
<= and >= will relax the boundary a bit... this one can be useful if you were pushing a box into a large hole.

You can also add a little supplemental offset to the check
Code:
If Dog.Left < Backyard.Left + L Or Dog.Left + Dog.Width > Backyard.Left + Backyard.Width - R _ Or Dog.Top < Backyard.Top + T Or Dog.Top + Dog.Height > Backyard.Top + Backyard.Height - D Then OutofBound = True End If

And you can substitute your own values for L, R, U, and D.

Here is an example of bound-exit detection.
Attached Files
File Type: zip Container.zip (2.7 KB, 229 views)
__________________

Iceplug, USN
Quadrill 1 Quadrill 2 (full) Quadrill 3 JumpCross .NET Website is ALIVE! - DL Platform Tour for VB.NET! Posting Guidelines Hint: Specify your location in your user cp profile if you want compassion!
Reply With Quote
  #10  
Old 05-24-2004, 11:58 AM
Iceplug's Avatar
IceplugOverlaps &amp; Collision Detection Iceplug is offline
MetaCenturion

Retired Moderator
* Guru *
 
Join Date: Aug 2001
Location: Iowa, USA
Posts: 16,583
Cool Boundary Collision Detection with API

Of course, you can also do something very similar using the API.
In the regular collision detection case, I used the IntersectRect API to determine if a rectangle is touching another one.

Here, we are trying to determine if a rectangle is touching the area surrounding a rectangle. Here, IntersectRect will not work for us... we need something else... a new API.

Well, there are only 3 really interesting 'operand-type' APIs... IntersectRect, UnionRect, and SubtractRect.
After a brief experimentation with these, you might find that SubtractRect will yield appreciable results for doing this kind of collision detection.
(See the Figure for how SubtractRect works also)
Code:
Private Declare Function SubtractRect Lib "user32.dll" (lprcDst As RECT, lprcSrc1 As RECT, lprcSrc2 As RECT) As Long
Interestingly enough, SubtractRect does not give you the same result if you switch the operands for lprcSrc1 and lprcSrc2...
SubtractRect will take the first rectangle, remove the intersection of the two rectangles (the area where both rectangles overlap) from the first recangle, and then the final result is then fitted to a rectangle.

How will this help us with collision detection? Well, if we have a small rectangle that is 'on' another rectangle, if we subtract the big rectangle from the small one, we should get nothing (an empty rect) from this operation.
However, if the small rectangle is touching the outside, this means the result rectangle will have a small strip along the outside of the plane.

Recall that these API functions returns 0 when the result rectangle is empty and usually 1 if the result rectangle is not empty.
So, if the small rectangle has collided with the outside, SubtractRect will return 1, otherwise 0 if we have not collided.

We can implement this with Rects and BitBlt like this:
Code:
If SubtractRect(dummy, Dogrect, Backyardrect) = 1 Then OutOfBounds = True End If

From here, you can check OutOfBounds to determine if you should throw your dog into a pond or move it back into the field.
Remember that the order matters... if you switch Dogrect and Backyardrect, you will be removing the Dogrect from the Backyardrect, which will be ineffective, since the removal of Dogrect from Backyard will be insignificant.

(In fact, if the operands to SubtractRect have different values for their Left, Top, Right, and Bottom, then only one of these orders will have some chance of effect)

Check out the attachment to see my SubtractRect collision detection.

Enjoy.
Attached Images
File Type: gif Rects.GIF (4.2 KB, 228 views)
Attached Files
File Type: zip Boundings.zip (17.4 KB, 193 views)
__________________

Iceplug, USN
Quadrill 1 Quadrill 2 (full) Quadrill 3 JumpCross .NET Website is ALIVE! - DL Platform Tour for VB.NET! Posting Guidelines Hint: Specify your location in your user cp profile if you want compassion!

Last edited by Iceplug; 06-12-2004 at 08:18 PM.
Reply With Quote
  #11  
Old 05-24-2004, 05:07 PM
Iceplug's Avatar
IceplugOverlaps &amp; Collision Detection Iceplug is offline
MetaCenturion

Retired Moderator
* Guru *
 
Join Date: Aug 2001
Location: Iowa, USA
Posts: 16,583
Red face Collision Detection with RECTs and 'infinitely small objects'

(Since there is already a large debate going on about acronyms, I will say small objects instead of ISOs.)

Well, most of the examples above covered collision detection between rectangles. There are some times where you do not need a rectangle to require a collision detection. One of which occurs when you have a small object (A really small width / height; the width and height are really really small ). Some examples are bullets, confetti, dust, electrons, raindrops, etc.

When the width is small and approaches zero, you may notice that the two collision detection techniques (IntersectRect vs. SubtractRect) become completely complementary... you can determine if a small object is in the rectangle by checking IntersectRect for 1, and if it is out of it by checking IntersectRect for 0.
Similarly, SubtractRect will yield 1 if it is out, and 0 if it is in. hmm 4 2-letter words in a row, all starting with i. They can't actually have 0-width and height, or they'll be labeled as empty rects.

So, you could use either of these for collision detection with small objects, but there is an easier way.
Since these rects are so small, we can approximate them as points, and just determine if the point is inside of the RECT. How to determine if the point is in the RECT?
PtInRect API!

And it's as easy to use as the IntersectRect API for collision.
Code:
If PtInRect(MyRect, Molecule.X, Molecule.Y) Then Collision = True End If
PtInRect will return a 1 if the point is in rect and a 0 if it isn't.

Check out the attachment and have fun.
Attached Files
File Type: zip PtInRect.zip (2.8 KB, 199 views)
__________________

Iceplug, USN
Quadrill 1 Quadrill 2 (full) Quadrill 3 JumpCross .NET Website is ALIVE! - DL Platform Tour for VB.NET! Posting Guidelines Hint: Specify your location in your user cp profile if you want compassion!
Reply With Quote
  #12  
Old 06-05-2004, 08:10 PM
Iceplug's Avatar
IceplugOverlaps &amp; Collision Detection Iceplug is offline
MetaCenturion

Retired Moderator
* Guru *
 
Join Date: Aug 2001
Location: Iowa, USA
Posts: 16,583
Arrow Collision detection on a side.

At times, it might be useful to determine which side of the rectangle our object collided.
It is possible. It has to be .
We can perform this check for boundary collision detect and regular collision detect.
The boundary collision case is real easy. Each case is explicitly checked as each condition:
Code:
If Dog.Left < Backyard.Left Or Dog.Left + Dog.Width > Backyard.Left + Backyard.Width _ Or Dog.Top < Backyard.Top Or Dog.Top + Dog.Height > Backyard.Top + Backyard.Height Then OutofBound = True End If
This can simply be broken into four If statements and checked like this.
Code:
If Dog.Left < Backyard.Left Then BCDSide = 1 ElseIf Dog.Left + Dog.Width > Backyard.Left + Backyard.Width Then BCDSide = 3 ElseIf Dog.Top < Backyard.Top Then BCDSide = 2 ElseIf Dog.Top + Dog.Height > Backyard.Top + Backyard.Height Then BCDSide = 4 End If
I generally use 1 for left, 3 for top, 2 for right, and 4 for bottom.
That was simple.
The regular collision isn't quite as easy to modify, and it'll be slightly more difficult... ok it's mayhem .

So, if the object crosses the left wall, it'll be in the rectangle. If it crosses the top wall, it'll also be in the rectangle. In fact, it will always be in the rectangle if it collided, since that's what we are checking in the first place (Rats). So, we're interested in where the object came from... and we'll treat it like an inverse of boundary collision.

This unfortunately requires us to check the previous values of the object... which might be a little bit too much.
The best bet here would be to perform a collision detection prediction... where we check which side the object will collide with if it collides.
That might be fine in some cases.
Code:
If Dog.Left < Brick.Left Then RCDSide = 1 ElseIf Dog.Left + Dog.Width > Brick.Left + Brick.Width Then RCDSide = 3 ElseIf Dog.Top < Brick.Top Then RCDSide = 2 ElseIf Dog.Top + Dog.Height > Brick.Top + Brick.Height Then RCDSide = 4 End If
It might be a little much if you have multiple dogs and you have to have an RCDSide variable for each dog.
(Not to mention, there's a little error about blind spots)
If only we could predict it simpler. (A Google search for PsychicFriends.dll doesn't find anything for me)

If we look at our collision zone, we see that there are four regions around the square that predetermine the collision type. If we somehow press all four of these regions to the inside of the square, we should be able to get rid of the prediction check.

Then, we have four triangles embedded into our rectangle which determine the type of collision.
So, we break the rectangle up into the four triangles, as shown in the picture, where each triangle corresponds to some side.

This one should work for all types... the big problem being that the object might move into another region. You can hide this error by making the object move smaller distances.
This one is of course covered in the Collision Detection module at the top.

Quick notes before looking at it:
A line is usually expressed as Y = MX + B.
If you put in a value for X, you get a value Y, and all of these points lie on a line.
The M is the slope, and B is top-intercept, where the line crosses the left edge of the form.

To determine if two lines cross, there will be a value for X that equals a value for Y for both lines:
Line A -> Y = Ma * X + Ba; Line B -> Y = Mb * X + Bb
Y = Ma * X + Ba = Mb * X + Bb
Ma * X = Mb * X + (Bb - Ba)
(Ma - Mb) * X = (Bb - Ba)
X = (Bb - Ba) / (Ma - Mb)
To determine if a point is above a line:
Y <= M * X + B
Below would use >= instead of <=
So, if the point is above both lines, Y <= Ma * X + Ba and Y <= Mb * X + Bb
Code:
'MC is the rectangle control. E1 is the dog. Dim M1 As Single Dim B1 As Single 'Data for L line. Dim M2 As Single Dim B2 As Single 'Data for R line. Dim Xm As Single Dim Ym As Single Dim UR As Boolean, UL As Boolean M1 = -MC.Height / MC.Width 'M1 is the slope of the L line in the figure. B1 = ((MC.Top + MC.Height) - M1 * MC.Left) 'B1 is the top-intercept of the L line. M2 = -M1 'The R line has a slope that is opposite of the L line. B2 = MC.Top - M2 * MC.Left 'And that is its top-intercept. Xm = E1.Left + E1.Width \ 2 Ym = E1.Top + E1.Height \ 2 'This is the center of the dog. If Ym <= (M1 * Xm) + B1 Then UL = True 'This first check is to check if the dog's center is above the L line. If Ym <= (M2 * Xm) + B2 Then UR = True 'This check is for dog's center and the R line. If UL And UR Then 'If it's above both lines, then it's at the top. If E1.Top >= MC.Top - E1.Height Then QuadContact = 2 'The if statement checks collision... at this point, we have determined that 'the object is above the center of the shape, we only need to check if it is 'touching the shape, now. ElseIf UL Then 'Above the L line and not the R line means that it crosses on the left. If E1.Left >= MC.Left - E1.Width Then QuadContact = 1 ElseIf UR Then 'Above the R line and not the L line means that it crosses on the right. If E1.Left <= MC.Left + MC.Width Then QuadContact = 3 Else 'Not crossing either line; crosses on the bottom. If E1.Top <= MC.Top + MC.Height Then QuadContact = 4 End If End Function

In the ZIP file, there is an example of the collision prediction for sides.
The picture illustrates 1) the boundary collision side checks,
2) the collision detection side prediction as the inverse to boundary collision side detection...
3) the quadcontact method with two lines being placed across the rectangle.

Have fun.
Attached Files
File Type: zip Fourside.zip (1.8 KB, 215 views)
__________________

Iceplug, USN
Quadrill 1 Quadrill 2 (full) Quadrill 3 JumpCross .NET Website is ALIVE! - DL Platform Tour for VB.NET! Posting Guidelines Hint: Specify your location in your user cp profile if you want compassion!

Last edited by Iceplug; 06-12-2004 at 08:11 PM.
Reply With Quote
  #13  
Old 06-18-2004, 05:17 PM
Iceplug's Avatar
IceplugOverlaps &amp; Collision Detection Iceplug is offline
MetaCenturion

Retired Moderator
* Guru *
 
Join Date: Aug 2001
Location: Iowa, USA
Posts: 16,583
Question Once more upon the line collision.

So far, I have discussed collision detection methods of every control except the oddball: the line control.
(Line and rectangle collisions will be discussed later)
The line control is different in the fact that it is not represented as a rectangle, but rather a pair of X and Y coordinates. Furthermore, approximating a line as a rectangle and using rectangle collision detection is not valid collision detection, according to the first figure below (you can clearly see the two lines do not cross, but their rectangles do)... even if the blue rectangle was actually a rectangular object. To solve this problem, we need to reach back to algebra.

I'm sure everyone (that has taken Algebra) knows the line equation by heart:
Y = M * X + B (or something similar to this with different letters), M is the slope of the line, and B is the Y-intercept (where the line crosses the Y-axis).
You may have had to find where two lines intercept by setting two line equations equal to each other (as discussed in the post above):
Y = M2 * X + B2, and Y = M1 * X + B1
M1 * X + B1 = M2 * X + B2
The X coordinate of the collision is at (B2 - B1) / (M1 - M2)
The Y coordinate would be M1 * X + B1 (or M2 * X + B1, since they are equal).
To little surprise, you can relate this directly to the line controls on the form.

You can arrange a line control on the form, and find its slope by rise/run and the Y intercept by B = Y - MX
Code:
M1 = (Ln.Y2 - Ln.Y1) / (Ln.X2 - Ln.X1) B1 = Ln.Y1 - M1 * Ln.X1
The only problem with this is a vertical line, which will promptly throw VB into an overflow (because Ln.X2 = Ln.X1, the denominator is 0, and the slope is infinite). The vertical line can be checked and approximated, however.
Code:
If Ln.X2 = Ln.X1 Then M1 = 1000000 'An arbitrary big number that looks like infinity. B1 = 0
The calculation with this number should work pretty well. The B is arbitrary and could be any number along the Y axis.
Remember that you need to calculate the slope for every line control on the form.


Now, we have the information we need to do the collision detection.
First, we find the point of collision (this gets a little messy)
Code:
If M1 = 1000000 Then X = Bigline.X1 'Vertical line. Y = M2 * X + B2 'use the decent line. ElseIf M2 = 1000000 Then X = Ln.X1 Y = M1 * X + B1 'use the decent line. Else X = (B2 - B1) / (M1 - M2) 'from the second paragraph. Y = M1 * X + B1 'or M2 * X + B2.
Now, we have found the point of collision... what do we do with it?
Well, we need to determine if this point lies on both lines.
(What you talking about, icey? They're both lines)
They're called lines, but they represent segments in standard geometry, and were probably named that way to avoid confusion with other computer-based segments. Anyway, they're segments, so the point has to line on both lines.
We've already found the point where both lines intersect if they extended to infinity. So, to check if the point lies on the line, we only need to check if the point lies between the end points of the lines.
Code:
'A handy function for determining if a value lies between two other values. Public Function Between(ByVal CValue As Double, ByVal Bound1 As Double, ByVal Bound2 As Double) As Boolean If (CValue >= Bound1 And CValue <= Bound2) Or (CValue <= Bound1 And CValue >= Bound2) Then Between = True End Function
And then:
Code:
If Between(X, Ln.X1, Ln.X2) And Between(X, Bigline.X1, Bigline.X2) And _ Between(Y, Ln.Y1, Ln.Y2) And Between(Y, Bigline.Y1, Bigline.Y2) Then Collided = True End If
That should work for most cases, but there is one little error in there:
If their slopes are the same.
In this case, the X variable will see the overflow (B2 - B1) / (M1 - M2)
To avoid this, you can make a simple little check.
Code:
If M1 = M2 Then If B1 = B2 Then 'This determines if the lines lie on top of each other. Collided = True End If
Of course, this doesn't handle the case where both lines are vertical, but this is another simple check:
Code:
If M1 = M2 Then If M2 = 1000000 Then If Ln.X1 = Bigline.X1 Then 'Vertical line collision. Collided = True End If ElseIf B1 = B2 Then 'This determines if the lines lie on top of each other. Collided = True End If

Our final result:
Code:
If Bigline.X1 = Bigline.X2 Then M1 = 1000000 B1 = 0 Else M1 = (Bigline.Y2 - Bigline.Y1) / (Bigline.X2 - Bigline.X1) B1 = Bigline.Y1 - M1 * Bigline.X1 End If If Ln.X1 = Ln.X2 Then M2 = 1000000 B2 = 0 Else M2 = (Ln.Y2 - Ln.Y1) / (Ln.X2 - Ln.X1) B2 = Ln.Y1 - M2 * Ln.X1 End If If M1 = M2 Then If M2 = 1000000 Then If Ln.X1 = Bigline.X1 Then 'Vertical line collision. Collided = True End If ElseIf B1 = B2 Then 'This determines if the lines lie on top of each other. Collided = True End If Else If M1 = 1000000 Then X = Bigline.X1 'Vertical line. Y = M2 * X + B2 'use the decent line. ElseIf M2 = 1000000 Then X = Ln.X1 Y = M1 * X + B1 'use the decent line. Else X = (B1 - B2) / (M2 - M1) Y = M1 * X + B1 End If If Between(X, Ln.X1, Ln.X2) And Between(X, Bigline.X1, Bigline.X2) And _ Between(Y, Ln.Y1, Ln.Y2) And Between(Y, Bigline.Y1, Bigline.Y2) Then Collided = True End If End If If Collided Then Ln.BorderColor = vbRed Else Ln.BorderColor = vbBlack End If
That's a lot of code. You can put that into a function that takes two lines to determine if they collide.

Edit: Woops wrong picture
Attached Images
File Type: jpg noverlap.JPG (5.0 KB, 102 views)
Attached Files
File Type: zip lineara.zip (1.8 KB, 216 views)
__________________

Iceplug, USN
Quadrill 1 Quadrill 2 (full) Quadrill 3 JumpCross .NET Website is ALIVE! - DL Platform Tour for VB.NET! Posting Guidelines Hint: Specify your location in your user cp profile if you want compassion!

Last edited by Iceplug; 06-18-2004 at 09:11 PM.
Reply With Quote
  #14  
Old 01-10-2005, 02:58 PM
Iceplug's Avatar
IceplugOverlaps &amp; Collision Detection Iceplug is offline
MetaCenturion

Retired Moderator
* Guru *
 
Join Date: Aug 2001
Location: Iowa, USA
Posts: 16,583
Lightbulb More on Side Collisions

The previous side collision tutorial (two posts up) is a more exact style of collision detection. However, there is an easier way to do this style of collision detection, although it is less exact.

Of course, this style of collision detection is very useful in paddle games such as BreakOut or whatever, where the ball moves by small amounts each frame.
So, in general, when the ball is moving slowly (imagine the ball moving 1 pixel right and 1 pixel down each frame), only one of these movements will be the first to cause the ball to collide with something... either the 1 pixel right or the 1 pixel down. So, if the ball collides while moving 1 pixel right, then it has obviously hit the wall on the left side, and should begin moving towards the left. The ball should not logically hit the top of the paddle by moving right. Similarly, moving down should cause the ball to hit something only on the top face.

This same concept can be an efficient substitute for many situations like this requiring the side of collisions.
This requires our ball to have a Horizontal velocity and a Vertical velocity, though, but what we do is:

Move the ball horizontally, and then check for collision.
Move the ball vertically, and then check for collision again.

So, we're checking for collisions twice, but, depending on which collision activates first, we can determine the side that the ball hits the paddle.
The first collision after the horizontal movement would be a collision on the left/right side, left or right can be determined by examining the ball's horizontal velocity: negative value is a collision on the right side of the paddle, and positive is the left side of the paddle.
If the first collision does not activate, and the second one does, then the collision is either on the top/bottom, bottom being from negative values and top being from positive values.

So, we use the regular collision detection code:
Code:
If Apple.Left < Orange.Left + Orange.Width And Orange.Left < Apple.Left + Apple.Width Then If Apple.Top < Orange.Top + Orange.Height And Orange.Top < Apple.Top + Apple.Height Then 'collision! End If End If
Except we check for collision after moving the ball horizontally and again after moving it vertically.

Code:
Apple.Left = Apple.Left + VelocX If Apple.Left < Orange.Left + Orange.Width And Orange.Left < Apple.Left + Apple.Width Then If Apple.Top < Orange.Top + Orange.Height And Orange.Top < Apple.Top + Apple.Height Then HCollision = True End If End If 'Resolve the horizontal collision. Apple.Top = Apple.Top + VelocY If Apple.Left < Orange.Left + Orange.Width And Orange.Left < Apple.Left + Apple.Width Then If Apple.Top < Orange.Top + Orange.Height And Orange.Top < Apple.Top + Apple.Height Then VCollision = True End If End If 'Resolve the vertical collision.

To resolve the collisions, you have the option of resolving them immediately so that the apple does not contact the orange for the vertical collision, or you can wait until after both are finished and then check the collisions (H first, then V, though)

Attached: a small example demonstrating this method.
Attached Files
File Type: zip Foursided.zip (1.7 KB, 217 views)
__________________

Iceplug, USN
Quadrill 1 Quadrill 2 (full) Quadrill 3 JumpCross .NET Website is ALIVE! - DL Platform Tour for VB.NET! Posting Guidelines Hint: Specify your location in your user cp profile if you want compassion!

Last edited by Iceplug; 03-16-2006 at 05:30 PM.
Reply With Quote
  #15  
Old 10-10-2005, 05:45 PM
Iceplug's Avatar
IceplugOverlaps &amp; Collision Detection Iceplug is offline
MetaCenturion

Retired Moderator
* Guru *
 
Join Date: Aug 2001
Location: Iowa, USA
Posts: 16,583
Default Container Collision with Forms and ScaleModes.

This post is a corollary to post 9 and post 12.
As stated in post 9, you can determine if a rectangle/control is within another rectangle/control by using:
Code:
If Dog.Left < Backyard.Left Or Dog.Left + Dog.Width > Backyard.Left + Backyard.Width _ Or Dog.Top < Backyard.Top Or Dog.Top + Dog.Height > Backyard.Top + Backyard.Height Then OutofBound = True End If
Also, you can check which side by using:
Code:
If Dog.Left < Brick.Left Then RCDSide = 1 ElseIf Dog.Left + Dog.Width > Brick.Left + Brick.Width Then RCDSide = 3 ElseIf Dog.Top < Brick.Top Then RCDSide = 2 ElseIf Dog.Top + Dog.Height > Brick.Top + Brick.Height Then RCDSide = 4 End If

If you wanted to make the containing control a form, then, in the collision, you merely change Backyard.Left or Brick.Left with Me.ScaleLeft,
along with:
Backyard.Top or Brick.Top with Me.ScaleTop,
Backyard.Width or Brick.Width with Me.ScaleWidth,
and
Backyard.Height or Brick.Height with Me.ScaleHeight

So, your collision would then look like:
Code:
If Dog.Left < Me.ScaleLeft Or Dog.Left + Dog.Width > Me.ScaleLeft + Me.ScaleWidth _ Or Dog.Top < Me.ScaleTop Or Dog.Top + Dog.Height > Me.ScaleTop + Me.ScaleHeight Then OutofBound = True End If

or this for checking which side that it hit on the form.
Code:
If Dog.Left < Me.ScaleLeft Then RCDSide = 1 ElseIf Dog.Left + Dog.Width > Me.ScaleLeft + Me.ScaleWidth Then RCDSide = 3 ElseIf Dog.Top < Me.ScaleTop Then RCDSide = 2 ElseIf Dog.Top + Dog.Height > Me.ScaleTop + Me.ScaleHeight Then RCDSide = 4 End If

Note that ScaleLeft and ScaleTop are typically 0, so assuming that they are 0 will shorten your checks to:
Code:
If Dog.Left < 0 Or Dog.Left + Dog.Width > Me.ScaleWidth _ Or Dog.Top < 0 Or Dog.Top + Dog.Height > Me.ScaleHeight Then OutofBound = True End If

or for the sided case:
Code:
If Dog.Left < 0 Then RCDSide = 1 ElseIf Dog.Left + Dog.Width > Me.ScaleWidth Then RCDSide = 3 ElseIf Dog.Top < 0 Then RCDSide = 2 ElseIf Dog.Top + Dog.Height > Me.ScaleHeight Then RCDSide = 4 End If

Also, check out the attachment below for an example of this in action.
Attached Files
File Type: zip Bouncy.zip (1.7 KB, 187 views)
__________________

Iceplug, USN
Quadrill 1 Quadrill 2 (full) Quadrill 3 JumpCross .NET Website is ALIVE! - DL Platform Tour for VB.NET! Posting Guidelines Hint: Specify your location in your user cp profile if you want compassion!
Reply With Quote
Reply


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump

Advertisement:





Free Publications
The ASP.NET 2.0 Anthology
101 Essential Tips, Tricks & Hacks - Free 156 Page Preview. Learn the most practical features and best approaches for ASP.NET.
subscribe
Programmers Heaven C# School Book -Free 338 Page eBook
The Programmers Heaven C# School book covers the .NET framework and the C# language.
subscribe
Build Your Own ASP.NET 3.5 Web Site Using C# & VB, 3rd Edition - Free 219 Page Preview!
This comprehensive step-by-step guide will help get your database-driven ASP.NET web site up and running in no time..
subscribe
Overlaps &amp; Collision Detection
Overlaps &amp; Collision Detection
Overlaps &amp; Collision Detection Overlaps &amp; Collision Detection
Overlaps &amp; Collision Detection
Overlaps &amp; Collision Detection
Overlaps &amp; Collision Detection Overlaps &amp; Collision Detection Overlaps &amp; Collision Detection Overlaps &amp; Collision Detection Overlaps &amp; Collision Detection Overlaps &amp; Collision Detection Overlaps &amp; Collision Detection
Overlaps &amp; Collision Detection
Overlaps &amp; Collision Detection
 
Overlaps &amp; Collision Detection
Overlaps &amp; Collision Detection
 
-->