我正在尝试实现用于碰撞检测的矩形四叉树（而不是点）。
由于某种原因，并不总是检测到重叠/交叉/碰撞。我怀疑这与插入的对撞机查找附近对撞机的方式有关（参见 Quadtree.as 的“碰撞 A”和“碰撞 B”部分）。谁能确定为什么会发生这种情况？
下面是我的四叉树代码，以及其他几个类，当它们一起编译时，当我说“四叉树”“不准确”时，它们会告诉你我的意思。您只需要查看 Quadtree.as，但是将它与其他类一起编译应该可以帮助您理解我的问题。
谢谢！
四叉树.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();
}
}
}
主要作为：
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;
} );
}
}
}
测试对象.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;
}
}
}
对撞机.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 );
}
}
}
}