Flash游戏大场景管理与四叉树

21:26 , Qizhi

Flash游戏开发不得不面对的问题是Flash Player渲染性能较低（与传统桌面游戏相比较），这个问题在场景较大时显得尤为突出。Facebook上最近新出了一款Zynga开发的游戏Roller Coaster Kingdom ，场景较大，人物较多，在我的机器上就跑的惨不忍睹。
最常见的渲染优化手段是关闭DisplayObject的一些属性如mouseEnabled = false，使用cacheAsBitmap，scrollRect等等。但是性能提升并不明显。第二种手段是使用Bitmap来渲染游戏。这是最传统的做法，利用双缓冲画布、脏矩形等技术可以做到十分平滑高效的渲染，通常能获得2-3倍的性能提升。缺点是可扩展性和维护成本较大，一些鼠标事件也会丢失。
这些渲染都是针对最终输出到屏幕上的大量可视元素所做的。对于一张3000×3000px，放满了建筑跑满了人的地图而言，我们只能采取更高级的手段去优化它——想想3D引擎是怎么做的？视锥剪裁。其基本原理是将不需要渲染的点从屏幕上去掉。

设想你的地形是一个非常大的方格，在一个X和Z的面上扩展。我们有一个摄象机在地形的右下角，它的可视截面（蓝三角）扩展为在相同方向上的小单元，这样在优化前，绘制地形的程序代码看起来象这样:

for(var i:int=0; i<size;i++) { drawCell();//... }

采用剪裁手段后，我们就只需要绘制剪裁后的部分，代码变为：

var result:Array = cullMap();
var len:uint = result.length;
for(var i:int=0; i<len;i++) { drawCell();//... }

剪裁的手段有很多种，在不同的场景下有各种实现手段，如BSP树、四叉树/八叉树等。四叉树对于特大场景是一个不错的选择。其基本思想是将一幅地形数据等分为4部分，逐块检查其网格属性值；如果某个子区的所有格网值都具有相同的值，则这个子区就不再继续分割，否则还要把这个子区分割为四个子区；这样依次分割，直到每个子块都只含有相同的属性值为止。详细介绍请猛击此处。

我的例子中，单机鼠标左键会渲染以鼠标为原点，150×150矩形范围内的随机矩形。而整个场景有10 000个矩形分布在5000*3000的屏幕中。

Flash Player文件

点击打开/折叠播放器

Actionscript3版四叉树的插入与查询：

public function query(queryArea:Rectangle):Array
{
  var result:Array = [];

  for each(var item:IQuadNodeItem in contents)
  {
    if(queryArea.intersects(item.getRectangle()))
      result.push(item);
  }
  for each(var node:QuadNode in nodes)
  {
    if(node.isEmpty)continue;
    if(node.bounds.containsRect(queryArea))
    {
      result = result.concat(node.query(queryArea));
      break;
    }
    if(queryArea.containsRect(node.bounds))
    {
      result = result.concat(node.subTreeContents);
      continue;
    }
    if(node.bounds.intersects(queryArea))
      result = result.concat(node.query(queryArea));
  }
  return result;
}

public function insert(item:IQuadNodeItem):void
{
  if(!bounds.containsRect(item.getRectangle()))return;
  if(nodes.length == 0)
    createSubNodes();
  for each(var node:QuadNode in nodes)
  {
    if(node.bounds.containsRect(item.getRectangle()))
    {
      node.insert(item);
      return;
    }
  }
  this.contents.push(item);
}