Thread: identify my algorithm, please!

  1. #1
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300

    identify my algorithm, please!

    So I am working on the 3D breakout.

    Here's something that came as a pleasant surprise and felt like a real feat of genius, but doubtless someone else has thought of it before, so I want to find out what its called to learn more about it.

    If you give an object an x, y, and z velocity, it can move in any direction. Pretty straightforward -- that's a simple vector. Now, if instead you just assign it a velocity, and then x y z values clamped 0.0 to 1.0 such that they total 1.0 (as absolute numbers), you can apply these to the velocity and do the same thing (if x is 0.5, and y -0.5, and z 0.0, it moves diagonally down to the right).

    My first happy realization was that you can then bounce that object off any surface that extents straight along an axis (eg, all values in one of x y or z are the same, like the walls in a normal room), and all you have to do to get a perfect reflection is invert the appropriate value. Going with the object x=0.5, y=0.25, z=0.25, if it hits the ceiling, you just invert y to -0.25 -- its inertia in z and x do not change (is that real physics?) It reflects exactly like a tennis ball would, anyway.

    So, that's nice (and a surprise, because in all the hundreds of pages on 3D programming I've read, this is never referred to). But what about surfaces that angle across all three dimensions? You could use a local coordinate system, but this is problematic. I wondered if there could be a simpler way.

    I wanted to make it possible to tilt the paddle in x and y, so you could direct the ball up or down and to the sides (right now, it looks like a racket ball court). Fortunately, math is really hard for me so real trigonometry is a last resort.

    Here's what I figured out: you assign the paddle a rotation, not in degrees, not in radians, but where 1.0 = 45 degrees, and you use that as an adjustment. Here "obj" refers to the ball and "Pad" to the paddle, ie, the angled surface; the obj "R" values are the velocity modifiers I mentioned:

    Code:
    if ( ball has hit paddle ) {
                    hit = 1;
                    /* horizontal tilt */
                    if (Pad.yR > 0.0f) {     /* left */
                            obj->xR = Pad.yR - fabsf(obj->xR);
                    } else {     /* right or straight */
                            obj->xR += Pad.yR;
                    } 
                    /* vertical tilt */
                    if (Pad.xR > 0.0f) {   /* up */
                            obj->yR = Pad.xR - fabsf(obj->yR);
                    } else {   /* down */
                            obj->yR += Pad.xR;
                    } 
                    if ((obj->xR > 1.01f) || (obj->xR < -1.01f) || 
                        (obj->yR < -1.01f) || (obj->yR > 1.01f)) {
                            Those values indicate  contact with the surface
                            would have been impossible, OR that the angle of
                            reflection would be back so:
                            hit = 0;
                    }
            }
            if (hit) obj->zR = 1.0 - (fabsf(obj->xR) + fabsf(obj->yR));
    The last line just makes the z value the balance after x and y are calculated. z is also inverted.

    Now, this is pretty cool because 1) it totally works, 2) there's no trig, vectors, or dot products involved.

    Of course, applying this to other circumstances may not be so easy -- that last condition is significant, because those angles are in error (but it doesn't matter, the ball is out).

    I have done some googling and there is amazingly little to be found about simple "vector reflection", etc, and this is not really it. But some other people must use a system like this and have hopefully figured out a way to make it more generally applicable.

    Anyone know? Any thoughts, comments, questions? In case it does not make sense, here's the line in red again:

    obj->xR = Pad.yR - fabsf(obj->xR); [edited]

    So if the object was travelling dead staight on z (so yR = 0.0, zR = 1.0) and hit the paddle angled 45 degrees left (-1.0), it's new yR value would be -1.0, and so the balance (zR) would be 0.0. These modify the velocity in each dimension, so now instead of moving straight on z, it moves straight on y.

    I may post all the code for this here tomorrow for other reasons, but I have been playing with it and tweaking stuff half the day -- it looks totally real.

    ps. if you are so smart and gracious as to identify a flaw in the code there that'd be great too...
    Last edited by MK27; 11-25-2009 at 03:55 PM. Reason: tweak tweak -- some values that should have been fabsf weren't
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  2. #2
    Registered User C_ntua's Avatar
    Join Date
    Jun 2008
    Posts
    1,853
    This is what I understand. You have:
    x = 2 m/s
    y = 4 m/s
    z = 0 m/s

    You can have
    x = 0.33
    y = 0.66
    z = 0.0
    So |x|+|y|+|z| = 1.0

    Is that what you are saying?

    Without giving it a lot of thought, what is an alternative way to do this. A famous alternative way that people in 3D designing use oftenly, so that we can see the value of what you are saying. They way you do it is really clean and simple, but I am not aware of alternatives to compare.

    Having |x|+|y|+|z| = 1.0 is clever, so you can always know the value of z if you know the value of y,x. It is a good otpimization if the velocities are changing a lot.

    So, we are speaking for two things
    1) Caclulating z as 1-x-y
    2) Assigning 45deg = 1 and making easy calculations
    right?

  3. #3
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Yeah, exactly*. Just I don't have any formal math and rarely deal with it, so it is hard for me to formalize this in a way that I can apply more generally with confidence. But I have to assume someone else already has.

    Like, what if I hadn't known what an "absolute number" is? It's an intuitive enough concept. But I'm a big believer in the idea that language helps give form to hunches and ideas. And in the "language of math", I am a real beginner.

    All the 3D stuff I have seen leans heavily on trigonometry. This makes sense, since that is what trig is for (geometry), and if you have a strong math background it is probably an easy choice. But it is also computationally expensive, I think. Meaning it makes sense in a full fledged FPS setting with many actors, or if you are just an engineer who wants the correct answer. But if I had just sat down and done this that way, it would be a much heavier affair, I think, with a ton more code.

    This week I may try adding multiple balls, etc, which I have a hunch I could use the same idea there for the ball collisions. If so, that's great...if not, well, it at least works for the paddle.

    * technically I am restricting the x y z portions to 16th values (multiples of 0.0625) for floating point precision.
    Last edited by MK27; 11-24-2009 at 07:10 PM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  4. #4
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229
    A unit vector?

    magnitude = sqrt(x^2+y^2+z^2);
    x /= magnitude;
    y /= magnitude;
    z /= magnitude;

  5. #5
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229
    Uh no, had a brainfart :P.

    I'm not aware of a name for it.

  6. #6
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by cyberfish View Post
    Uh no, had a brainfart :P.

    I'm not aware of a name for it.
    I didn't mean a traditional math formulation (esp one involving sqrt!) -- I meant more of a computer programming style algorithm. You know, like "merge sort" is an algorithm, but I dunno if it's possible or meaningful to describe it in purely mathematical terms, altho it may be subject to mathematical analysis in terms of performance.

    I thought this because I have seen other people here say "oh well, the first time I had to sort something I did this, and it turned out that's insertion sort" or whatever.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  7. #7
    Registered User C_ntua's Avatar
    Join Date
    Jun 2008
    Posts
    1,853
    Can you give a more complex example? It seems like a really good solution. You could try to prove its correctness also mathimatically maybe?

  8. #8
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by C_ntua View Post
    You could try to prove its correctness also mathimatically maybe?
    Egads no! Not I! That is perhaps my missing link in generalizing this completely.

    Until I try the thing with the multiple balls, I can't even say that it will work with angles beyond 45 degrees, etc -- mostly because I really banged my head for several hours, doodling little little diagrams and guestimating, just to get this far. The first version had 45 degrees as 0.5 and involved some multiplication and division...then I saw the light

    Central to the conceit is that the "primary" trajectory is in z, and that z MUST be CORRECTLY invertable at the end (or 0). That is to say, if the angle of reflection is such that the z value would remain positive (and x/y is more than 1.0...), the algorithm (as is) does not work correctly. It works for my purposes, because if the z is still positive, the ball is out of bounds anyway, so I don't care if the resulting trajectory is incorrect (this is one of the things I wanted to find "presolved" by someone else )

    For example, going back to this:

    obj->xR = Pad.yR - fabsf(obj->xR);

    If the paddle is at 45 degrees right (1.0), any x trajectory >= 0.5 with a positive z CANNOT hit this surface -- it may hit the back of the surface, but that is out. The only reason "I would think that it could" is that objects in 3D simulation may move a number of units per frame -- witness, I left out the part where I decide whether it has contacted the paddle. For game purposes, since the perspective is first person, I am not really concerned with the paddle as a realistic object -- it might as well be a volumetric "field".

    From the reading I have done, this is an (elementary) issue no matter what in 3D programming. If you have an object that is travelling at 5 units per frame and it ends up 3 units in front of a wall at render time, next frame it is 2 units behind, so it never hit the wall! My solution is just to say if it is within striking distance, that is calculable -- but it still cannot be a valid hit if the paddle is at 45 degrees and the object is travelling at a 30 degree angle. That cannot hit the front.

    Actually, I think can get this to work out more generally. Just the marbles are done for now But I can still cross my fingers some else can point me in the right direction.
    Last edited by MK27; 11-25-2009 at 03:56 PM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  9. #9
    Registered User C_ntua's Avatar
    Join Date
    Jun 2008
    Posts
    1,853
    Lets say 2d, with z=0. We have
    x = a
    y = 1-a

    The angle of the moving ball is A = tan(x/y) = tan(a/1-a) => artan(A) = a/1-a
    Thus, a = arctan(A) / arctan(A)+1
    this is always true

    After hitting a paddle the angle changes. It becomes lets say B
    So again you would have
    x' = arctan(B) / arctan(B)+1
    y' = 1 -x'

    Now, you would have
    Dx = x'-x = [arctan(B) / arctan(B)+1] - [arctan(A) / arctan(A)+1]

    In your case, lets say for the right and straight, you would have
    Dx = xR' - xR = Pad.yR

    So I would guess
    Pad.yR = [arctan(B) / arctan(B)+1] - [arctan(A) / arctan(A)+1]

    So, in order to calculate the paddle you need to know the resulting angle and the initial angle of the ball. In any way IF my calculations are correct, or close to correct (take no responsibility about them cause :P) then you cannot apply values for paddle (xR,yR,zR) for every surface. They would change depending on the xR,yR,zR value of the moving ball. In which case you need to provide an algorithm on how this happens. But I would guess that there are already similar methods.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Implement of a Fast Time Series Evaluation Algorithm
    By BiGreat in forum C Programming
    Replies: 7
    Last Post: 12-04-2007, 02:30 AM
  2. Replies: 4
    Last Post: 12-10-2006, 07:08 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM