applecinnabun

fatigue elemental raccalope

  • they/she

game dev/sk8r grrl/guitar/flute/tree liker/indie game obsesser/basic autumn bitch. working on hoptix!

<3 @static-echo <3


play the latest (free!) hoptix demo!
sonicfangameshq.com/forums/showcase/hoptix.1948/
hoptix on twitter (not active, some cool dev posts there though)
twitter.com/hoptixGame
profile pic by @cottontailcat
cohost.org/cottontailcat
BUSINESS
hoptixgame@gmail.com

as a side project, i'm working on a silly little open source multiplayer arcade game, written in python because i want beginner programmers to be able to make their own versions of it.

what i'm looking for is a good way to test 2D moving circle vs static line-segment collision. i can successfully test if a circle would collide with a static line-segment, given a frame of movement, but i can't figure out where it collides (which is different then where it is closest to the line, since it usually should collide before it gets to that point). am wondering if any of the hugely skilled people who follow me or read the #programming tag can point me in the right direction for this?


You must log in to comment.

in reply to @applecinnabun's post:

i don't necessarily know if this is the solution, but some mspaint doodling shows that given the circle's previous and current position, drawing a line between the centers of those positions, the circle would collide at the point along that line where it is tangent to the edge. the point of collision would then be the center of that circle - surface normal * radius
circles

furthermore, the projection of the circle's trajectory onto the edge, along with the edge itself and the circle's radius, make up a right triangle and you could probably solve for the target point using this
circles 2 electric boogaloo

hey thank you! we're on the same page actually, i was just thinking about this triangle. so it sounds like i just need to solve for where that arm of the triangle = the radius of the circle, which i should be able to do given that i know all of the angles of the triangle...

my concern is that it seems like that might only be true of clean collisions with the centers of line segments. take for instance:

my mspaint doodling is bad and my brain's pretty fried for the day but it seems possible for a circle to sail past what would be the normal point of collision with an infinite line, since these are line segments, and collide like the green circle here in a way that doesn't follow the same right triangle pattern...

at very least it seems like that right triangle gives us the earliest possible collision, and i just need to check for weird later collisions in these edge cases?

edit: oh! ok, i figured it out. moving circle - static line segment collision either follows the right triangle pattern you pointed out, or you know for certain you're dealing with a collision with the endpoint specifically, and you're now doing circle-point collision, which i think is easier. just gotta find where the distance from the point to the circle center = r! ty for helping me sort this out bytebat :3

I have two insights to share:

  1. If you know where the circle's center is at the time of collision, you can find the collision location. (It's the closest point on the line segment to the center).

  2. To find the center of the circle at the time of collision, solve an equivalent but easier problem. Expand the line segment by the radius of the circle -- now it's a "capsule". Shrink the circle down to a point -- now the path it sweeps through is a ray.

The point where the ray intersects the capsule is the same as the point where the swept circle is when it intersects the line segment!

Swept circle vs line segment collision test

hey thank you so much! that makes perfect sense :3

last question, if you happen to have an easy answer you're willing to give, is now how does ray vs capsule intersection work... my intuition is i would test ray vs the circle formed at endpoint 1, at endpoint 2, and ray vs the rectangle formed between the two, all separately, but i don't know my capsule geometry well enough to know if there's an easier way?

either way thank you again, this is a very helpful way to think about it!

There is at least a "less computation" way to do it, but I hesitate to call it "easier", at least if you're looking for a derivation.

But if all you need is an implementation, you can find a ray/capsule intersection test on Inigo Quilez's blog. (It's all vector math, so don't worry that it's in 3D. It generalizes to any number of dimensions.)

oh wow, this is such a cool resource, thank you so much! now for the age old programmer's dilemma: do i succumb to pride and use my original, worse way to do this with some of my own reasoning, or do i be reasonable and accept wholesale public implementations from people who are smarter than me :p

whichever i decide on, you've been extremely helpful and i really appreciate it!