Advanced Collision Detection and Linear Search Algorithm
IAT-265, Spring 2022
School of Interactive Arts and Technology
______________________________________________________________________________________
Copyright By PowCoder代写 加微信 powcoder
SCHOOL OF INTERACTIVE ARTS + TECHNOLOGY [SIAT] | WWW.SIAT.SFU.CA
Advanced collision detection using Shape/Area
– Shape interface declared with intersects and contains methods
– Area object for creating outline and generating bounding box for compounded figures
Linear search algorithm
– Searching for smallest, largest, closest etc.
February 6, 2022 IAT 265 2
Advanced Approach for Collision Detection
Using Shape interface and Area class
February 6, 2022 IAT 265 3
Simple Collision method
Using bounding boxes for collision detection – like what we did in IAT-167
For instance for our bugs, we can detect collision with the following formula:
if (Math.abs(bugX – otherBug.bugX) <((BODY_WIDTH/2 + HEAD_WIDTH) * scale + (BODY_WIDTH/2 + HEAD_WIDTH)* otherBug.scale)
&& Math.abs(bugY - otherBug.bugY) < (BUG_HEIGHT/2 * scale + BUG_HEIGHT/2 * otherBug.scale)) {
// do something
February 6, 2022 IAT 265 4
Bug collision
– Complex Situation
What if the bugs are rotated?
– Apparently using the same box as is would be
problematic in terms of precision of collision detection – If we follow the same approach, we’ll need a more
convoluted formula that compares rotated bugs
• Involves a lot of computation using sin() and cos()
– too complex
February 6, 2022 IAT 265 5
: Collision with Dynamic Bounding Box
With Java constructs, we can create a dynamic bounding box, which bounds the figure no matter how its orientation changes ...
Specifically, java.awt package has an interface Shape and a class Area, which would facilitate us to create bounding boxes as such for collision detection
February 6, 2022 IAT 265 6
PPP for illustration of the Algorithm
Specifically, in order to create a dynamic bounding box for a compounded figure, we need to:
– Create the outline of the figure as an Area object
– Transform the outline in exactly the same manner as the figure
– Use the outline to generate the bounding box as a Rectangle2D object, which accommodates dynamically the outline and thereby the whole figure
– Use both outline and bounding box for collision detection via Shape’/Area’s relevant methods
February 6, 2022 IAT 265 7
Shape interface and Area class
Methods declared by Shape :
– boolean contains(Rectangle2D rect), contains(double x, double y) – boolean intersects(Rectangle2D rect)
– Rectangle2D getBounds2D() – used to return the bounding box
Area – the class for creating figure outline – implements Shape
– Many Graphics2D classes implement Shape : including those geom classes: Rectagle2D, Ellipse2D, Line2D, ... etc.
We will use these methods for collision detection, e.g.
– Use one figure’s outline to call intersects(Rectangle2D rect) to
check against another’s bounding box
– To detect collision b/w a point and a figure: Use figure’s outline to
call contains(double x, double y) to check against a point (x, y) February 6, 2022 IAT 265 8
February 6, 2022 IAT 265
From http://www.datadisk.co.uk/html_docs/java/graphics_java2d.htm
Step1: Create the Outline for a Figure
Create the outline for the compounded figure, which consists of multi-shapes
– The outline is an Area object, which can be composed by way of the following method
– add(Area a): adds a constituent shape (converted into an Area object first) as part of the outline
– Repeat calling it until all the constituent shapes are added in the complete outline for the compounded figure
February 6, 2022 IAT 265 10
How to generate the Bounding Box?
The outline as an Area object, has the following method for so doing
getBounds2D()
– Returns the bounding box that holds the outline – and thereby the whole compounded figure
– We are sure it must have such a method, why? February 6, 2022 IAT 265 11
Example: complex shape
shap = new Ellipse2D.Double(-10,-10,100,20); shap1 = new Ellipse2D.Double(-50,-10,20,120);
//compose its outline area
Area outline = new Area(); outline.add(new Area(shap)); outline.add(new Area(shap1));
//return its bounding box*
outline.getBounds2D();
* Please note bounding box generated here is a
static one as no transformation is involved yet
February 6, 2022 IAT 265 12
Note to the Outline of a Figure e.g. Bug
Only shapes that contribute to the outline need to be included:
February 6, 2022 IAT 265 13
Recap: What we need:
Specifically, in order to create a dynamic bounding box for a compounded figure, we need to:
– Create the outline of the figure as an Area object
– Transform the outline in exactly the same manner as the figure
– Use the outline to generate the bounding box as Rectangle2D object, which accommodates dynamically the outline and thereby the whole figure
– Use both outline and bounding box for collision detection via Shape’/Area’s relevant methods
February 6, 2022 IAT 265 14
Why transforming outline?
That’s because our figure (e.g. bug) keeps moving, rotating and/or scaling
– As its outline, it must move, rotate, and/or scale in the same manner as the figure
– The bounding box generated by it, will adjust its room dynamically to accommodate the space needed by these different transformations of the figure
February 6, 2022 IAT 265 15
Step 2: Transforming Outline
Create a method for transforming outline, and then return its dynamic bounding box
– We can use an AffineTransform object to do the transformations for the outline of the figure in exactly the same manner as the figure itself
– However, the transformation involved here is not intended for rendering* but for collision detection purpose only doesn’t make sense to use g2 – the drawing pen – for doing the transformation for the outline
* We may choose to render the outline/bounding box for demonstration purpose, but need to remove them eventually
February 6, 2022 IAT 265 16
AffineTransform revisited
Remember we ever called g2.getTransform() before, which returns AffineTransform object that stores the drawing space attributes
Apparently, when calling g2.translate(), g2.rotate(), g2.scale() they were modifying the drawing space associated with g2
Here g2 used its internal copy of AffineTransform object to compute coordinates for drawing objects intended for rendering
Since our purpose here is not for rendering, we would, rather than using g2, create an AffineTransform object by ourselves
Specifically, we’ll make our outline object have the same transformation as the figure it wraps around
February 6, 2022 IAT 265 17
AffineTransform Class
Create an AffineTransform object, make it do the same transformations as the figure in question, and then apply it to its outline object
AffineTransform defines relevant methods for us to do so: – translate(double tx, double ty)
– rotate(double angle)
– scale(double sx, double sy)
Here is the killer method: creating a transformed outline that is dynamically transforming along with the figure
– Shape createTransformedShape(Shape s)
February 6, 2022 IAT 265 18
Transformed outline
Please note, the way of transformation shown here is for outline transformation only, you can’t use it for your regular shape’s transforms for rendering stick to Graphics2D
The transformation done here is not for drawing, we could however draw it out explicitly if necessary for demo purpose
February 6, 2022 IAT 265 19
createTransformedShape() returns Shape – But Shape is an interface! It cannot be directly
instantiated. So what object does it return?
– It returns an object Path2D.Double, a geom class for
building polygon that implements Shape
Apparently it makes sense to treat the outline of a compounded figure as a polygon object
February 6, 2022 IAT 265 20
Step 3: Generate the dynamic Bounding Box
Once we have the transformed outline as returned from createTransformedShape(), we can simply call its getBounds2D() method to return the dynamic bounding box:
– Shape outline = getTransformedOutline();
– Rectangle2D bbox = outline.getBounds2D();
Now we are ready to check collision using both outline and bounding box!
February 6, 2022 IAT 265 21
Step 4: Check collision using Outline and Bounding box
Create a method for checking collision between two objects via transformed outlines and their bounding boxes
– Need to call Area’s intersects() or contains() method
– intersects(Rectangle2D rect) is for checking collision between objects
– contains(double x, double y) is for checking if a point (e.g. mouse point) hits an object
February 6, 2022 IAT 265 22
Intersects method
Declared in Shape interface
– boolean intersects(Rectangle2D rect)
– Tests if the outline’s area intersects the specified Rectangle2D object
We can check one object’s outline against the bounding box of the other object, like:
if (outline.intersects(otherOutline.getBounds2D())){
//resolve collision
Which object’s outline to use for calling the method, to check against the other’s bounding box?
Oct 12, 2017 IAT W265 23
Intersects method
green.intersects(red.getBounds2D())? Or
red.intersects(green.getBounds2D())?
It turns out that we need BOTH calls to test a close-
to-accurate collision, i.e.
If (green.intersects(red.getBounds2D()) &&
red.intersects(green.getBounds2D())){
//collision
Oct 12, 2017
IAT 265 24
Calling one vs. Both
Tests to true when taking green’s outline against
red's bounding box
– Objectsthemselvesarestillfarawayfromeach
Tests to true when taking red's outline against
green’s bounding box
– Objectsthemselvesarestillfarawayfromeach
Tests to true when taking green’s outline against red's bounding box && taking red’s outline against green's bounding box
– Objectsthemselvesareclosesttooneanother
February 6, 2022 IAT 265 25
Case study: Bug vs. Seeds
A bug always chases and eats the seed that is closest to it!
February 6, 2022 IAT 265 26
A couple of issues to be addressed
How to detect collision between bug and a seed by way of outline-bound intersects?
For the bug: how to identify the closest seed among a collection and then approach to it?
How to detect collision between bug and edges via outline-bound intersects?
February 6, 2022 IAT 265 27
Detect Collision b/w bug and a seed
class Bug {
//Fields for Ladybug attributes
...private Area outline;
...private void createOutline(){
outline = new Area(new Area(body));
public boolean detectCollision(Seed seed){ boolean hit = false;
if(getTFOutline().intersects(seed. getTFOutline().getBounds2D())
&& seed.getTFOutline().intersects( getTFOutline().getBounds2D()))
hit = true;
} return hit;
private Shape getTFOutline(){ AffineTransform at = new AffineTransform(); at.translate(pos.x, pos.y); at.rotate(vel.heading());
at.scale(scale, scale);
}return at.createTransformedShape(outline);
outline.add(new Area(head));
outline.add(new Area(upAntenna)); } outline.add(new Area(dnAntenna));
Then in BugPanel:
for (int i = 0; i < seeds.size(); i++) { if (bug.detectCollision(seeds.get(i)))
seeds.remove(i);
February 6, 2022 IAT 265 28
Identify the closest seed among a collection
Actually a search issue in terms of computing concept
– how to search for the seed in a list that has the smallest distance from the bug
Search algorithm: about searching for an item in a list per some criteria: largest, smallest, match certain target (e.g. give me smith’s phone#)
– E.g. find the smallest number in an array:
February 6, 2022 IAT 265 29
Algorithm for searching the smallest number
For an unsorted list like this, must search linearly
Linear search algorithm:
1. Start by declaring a variable s for holding the smallest number
and initialize it with the first element
2. Iterate through the rest of the elements
• Compare the current element with s
• If the current element is smaller then update s with it
3. After running though the whole list, s ends up with holding the smallest number
February 6, 2022 IAT 265 30
Codify the algorithm
int findSmallestNumber(int[] arr) { int smallest = arr[0];
for(int i=1; i
if (seeds.size() == 0) //if list empty
return null;
Seed closestSeed = seeds.get(0);
float closestDist = PVector.dist(this.getPos(),
closestSeed.getPos());
for (Seed s : seeds) //for-each loop
if (PVector.dist(this.getPos(), s.getPos())<
closestDist) {
closestSeed = s;
closestDist = PVector.dist(this.getPos(),
closestSeed.getPos()); } return closestSeed;
February 6, 2022 IAT 265 33
Then in BugPanel: Seed target =
bug.searchClosestSeed(seeds);
if (target != null) { target.setColor(Util.randomColor());
} bug.chase(target);
Case study: Bug vs. Edges
detect collision between bug and edges via outline-bound intersects
February 6, 2022 IAT 265 34
Detect collision between bug and edges
Create four thin Rectangle2D objects (invisible) around the edges
Check if bug’s outline intersects any one of them
February 6, 2022 IAT 265 35
Four thin Rectangle2D objects around the edges
February 6, 2022 IAT 265 36
Codify Collision Detection between bug and edges
class Bug {
//All others the same as before
...public void edgeCollision(Dimension panelSize) { Rectangle2D.Double left = new Rectangle2D.Double(40, 50, 10,
panelSize.height - 100);
Rectangle2D.Double right = new Rectangle2D.Double(panelSize.width
- 100, 50, 10, panelSize.height - 150); Rectangle2D.Double top = new Rectangle2D.Double(50, 40,
panelSize.width, 10);
Rectangle2D.Double bottom = new Rectangle2D.Double(50,
panelSize.height - 100, panelSize.width - 150, 10);
if (getTFOutline().intersects(left) && vel.x < 0) vel.x *= -1; if (getTFOutline().intersects(right) && vel.x > 0) vel.x *= -1; if (getTFOutline().intersects(top) && vel.y < 0) vel.y *= -1;
if (getTFOutline().intersects(bottom) && vel.y > 0) vel.y *= -1; February 6, 2022 IAT 265 37
Summary on advanced collision detection
Using geometry directly is difficult when translations, rotations and scaling are involved
Java.awt.geom package provides classes for representing objects as geoms, which have facility for checking intersections or containment
For compounded figure objects we can create its outline using Area class
AffineTransform object can be used to transform the outline in the same manner as its figure
We test collision for compounded figure objects using Shape’/Area’s intersects method, involving their outlines and bounding boxes
Oct 12, 2017 IAT 265 38
Required
– Week 5 Readings in Canvas
February 6, 2022 IAT 265 39
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com