Collisions |
| COMP 310 Java Resources Eclipse Resources |
[Back to Ballworld]
See the demo of the command-dispatching Ballworld with inter-ball interactions
The discussion below should be viewed in terms of two separate processes:
In the end, you should modify the code below such that these two separate processes are clearly expressed in your architecture, which enables you to separately vary the concrete implementations of these processes.
Basic physics of elastic collisions of two spherical objects of different mass: 2-Body Elastic Collisions
Make sure that the other ball does not have infinite mass (mass = Double.POSITIVE_INFINITY)! (Note: balls with infinite mass and non-zero velocities technically have infinite kinetic energy, so they tend to continuously add energy to the system, which quickly causes problems.) We will use a mass here that is proportional to the area of the ball (square of the radius), so we will not encounter this issue here, but I mention it if you wish to separate the mass as an independent quantity and thus create things like infinitely heavy "rock" balls.
CollideStrategy is a strategy that adds elastic collisions to a ball. It provides a number of utility methods that by encapsulating many of the more mathematical calculations, help the main calculations focus on what they are fundamentally trying to achieve. Read the documentation below very carefully!
Basic recipe for a collision command:
IMPORTANT: The following description combines BOTH the interaction criteria and interaction behavior. The actual implementation would separate these into separate entities!
Here is most of code for CollideStrategy showing the utility methods that are used:
public class CollideStrategy extends IUpdateStrategy {
// THIS CODE IS NOT COMPLETE -- IT IS ONLY A GUIDE FOR SOME OF THE REQUIRED PIECES
// TO CREATE ELASTIC COLLISION BEHAVIOR. THE STUDENT IS EXPECTED TO IMPLEMENT ANY
// MISSING PIECES!
@Override
public void updateState(final Ball source, IDispatcher<IBallCmd> dispatcher) {
// "source" ball is the "context" of the strategy. The "target" ball is the ball receiving the command from the source ball's strategy.
// TODO: To be completed by student. This is the interaction criteria code if this were the interaction criteria strategy.
/**
Basic outline of the algorithm (use the utility functions below to calculate what you need) :
1. Send command to all the other balls to see if you can interact with them
2. Make sure you're not interacting with yourself
3. Check the interaction criteria
4. If interaction criteria is met:
a. Model the ball's "mass" as desired, e.g. proportional to ball's area
b. It is handy to calculate the distance between the balls and the minimum non-colliding distance (= max colliding distance)
c. Calculate the reduced mass of the system
d. Calculate the unit vector pointing from the source ball to target ball
e. Calculate the impulse vector for the source ball
f. Calculate the "nudge" vector, which is the amount to move the source ball out of the way of the target ball after the collision.
g. Update the velocity of the source ball using the impulse vector
h. Update the velocity of the target ball using the NEGATIVE of the impulse vector.
i. "Nudge" the source ball by translating its location by the nudge vector.
j. Let both the source and target balls run whatever interaction behaviors they already have.
*/
// QUESTION: What would change in this code if this strategy's job was merely to deliver the interaction behavior to the context ball?
}
/**
* Returns the reduced mass of the two balls (m1*m2)/(m1+m2) Gives correct
* result if one of the balls has infinite mass.
*
* @param mSource
* Mass of the source ball
* @param mTarget
* Mass of the target ball
* @return The reduced mass of the two balls
*/
protected double reducedMass(double mSource, double mTarget) {
if (mSource == Double.POSITIVE_INFINITY)
return mTarget;
if (mTarget == Double.POSITIVE_INFINITY)
return mSource;
else
return (mSource * mTarget) / (mSource + mTarget);
}
/**
* Calculate the unit vector (normalized vector) from the location of the source ball to the location of the target ball.
* @param lSource Location of the source ball
* @param lTarget Location of the target ball
* @param distance Distance from the source ball to the target ball
* @return A double-precision vector (point)
*/
Point2D.Double calcUnitVec(Point lSource, Point lTarget, double distance) {
// Calculate the normalized vector, from source to target
double nx = ((double) (lTarget.x - lSource.x)) / distance;
double ny = ((double) (lTarget.y - lSource.y)) / distance;
return new Point2D.Double(nx, ny);
}
/**
* Calculates the impulse (change in momentum) of the collision in the
* direction from the source to the target This method calculates the
* impulse on the source ball. The impulse on the target ball is the
* negative of the result. The change in velocity of the source ball is the
* impulse divided by the source's mass The change in velocity of the target
* ball is the negative of the impulse divided by the target's mass
*
* Operational note: Even though theoretically, the difference in velocities
* of two balls should be co-linear with the normal line between them, the
* discrete nature of animations means that the point where collision is
* detected may not be at the same point as the theoretical contact point.
* This method calculates the rebound directions as if the two balls were
* the appropriate radii such that they had just contacted
* _at_the_point_of_collision_detection_. This may give slightly different
* rebound direction than one would calculate if they contacted at the
* theoretical point given by their actual radii.
*
* @param normalVec
* The unit vector (normalized vector) from the location of the source ball to the location of the target ball.
* @param vSource
* Velocity of the source ball
* @param vTarget
* Velocity of the target ball
* @param reducedMass
* Reduced mass of the two balls
* @return The value of the collision's impulse
*/
protected Point2D.Double impulse(Point2D.Double normalVec, Point vSource, Point vTarget, double reducedMass) {
// Get the coordinates of the unit vector from source to target
double nx = normalVec.getX(); //((double) (lTarget.x - lSource.x)) / distance;
double ny = normalVec.getY(); //((double) (lTarget.y - lSource.y)) / distance;
// delta velocity (speed, actually) in normal direction (perpendicular to the plane of interaction,
// i.e. in the direction from the source location to the target location
double dvn = (vTarget.x - vSource.x) * nx + (vTarget.y - vSource.y)* ny;
// Impulse is the change in speed times twice the reduced mass in the normal direction
return new Point2D.Double(2.0 * reducedMass * dvn * nx, 2.0
* reducedMass * dvn * ny);
}
/**
* The multiplicative factor to increase the separation distance to insure that the two balls
* are beyond collision distance
*/
private static final double NudgeFactor = 1.1;
/**
* Calculate the vector to add to the source ball's location to "nudge" it out of the way of the target ball.
* @param normalVec The unit vector (normalized vector) from the location of the source ball to the location of the target ball.
* @param minSeparation The minimum allowed non-colliding separation between the centers of the balls = maximum allowed colliding separation.
* @param distance The actual distance between the centers of the balls.
* @return A Point object which is the amount to "nudge" the source ball away from the target ball.
*/
Point calcNudgeVec(Point2D.Double normalVec, double minSeparation, double distance) {
// The minimum allowed separation(sum of the ball radii) minus the actual separation(distance between ball centers). Should be a
// positive value. This is the amount of overlap of the balls as measured along the line between their centers.
double deltaR = minSeparation - distance;
// Calc the amount to move the source ball beyond collision range of the target ball, along
// the normal direction.
return new Point((int) Math.ceil(-normalVec.getX() * deltaR * NudgeFactor),
(int) Math.ceil(-normalVec.getY() * deltaR * NudgeFactor));
}
/**
* Updates the velocity of a ball, given an impulse vector. The change in velocity is the
* impulse divided by the ball's mass.
*
* @param aBall
* The ball whose velocity needs to be modified by the impulse
* @param mass
* The "mass" of the ball
* @param impulseVec
* The impulse vector for the ball
*/
protected void updateVelocity(Ball aBall, double mass, Point2D.Double impulseVec) {
aBall.getVelocity().translate((int) Math.round(impulseVec.getX() / mass),(int) Math.round(impulseVec.getY() / mass));
}
}
Unit vector calculation:
The above code includes a calculation of the unit vector pointing from the source ball's location to the target ball's location. This vector of length "1", is used to transform the calculations performed in the center-of-mass coordinates (where this vector is the x-axis) back to the coordinates used by the balls.
Nudging:
Because of the discrete nature of the movement of the balls and because the Ballworld system uses a single-pass updating mechanism (vs. a two-pass system where updating behaviors are calculated on the first pass and executed on a second pass), the balls may not be in the exact positions that one would expect them to be when they contact each other.
It is non-trivial to calculate the exact theoretical contact position of the two balls, so the CollideStrategy class pretends that the radius of the balls is exactly the size such that the initial contact between the balls occurrs right at their current location.
In such, all calculations are based off of the "normal vector" which runs from the center of the source ball, through the point of contact between the balls, to the center of the target ball. This is the line that is normal to the plane of contact between the two balls, if their radii where exactly the size such they just touched at their current locations. A round or spherical surface can only exert a force along the normal to its tangential planes.
Theoretically, this normal line would be co-linear with the difference in velocities between the two balls (their relative motion, which is used to calculate the impulse), but in actuality, the two are not co-linear.
The shortest distance to move the source ball to get it out of collision distance with the target ball is along the normal direction. A "nudge" factor is introduced to insure that that the source ball is far enough away to not "double collide" with the target ball. (Why don't you move the target ball?)
Since the above "nudging" borders on a "hack" because it does not fit into any reasonable abstraction of the collision process, there are bound to be lingering errors. For instance, it is normal to see strange collision behaviors that look like multiple collisions, as if the nudging process didn't work, when a small, fast-moving ball collides with a large, slow-moving ball. Can you figure out why this would happen? Hint: consider the discrete nature of the Ballworld simulation process and possible collision scenarios for a small, fast ball and a large, slow one.
Exact calculations:
For those with an interest in a much more rigorous treatment of where the ball should be placed, please read the following derivation and code for the elastic rebounding between balls of unequal radii and mass. Note also that the collision time calculation can also be used as part of a more exact detection of whether or not two balls ever collided during the last timer tick, i.e. as part of an interaction criteria. Such a calculation would be able to detect if one ball was moving so fast that it completely jumped over another ball during one tick, a situation that would not be detected by simpler overlap calculations.
Interaction Strategies
In trying to get a large system to run, it is tempting to simply add methods and classes in to "get it to work". But we must always return to the central driving force: our software as a model of our system.
The post-collision behavior is fundamentally different than the behavior as defined by an IUpdateStrategy. An IUpdateStrategy defines the behavior of a single ball, in isolation. On the other hand, the post-collision behavior is necessarily the behavior of 2 balls in relationship to each other. This overall behavior can be expressed as two single behaviors, one for each ball. Note that each single behavior depends on both balls and that they are not necessarily the same or mirror images of each other. For instance, one ball may adjust its velocity to point in parallel with the other ball's, but the other ball's behavior may be to kill the first ball. We see the two individual interaction behaviors being invoked in Step 2.c above.
Thus, an IInteractStrategy has been added to the Ball class. In addition to the usual getter and setter, there is a method, public void interactWith(Ball target, Dispatcher disp) that is used to invoke the ball's interaction strategy.
/**
* Strategy that defines a directed interaction between two balls where the balls are NOT
* equivalently processed.
*
* @author swong
*
*/
public interface IInteractStrategy {
/**
* Performs a directed interaction between the context ball and the target Ball from the
* perspective of the context Ball.
* @param context The Ball from whose perspective the interaction
* processing takes place.
* @param target The Ball that is the "other ball" in the perspective of this processing.
* @param disp The Dispatcher that is to be used if desired.
*/
public void interact(Ball context, Ball target, IDispatcher<IBallCmd> disp);
/**
* Null strategy with no-op behavior.
*/
public static final IInteractStrategy NULL_STRATEGY = (context, target, disp)->{};
}
Interaction criteria is performed simply by an IUpdateStrategy sending out an IBallCmd to all the other balls. In that command, the sending ("source") ball is compared to the recieving ("target") ball. If the comparison results in deciding that an interaction should be invoked, the IUpdateStrategy delegates to the method of the ball that invokes its interaction, e.g. an "interactWith()" method.
It up to the system's designer to decide whether one or both of the balls' interaction behaviors should invoked when an interaction criteria is satisfied. The decision must be justified in terms how the system's theoretical model represents ball interactions. The code must be justified by the goals of the model -- Do NOT justify the model in terms of its implementing code!
Thus, we would expect an IUpdateStrategy that implements an interaction criteria to look something like this:
public class MyInteractCriteriaStrategy extends IUpdateStrategy {
@Override
public void updateState(final Ball source, IDispatcher<IBallCmd> dispatcher) {
dispatcher.updateAll(new IBallCmd() {
public void apply(Ball target, IDispatcher<IBallCmd> disp) {
// compare source and target Balls -- interaction criteria
// if interaction criteria is satisfied:
// For example -- NOT GOSPEL!! The system designer needs to justify the following calls in terms of the theory driving the model!
source.interactWith(target); // Justify this call by how the system is modeling interactions.
target.interactWith(source); // Justify this call by how the system is modeling interactions.
}
}
// Other code elided
}
It is an exercise left to the student to understand and implement the relationship between the interactWith() (or whatever it is called) method and the IInteractStrategy of a Ball.
Just like paint strategies, update strategies may need to be initialized before they are ready to be used. These initializations could include setting and/or reading ball properties or calculating invariant values that will be used used multiple times across the many invocations of the strategy.
Code and design are dynamic living things, ever changing to meet new changing requirements as well as simply a changing outlook and understanding of the problem. Looking back at the above code, could the entire collision process be considered simply an interaction detection plus interaction behaviors? That is, could part or all of the code past the actual collision detection be moved to an interaction strategy? If so, how would you handle the shared portion of the calculation, e.g. the impulse calculation, which is invariant for both balls?
But if we break elastic collisions into a two-part notion of a detection algorithm followed by interaction strategies, could this architecture be used for more than contact-based interaction? How about interaction at a distance or other relative location, or interaction by type of ball? What does this all lead to?
There are some tough issues that arise when attempting to separate the collision behavior from the collision interaction criteria. For some ideas on how one might tackle this, see the page on Commands as Deferred Behavior.
Sometimes, all a strategy does is to initialize, installing or modifying parts of the ball that will change it's behavior later. For instance, the initialization may simply install an interaction strategy into the context ball.
Remember to initialize the strategy, even when it comes in via a constructor, i.e. always delegate the setting of the strategy to a setter method which is where the initialization should take place.
Consider a "kill" strategy that deletes other balls if they collide. This KillStrategy relies on another IUpdateStrategy to detect the collision and process any rebounding. The KillStrategy only inserts an IInteractionStrategy that does the "killing" part of the interaction process.
IMPORTANT NOTE
The following example illustrates an interesting way in which one can view the update strategy installation process as a transport mechanism. Here, the IUpdateStrategy part of the KillStrategy is merely a "box" that transports an IInteractStrategy which is the real "killer". All the IUpdateStrategy part is doing is allowing Ballworld to enable the "kill"
behavior to be managed on the same update strategy drop lists on the view and to use that same mechanism to transport the interaction strategy to the ball where the update strategy's init() method will "inject" the interaction strategy into the ball.
This technique is really just a "trick" to enable one to use the existing IUpdateStrategy management and installation capabilities in Ballworld to manage and install IInteractStrategies by wrapping them in IUpdateStrategies.
There is nothing fundamental about this technique other than it is a harbinger of things to come later in the course where we will need "boxes of data" to be transported through a system.
Of course, one could implement the management and installation of interaction strategies in exactly the same manner as update and paint strategies were handled. The point of implementing the interaction strategies this way is to help drive home the realization that for the most part, the Ballworld system never really cares about whether the entities being put to and retrieved from the view's drop lists are for update strategies or a paint strategies or something else entirely but rather all those mechanisms are merely just to move those items around the system, independent of what they really are.
DO NOT INTEPRET THE EXAMPLE BELOW AS ANY SORT OF REQUIREMENT OR FUNDAMENTAL CHARACTERIZATION OF UPDATE OR INTERACTION STRATEGIES!!
The critical question is: What does the existence of this "trick" really saying about how entities are being transported around our system? Could the Ballworld system be redesigned in a way that separates this ability to transport the update and interaction strategies from the strategies themselves? This notion will become very important in later projects!
Always continually stop and re-examine your own designs to see what it is really saying to you about what is really going on in your system and then don't be afraid to refactor your design to better express those hidden characteristics.
DESIGN IS FOREVER EVOLVING AND NEVER STATIC!
public class KillStrategy implements IUpdateStrategy {
public void init(Ball context) {
context.setInteractStrategy(new MultiInteractStrategy(context.getInteractStrategy(), new IInteractStrategy(){
@Override
public void interact(Ball context, Ball target, IDispatcher<IBallCmd> disp) {
disp.removeObserver(target);
}
}));
}
@Override
public void updateState(Ball context, IDispatcher<IBallCmd> disp){
// No-op
}
}
// Or, using lambda expressions:
public class KillStrategy implements IUpdateStrategy {
public void init(Ball context) {
context.setInteractStrategy(new MultiInteractStrategy(context.getInteractStrategy(), (contextBall, targetBall, disp) -> disp.removeObserver(targetBall)));
}
@Override
public void updateState(Ball context, IDispatcher<IBallCmd> dispatcher) {
// No-op
}
}
Notice that no assumption is made about whether or not the ball had an existing interaction strategy.
© 2020 by Stephen Wong