四叉树

最近手头在做深度排序的优化.
于是做了下面一个实验
在场景上创建 2000 个对象. 然后使用传统的深度排序算法,全排.
[cc lang=”actionscript3″ nowrap=”false”]
private function checkCollsion() : void
{
_rects.sort(sortFun);

var rect : Rect;
for(var i : int = 0; i < _rects.length; i ++){ rect = _rects[i] as Rect; if(_container.getChildAt(i) != rect){ _container.setChildIndex(rect,i); } } } private function sortFun(p1 : DisplayObject, p2 : DisplayObject) : int { return p1.y > p2 .y ? 1 : -1;
}
[/cc]
结果帧数降到了6帧.

于是考虑使用四叉树来做.
在收集资料的时候发现了一篇 javsScript 实现的四叉树

改写成AS后的代码为

[cc lang=”actionscript3″ nowrap=”false”]
package
{
import flash.geom.Rectangle;

public class QuadTree
{
private static const MAX_OBJECT : int = 5;
private static const MAX_LEVELS : int = 5;

private var level : int;
private var objects : Vector.;
private var bounds : Rectangle;
private var nodes : Vector.;

public function QuadTree(plevel : int, pBounds : Rectangle)
{
level = plevel;
objects = new Vector.();
bounds = pBounds;
nodes = new Vector.();
}

/**
* 清空树
*/
public function clear() : void
{
objects.length = 0;

for(var i : int = nodes.length – 1; i >= 0; i –)
{
nodes[i].clear();
nodes[i] = null;
}
}

/**
* 将一棵树切成4棵树
*/
public function split() : void
{
var subWidth : int = int(bounds.width >> 1);
var subHeight : int = int(bounds.height >> 1);
var x : int = int(bounds.x);
var y : int = int(bounds.y);

nodes[0] = new QuadTree(level + 1, new Rectangle(x + subWidth, y , subWidth, subHeight)); //右上
nodes[1] = new QuadTree(level + 1, new Rectangle(x,y,subWidth,subHeight)); //左上
nodes[2] = new QuadTree(level + 1, new Rectangle(x,y + subHeight, subWidth, subHeight)); //左下
nodes[3] = new QuadTree(level + 1, new Rectangle(x + subWidth, y + subHeight, subWidth, subHeight)); //右下
}

/**
* 检测一个对象在哪一个节点
* 如果一个对象在多节点的分割线上,则该对象属于它们的父节点
*/
private function getIndex(pRect : Rectangle) : int
{
var index : int = -1;
var verticalMidPoint : Number = bounds.x + (bounds.width >> 1);
var horizontalMidPoint : Number = bounds.y + (bounds.height >> 1);

//对象能完全容纳在顶部节点
var topQuadrant : Boolean = (pRect.y < horizontalMidPoint && pRect.y + pRect.height < horizontalMidPoint); //对象能完全容纳在底部节点 var bottomQuadrant : Boolean = (pRect.y > horizontalMidPoint);
//对象能完全容纳在左部节点
if(pRect.x < verticalMidPoint && pRect.x + pRect.width < verticalMidPoint){ if(topQuadrant){ index = 1; }else if(bottomQuadrant){ index = 2; } } //对象能完全容纳在右部节点 else if(pRect.x > verticalMidPoint){
if(topQuadrant){
index = 0;
}else if(bottomQuadrant){
index = 3;
}
}

return index;
}

/**
* 插入一个对象,如果该树已经被占满,则分割成4棵新树
* 并将该对象插入对应的树中
*/
public function insert(pRect : Rectangle) : void{
var index : int;
if(nodes.length){
index = getIndex(pRect);

if(index != -1){
nodes[index].insert(pRect);
return;
}
}

objects.push(pRect);

if(objects.length > MAX_OBJECT && level < MAX_LEVELS){ split(); var removeList : Array = []; for each(var rect : Rectangle in objects){ index = getIndex(rect); if(index != -1){ nodes[index].insert(rect); removeList.push(rect); } } while(removeList.length) { objects.splice(objects.indexOf(removeList.shift()),1); } } } /** * 返回所有可能会碰撞的对象 */ public function retrieve(returnObjects : Vector., pRect : Rectangle) : Vector.
{
var index : int = getIndex(pRect);
if(index != -1 && nodes.length){
returnObjects = returnObjects.concat(nodes[index].retrieve(returnObjects, pRect));
}

returnObjects = returnObjects.concat(objects);

return returnObjects;
}
}
}
[/cc]

