Thread: 2D colision with vector map

  1. #1
    Registered User
    Join Date
    Aug 2001
    Location
    Melbourne, Australia
    Posts
    92

    2D colision with vector map

    I'm *trying* to develop a game (2D top view, - I guess details about the actual game are fairly unimportant at the moment so i'll skip that bit) and I want to have colision detection between my vehicles (for example a hovercraft and a tank) which shouldn't be too hard, depending on how I do it, most probably their colisions would be based on circles around them, based on "pool-table" style collisons.

    Ok i'll stop raving and get to the point:

    I want to have a vector-based map (ie. either using GDI regions or a more useful polygon library that one of you can suggest?) and I need to be able to find what line I would have crossed by moving from one point *ouside* the region to a point *inside* the region, and thus be able to find its normal and what angle I should be bouncing off at etc... BUT preferably I would like to be able to do even more - i'd like to be able to check it against a circular region around each player (not vital... i'm sure I *could* live without that kind of collision on the terrain)

    Can anyone point me on the right track or give me any suggestions? First person to answer my question gets a million bucks.

    Thanks all!
    Jeff

    DISCLAIMER:
    No money will be receieved as a result of helping me. "Million bucks" is merely a figure of speech, actually referring to a "million bucks" worth of my gratitude ;-)
    Last edited by PsychoBrat; 08-12-2003 at 02:31 AM.
    psychobrat at gmail

  2. #2
    Pursuing knowledge confuted's Avatar
    Join Date
    Jun 2002
    Posts
    1,916
    Yup. It can be done.

    First, for the cos of the angle between two vectors, use the dotproduct. Look it up on Google.

    For the collision detection, keep a radius for the bounding sphere/circle of each object (a and b) Then, compute the distance between the objects (use the distance formula - google) Call the distance r
    Code:
    if r<=(a+b)
       collision
    Away.

  3. #3
    Banned
    Join Date
    Jan 2003
    Posts
    1,708
    this is how I mirror vectors off of a surface, what it does is it calculates the component of the incoming vector that is perpendicular to the normal, multiplies it by two then subtracts it from the incoming vector. I know it works because i"ve got a little ball that bounces around a BSP.

    Code:
    Vector3	Perp(Vector3	*a, Vector3	*axis)
    {
    	Vector3	temp = *a - Parallel(a, axis);
    	return	temp;
    }
    
    Vector3	Mirror(Vector3	*a, Vector3	*axis)
    {
    	Vector3	temp = *a - (Perp(a, axis)*2);
    	return	temp;
    }

  4. #4
    Pursuing knowledge confuted's Avatar
    Join Date
    Jun 2002
    Posts
    1,916
    It looks (from your post) like you don't have the normals yet. The easiest way to keep them is to store them with the rest of your data. If you're using 3d, you can use the cross product of the vectors representing two sides of a triangle to find the normals. It looks like you're using 2d, though, so you could use this crossproduct <(x1,y1,0)-(x2,y2,0)> X <0,0,1> = normal. I think that works. You'll have to make sure all your normals are pointing out, though.

    edit: lol, or you could just use the negative reciprical of the slope of a side to find it's normal, which would be a lot faster
    Away.

  5. #5
    Registered User
    Join Date
    Aug 2001
    Location
    Melbourne, Australia
    Posts
    92
    Okey thanks for that!!

    Now one of my problems still remains: *which* line have I crossed over? For example, say I had a diamond shaped block that I didn't want the player to be able to penetrate. They come along and hit near one of the vertices of the diamond. How do I tell which line I should be looking at?

    Excuse my ignorance, I've never done anything like this before - in the past i've only ever dealt with *very simple* tile-based maps where collision detection practically writes itsself :s

    Thanks all!
    -Jeff

    P.S. confuted... at the time of me reading your second reply you had 1337 posts... go figure ! And did you know that internally the board still knows you as blackrat364?... thats who it told me had replied to my thread in the automatic e-mail notification...
    psychobrat at gmail

  6. #6
    Pursuing knowledge confuted's Avatar
    Join Date
    Jun 2002
    Posts
    1,916
    The thing with the name is because I replied to your message before I got my name changed

    Why exactly do you need to know which line it crossed, as long as you know it collided?

    Are you just using rectangles? (I guess it would work for n-gons, but as n increases, the code will slow down a lot) Is there any possibility of a square? (A square would have exceptions to what I am about to say if they lined it up just right)

    Computing the midpoint of a side, given the location of the two endpoints, is pretty simple. It's also pretty simple to compute the distance between two points. Here's what I propose (there might be a better way, I just made this up):

    Compute the midpoint of each side of the bounding box. I'll call the midpoints m[i], where i represents the number of sides.

    To make this a bit easier, I'll assume you just need to check for a collision with a single point, which I'll call P. If you need to determine a collision between two boxes, and which line on one box touched which line on the other box, you'll just need to add some more nested loops.

    Compute the distance, d[i], between each midpoint, m[i], and P, for every value of i. Simply find the smallest value of d. The side i which has this value for d[i] is the side with which the collision happened (actually, it will be the side closest to having had the collision happen with it. It will work for collisions with corners, but may return what a human would consider the "wrong" side)

    In the case of a perfect square, it is possible to run into a problem using this method if the collision happens *perfectly* with a corner, because there would be two values of d[i] which were equal. In this case, I suppose just picking one and going on would be the best choice.

    I have a feeling that was pretty confusing and unclear. Let me know if you have questions about what I just said. I'm not sure exactly what you're trying to do, and I probably just made that more complicated than you need.
    Away.

  7. #7
    Registered User
    Join Date
    Aug 2001
    Location
    Melbourne, Australia
    Posts
    92
    No... you that wasn't too confusing, but I have a couple of questions:

    I have attached an image showing an example colision, where the blue circle labeled (1) is the location of the player *before* the physics is calculated that moves him to his new location, (2). The shaded grey area represents a clipped (wall) area of my map, and each black circle marks a vertex.

    If I found the closest mid-point to the new (or old) location of my player, it would tell me that I have collided with the short wall when obviously I have actually collided with the south-east wall.

    ???

    Thanks,
    Jeff
    psychobrat at gmail

  8. #8
    Carnivore ('-'v) Hunter2's Avatar
    Join Date
    May 2002
    Posts
    2,879
    Blackrat was talking about rectanges, not 4-sided abstract shapes

    **EDIT**
    I mean confuted

    **EDIT2**
    Oh right, I guess that would apply to rectangles too. But not to squares, methinks
    Just Google It. √

    (\ /)
    ( . .)
    c(")(") This is bunny. Copy and paste bunny into your signature to help him gain world domination.

  9. #9
    Pursuing knowledge confuted's Avatar
    Join Date
    Jun 2002
    Posts
    1,916
    Yeah, I realized that, but I didn't know how to point out the problem without a diagram. I'll try to think of a way around that, and probably edit this post if I can think of one.

    edit: It's going in another post so I can attach a file.
    Last edited by confuted; 08-12-2003 at 10:45 PM.
    Away.

  10. #10
    Carnivore ('-'v) Hunter2's Avatar
    Join Date
    May 2002
    Posts
    2,879
    Equations of lines | Lots of if statements? lol...
    a)Find equation of line that you're moving along
    b)Find equations of hitbox lines (i.e. x = 100, x = 200, y = 50, y = 250)
    c)Determine the direction you're moving in (up, down, left, right)
    d)If up, then you collided with the bottom.
    e)If right and up, you either collided with left or bottom:
    f)Find where your line intersects the bottom (y=250). If it intersects between x=100 and x=200 (the left and right boundaries), then you collided with the bottom. Else, you collided with the left.

    Etc. etc. etc.

    Now, put it into code

    **EDIT**
    Actually, move (a) to between (e) and (f)... it's not needed if you're moving straight up, down, left or right. Also, this is all assuming that you've already determined that there's a collision
    Last edited by Hunter2; 08-12-2003 at 10:34 PM.
    Just Google It. √

    (\ /)
    ( . .)
    c(")(") This is bunny. Copy and paste bunny into your signature to help him gain world domination.

  11. #11
    Pursuing knowledge confuted's Avatar
    Join Date
    Jun 2002
    Posts
    1,916
    What Hunter just said works, but only if you're moving in one of the "cardinal" directions, and only if everything is oriented in one of these cardinal directions. Very simplistic, not very flexible, and probably not what you want if you mentioned a hovercraft. (If hunter's does what you want, use it)

    everything below the line was going to go in the edit of the other message, but I couldn't attach.
    -------
    edit: Got it, and this time it will work for ALL rectangles (it would still be possible to construct some funny 4 sided thing that would mess it up). I think it would work for n-gons too. Especially if you keep n within reason. It might be a bit tough to implement, though. I'm going to stick a figure in here, and refer to it.

    Another thing about what I'm about to say is that the amount of movement will have to be small relative to the size of the shape. If you're taking steps a lot bigger than your rectangle, then you'll be likely to step right over it. Not a good thing. Also not easy to fix. So avoid it now

    Alright. We have point p (blue dot) moving toward our shape. We've already covered how to detect if they collide. Well, we pretty much have. There are a lot of 'collision detection' tutorials out there anyway. So, suppose we detect a collision. That's where this picks up.

    With a rectangle, we can form four triangles. Each triangle has p has one vertex, and the endpoints of a side for the other two. Whichever triangle has the largest angle Q will contain the side with which you collided. In my diagram, that's side ab. You can use the law of cosines to find angle Q. Q will be between 0 and 180 in all cases. It just so happens that cos Q varies between 1 and -1 in this range. You're going for the maximum angle, which means the smallest value for cos Q -- as close to -1 as you can get. Don't take the arccos of cos Q to find Q, you'll just be wasting clock cycles, since you can use what I just said to your advantage. Anyway, once you determine which triangle has the largest angle Q, you'll know with which side you collided.
    Away.

  12. #12
    Registered User
    Join Date
    Aug 2001
    Location
    Melbourne, Australia
    Posts
    92
    I encountered the problem of skipping over parts of a map when moving to fast not long after I started programming... which was a few years ago - hopefully in this game I should be able to keep each movement calculation to a few pixels at most!

    For this to work i'd have to make my maps up of multiple segments each having shapes with only convex hulls then check each individually, right? (well that's what my mind seems to be telling itself...)

    Is there anything I could do that would allow me to use something simmilar check a multi-part vector region (for example if I was using GDI regions for my map or something) that would let me use one region for my whole level, or would I have to split it up into parts with only convex hulls?

    I've attached another image that show's the situation i'd be in if I tried to do that using the current method we've been talking about, even if I only checked for lines that are in front of me (using same symbols as last time): The line on the outside of the map would have a greater angle between the points from the player than the closer one.
    psychobrat at gmail

  13. #13
    C++ Developer XSquared's Avatar
    Join Date
    Jun 2002
    Location
    Ontario, Canada
    Posts
    2,718
    Assuming that you are moving towards the line, as long as A > B, you haven't collided with it.
    Naturally I didn't feel inspired enough to read all the links for you, since I already slaved away for long hours under a blistering sun pressing the search button after typing four whole words! - Quzah

    You. Fetch me my copy of the Wall Street Journal. You two, fight to the death - Stewie

  14. #14
    Registered User
    Join Date
    Aug 2001
    Location
    Melbourne, Australia
    Posts
    92
    Oooo good point! Thanks XSquared...

    This should mean that I could use the methods discussed here for pretty much any region, however many parts it were made up of! Awsome!

    Thanks once again to all who have read my problem and taken the time to help me get this one figured out.

    I'll try to remember to post again when I get something cool going out of this so you can see what I'm making...

    Cheers,
    Jeff
    psychobrat at gmail

  15. #15
    Carnivore ('-'v) Hunter2's Avatar
    Join Date
    May 2002
    Posts
    2,879
    but only if you're moving in one of the "cardinal" directions
    How so? I DID include the "if moving up and right" part, you realize...
    and only if everything is oriented in one of these cardinal directions
    True

    **EDIT**
    Also, XSquared, I don't understand your method... Isn't B always going to be greater than A, since it is A+something?
    Last edited by Hunter2; 08-13-2003 at 09:44 AM.
    Just Google It. √

    (\ /)
    ( . .)
    c(")(") This is bunny. Copy and paste bunny into your signature to help him gain world domination.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. 2D in directX
    By fighter92 in forum Game Programming
    Replies: 6
    Last Post: 01-25-2009, 11:23 AM
  2. Help with 2d arrays
    By thamiz in forum C Programming
    Replies: 25
    Last Post: 05-25-2008, 05:06 AM
  3. Best Graphics Library for 2d RTS?
    By arew264 in forum Game Programming
    Replies: 4
    Last Post: 04-18-2007, 12:05 PM
  4. Replies: 16
    Last Post: 09-22-2006, 03:39 PM
  5. Read file in 2D array
    By Chook in forum C Programming
    Replies: 1
    Last Post: 05-08-2005, 12:39 PM