AS3与数据结构

时至今日国内外都还没有一本专讲 AS3 与数据结构的书,对于我这种非科班毕业的社会闲杂人等来说,入门数据结构太难了,我参考了各方代码,经过一段时间的恶补,整理了一下目前 Flash 开发中有可能遇得到的数据结构。完整代码在文章结尾有下载,如有错漏请直接指出谢谢。

数组

Array 类应该是 Flash 里最常用的数据结构了。比其他语言的数组高级和灵活许多,随意装入任何数据类型,不用固定长度。 访问速度快,从后方添加(push)和删除(pop)快,但从中间或开头删除会很慢。

从 100 万长度的数组开头删除 500 个元素在我的机器上差不多要 1 秒钟。

actionscript-3

var arr:Array = []
for(var i:uint= 0 ;i<1000000;i++)arr[i]=i ;
var startT:Number = getTimer()
var num:uint = 500
while(num>0)
{
	arr.splice(0,1)
	num--
}
trace("time:",getTimer() - startT)

但如果数组没有顺序的话,快速删除法 1000 个在我机器上才需要 1 毫秒。

actionscript-3

var arr:Array = []
for(var i:uint= 0 ;i<1000000;i++)arr[i]=i ;
 
var startT:Number = getTimer()
var num:uint = 1000
while(num>0)
{
	arr[0] =arr[arr.length-1]
	arr.length -=1
	num--
}
trace(getTimer() - startT)

Vector:Vector 是 Array 的升级版。如果想追求效率,恰巧数组中的元素类型是固定的,或者长度是固定的,就可以将 Array 换成 Vector 类提升效率。

堆栈

堆栈是先进后出的结构,像子弹梭子一样,由于数组的 push() pop()非常快,所以数组本身就是最好的堆栈。

队列

队列是先进先出,数组也可以做队列,但是从数组前端删除数据比较慢,下边 10 万条数据我的机器运行差不多需要 2 秒。

actionscript-3

var startT:Number = getTimer()
var queue:Array = []
for(var i:int = 0 ; i<100000 ;i++)
{
	queue.push(i);
}
for(var i:int = 0 ; i<100000 ;i++)
{
	queue.shift()
}
trace(getTimer() - startT)

我参考 as3ds 改写了个链表(DLinkedList) ,实现了数组一样的 push() pop() shift() unshift() 四个方法。用这个链表只需要改一行代码,同样操作在我的机器上只要 100 多毫秒。

actionscript-3

var startT:Number = getTimer()
var queue:DLinkedList = new DLinkedList()
for(var i:int = 0 ; i<100000 ;i++)
{
	queue.push(i);
}
for(var i:int = 0 ; i<100000 ;i++)
{
	queue.shift()
}
trace(getTimer() - startT)

这个链表是一个双向链表,可以当作各种队列也可以当作堆栈,效率都不错。

链表

这个链表实现的是一个双向链表,因为删除数据会快些,单链表优点就是省一点点内存,但删除会慢很多,用处不大,所以没有实现。 我觉得除了把链表当成队列使用,平时几乎用不到。如果非要使用就要使用 Iterator 了,Iterator 是一种设计模式,不懂可以搜索一下。 下边是对链表所有操作的演示。

actionscript-3

 
var l:DLinkedList = new DLinkedList()
l.push(1)
l.push(2)
l.push(3)
trace(l,l.head,l.tail) //[1,2,3] 1 3
l.pop()
trace(l,l.head,l.tail) //[1,2] 1 2
l.unshift(0)
trace(l,l.head,l.tail) //[0,1,2] 0 2
l.shift()
trace(l,l.head,l.tail) //[1,2] 1 2
l.push(3)
trace(l,l.head,l.tail) //[1,2,3] 1 3
 
//遍历,输出  1,2,3
var it:DListIterator = l.getIterator()
for(it.start() ; it.hasNext(); it.next())
{
	trace(it.node.data)
}
it.start()  // 索引归0
it.next()
l.remove(it) //remove 2
l.remove(it) //remove 3
trace(l,l.head,l.tail) //[1] 1 1
l.insert(it,2)
trace(l,l.head,l.tail) //[1,2] 1 2
l.insert(it,3)
trace(l,l.head,l.tail) //[1,3,2] 1 2

哈希表

哈希表应该就是 Object? 在 Flash 里 Object 是动态的,赋值就 obj.abc = 123 ,删除就 delete obj.abc

actionscript-3

 
var o:Object = {}
o["key"] = obj   //插入
delete o["key"]  //删除

