CS代写 IAT-265, Spring 2022

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 seeds){
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