最近手头在做深度排序的优化.
于是做了下面一个实验
在场景上创建 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.
{
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.
{
add(objVec);
m_callBack = back;
}
private function add(objVec:Vector.
{
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%.