search

Sinova / Collisions

Collision detection for circles, polygons, and points
MIT License
315 stars 44 forks source link

Sweeping and linecasting #11

Open paperjack93 opened 6 years ago

paperjack93 commented 6 years ago

Hello, I am using your collisions system for my game and, with some adaptation (converting it to module.exports - I couldn't get the import thing to work on node.js), it's working pretty well. I have some questions however: 1) Is the correct method for raycasting to create a 2 point polygon and checking its potentials? I haven't encountered issues, but there might be corner cases I don't know about.

2) Sweeping items. Some items in my game will move pretty fast (ex. bullets) and I couldn't find a logic that handles this, therefore I think implementing pre-movement sweeping is necessary. I was wondering if it's a good approach to create a rectangle polygon with the widest points of the body being sweeped and a copy of the polygon at the target point. Then I check all the potentials for both, sorting them based on their distance from the original body. And for last, I use the x y overlap of the rectangle polygon (or the negative x y overlap if its closer to the original body than the middle of the rectangle of the body) as a point to move the original body to.

Thank you very much!

ShimShamSam commented 6 years ago

I think I might solve both of these issues this weekend if you're willing to wait (and trust I'll actually do it). But just to answer your questions:

  1. A 2-point polygon should work, but you'd have to detect the point of collision based on the polygon's starting position and the overlap vector and amount. However, this can potentially generate issues since the minimum overlap direction may point towards the opposite side of the body from your ray's origin. You'll have to detect that based on the overlap vector in comparison to your "ray" vector and flip the overlap vector. I'm not sure if I explained that right, but based on your second question, I'm pretty sure you get what I'm saying.

    NOTE: True raycasting would be a bit different since it would have an origin point and cast out infinitely. My implementation will do this.

  2. The rectangle idea won't be 100% accurate. What you need to do is extrude the polygon's points towards the target position by translating all points that are "in front of" the widest two points from the perspective of movement vector. Here's an off-the-cuff algorithm. You may want to research it a bit more, though.

    1. Clone the polygon
    2. Project the polygon's points onto the normal of the movement vector (i,e, the axis perpendicular to the direction of movement). This will give you the widest two points based on the direction of movement. The line formed by these two points is what I might call the "extruding line".

    3. Iterate through the polygon's points and determine which side of the extruding line they fall on. If they are on the side that is towards the direction of movement or if they fall on the extruding line itself, translate the point by the movement amount and vector.

      1. The polygon has now been swept in the direction of movement. Now just get the potentials and find the nearest collision.

      You're welcome to take a crack at this. I'll be trying my hand at it this weekend.