Geometry in motion
Part 2: Vectors
As you saw in last month's 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 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 on the MUJ site: a Practice movie and a shocked Tutorial. Download them now. They'll help you to understand the article.
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.
Introducing vectors
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.
In a friction-free world, the ball would continue in that direction at that speed forever... or until it hits the edge of the table or another ball. Friction will bring it gradually to a halt.
Vectors in Lingo
Here's a two-dimensional vector:
[4, 3]
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 spriteNum
property myVector
on beginSprite me
set myVector to [4, 3] -- USING LIST FORMAT
end
on prepareFrame me
set the loc of sprite spriteNum to
the loc of sprite spriteNum + myVector
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.
It then continues to move the sprite at the same speed and in the same direction.
property spriteNum
property myPrevLoc
property myVector
on beginSprite 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 sprite mySprite to myPrevLoc
else if voidP (myVector) then
-- THROW BALL
set spriteLoc to point (the mouseH, the mouseV)
set the loc of sprite mySprite to spriteLoc
set myVector to spriteLoc - myPrevLoc
else
-- MOVE BALL
set spriteLoc to the loc of sprite 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.
Scaling vectors
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?
The Scaled Throw behavior uses four new properties:
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.
Not only are we now scaling the vector, we are also no longer calculating the current loc of the sprite from its loc in the previous frame. Instead, we calculate it from a fixed point: where it was when you released the mouse. We'll use both these techniques again shortly.
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 Edge bounce behavior looks very straightforward, and the result is totally realistic. Is treating collisions really so easy?
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?
Nothing. The speed of the ball in the downward direction does not change when it hits a vertical edge.
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.
We know (but Director doesn't) that the two sprites are circular, and that, if they are intersecting, their loc are less than two radius-lengths apart. So we'll do our impact test in two steps: first see if the rect of the sprites intersect, then check if they balls themselves are actually close enough to intersect.
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:
* if the balls are not moving at the same speed or hit each other with a glancing blow, the angle of impact will not be correct if the balls have intersected
* if the frameTempo is fairly slow the player will see an unrealistic intersection
* in some circumstances, the balls will not bounce clear of each other but remains intersecting on the following frame. This will make them reverberate or freeze.
(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 c to (locDeltaH * locDeltaH) + (locDeltaV * locDeltaV) - 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:
* on the frame before the collision
* at the moment of impact
* on the frame following the collision.
It needs to know the initial position and vector of each of the colliding sprites. To do this as quickly as possible, it uses the call() function to communicate directly with the behaviors of the colliding sprites.
Friction
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.
Summary
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.
You have seen a variety of handlers for treating two-dimensional collisions in the absence of gravity, and to display them realistically on the screen. You have seen how to create vectors either by drawing a line or by "throwing" a sprite, and to scale them up for greater precision. You have learnt to bounce circular sprites off edges and off each other. You can calculate the precise moment and position of the impact, and deal with friction.
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.