如果追求 Object 做 key 可以用 flash.utils.Dictionary 类代替 Object。

上边数组和链表都叫线性结构,树是典型的非线性数据结构,普通的树也不常用,但作为一个基础必须掌握,这里的树使用上边提到的双向链表存储子树。操作树要用 TreeIterator,下边是演示。

actionscript-3

var tree:Tree = new Tree(0);
var itr:TreeIterator = tree.getIterator()
itr.appendChild(1)
itr.appendChild(2)
 
	  0
	 / \
	1   2
 
itr.down()
itr.appendChild(3)
 
		 0
		/ \
	   1   2
	  /
	 3
 
itr.up()
itr.appendChild(4)
 
		  0
		/ | \
	   1  2  4
	  /
	 3
 
itr.childEnd()
itr.down()
itr.prependChild(5)
itr.prependChild(6)
 
          0
        / | \
       1  2  4
      /      /\
     3      6  5
 
trace(tree.dump())

上边的代码输出如下:

markup

[TreeNode >(root) has 2 child nodes, data=room1]
+---[TreeNode > has 2 child nodes, data=room2]
|    +---[TreeNode >(leaf), data=room4]
|    +---[TreeNode >(leaf), data=room5]
+---[TreeNode >(leaf), data=room3]

我实现了一个 toXML 方法,如果把 tree.toXML(tree)赋给 Flex 的 Tree 组件的 dataProvider 属性,就会是这个样子。

/images/tree01.jpg

树的遍历分为前序遍历和后序遍历,演示:

上边是直接来自 as3ds 的演示,了解更多点击这里

代码实现看着很简单,但很需要费脑子的,是递归实现。

actionscript-3

 
/**
* 前序遍历
*/
public function preorder(Node:Tree,Process:Function):void
{
	Process(Node)
	var itr:DListIterator = Node.children.getIterator()
	while(itr.hasNext())
	{
		preorder(Tree(itr.node.data),Process)
		itr.next();
	}
}
 
/**
* 后序遍历
*/
public function postorder(Node:Tree,Process:Function):void
{
	var itr:DListIterator =  Node.children.getIterator()
	while(itr.hasNext())
	{
		postorder(Tree(itr.node.data),Process)
	}
	Process(Node)
}

二叉堆与优先队列

优先队列是一种特殊的队列,它不是先入先出,而是入队的元素会自动按你指定顺序排列,先出队的永远是你指定的顺序里排最前面的。 当然这个优先队列可以用数组实现,每次入队就 push 后排一次序,出队 pop 就可以了,但是这样效率不佳,我们的优先队列是使用二叉堆实现的。

首先了解二叉树是只有 2 个子节点的树 ,二叉堆是一种特殊的二叉树,他的每个父节点都比子节点大。 里边用了些特殊的算法,让元素入队出队时效率更好。后边的 A*寻路也用这个二叉堆来优化效率。具体算法见代码

actionscript-3

var priorityQueue:Heap =new Heap() //新建二叉堆,默认从大到小排列
priorityQueue.enqueue(2) //入队9个数字
priorityQueue.enqueue(6)
priorityQueue.enqueue(5)
priorityQueue.enqueue(8)
priorityQueue.enqueue(7)
priorityQueue.enqueue(4)
priorityQueue.enqueue(1)
priorityQueue.enqueue(3)
priorityQueue.enqueue(9)
 
trace(priorityQueue)  //输出9,8,5,7,6,4,1,2,3   ,发现并不是按顺序排列的
trace(priorityQueue.dequeue())  //9 但出队时就已经是排序好的了
trace(priorityQueue.dequeue())  //8
trace(priorityQueue.dequeue())  //7
trace(priorityQueue.dequeue())  //6
trace(priorityQueue.dequeue())  //5
trace(priorityQueue.dequeue())  //4
trace(priorityQueue.dequeue())  //3
trace(priorityQueue.dequeue())  //2
trace(priorityQueue.dequeue())  //1
 
//如果想要逆序排列,只需要提供一个compare Function,这个跟数组sort方法里的compareFunction参数一样,如下:
 
var f:Function = function(a:int,b:int):int{return b-a}
var p:Heap =new Heap(f)
p.enqueue(2)
p.enqueue(6)
p.enqueue(5)
p.enqueue(8)
p.enqueue(7)
p.enqueue(4)
p.enqueue(1)
p.enqueue(3)
p.enqueue(9)
 
