next »

[Jasmine]

delete me

[increpare]

This a copy/paste of this material?  Why not just link it?

[Glaiel-Gamer]

moved to tutorials

[Nix]

Well done for using google.

You shouldn't be snarky after being caught copying material without citation

[Zaphos]

well based on the user name its Jasmine's posts from another forum, copied here -- it's doesn't appear to be someone else's work.

[Trevor Dunbar]

Well done for using google.

You shouldn't be snarky after being caught copying material without citation

It's all nice nonetheless. What does it matter if it's to help people code better games?

[Nix]

okay 

Cool stuff then

[Mikademus]

If anyone has any requests for further mathematical tutorials then post your ideas here and I'll see what I can do.

Good stuff!

I'd love an article on path prediction given a set of 3D position/velocity samples. I have never found a discussion of this.

[Geeze]

Yo Jasmine I need your help to "humiliate" my math teacher.
I asked him how to determine which direction to shoot, if we know enemy's postition, direction and velocity(assume his direction and speed won't change) and speed of our projectile.

When I asked it, he said "Oh god, not these on mondays. When you need the answer?"

So how it's done? (Vector math is highly apprecated)
I don't need code, just the way to solve it.

[ஒழுக்கின்மை (Paul Eres)]

If anyone has any requests for further mathematical tutorials then post your ideas here and I'll see what I can do.

could you explain how to make 2d springs/strings, like in umihara kawase? i know it's more a physics than a math question, but it's sort of both

example of what i mean:





super castlevania 4 did a similar thing with its whip:



-- skip to 12:25 (not the best example of it in that game, but i can't seem to find better right now)

[Mikademus]

Thank you for the article on linear path prediction! Extra kudos for the surrounding discussion!

Linear inter- and extrapolation is the most common use case that covers the basic needs of most games. Can we extend this to more advanced predictions, that is curvilinear path extra/interpolation and prediction?

* Case 1: 2 samples. Say that I have two samples of 2 3D vectors each (a position and a velocity [direction with magnitude]). How do I interpolate the path between these? In actually, I would have samples of a rotation matrix and a velocity, so in addition to position, rotation would also be part of the inter- and extrapolation.

* Case 2: n samples. Is there any meaning to using more than two samples for curvilinear path prediction?

This is a topic and discussion where both my math and the internet has failed me so far

[Mikademus]

@Mikademus: Do you mean like this?

Yes, that's it!

If sample 0 is at t0 and sample 1 is at t1, how can we interpolate positions/directions at a t between 0 and 1, and how can we predict or backtrack (extrapolate?) positions/directions at t > 1 or t < 0?

[Zaphos]

But I won't do it with vectors because that wouldn't be suitable for the computer to process.

They can process vectors though ... I think it's pretty standard to have a vector class that can do addition,subtraction,multiplication,dot-product,cross-product etc with vectors.

[Mikademus]

To calculate that curve, you would use cubic beziers. I could write an article on beziers and splines.

Hmm, well that would make for an interesting article: beziers and splines, and then an section on lateral usages for the techniques, like applying them for curvilinear interpolation and path prediction!

[increpare]

At worst, having vector classes will be nothing more than a layer of abstraction that adds deadweight to the machine code.

The fastest way to do high-performance linear algebra (vectors/matrices/&c.) in C++ is with expression templates, which allows for you to do operator overloading as you see fit an no extra cost. (this is regardless of things like special vector registers).

In other languages, it doesn't usually make much of a difference, and makes working in 3d a lot more pleasant/natural (who wants to type everything three times? ).  In the inside of a physics engine/&c. things might be different, but for high performance cases people will usually use C++, so will likely end up using expression templates, where you can use whatever syntax you want.  

Unity deals with vectors directly as things with operations on them, and I've found it very very pleasant (especially with rotations/translations).  In general when programming, but in particular with 3d maths stuff, my priority is to express things as clearly and simply and easily as possible - and part of this process is uses (and creating as needs be) a big pile of helper functions/methods.

If something is done in a bare-bones style without using classes/methods, it's easier to copy/paste into any language and have it work with minimal tinkering (and it's easier for a complete novice to look at it and to know what's happening (even if they don't know what it means)), so I can appreciate there being some particularly good points to this sort of presentation.  People who know vector maths can always easily convert it.

[Zaphos]

I agree with increpare... will add, if you do want to use the special vector processor stuff like SSE then the Eigen library claims to do a good job of handling that stuff.

[Zaphos]

* Case 1: 2 samples. Say that I have two samples of 2 3D vectors each (a position and a velocity [direction with magnitude]). How do I interpolate the path between these? In actually, I would have samples of a rotation matrix and a velocity, so in addition to position, rotation would also be part of the inter- and extrapolation.

Some terser-than-tutorial thoughts on this:

Quaternion interpolation can perhaps be used for the orientation, if the orientation is purely aesthetic (ie does not affect the path).

The position+velocity interpolation is exactly a Cubic Hermite spline.
http://en.wikipedia.org/wiki/Cubic_Hermite_spline
(This is really the same as a cubic bezier curve, but written more directly in the terms you want.)

Assuming you choose a model like a Bezier or Hermite curve, you'll end up with a polynomial c(t) as the creature's position.  So for path prediction, you can try to adopt Jasmine's linear method to this case as well.  It is just:

given c(t) = equation of creature at time t, p = your initial position, s = your missile speed

use algebra to solve: ||(c(t)-p)||^2 = (s*t)^2

However if you use a cubic spline for prediction, c(t) will be a cubic and after the square you'll be stuck solving a degree 6 root finding problem, which is an unstable numerical problem.
If you use a quadratic spline for prediction instead, you'll get a degree 4 root finding problem which you can solve directly (edit: though it seems it's still not a super nice stable problem, sadly...).  ( http://en.wikipedia.org/wiki/Quartic_function )
A reasonable quadratic function to use for path prediction is probably p(t) = p_initial + v_initial*t + .5 * acceleration_guess*t^2, which is likely familiar from your first physics course.  Acceleration could be guessed naively by taking the difference of the velocities at the two samples and dividing by change in time.

[Zaphos]

Ah, mostly I was thinking that algorithms to generally find all roots of a polynomial tend to just not work in all cases / be ill-conditioned.  But I guess if you adapt it to the specific problem and just search for any root or the first root in a range ahead of t=0, it is probably not so bad.

[Zaphos]

It is pretty hard to get a good method if you want to find all the roots accurately ... But yeah, in this case you don't need that.

[Mikademus]

I am feeling hopeful and confused at the same time here It seems that there are pitfalls, but there is light at the end. Given an accuracy requirement of "good enough", how can it be done?