Geometry in motion
Part 2: 2D Vectors
As you saw in the earlier article, Lingo's trig functions are simple to use for creating amazing visual effects. Unfortunately, trig functions are relatively slow, so we looked at ways of limiting their use. In this second episode, I'll show you how you can often improve performance by avoiding trig functions altogether.
The theme this time is bouncing sprites off each other. Games such as pool, pong and pinball spring to mind, but I'm sure that you'll be able to find other applications. In this article I'll develop math handlers which you can use as building blocks for a game of pool
We'll explore the concept of 2D vectors. Vectors are simple, powerful and fast.. We'll run tests to show that, in this context, vectors are up to five times faster than floating point trig.
For rapid action games, that difference can be crucial.
In passing, you'll learn a little about the mechanics of elastic collisions. Isaac Newton's phrase will be our watchword:
For every action there is an equal and opposite reaction.
Once again, you'll find two movies available for download: a shocked Tutorial...
Interaction between pool balls also requires a complex network of messages between the sprites. While I do not deal explicitly with this here, you can discover a number of inter-sprite communication techniques in the handlers in the Practice movie.
If you've ever played pool, you should have a good idea of what a vector is. A vector is the invisible line that an object is moving along at any given moment in time. In pool, you point your cue at the cue ball in the direction you want it to go, and then you move the cue along that line. Assuming you strike it dead center, the ball will move in the direction you intended. The faster you hit the ball, the faster it will move off. Think of a vector as being the movement of an invisible cue.
Vectors in Lingo
Here's a two-dimensional vector:
That doesn't look that intimidating does it? It's simply a two-item list. A point is also a two-item list, so it's very handy to store 2-D vectors in point format. The same vector could be defined tlike this:
point (4, 3)
There is a major difference though, between a point and a vector in point format: a point is fixed, a vector moves. Since we'll be exploiting the point format to store vectors, it is important to understand this.
You'll find a behavior called Vector in the Practice movie. The essence of the behavior is this:
property mySprite property myVector
on beginSprite me set mySprite to sprite(the spriteNum of me) set myVector to [4, 3] -- USING LIST FORMAT end
on prepareFrame me set newSpriteLoc to the loc of mySprite + myVector set the loc of mySprite to newSpriteLoc end
All this does is to move the sprite 4 pixels right and 3 pixels down each time the prepareFrame handler is called. The current position of the sprite is stored in the loc of sprite spriteNum. Information about the sprite's movement is stored in myVector. On each prepareFrame the two combine to create a new loc. The loc is constantly changing; myVector remains constant.
Throwing the cue ball
A vector separates the movement of the sprite into two components, one horizontal and the other vertical. This is handy, because it allows us to use screen coordinates directly.
As you move the mouse across the screen, its coordinates change. You can exploit this fact to create a vector with the mouse. The following behavior saves the position of the mouse between from one prepareFrame event and the next while the mouse is down. When the mouse is released, it calculates how far the mouse traveled during the last frame, and converts that into a vector.
property mySprite property myPrevLoc property myVector
on beginSprite me set mySprite to sprite(the spriteNum of me) set myVector to point (0, 0) -- USING POINT FORMAT end
on prepareFrame me if the mouseDown then set myVector to void -- DRAG BALL AROUND ON STAGE set myPrevLoc to point (the mouseH, the mouseV) set the loc of mySprite to myPrevLoc else if voidP (myVector) then -- THROW BALL set spriteLoc to point (the mouseH, the mouseV) set the loc of mySprite to spriteLoc set myVector to spriteLoc - myPrevLoc else -- MOVE BALL set spriteLoc to the loc of mySprite + myVector set the loc of sprite mySprite to spriteLoc end if end
Try the Instant Throw behavior in the Practice movie. In particular, try to the throw the sprite slowly, and at a slight angle. It's not possible, is it? If you throw too slowly, the sprite will insist on moving horizonally, vertically or in a diagonal line... or not at all.
This is due to the fact that the behavior only notices the last split second of the movement of the mouse, just before you release it. You could get greater precision if you could average the movement of the mouse over a longer period.
The Scaled Throw behavior does just this: it creates a list of all the mouse positions over the last quarter of a second. When you release the mouse it compares the current position with the mouse position a quarter of a second before. This means that you can move the sprite as slowly as four pixels per second... or as fast as you like.
Why use a quarter of a second? The value is not absolute. It's a compromise between precision and instantaneous control. Shorter times allow you to shoot from the hip. Longer times make sure your aim is true... but if you move the sprite in a circle before you release it, you may get unexpected results.
At a frameTempo of 60, this technique gives you 15 times a much precision. But it also means that the vector that is created scaled15 times. How come the sprite doesn't move 15 times as fast?
property myPrevLocList -- STORES THE MOUSE LOC OVER 1/4 OF A SECOND property myScaleFactor -- THE NUMBER OF ITEMS IN myPrevLocList = -- THE NUMBER OF FRAMES IN 1/4 OF A SECOND property myLastKnownLoc -- THE SPRITE'S POSITION AT MOUSE UP property myFrameCount -- THE NUMBER OF FRAMES SINCE THE MOUSE UP
It uses the first two to create a vector which is scaled up by myScaleFactor. While the mouse is down, the prepareFrame handler adds the current mouse position at the end of myPrevLocList, while removing out-of-date items from the beginning:
append (myPrevLocList, mouseLoc) if count (myPrevLocList) > myScaleFactor then deleteAt (myPrevLocList, 1) end if
When the mouse is released, it remembers when and where the mouse was...
set myFrameCount to 0 set myLastKnownLoc to point (the mouseH, the mouseV)
... calculates the scaled vector ...
set prevLoc to getAt (myPrevLocList, 1) set myVector to myLastKnownLoc - prevLoc
... and then scales the whole stage up by the same factor:
set myLastKnownLoc to myLastKnownLoc * myScaleFactor
As the sprite continues to move, it calculates its position on each successive frame, as if it were moving on a stage much larger than the real one...
set myFrameCount to myFrameCount + 1 set spriteLoc to myLastKnownLoc + (myVector * myFrameCount)
... but before it actually displays the sprite, it maps the scaled stage back onto the real stage:
set the loc of sprite mySprite to spriteLoc / myScaleFactor
Try it out. You'll see that it is much more responsive than the Instant Throw behavior.
Bouncing off the walls by multiplying lists
When a ball reaches the edge of a pool table, it bounces. If you use a vector to divide the ball's movement into a horizontal and a vertical component, it is very easy to make the ball bounce off the edges of the stage. You simply make one of the coordinates in the vector negative. You can do this by multiplying your vector by a list:
set myVector to myVector * [1, -1]
Try it in the Message window:
put [4, 3] * [1, -1] -- [4, -3]
Director simply takes the first item in the first list and multiplies it by the first item in the second list. Then it multiplies the second two items together. It's no more complicated than that.
Check out the Edge bounce behavior in the Practice movie to see this matrix math at work.
The answer is ... yes, except for the math. The behavior works because the ball is bouncing off horizontal and vertical surfaces, and this lets skip a few calculations. But once you understand why it works, you'll be able to adapt it to angled surfaces and even to moving objects.
Actually, it's slightly easier to bounce off circular objects than off a straight line. To simplify matters, I won't go into bouncing off angled lines here. You'll find a couple of behaviors for this in the Practice movie for you to study on your own.
The mechanics of elastic collisions
When two objects collide, they exchange momentum. The exchange occurs in a direction perpendicular to the surface of collision.
You can think of momentum as the mass of an object multiplied by its velocity. A high speed train has a good deal of momentum in the same direction as its tracks. Its velocity at right angles to the tracks is zero: the train has no sideways momentum. You have to apply a force in order to give a stationary object momentum. The longer you apply that force, the greater the momentum you give the object.
Momentum can be treated as a vector. It can be expressed in terms of motion in two different directions. Think of how a yacht can exploit the movement of the wind in one direction in order to move in different direction.
For a given mass, the momentum of an object is proportional to its speed in a given direction. For simplicity's sake, let's that eight-ball in our edge bounce example has a mass of 1. This would mean that a ball with our original vector of [4, 3] has a total of 5 units of momentum in the direction in which it is moving. We can express that momentum as a vector: four units of momentum in the horizontal direction, and three vertically.
Imagine a pair of miniature twins. One is leaning casually against the vertical edge of the pool table, the other is sitting minding his own business in the middle of the eight-ball. The first twin will see the eight-ball speeding towards him. At the moment of impact, the ball will strike him with a force of four untis. His brother inside the eight-ball will see the edge of the table rushing up at great speed. At the moment of impact, the edge of the table will strike him with a force of four units... an equal force, but in the opposite direction.
The eight-ball has given its momenutm to the table, and received an equal-and-opposite amount of momenutm in return. Which is why we reverse the sign of one of the components of the vector. With its new momenutm vector, the ball bounces off in a new direction.
Vectors with a dual personality
What happens to the 3 units of momentum in the vertical direction at the moment of impact?
It's as if the movement of the ball had a dual personality. One component of the vector does not know what the other component is doing. This is what makes the calculations in the Edge bounce behavior so simple.
Here's the catch: this only works because our vector already contains a component that is perpendicular to the edge of the stage. If the ball met an angled surface, such as another ball, we'd have to calculate a different vector, one that contained a component perpendicular to the angled surface.
Guess who's going to help us do that? Our old friend Pythagoras.
Bouncing off a curved surface
To draw a circle, all you need to know is the loch and locV of its center and its radius. The distanceFromCircle handler below uses Pythagoras' theorem to calculate the distance between the point and the center of the circle. It returns a negative value if the point is inside the circle.
property deltaH, deltaV
on distanceFromCircle, centreOfCircle, radiusOfCircle, thePoint set centerH to the locH of centreOfCircle set centerV to the locV of centreOfCircle set pointH to the locH of thePoint set pointV to the locV of thePoint set deltaH to centerH - nextH set deltaV to centerV - nextV
-- PYTHAGORAS' THEOREM return sqrt ((deltaH * deltaH) + (deltaV * deltaV)) - radiusOfCircle end
The point of impact between a ball and a circle (or between two balls) is always on a line between their centers. The distanceFromCircle handler already calculates the slope of this line and saves it in the properties deltaH and deltaV. Here's a function that exploits these properties to calculate the vector after the bounce.
on circleBounce motionVector set vectorH to getAt (motionVector, 1) set vectorV to getAt (motionVector, 2)
set ratio1 = (vectorV * deltaH) - (vectorH * deltaV) set ratio2 = (deltaH * deltaH) + (deltaV * deltaV) set vectorH = -(2 * ratio1 * deltaV) / ratio2 - vectorH set vectorV = (2 * ratio1 * deltaH) / ratio2 - vectorV
return [newH, newV] end
The Circle bounce behavior in the Practice movie demonstrates it. Note that here the use of scaled integers gives rise to rounding errors: the sprite bounces at a slightly too acute an angle and gradually slows down. It eventually settles to bouncing back and forth along the same radius. This is not entirely realistic behavior. We'll correct it later.
Detecting impact with another ball
Bouncing balls of the sides of the pool table (even a round one) may be fun for a while. But the real aim of the game is to make the balls bounce off each other.
First, we have to detect whether one ball has struck another before applying the impact handler. The obvious way of doing this is to use the sprite intersects function.
To quote the on-line help on this function: "If both sprites have matte ink, their actual outlines, not the bounding rectangles, are used."
This sounds just what we need. It isn't. It's slow. Director must compare the screen positions of the two balls pixel by pixel until it finds a match. Fortunately, there is a faster method.
With any ink other than matte, the sprite intersects function is very fast indeed.
Unfortunately, there's another reason why we can't use it. Director updates the rect of each sprite at the same time it updates the stage. The sprite intersects function will tell us whether the sprites were intersecting before they moved, not after. So we will have to calculate the next rect of each sprite, and compare these using the intersection() function for rects. In the following script myRectData gives the distance in pixels from the loc of the sprite to each edge of its bounding box
property myRectData property myNextRect
on beginSprite me set theLoc to the loc of sprite the spriteNum of me set theRect to the rect of sprite mySprite set myRectData to theRect - rect (theLoc, theLoc) end
on prepareFrame me set nextLoc to the loc of sprite mySprite + myVector set myNextRect to rect (nextLoc, nextLoc) + myRectData end
on intersection me, theRect -- ANOTHER SPRITE'S myNextRect return max (intersect (myNextRect, theRect)) end
Note that you can use the function max() on a rect. If two rects do not intersect, the intersection() function returns rect (0, 0, 0, 0), whose max() is zero (or FALSE).
Impact, not intersection
However, in most cases, it tells us that the sprites have struck each other when it's already too late: pool balls can't intersect the way sprites can. We want to know the exact point of impact, and we want to know this for three reasons:
(You can see an example of this last effect with the Angle bounce behavior. Set the vector to [2560, 1024]. This makes the ball move almost parallel to one pair of walls. When it touches one of these walls, it sticks. Other values will also have this effect).
So we need to let the sprites intersect in order to detect an impact, then we must move them back along their paths slightly to where the would have been the instant before they intersected.
You'll be pleased to learn that this requires you to solve a quadratic equation, where the unknown variable is Time. In the Practice movie, you'll find a Point of impact behavior which does just this. In the key lines below, locDelta is the difference between the positions of the two sprites at the moment that intersection is detected, vectorDelta is the difference between their vectors, and myDiameterSquared is precacluated and stored as a property. The function returns the fraction of the frame since the impact:
on findImpactTime -- CALCULATIONS OF locDelta AND vectorDelta OMITTED -- set a to (vectorDeltaH * vectorDeltaH) + (vectorDeltaV * vectorDeltaV) set b to 2 * ((locDeltaH * vectorDeltaH) + (locDeltaV * vectorDeltaV)) set temp to (locDeltaH * locDeltaH) + (locDeltaV * locDeltaV) set c to temp - myDiameterSquared -- CHECK FOR THE EXISTENDE OF A REAL SOLUTION set discriminant to (b * b) - (4 * a * c) if discriminant < 0 then return #noSolution -- FIND FIRST SOLUTION FOR THE QUADRATIC EQUATION set numerator to sqrt (discriminant) - b set denominator to 2 * a
return float (numerator) / denominator end
This routine will be run immediately after the intersection of two sprites has been detected, so the time in frames since the impact will be less than 1. I convert this time to a floating point number, but only for display purposes: the calculations themselves are all done in integers.
Did you see that c tells you how much the ball themselves? If you calculate c first, and discover that the balls don't in fact touch (c > O), then there is no need to continue the function. The collision has not yet occurred.
Note that using integers introduces a slight rounding effect: the recalculated sprite positions may both be off by 1 pixel along each axis. This means that the sprites may in fact overlap by up to two pixels. My example uses "Darkest" ink on purpose to make this effect visible. With other inks, you wouldn't even notice.
If more than two balls happened to intersect in the same frame, (or two balls and an edge), then you could use the value returned by findImpact() to decide which impact to treat first. The greater the value, the earlier the impact occurred. Putting this into practice, however, entails communication between the various sprites and the stage, and goes beyond the geometrical purpose of this article.
Bouncing off another ball
One final hurdle: a ball moves when another ball hits it, while the sides of the table do not. (Actually they do, but so little that we can ignore the effect).
When two balls collide, they exchange momentum along a line that joins their centres. This function uses difference between the two centres (deltaH and deltaV which we calculated previously) to determine how much momentum is exchanged along this line:
on momentumVector me, deltaH, deltaV set vectorH to getAt (myVector, 1) set vectorV to getAt (myVector, 2) set numerator to mass * ((vectorH * deltaH) + (vectorV * deltaV)) set denominator to (deltaH * deltaH) + (deltaV * deltaV) set momentum H to numerator * deltaH / denominator set momentum V to numerator * deltaV / denominator return [#momentumH: momentumH, # momentumV: momentumV] end
You need to determine how much momentum each ball exchanges. In the following handler, you is the behavior attached to the sprite that current sprite has collided with :
on collide me, you, deltaH, deltaV set myMomentumVector to momentumVector (me, deltaH, deltaV) set yourMomentumVector to momentumVector (you, deltaH, deltaV) -- EXCHANGE MOMENTUM ALONG LINE BETWEEN CENTERS newVector (me, yourMomentumVector, myMomentumVector) newVector (you, myMomentumVector, yourMomentumVector) end
on newVector me, momentumIn, momentumOut set momentumInH to getAt (momentumIn, 1) set momentumInV to getAt (momentumIn, 2) set momentumOutH to getAt (momentumOut, 1) set momentumOutV to getAt (momentumOut, 2) set vectorH to getAt (myVector, 1) set vectorV to getAt (myVector, 2) -- EXCHANGE MOMENTUM set vectorH to vectorH + momentumInH - momentumOutH set vectorV to vectorV + momentumInV - momentumOutV set myVector to [vectorH, vectorV] end
The Ball bounce behavior in the Practice movie is an extension of the Impact behavior. It allows you to set the initial conditions for a collision, and illustrates the position of each ball:
Friction is simple to add. You simply multiply the vector by a number slightly less than one each prepareFrame. To ensure that ratio between the components of the vector remains the same, I identify the greater component (which I call myVectorMax) and calculate the smaller component from that. Here is how I add friction:
set myVectorMax to (myVectorMax * (myFriction - 1)) / myFriction
A value of 2 will halve the speed on each frame. A value of 1000 for myFricition will slow the vector by one part in a thousand. The greater the value, the longer the sprite will take to stop.
Vectors are efficient tools for dealing with movement. They allow you to calculate straight-line movements in integers, using nothing more complex than Pythagoras' Theorem.
Over to you...
To develop this into a dynamic game, you'll need to create a network of messages between the colliding sprites. Functions such as sendAllSprites and call() are designed for this very purpose. The tricky parts will be detecting all collisions (but only once each), and treating near-simultaneous collisions in the correct order.
The Ball bounce behaviors should get you started.