trace(p.dequeue()) //1
trace(p.dequeue()) //2
trace(p.dequeue()) //3
trace(p.dequeue()) //4
trace(p.dequeue()) //5
trace(p.dequeue()) //6
trace(p.dequeue()) //7
trace(p.dequeue()) //8
trace(p.dequeue()) //9

其实 Heap 内部也是由数组存储的,它的算法有两个关键

  1. 如何用数组储存二叉树结构

比如原树状结构为:

markup

	      4
	     / \
	    3   0
	   /\
	  1  2

则存储成数组为:[4,3,0,1,2]

  1. 如何永远保持 parent 比 child 大

这点比较麻烦具体可以参考我的代码,或者找本书看看。

四叉树

四叉树通常用于 2d 游戏碰撞检测。假设屏幕上有 500 个 mc,每 2 个之间都要进行碰撞检测,那么每一个 mc 都要与其他 499 个 mc 进行一次碰撞检测,那每帧总共就接近做 500×500 = 250000 次检测。 如果是小球还好办,用半径法,如果碰上复杂的 mc 需要位图碰撞检测,那每帧检测 25 万次 flash 是吃不消的。 一个优化的办法就是只与有可能碰撞的 mc 进行碰撞检测,这时四叉树就派上用场了。

移动鼠标会发现,只有红色的方块是有可能与鼠标拖动的方块产生碰撞的,你只要将鼠标方块与红色的方块逐个进行检测就好了,大大提升了效率

四叉树首先通过一个建树的过程将屏幕上的物体分配到,左上,右上,左下,右下四个象限中,这四个象限对应树的四个节点,每个象限还可以继续分成四个象限,根据具体情况考虑分配几层达到一个查找最快效果。

对比一下速度,下边是数组遍历,250 个 Sprite,两两碰撞在我机器上就惨不忍睹了。 (放上鼠标开始)

四叉树版本,500 个 Sprite,2 倍精灵的数量两两碰撞仍然跑的流畅(放上鼠标开始)

四叉树的思想就是先屏幕分割,然后过滤出离自己很近的,有可能产生碰撞的进行碰撞检测。Flash 界使用四叉树最出名的应该就是Flixel 游戏引擎,它把四叉树隐藏在碰撞检测的 API 里,用户不需要直接操作四叉树。 调用碰撞检测的同时,引擎内部就自动建树了。大家都看到 Flixel 引擎的效率是非常高的,各种大小相差几倍的精灵放在一起检测也没有问题,这也是四叉树分区相比网格分区的一个优势。可惜 Flixel 里的四叉树 经过了各种优化,已经不是传统四叉树的样子了,很难分离出来。as3ds 包里也没有四叉树的实现,所以我又 google 了一下,在网上看到一个写的比较清晰的 JavaScript 版本JavaScript QuadTree Implementation 又无意中搜到GhostCat 里也有一个四叉树类,GhostCat 的这个版本是我看到写的最简洁的四叉树,很是佩服作者。 不过经过研究,他们有一个共同的问题就是只能把点(point)添加到树中,这对子弹或者小球的碰撞检测还好,但通常游戏中不论是 MC 还是 Bitmap 大都是有宽高的方形。如果把他们按照点来分配进树的话,就会有漏检查的情况出现。 下图是我将上边提到的,mikechambers 写的 JavaScript 版本转成 AS3 后发现的问题,mike 虽然已经将压线的矩形作为有可能碰撞的对象返回,但百密一疏,由于他是按照点来分配的,始终会有漏检

/images/tree02.jpg

所以我又回头看 Flixel 里的四叉树是怎么插入的,最后综合以上所有版本,我写了我的这个四叉树类。就是上边演示的那个,代码在文章末尾下载包里,太长就不贴了,我记得应该是写了很多注释。大家可以研究讨论一下。

图由节点 node 和指针 arc 组成,图的遍历与树差不多,分为广度优先遍历(与树的后序遍历),和深度优先遍历(与树的前序遍历)。

图在游戏中通常用作保存地图,网上流行的页游地图都是 tilemap 的,区块其实就是简化了指针之后的图,所以他们的理论是相通的。

请看基于图的 A*算法演示:

因为我用了 Adobe kuler 配了一下色,所以漂亮了许多 :)

QuadTree_collition

为什么要用 A*寻路而不是广度或深度遍历寻路呢?因为他们本身是很傻很执着的,由于不知道终点位置而盲目扫描整个图,这会浪费效能,而 A 星之所以叫做启发式寻路,是因为它事先预测了终点的大概方向而向那个方向扫描,这样增加了效率。

我是照着这篇很有名的 A Star 入门教程写的代码:A*寻路初探

