• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
ryt

Colliding position

7 posts in this topic

I have two objects and I want to find when will they collide. Lets say first target has position p0, velocity v0 and the time it will arrive at desired position is t0. Similar for the second target it has position p1, velocity v1 and the time t1.

The general formula for speed with constant velocity is:

 

p = v*t + p0

 

So if we try to find their colliding position p0 and p1 should be equal at desired time so p0 = p1.

 

v1 * t1 + p1 = v2 * t2 + p2

 

t2 = v1 * t1 + p1 - p2 / v2

 

t2 is the time that will second object arrive at colliding position.

I wonder how we can calculate this ? On the right hand side of last equation we have vector division. So since t2 is a scalar on the right hand side there also must be a scalar. So I think we should take the magnitude of vectors on right side and divide them.

What to do in these situations when we have a division of two vectors ? Is this approach correct one ?

Edited by ryt
0

Share this post


Link to post
Share on other sites

Generally, you can not divide vectors. In your particular case, you should take t1 = t2 (because object collision is equivalent to that objects are at same place in same time). So 
v1 * t1 + p1 = v2 * t1 + p2
t1 * (v1 - v2) = p2 - p1
Hence you only need to check if vectors a = (v1 - v2) and b = (p2 - p1) are collinear. This can be done in two-dimensional space by computing dot product : a*B, where B is normal vector to b. More simply, if a = (a1, a2) and b = (b1, b2) you should check if a1 * b2 - a2 * b1 = 0 with necessary accurancy, or just if a1 / a2 = b1 / b2. 

Edited by richardwagner
0

Share this post


Link to post
Share on other sites

I have two objects and I want to find when will they collide. Lets say first target has position p0, velocity v0 and the time it will arrive at desired position is t0. Similar for the second target it has position p1, velocity v1 and the time t1.

The general formula for speed with constant velocity is:

 

p = v*t + p0

 

So if we try to find their colliding position p0 and p1 should be equal at desired time so p0 = p1.

 

v1 * t1 + p1 = v2 * t2 + p2

 

t2 = v1 * t1 + p1 - p2 / v2

 

t2 is the time that will second object arrive at colliding position.

I wonder how we can calculate this ? On the right hand side of last equation we have vector division. So since t2 is a scalar on the right hand side there also must be a scalar. So I think we should take the magnitude of vectors on right side and divide them.

What to do in these situations when we have a division of two vectors ? Is this approach correct one ?

 

I'm not sure what you are trying to solve for here. There are two ways that this problem can have no solution: 1) the lines that the objects are moving along do not intersect and 2) that they arrive at the target location at different times.

 

The way that you have phrased the problem suggests that both of the objects are moving towards a common location. So they should intersect. However, the velocities in your equations are arbitrary so mathematically, this intersection is not guaranteed. To ensure that the objects do intersect you should construct the velocities of the objects so that they are oriented towards to target location. You can do this using the starting position of the object and the target position,

 

v1 = s1 * (p1(0) - p0) / |p1(0) - p0|

 

where 's' is the speed of the first object. The equation of motion for the first object becomes,

 

p1(t) = t * s1 * (p1(0) - p0) / |p1(0) - p0| + p1(0)

 

The time it takes for object 1 to get to the target is independent of object 2 so we can for 't' directly from this equation,

 

