Collision in Collection and Collision Avoidance
IAT 265, Spring 2020
School of Interactive Arts and Technology
______________________________________________________________________________________
Copyright By PowCoder代写 加微信 powcoder
SCHOOL OF INTERACTIVE ARTS + TECHNOLOGY [SIAT] | WWW.SIAT.SFU.CA
Formalizing some code-refactoring tips – Using collision detection as an example
Collisions among collections of objects – Collision within the same collection
– Collision between different collections – Nested loops for collision testing
Collision Avoidance
– Forces and acceleration
– Steering along walls
– Steering around an obstacle
2/14/2022 IAT 265 2
Recap: collision detection
Using static bounding boxes is difficult when translation, rotation and scaling are involved
For an object with complex figures we can create an outline for it using Area class and then return its dynamic bounding box for collision detection
AffineTransform object can be used to transform any Shape object without drawing it
We check for collision on transformed objects using Shape’/Area’s intersects(Rectangle2D rect) method
– Between one object’s outline and the other’s dynamic bounding box, and vice versa as well
We can also detect collision between a point and an object using Shape’/Area’s contains(double x, double y) method
2/14/2022 IAT 265 3
Some code-refactoring considerations
We know how to write the methods for collision detection & resolution, but which object should define these methods, and who should call these methods?
– “To be or not to be, this is a question!”
2/14/2022 IAT 265 4
Who should define collision method?
If it involves an active object (who can act) vs. an inactive object, let the active object be the implementer
– Example: creature vs. food, creature vs. boundary, etc.
– Active object should define both collision detection and resolution methods
If however both parties can act, pick the action initiator (active object) over the action receiver (passive object)
– Example: frog vs. insect, shark vs. fish, etc.
2/14/2022 IAT 265 5
An Example
• Edge collision: Bug objects vs. edges
• Bug is active and therefore defines the edgeCollision() method
February 14, 2022 IAT 265 6
Who should call the collision method?
Options:
– Active object
• Typically will changes its state/behavior when colliding – Inactive/Passive object
• May or may not alter its state/behavior when colliding – Controller (e.g. JPanel object)
• Holds the information in collection for both – make it a desirable candidate for this in general, but there are exceptions
Who should call the collision method? (1)
Rule of Thumb 1 (RoT 1): make active object call if it runs against inactive objects that typically doesn’t alter its state/behavior
– E.g. boundary detection
– Implementation: Active object iterates over the list of inactive objects, calls its own detection method and responds accordingly
– Typically invoked in active object’s move or update method
2/14/2022 IAT 265 8
An example of RoT 1
A case that bug as active object vs. edges as inactive objects, invoke the collision method in bug’s move() method as per RoT 1
public void move(){
vel.normalize().mult(maxSpeed);
pos.add(vel);
edgesCollision();
2/14/2022 IAT 265 9
Note: PVector’s normalize() unit PVector
Who should call the collision methods? (2)
RoT #2: make controller (e.g. panel object) call for the following scenarios:
– Two objects of different types (active vs. passive), both change state/behavior with collision
• E.g. A predator eats a prey, a racket hits a ball
– Two active objects of the same type, only one changing
state/behavior
• E.g. a small creature yields road to a larger one of the same kind
Assume objects of the same kind are kept in their ArrayLists, e.g. predatorList, preList etc.
– Allheldinsidepanelobject
2/14/2022 IAT 265 10
PPP for Controller to call Collision methods
1. Update all active & passive objects
2. Iterate over object of list 1 (active) Iterate over object of list 2 (passive)
If (o1.checkCollision(o2)) {
IAT 265 11
o1.respond(o2); o2.respond(o1);
//may or may not be necessary
Recap: Nested Loop
A nested loop: putting one loop inside another
for(float i = 10; i <= 100; i += 10) { //outter loop for(float j = 10; j <= 100; j += 10){ //inner loop
point(i, j);
For each iteration of the outerloop, the inner loop will run through all its iterations
2/14/2022 IAT 265 12
Nested Loops
Nested Loops are especially useful for: – drawing a grid in a 2-D space
– Running through a 2-D matrix to process data (e.g. image processing)
– Testing within a collection or between collections of objects for collision detection
2/14/2022 IAT 265 13
Case study: Collison within the same collection of Bugs
Collision between two bugs
In Bug class, create the method for collision detection between the current bug and another bug
boolean detectCollision(Bug otherBug) {
boolean bump = false;
if (getOutline().intersects(otherBug.getOutline().getBounds2D()) &&
otherBug.getOutline().intersects(getOutline().getBounds2D())) bump = true;
return bump;
2/14/2022 IAT 265 15
Resolve: make smaller one turn away
bug otherBug
Codify: method of resolution
In Bug class, create the method for collision resolution to identify the smaller one and turn it away
void resolveCollision(Bug otherBug) {
float angle = (float) Math.atan2(pos.y-otherBug.pos.y, pos.x-
otherBug.pos.x);
//if current bug smaller, turn it away by the angle
if(scale < otherBug.scale) {
vel = PVector.fromAngle(angle); vel.mult(maxSpeed);
//Otherwise send the otherBug away in the opposite direction: angle+PI
otherBug.vel = PVector.fromAngle(angle+(float)Math.PI); } otherBug.vel.mult(maxSpeed);
2/14/2022 IAT 265 17
Collision: within the same collection of Bugs
In BugPanel, use a nested-loop to test each bug against any other bug:
for(int i = 0; i < bugs.size(); i++) {
Bug bugi = bugs.get(i);
Anything wrong here?
2/14/2022 IAT 265 18
for(int j = 0; j < bugs.size(); j++){
Bug bugj = bugs.get(j);
if (bugi.detectCollision(bugj)) {
bugi.respondToCollision(bugj);
One approach to fix ...
Must rule out the situation that a bug checks collision against itself
for(int i = 0; i < bugs.size() ; ++i) {
Bug bugi = bugs.get(i);
for(int j = 0; j < bugs.size(); j++){
Bug bugj = bugs.get(j);
if (i != j && bugi.detectCollision(bugj)) {
bugi.respondToCollision(bugj);
Still involve with redundant checking
2/14/2022 IAT 265 19
A better solution ...
Test each bug against those unchecked bugs only
ArrayList
for(int i = 0; i < bugs.size() ; ++i) {
Bug bugi = bugs.get(i);
for(int j = i+1; j < bugs.size(); j++){
Bug bugj = bugs.get(j);
if (bugi.detectCollision(bugj)) {
bugi.respondToCollision(bugj);
2/14/2022 IAT 265 20
Why i = j+1 works?
2/14/2022 IAT 265 21
Collision: b/w different Collections of Objects
Test each of one collection against each of the other collection
ArrayList
ArrayList
for(int i = 0; i < frogs.size() ; i++) {
Frog frogi = frogs.get(i);
if (frogi.detectCollision(bugj)) {
frogi.respondToCollision(bugj);
bugj.respondToCollision(frogi);
for(int j = 0; j < bugs.size(); j++){ Bug bugj = bugs.get(j);
2/14/2022 IAT 265 22
Collision Avoidance
Some collisions are undesirable
– Creatures typically don’t bounce from obstacles
– Creatures want to avoid bouncing against each other – Preys wants to escape from predators
We need a way to predict the collision that will occur and modify behaviors accordingly
Oct 12, 2017 IAT 265 23
Techniques for collision avoidance: Force Model
Forces in the environment, e.g. gravity, attraction, repulsion etc.
– Forces can be associated with passive or active objects, e.g. food attracts animals, boundaries repulse animals, gravity pulls objects down, wind blows things away, etc.
Force causes change in acceleration, acceleration changes velocity
– Benefit: leads to fluent, more believable behavior
Oct 12, 2017 IAT 265 24
Modeling Environmental Forces
Environmental forces are well related to distance, e.g. the farther the distance, the smaller the gravity, attraction, impulsion forces etc., and vice versa
Formula for computing environment forces based on ROT: F = coef / (distance from edge) 2
• coef is normally a value provided based on ROT
• distance from edge can be calculated using Line2D’s method ptLineDist(double px, double py), where px, py is typically about the center location of the object
• Power of 2 can be computed using Math.pow(n, p)
Oct 12, 2017 IAT 265 25
Steering along Walls
Typically done by a vector that holds the pushing-away force – an add-up of forces from all four edges of environment
– Apparently, when the distance is very far from an edge, its forces can be so weak that could be ignored
– When getting closer to it, its forces will become ever more significant so as to steer it away gradually
Oct 12, 2017 IAT 265 26
Case study: Steering along the walls (1)
Step 1: Represent the walls (i.e. edges of Sea env) as Line2D objects
Oct 12, 2017 IAT 265 27
Steering along the walls (2)
Step 2: In Fish class, create a method to calculate the PVector of wall force that pushes the fish away
Call Line2D’s method
ptLineDist(double px, double py)
that returns the distance from a point to this line.
Oct 12, 2017
Compute the force per the ROT model:
F = coef / (distance from edge) 2
IATN2o6ti5ce the direction of force via -/+ 28
Steering along the walls (3)
Step 3: In Fish’s moveToTarget(Food f) method, call wallPushForce() to return the force and calculate acceleration
As we only want it to turn away rather than speed it up, so restore the speed to its
wallSteerAccel is computed as per the formula:
a = force / mass
Where mass is simulated using scale related to size and thereby mass
Oct 12, 2017 original magnitude IAT 265 29
Steering around obstacles
Avoiding obstacle: creatures will steer away when they are getting close enough to an obstacle, rather than bump into it
– Question: How to detect an obstacle before hitting, so as to steer around it?
Oct 12, 2017 IAT 265 30
Techniques for obstacle detection
Generally two ways for detecting obstacles
– Field of View: a view cone or arc projecting from creature’s eye position to indicate range of view
– Feeler for detection: an object sticking out from head or body for obstacle detection
• Cat whiskers, bug’s antenna, blind man’s stick, car’s curb feeler, etc. ...
Oct 12, 2017 IAT 265 31
Feeler: Implementation consideration
Feeler can be done using a vector projecting along the direction of motion so as to check for collision with potential future positions (aka forward-pointing probing)
– Feeler is supposed to be an invisible object, although we can, for understanding purpose, render it out as a line segment (the length of it is determined by the speed mag)
Oct 12, 2017 IAT 265 32
Feeler: Implementation consideration (1)
An obstacle can be represented using an outline (as for collision)
The steering force computed from the center of the obstacle to the frontend point of the feeler
Oct 12, 2017
IAT 265 33
Case study: Steering around an obstacle (1)
Step 1: Create the outline for the obstacle ...
Oct 12, 2017 IAT 265 34
Case study: Steering around an obstacle (2)
Step 2: Create feeler as a PVector and make it go along the direction of the velocity
How far should the feeler be probing?
– If too far, turned too early (way ahead of the obstacle)
– If too short, little time to correct speed for graceful turning
The distance (i.e. feeler’s length) should be proportionate to the magnitude of speed
Get a copy of speed vector so that it won’t mess it up
Oct 12, 2017 IAT 265 35
Case study: Steering around an obstacle (3)
Step 3: Generating the steering force
– Let Obstacle class implement the method (why?)
– The force goes from center of the obstacle to the end of the feeler
Pvector’s sub returns the force direction:
from ob’s center toward feelerEndPoint,
then set its amount as per ROT
Oct 12, 2017 IAT 265 36
Case study: Steering around an obstacle (4)
Step 4: Create a method for feeler to probe an obstacle in Fish class
– Which associates its feeler to an obstacle, and returns the steering force from it
Oct 12, 2017 IAT 265 37
Case study: Steering around an obstacle (5)
Step 5: Compute the acceleration and apply it for steering away
In moveToTarget(Food f) method, call the obstaclePushForce() method and compute acceleration, and then apply it for steering away from the obstacle
Oct 12, 2017 IAT 265 38
Summary on Collision Avoidance
Some collisions are undesirable and therefore need to be avoided – We need to predict the collision that will occur and modify
behaviors accordingly
Our approach here is to use force, which causes change in
acceleration, and acceleration changes velocity Two major applications
– Steer along walls
• Create a force vector to hold force added up forces from all four edges of the environment, and apply it to influence acceleration and finally the motion
– Steer around obstacles
• Use either FOV or feeler to project in the direction of moving.
• For feeler, use obstacle’s outline (Area object) to contain feeler’s endpoint for collision checking, and then generate force to turn the object away before hitting
Oct 12, 2017
IAT 265 39
Required
– Week 6 Readings in Canvas
2/14/2022 IAT 265 40
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com