因为他是基于区块的,所以要改动一下,而需要改变的只有一个地方,他的文章里是循环检查 周围相邻的 8 格 ,而我们改成 连通的所有节点 就 ok 了。

我的 Astar 类已经按照教程逐句做了注释,对照教程应该很容易理解了。

与教程不同的地方就是:

  1. 我使用了上边提到 Heap 优先队列来优化了 open 列表,使 F 值最小的始终在列表最上方,这个在教程后边也有讲。

2)改用了 距离的启发值函数 计算 H 值,而原教程使用的 曼哈顿距离启发值函数 也有提供,可以替换,只是貌似没有距离的效果好,大家可以自己试一下。

actionscript-3

 
package examples.Astar
{
	import ds.Graph;
	import ds.GraphArc;
	import ds.GraphNode;
	import ds.Heap;
	public class Astar
	{
		/**
		*   距离启发函数
		*/
		public static function distance(startNode:GraphNode,endNode:GraphNode):Number
		{
			return  Math.sqrt( (endNode.data.x - startNode.data.x)*(endNode.data.x - startNode.data.x) + (endNode.data.y - startNode.data.y)*(endNode.data.y - startNode.data.y))
		}
		/**
		*  曼哈顿启发函数
		*/
		public static function manhattan(startNode:GraphNode,endNode:GraphNode):Number
		{
			return  Math.abs(endNode.data.x - startNode.data.x)+Math.abs(endNode.data.y - endNode.data.y);
		}
 
		/**
		*  寻路
		*/
		public static function find(graph:Graph , startIndex:int,endIndex:int):Array
		{
			//还原值
			for each (var n:AstarNode in graph.nodes)
			{
				n.f = n.g = n.f = 0
				n.parent = null
			}
 
			//根据f值升序排列
			var open:Heap = new Heap(function(a:AstarNode,b:AstarNode):Number{return b.f - a.f});
 
			var close:Array = []
			//1,把起始节点添加到开启列表。
			AstarNode(graph.getNode(startIndex)).f = 0
			open.enqueue(graph.getNode(startIndex));
			//2,重复如下的工作:
			while(open.heap.length>0)
			{
				//a) 寻找开启列表中F值最低的节点。我们称它为当前节点。
				var cur:AstarNode = AstarNode(open.dequeue())
				if(cur==graph.getNode(endIndex))return  Astar.getPath(cur)
				//把目标格添加进了关闭列表,这时候路径被找到
 
				//b) 把它切换到关闭列表。
				close.push(cur)
				//c) 对相邻的格中的每一个?
				for each(var i:GraphArc in cur.arcs)
				{
					var test:AstarNode = AstarNode(i.targetNode)
					//如果它不可通过或者已经在关闭列表中,略过它。
					if(close.indexOf(test)>=0)continue
					//如果它不在开启列表中,把它添加进去。
					//把当前格作为这一格的父节点。记录这一格的F,G,和H值。
 
					if(open.heap.indexOf(test)<0)
					{
						test.parent =cur
						test.g = cur.getArc(test).weight
						test.h = Astar.distance(test,graph.getNode(endIndex))
						// 这里使用距离启发值,原教程使用的曼哈顿启发函数
										//可以替换成这句  Astar.manhattan(test,graph.getNode(endIndex))
						test.f = test.g + test.h
						open.enqueue(test);
					}else
					{
						//如果它已经在开启列表中,用G值为参考检查新的路径是否更好。
									//更低的G值意味着更好的路径。
						//如果是这样,就把这一格的父节点改成当前格,并且重新计算这一格的G和F值。
									//如果你保持你的开启列表按F值排序,改变之后你可能需要重新对开启列表排序。
						if( cur.g+ cur.getArc(test).weight < test.g)
						{
							test.parent = cur
							test.g = cur.g+ cur.getArc(test).weight
							test.f = test.h+test.g
							open.modify(test,test);
						}
					}
				}
			}
			return []
		}
 
		public static function getPath(node:AstarNode):Array
		{
			var arr:Array = [node]
			while(node.parent)
			{
				arr.push(node.parent)
				node = node.parent
			}
			return arr
		}
 
	}
}
 

以上就是我目前了解到的对于 flash 开发还比较实用的数据结构了,欢迎补充,以供我继续学习。

最初代码在此下载 后期修了一些 bug,最新的代码点此直达 github

我的版本很多方法都是直接抄自as3ds ,有些方法却改成比较容易理解的方式,提供的方法也少很多,仅供学习参考.