1
J'essaie de mettre en œuvre un quadtree de rectangles (au lieu de points) à utiliser pour la détection de collision.Quadtree détecte une collision inexacte
Pour une raison quelconque, le chevauchement/intersection/collision n'est pas toujours détecté. Je suppose que cela a quelque chose à voir avec la façon dont un collisionneur inséré cherche des collisionneurs proches (voir les sections "COLLISION A" et "COLLISION B" de Quadtree.as). Quelqu'un peut-il identifier pourquoi cela se produit? Ci-dessous est mon code pour le quadtree, et plusieurs autres classes qui, une fois compilées, vous montreront ce que je veux dire quand je dis que le "quadtree" est "inexact". Vous avez seulement besoin de regarder Quadtree.as, mais le compiler avec les autres classes devrait vous aider à comprendre mon problème.
Merci!
Quadtree.as:
package
{
import flash.geom.Rectangle;
import flash.display.Sprite;
public class Quadtree
{
private var root:Node;
public function Quadtree(width:Number, height:Number, depth:int)
{
root = new Node(0, 0, width, height, depth);
}
public function insert(collider:Collider) : void
{
var current:Node = root;
var colliderRectangle:Rectangle = collider.colliderRectangle;
// Insertion is not recursive, to reduce function calls and make the tree faster.
// A break is called when the collider is inserted into a particular node.
while(true)
{
// BEGIN COLLISION A
// Collide the collider being inserted with the colliders already present in the tree.
// At least, it will see all of the colliders it passes by as it goes down.
var colliders:Array = current.colliders;
var max:int = colliders.length;
for(var i:int = 0; i < max; i++)
{
// Narrow collision detection (and response) is performed by the Collider.collide() function.
var other:Collider = colliders[i];
collider.collide(other);
other.collide(collider);
}
// END COLLISION A
// If the current node is at the maximum depth (lower is higher),
// insert the collider into the current node.
if(current.depth == 0)
{
current.colliders.push(collider);
break;
}
// Determine which quadrants the collider intersects with.
var currentX:Number = current.x;
var currentY:Number = current.y;
var halfWidth:Number = current.halfWidth;
var halfHeight:Number = current.halfHeight;
var onLeft:Boolean = (currentX + current.width) - colliderRectangle.right >= halfWidth;
var onTop:Boolean = (currentY + current.height) - colliderRectangle.bottom >= halfHeight;
var onRight:Boolean = colliderRectangle.left - currentX >= halfWidth;
var onBottom:Boolean = colliderRectangle.top - currentY >= halfHeight;
// If the collider is not completely contained in one quadrant of the current node,
// insert the collider into the current node, then check if the collider collides with
// any of the colliders in the descendants of the current node (see COLLISION B).
if((!onTop && !onBottom) || (!onLeft && !onRight))
{
current.colliders.push(collider);
// BEGIN COLLISION B
var tl:Node = current.tl;
var tr:Node = current.tr;
var bl:Node = current.bl;
var br:Node = current.br;
if(tl)
{
tl.collideDescendants(collider);
}
if(tr)
{
tr.collideDescendants(collider);
}
if(bl)
{
bl.collideDescendants(collider);
}
if(br)
{
br.collideDescendants(collider);
}
// END COLLISION B
break;
}
// If the collider does not span more than one quadrant, determine which of the quadrants contain it.
else if(onTop && onLeft)
{
if(!current.tl)
{
current.tl = new Node(currentX, currentY, halfWidth, halfHeight, current.depth);
}
current = current.tl;
}
else if(onTop && onRight)
{
if(!current.tr)
{
current.tr = new Node(currentX + halfWidth, currentY, halfWidth, halfHeight, current.depth);
}
current = current.tr;
}
else if(onBottom && onLeft)
{
if(!current.bl)
{
current.bl = new Node(currentX, currentY + halfHeight, halfWidth, halfHeight, current.depth);
}
current = current.bl;
}
else if(onBottom && onRight)
{
if(!current.br)
{
current.br = new Node(currentX + halfWidth, currentY + halfHeight, halfWidth, halfHeight, current.depth);
}
current = current.br;
}
}
}
public function clear() : void
{
root.clear();
}
}
}
import flash.display.Sprite;
import flash.geom.Rectangle;
class Node
{
public var extent:Rectangle;
public var tl:Node;
public var tr:Node;
public var bl:Node;
public var br:Node;
public var colliders:Array;
public var depth:int;
public var x:Number;
public var y:Number;
public var width:Number;
public var height:Number;
public var halfWidth:Number;
public var halfHeight:Number;
public function Node(x:Number, y:Number, width:Number, height:Number, depth:int)
{
extent = new Rectangle(x, y, width, height);
halfWidth = width * 0.5;
halfHeight = height * 0.5;
this.depth = depth - 1;
colliders = [];
this.x = x;
this.y = y;
this.width = width;
this.height = height;
}
public function collideDescendants(collider:Collider) : void
{
var max:int = 0;
var other:Collider;
for(var i:int = 0; i < max; i++)
{
other = colliders[i];
collider.collide(other);
other.collide(collider);
}
if(depth == 0)
{
return;
}
var colliderRectangle:Rectangle = collider.colliderRectangle;
var left:Number = colliderRectangle.left;
var right:Number = colliderRectangle.right;
var top:Number = colliderRectangle.top;
var bottom:Number = colliderRectangle.bottom;
if(tl && !(bottom < tl.y || tl.y + tl.height < top || right < tl.x || tl.x + width < left))
{
tl.collideDescendants(collider);
}
if(tr && !(bottom < tr.y || tr.y + tr.height < top || right < tr.x || tr.x + width < left))
{
tr.collideDescendants(collider);
}
if(bl && !(bottom < bl.y || bl.y + bl.height < top || right < bl.x || bl.x + width < left))
{
bl.collideDescendants(collider);
}
if(br && !(bottom < br.y || br.y + br.height < top || right < br.x || br.x + width < left))
{
br.collideDescendants(collider);
}
}
public function clear() : void
{
colliders.splice(0, colliders.length);
if(tl)
{
tl.clear();
}
if(tr)
{
tr.clear();
}
if(bl)
{
bl.clear();
}
if(br)
{
br.clear();
}
}
}
Main.as:
package
{
import flash.display.Sprite;
import flash.events.Event;
import flash.events.MouseEvent;
import flash.text.TextField;
import flash.text.TextFormat;
public class Main extends Sprite
{
public function Main()
{
if (stage) init();
else addEventListener(Event.ADDED_TO_STAGE, init);
}
private function init(e:Event = null) : void
{
removeEventListener(Event.ADDED_TO_STAGE, init);
var objects:Array = [];
var quadtree:Quadtree = new Quadtree(640, 480, 5);
var max:int = 50;
for(var i:int = 0; i < max; i++)
{
var object:TestObject = new TestObject();
addChild(object);
objects.push(object);
}
var bruteMsg:String = "Using BRUTE FORCE! Click to switch to QUADTREE";
var quadMsg:String = "Using QUADTREE! Click to switch to BRUTE FORCE";
var text:TextField = new TextField();
text.text = quadMsg;
text.selectable = false;
text.width = 300;
text.defaultTextFormat = new TextFormat("Arial");
text.setTextFormat(text.defaultTextFormat);
addChild(text);
var last:Date = new Date();
var useQuadtree:Boolean = true;
addEventListener(Event.ENTER_FRAME, function(f:Event) : void {
var now:Date = new Date();
var deltaTime:Number = (now.getTime() - last.getTime()) * 0.001;
last = now;
for(i = 0; i < max; i++)
{
object = objects[i];
object.update(deltaTime);
}
if(useQuadtree)
{
quadtree.clear();
for(i = 0; i < max; i++)
{
object = objects[i];
quadtree.insert(object.collider);
}
}
else
{
for(i = 0; i < max; i++)
{
var a:TestObject = objects[i];
for(var j:int = i + 1; j < max; j++)
{
var b:TestObject = objects[j];
a.collider.collide(b.collider);
b.collider.collide(a.collider);
}
}
}
});
stage.addEventListener(MouseEvent.CLICK, function(f:Event) : void {
text.text = useQuadtree ? bruteMsg : quadMsg;
useQuadtree = !useQuadtree;
});
}
}
}
TestObject.as:
package
{
import flash.display.Sprite;
import flash.geom.Point;
public class TestObject extends Sprite
{
private static const WIDTH:int = 20;
private static const HEIGHT:int = 30;
private static const SPEED:Number = 100;
private static const CANVAS_WIDTH:Number = 640;
private static const CANVAS_HEIGHT:Number = 480;
public var direction:Point;
public var collider:TestCollider;
public function TestObject()
{
super();
graphics.lineStyle(1, 0x0000FF);
graphics.drawRect(0, 0, WIDTH, HEIGHT);
x = Math.random() * (CANVAS_WIDTH - WIDTH);
y = Math.random() * (CANVAS_HEIGHT - HEIGHT);
direction = new Point(Math.random() - 0.5, Math.random() - 0.5);
direction.normalize(1);
collider = new TestCollider(this, x, y, width, height);
}
public function update(deltaTime:Number) : void
{
var displacement:Number = SPEED * deltaTime;
x = x + direction.x * displacement;
y = y + direction.y * displacement;
if(x < 0)
{
x = 0;
direction.x *= -1;
}
else if(x + WIDTH > CANVAS_WIDTH)
{
x = CANVAS_WIDTH - WIDTH;
direction.x *= -1;
}
if(y < 0)
{
y = 0;
direction.y *= -1;
}
else if(y + HEIGHT > CANVAS_HEIGHT)
{
y = CANVAS_HEIGHT - HEIGHT;
direction.y *= -1;
}
collider.colliderRectangle.x = x;
collider.colliderRectangle.y = y;
}
}
}
Collider.as:
package
{
import flash.geom.Rectangle;
public class Collider
{
virtual public function get colliderRectangle() : Rectangle { return null; };
virtual public function collide(collider:Collider) : void { /* NARROW COLLISION DETECTION AND COLLISION RESPONSE CODE HERE */ }
}
}
TestCollider.as:
package
{
import flash.geom.Rectangle;
public class TestCollider extends Collider
{
private var rectangle:Rectangle;
private var parent:TestObject;
public function TestCollider(parent:TestObject, x:Number, y:Number, width:Number, height:Number)
{
this.parent = parent;
rectangle = new Rectangle(x, y, width, height);
}
override public function get colliderRectangle() : Rectangle
{
return rectangle;
}
override public function collide(collider:Collider) : void
{
var otherRect:Rectangle = collider.colliderRectangle;
if(rectangle.intersects(otherRect))
{
var intersection:Rectangle = rectangle.intersection(otherRect);
if(intersection.width < intersection.height)
{
parent.x += intersection.width * 0.5 * (rectangle.x < otherRect.x ? -1 : 1);
}
else
{
parent.y += intersection.height * 0.5 * (rectangle.y < otherRect.y ? -1 : 1);
}
parent.direction.x *= ((parent.direction.x > 0 && otherRect.x > rectangle.x) || (parent.direction.x < 0 && otherRect.x < rectangle.x) ? -1 : 1);
parent.direction.y *= ((parent.direction.y > 0 && otherRect.y > rectangle.y) || (parent.direction.y < 0 && otherRect.y < rectangle.y) ? -1 : 1);
}
}
}
}