书接上回，上回书说道搜索优化在ARPG类游戏中的应用，并举了一些栗子，今天我们就来具体的完成一个四叉树的创建
标题：四叉树创建
鄙人会2中方法 ，一种是循环式，另一种是递归式，我更倾向于递归式创建，因为这种创建方式比较自然，简洁，也很好理解，下面来介绍一下如何使用递归方式创建一个四叉树
本系列文章均采用AS3编写，如有不懂的地方，请自行查阅相关语法
首先，我们创建一个四叉树类，NodeTree.as
为了方便使用，我在NodeTree.as中声明了如下属性：
protected var _id_:String;
//是否初始化
public var initialized:Boolean;
//简单实现一种宽高一致的地图
private var _mapSize:int = 10000;
//最小的格子大小
private var _minSize:int = 200;
//树的深度
private var _depth:int;
//顶层节点
private var _topNode:NodeRect;
//节点列表
private var _nodeHash:Dictionary;
有了上面的属性，我就可以很方便的知道这个树有没有被初始化创建完毕，以及树的深度，和节点列表信息
接下来需要一个很关键的方法了，建树的方法，我给他起了个名字叫 function build():void{}
public function build(mapSize:int,minSize:int):void{
TreeManager.instance.put(this);
_depth = getDepth(mapSize,minSize);
//去整，算出所有的
minSize = Math.round(mapSize/Math.pow(2,_depth));
mapSize = minSize*Math.pow(2,_depth);
_topNode = new NodeRect;
//不规则地图还需详细计算，这里不做考虑
_topNode.setup(this.id_,null,new Rectangle(0,0,mapSize,mapSize),_depth);
initialized=true;
}
这个方法中你会发现TreeManager.instance.put(this)，不要惊慌，他其实就是一个简单的单例，我为了方便查找不同的四叉树对象，对他进行了一下简单的管理，如果你真的想知道里面是什么样子的，我现在就告诉你
public class TreeManager
{
public var hash:Dictionary = new Dictionary;
private static var _instance:TreeManager;
public function TreeManager()
{
}
public static function get instance():TreeManager{
return _instance||= new TreeManager;
}
public function put(tree:NodeTree):void{
if(tree == null)return;
if(hash[tree.id_] == null){
hash[tree.id_]= tree;
}
}
public function take(_id:String):NodeTree{
return hash[_id];
}
看到了吧，其实很简单，有了这个管理器你可以在需要的时候根据每个树的唯一id就可以获取到了
接下来如果没猜错的话，你会一直寻找
//顶层节点
private var _topNode:NodeRect;
在哪里定义和实现，下面就来展示一下这个NodeRect.as 矩形节点类，这个类是树节点的核心部分，完成建树的递归过程也在此实现
下面来实现NodeRect.as中的setup方法
四叉树每个叶子节点都有4个，我么做如下声明
//该节点下的叶子节点
private var _nodeA:NodeRect;
private var _nodeB:NodeRect;
private var _nodeC:NodeRect;
private var _nodeD:NodeRect;
//该节点隶属的深度
private var _depth:int;
//该节点的父节点(topNode) id
private var _tid:String;
为了方便获取四叉树对象，我把树的唯一id (tid）作为了第一个参数，
为了记录父节点的信息，我将父节点的唯一ID(oid)作为第二个参数
第三个参数是必须存在的，他记录了该节点所覆盖的矩形范围大小
第四个参数也是很必要的，他记录了该节点所隶属的深度大小
每当完成一个节点信息的设置，我要把他添加的树中
var tree:NodeTree = TreeManager.instance.take(tid);
tree.addNode(this._id_,this);
然后递归遍历叶子节点，知道子节点的深度为0，完成递归建树，具体代码实现如下“：
/**
*
* @param tid tree id
* @param oid 父节点id
* @param rect 节点矩形范围
* @param depth 该节点隶属深度
*
*/
public function setup(tid:String,oid:String,rect:Rectangle,depth:int):void{
this._tid = tid;
this._oid_= oid;
_depth = depth;
//子节点深度
var childDepth:int =depth -1;
//子节点起始坐标,宽高=父节点宽高/2
var cx:int = rect.x;
var cy:int = rect.y;
var cw:int = rect.width/2;
var ch:int = rect.height/2;
//创建一个唯一id
this._id_ = cx+'_'+cw+'_' +cy+'_'+ch;
var tree:NodeTree = TreeManager.instance.take(tid);
tree.addNode(this._id_,this);
//别着急 我要开始递归啦！
if(childDepth>0)
{
if(_nodeA == null){
_nodeA = new NodeRect;
var rectA:Rectangle = new Rectangle(cx,cy,cw,ch);
_nodeA.setup(tid,this._oid_,rectA,childDepth);
}
if(_nodeB==null){
_nodeB = new NodeRect;
var rectB:Rectangle = new Rectangle(cx,cy+ch,cw,ch);
_nodeB.setup(tid,this._oid_,rectB,childDepth);
}
if(_nodeC==null){
_nodeC = new NodeRect;
var rectC:Rectangle = new Rectangle(cx+cw,cy,cw,ch);
_nodeC.setup(tid,this._oid_,rectC,childDepth);
}
if(_nodeD==null){
_nodeD = new NodeRect;
var rectD:Rectangle = new Rectangle(cx+cw,cy+ch,cw,ch);
_nodeD.setup(tid,this._oid_,rectD,childDepth);
}
}
这样的实现过程就很简单明了了，好了，今天的内容就写到这里了，下回我们来讲解如何在四叉树中绑定显示对象。