p1(t') = p0 = t' * s1 * (p1(0) - p0) / |p1(0) - p0| + p1(0)

 

0 = t' * s1 * (p1(0) - p0) / |p1(0) - p0| + p1(0) - p0

0 = (t' * s1 / |p1(0) - p0| + 1) * (p1(0) - p0))

 

Assuming that p1(0) != p0,

 

0 = t' * s1 / |p1(0) - p0| + 1

 

Or,

 

t' = -|p1(0) - p0| / s1

 

Now, that makes sense; it is negative because I defined the velocity direction away from the target and there is no solution if s1 == 0, which is the same as if the object had no speed.

 

If you want to know if the two objects arrive at the same time, then you would have to have,

 

|p1(0) - p0| / s1 = |p2(0) - p0| / s2

 

However, this means that speeds of the objects have to be chosen just right depending upon their starting position in order to collide. If the speeds of the objects are not variables that you are trying to solve for, and you still want to determine if the objects will collide with one another, they problem becomes a little harder because you actually have to find the distance between the objects as a function of 't' and they collide if that minimum distance is less than some threshold. Assuming that the objects are spheres, that problem can be written as,

 

let x(t) = p1(t) - p2(t)

 

To find the time of the collision between the objects you have to solve,

 

x(t)^2 - r^2 = 0

 

where 'r' is your threshold distance (the sum of the radii of the objects if they are spheres). Expanding this equation out gives a quadratic equation,

 

(v1 * t + p1(0) - v2 * t - p2(0)) . (v1 * t + p1(0) - v2 * t - p2(0)) - r^2 = 0

t^2 * (v1 . v1 + v2 . v2 - 2 * v1 . v2) + t * (v1 . (p1(0) - p2(0)) - v2 . (p1(0) - p2(0))) + (p1(0) . p1(0) + p2(0) . p2(0) - 2 * p1(0) . p2(0)) - r^2 = 0

 

Lots of terms there (definitely check my working). However, the only thing that is unknown is 't', so we just have to solve,

 

A * t^2 + B * t + C = 0

 

Like any quadratic equation, there can be 0, 1, or 2 solutions. 0 solutions implies that there is no collision at all, 1 solution implies that the objects touch at one point in time, and 2 solutions means that the objects collide for a finite period of time.

 

-Josh

0

Share this post


Link to post
Share on other sites

Well my original question was about how to deal with the situation when we have vector division. In this case I took the magnitude of resulting vectors like:

 

t2 = |v1 * t1 + p1 - p2| / |v2|

 

So I wonder if this is the right way to use the magnitude and to get time t2 ?

 

In my example the two objects always collide since their final positions are same like p1 = p2 where p1 is final position of first object and p2 is final position of second object.

If first object has some speed at some time t1 will arrive at position p1. So if their final positions of two objects are the same p2 is also known and we can find v2 and t2. If we set v2 to some speed and direction all we need to find is t2. This is the time that is in last equation.

I made a mistake in the original post. I meant to say p1 = p2.

Edited by ryt
0

Share this post


Link to post
Share on other sites

I think you should be solving:

 

p0 = p0 + v0 ( T )

p1 = p1 + v1 ( T )

 

T = Dot ( n, p1 - p0 )  / 

      Dot ( n, v0 - v1 )

 

where   n = Normalize( p1 - p0 )

 
 

instead of 

 

p0 = p0 + v0 ( T0 )

p1 = p1 + v1 ( T1 )

 

Otherwise, you’re probably looking for a “ray to ray” intersection test.

 

Also, once you find T, p0 and p1 will be close, but never exact.  32-bits of precision can cause nightmares…

0

Share this post


Link to post
Share on other sites

I don't understand. Why we should take T0 = T1 that is compute it for some T. The two objects will have the same position and it will take different times to get there. That is if first object travels faster or is closer to the collision point than obviously T0 < T1.

 

Why did you took the Dot and normalized the vectors ?

0

Share this post


Link to post
Share on other sites

Since you qualified your question to specify that collision is guaranteed, then yes, you can use the magnitude of the vectors. IF they both will arrive at final position p, then v0 and v1 must be coplanar, and it can be assumed that time = distance / speed.

p = p0 + v0 * t0; // p0 is the initial position of object 0
p - p0 = v0 * t0;
t0 = mag(p-p0) / mag( v0 );

t1 (similarly) = mag(p - p1) / mag( v1 ); p1 is the initial position of object 1

time to collision = greater( t0, t1 )

Caution: if the velocity of one or both objects is away from p, you'll get erroneous results. I.e., one or both objects will arrive in negative time.

Edited by Buckeye
1

Share this post


Link to post
Share on other sites


I don't understand. Why we should take T0 = T1 that is compute it for some T. The two objects will have the same position and it will take different times to get there. That is if first object travels faster or is closer to the collision point than obviously T0 < T1.

 

 

http://fivedots.coe.psu.ac.th/Software.coe/241-213/F.Dunn,%20I.Parberry%20-%203D%20Math%20Primer%20for%20Graphics%20and%20Game%20Development.pdf

 

Page 283

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0