运行结果可以看出 对于左下角的元素判定附带了所有相交于分割线上的点,这是因为该算法对于无法区分归属的点,都作为父树的元素.
但是这个算法有一个问题就是无法区分相交的矩形.

于是对此做了些修改
[cc lang=”actionscript3″ nowrap=”false”]
package quadTree
{
import flash.display.DisplayObject;
import flash.filters.DisplacementMapFilter;
import flash.geom.Rectangle;
import flash.utils.getTimer;

import quadTree.FNode;

public class FQuad
{
public var x:Number;
public var y:Number;
public var width:Number;
public var height:Number;

public static var divisions:uint = 8;

protected var m_nodes : Vector.;
protected var m_rect : Rectangle;
protected var m_halfWidth:Number;
protected var m_halfHeight:Number;
protected var m_midX:Number;
protected var m_midY:Number;
protected var m_canSubDivide:Boolean;
protected var m_headNode:FNode;
protected var m_tailNode:FNode;

protected static var m_target : DisplayObject;
protected static var m_targetRect : Rectangle = new Rectangle();
protected static var m_callBack : Function;
protected static var m_iterator : FNode;
protected static var m_min : uint;

public function FQuad(X:Number, Y:Number, w:Number, h:Number, p:FQuad = null)
{
x = X;
y = Y;
width = w;
height = h;

m_headNode = m_tailNode = new FNode();

if (p != null)
{
var iterator:FNode;
var ot:FNode;
if (p.m_headNode.object != null)
{
iterator = p.m_headNode;
while(iterator != null)
{
if (m_tailNode.object != null)
{
ot = m_tailNode;
m_tailNode = new FNode();
ot.next = m_tailNode;
}
m_tailNode.object = iterator.object;
iterator = iterator.next;
}
}
}
else
{
m_min = (width + height) / (2 * divisions);
}
m_canSubDivide = (width > m_min) || (height > m_min);
m_rect = new Rectangle(X,Y,X + width,Y + height);
m_nodes = new Vector.();
m_halfWidth = width >> 1;
m_halfHeight = height >> 1;
m_midX = X + m_halfWidth;
m_midY = Y + m_halfHeight;
}

public function clear() : void
{
m_headNode = m_tailNode = new FNode();
m_nodes = new Vector.();
}

public function destroy():void
{
m_headNode.destroy();
m_headNode = null;
m_tailNode.destroy();
m_tailNode = null;

var node : FQuad;
for each(node in m_nodes)
{
node.destroy();
node = null;
}
m_nodes = null;

m_target = null;
m_callBack = null;
}

public function load(objVec:Vector., back:Function = null):void
{
add(objVec);
m_callBack = back;
}

private function add(objVec:Vector.):void
{
var len:int = objVec.length;
for (var i:int = 0; i < len; i++) { m_target = objVec[i]; m_targetRect.x = m_target.x; m_targetRect.y = m_target.y; m_targetRect.width = m_target.width; m_targetRect.height = m_target.height; addObject(); } } /** * 检测一个对象在哪一个节点 * 如果一个对象在多节点的分割线上,则该对象属于它们的父节点 */ private function getIncludeIndex() : int { var index : int = -1; //对象相交在顶部 var topQuadrant : Boolean = (m_targetRect.top > m_rect.top && m_targetRect.bottom < m_midY) //对象相交在底部 var bottomQuadrant : Boolean = (m_targetRect.top > m_midY && m_targetRect.bottom < m_rect.height) //对象在左侧 if(m_targetRect.left > m_rect.left && m_targetRect.right < m_midX) { if(topQuadrant){ index = 0; }else if(bottomQuadrant){ index = 3; } } //对象在右侧 else if(m_targetRect.left > m_midX && m_targetRect.right < m_rect.right) { if(topQuadrant){ index = 1; }else if(bottomQuadrant){ index = 2; } } return index; } /** * 检测一个对象在哪一个节点 * 如果一个对象在多节点的分割线上,则该对象属于它们的父节点 */ private function getCrossIndex() : int { var index : int = -1; //对象相交在顶部 var topQuadrant : Boolean = (m_targetRect.bottom > m_rect.top && m_targetRect.top < m_midY); //对象相交在底部 var bottomQuadrant : Boolean = (m_targetRect.bottom > m_midY && m_targetRect.top < m_rect.height); //对象在左侧 if(m_targetRect.left > m_rect.left && m_targetRect.right < m_midX) { if(topQuadrant){ index = 0; }else if(bottomQuadrant){ index = 3; } } //对象在右侧 else if(m_targetRect.left > m_midX && m_targetRect.right < m_rect.right) { if(topQuadrant){ index = 1; }else if(bottomQuadrant){ index = 2; } } return index; } /** * 将一棵树切成4棵树 */ public function split() : void { if(!m_nodes.length){ m_nodes[0] = new FQuad(m_rect.left, m_rect.top, m_halfWidth, m_halfHeight, this); //左上 m_nodes[1] = new FQuad(m_midX, m_rect.top, m_halfWidth, m_halfHeight, this); //右上 m_nodes[2] = new FQuad(m_midX, m_midY, m_halfWidth, m_halfHeight, this); //右下 m_nodes[3] = new FQuad(m_rect.left, m_midY, m_halfWidth, m_halfHeight, this); //左下 } } private function addObject():void { if (!m_canSubDivide || ((m_rect.left >= m_targetRect.left) &&
(m_rect.right <= m_targetRect.right) && (m_rect.top >= m_targetRect.top)
&& (m_rect.bottom <= m_targetRect.bottom))) { addToList(); return; } //分割 split(); var index : int; if(m_nodes.length){ index = getIncludeIndex(); if(index != -1){ m_nodes[index].addObject(); return; } index = getCrossIndex(); if(index != -1){ m_nodes[index].addObject(); } } } protected function addToList():void { var ot:FNode; if (m_tailNode.object != null) { ot = m_tailNode; m_tailNode = new FNode(); ot.next = m_tailNode; } m_tailNode.object = m_target; if (!m_canSubDivide) return; var node : FQuad; for each(node in m_nodes) { node.addToList(); } } public function execute():void { var iterator:FNode; if (m_headNode.object != null) { iterator = m_headNode; while (iterator != null) { m_target = iterator.object; m_iterator = iterator.next; if (m_iterator != null && m_iterator.object != null) { overlapNode(); } iterator = iterator.next; } } var node : FQuad; for each(node in m_nodes) { node.execute(); } } public function getCheckList(target : DisplayObject) : Array { var iterator : FNode; var result : Array = []; if(m_headNode.object != null) { iterator = m_headNode; while (iterator != null) { m_target = iterator.object; m_iterator = iterator.next; if ((m_target === target) && (m_iterator != null) && (m_iterator.object != null)) { result = result.concat(overlapNode()); } iterator = iterator.next; } } var node : FQuad; for each(node in m_nodes) { result = result.concat(node.getCheckList(target)); } return result; } protected function overlapNode():Array { var checkObject:DisplayObject; var result : Array = []; while(m_iterator != null) { checkObject = m_iterator.object; if(m_target === checkObject) { m_iterator = m_iterator.next; continue; } m_callBack(m_target, checkObject); result.push(checkObject); m_iterator = m_iterator.next; } return result; } } } [/cc] 使用四叉树后,在2000个对象的情况下进行深度排序,发现只比传统方式快2帧而已... 最消耗性能的是 setChildIndex 的方法. 那么如何避免频繁调用 setChildIndex呢,那就是改变树的精度,将树的层级提高,每层可容纳的显示对象减少,这样在一个区域内需要进行比较的数量也将会极少. 在我将 树的层级拉到20级的时候, 帧数已经达到了 传统的方式的一倍以上. 但是层级最高划分区域不能小于最大对象的大小,否则层级就失去意义了. 总结: 对于手头的页游来说,同屏1000人情况传统方式可以完全满足,优化的余地不大了.同屏2000人的时候...我估计客户端都挂掉了吧...可以考虑用在别处. 如果把四叉树用在 hitTestObject 上,那么遍历效率倒是有非常大的提升. BTW:Rectangle 中 intersects 方法 甚至还不如 手动的 top,left,right,bottom比较. 其性能差距有90%.

发表评论

电子邮件地址不会被公开。 必填项已用*标注