Jump to content
  • Advertisement
Sign in to follow this  
Ganoosh

Intersection of looping path and area inside

This topic is 2660 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Ok, I'm gonna start by posting a video of the effect I'm looking for to make this easier:
- gameplay from good old NiGHTs on Saturn.

What I'm looking to achieve is the looping/collection effect seen in the game. To make it simpler I'm only looking to do this on a 2D plane. I assume you'd start by keeping track of previous points of movements (a trail), used to calculate line segments. The last segment can then be tested against the others for intersection to "complete a loop," and once found you would know which segment starts the loop, and the last segment would have to be the end. Because the already existing trail doesn't change you would only have to check as a new end segment is added. However, this may be pretty slow, and I'm sure this is a better way to go about doing this.

The biggest stump I'm on, is actually calculating what's inside the loop, and if objects are inside that area. I know how to calculate the area using calculus, but doing this as a step by step method would also be slow, plus I still don't know how to test if a point is actually within the area, as it can be very irregular or asymmetric ellipses. Any tips, ideas, etc?

Share this post


Link to post
Share on other sites
Advertisement
What if each line segment you add to your path just incrementally updates a winding number that you store for each object? Then, whenever the absolute value of an object's winding number exceeds 2 pi -- bam -- it explodes, and you set the winding number back to zero.*

If object n has winding number w[sub]n[/sub] and position vector p, and you've just added a line segment with endpoints x[sub]1[/sub] and x[sub]2[/sub] to your path, then the update would be,

w[sub]n[/sub] += asin(det(x[sub]1[/sub]-p, x[sub]2[/sub]-p)/(||x[sub]1[/sub]-p|| ||x[sub]2[/sub]-p||))

where, for any two vectors v[sub]1[/sub] and v[sub]2[/sub], det(v[sub]1[/sub], v[sub]2[/sub]) denotes the determinant of the matrix that has v[sub]1[/sub] and v[sub]2[/sub] as columns.

* This isn't quite right, however. You really don't need to check for the winding number exceeding +/- 2 pi; what you need to check is whether the winding number has changed by more than 2 pi. Maybe the test should be that the maximum and minimum values for the winding number over the last so many frames need to differ by more than 2 pi. Again, this is an incremental update; you only need to store the max, the min, and the frames on which they occurred.

I'm not totally satisfied with this answer, but I think that the "best" approach will have roughly this spirit. I'll post back if any improvements spring to mind.

Share this post


Link to post
Share on other sites
The winding number sounds like a good idea, except it doesn't take into account spirals. A slightly modified approach might be to first detect an intersection in your path then use the line segments that form the loop to create a set of winding numbers. You could also decompose the loop into convex polygons and check if each object lay inside them but the winding number solution sounds a lot nicer.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!