超品相师 有声小说:AS3与数据结构

AS3与数据结构

时至今日国内外都还没有一本讲AS3与数据结构的书，对于我这种非科班毕业的社会闲杂人等来说，欲入门数据结构只能从其他语言的古书下手学习，因为有些数据结构随着编程语言的进化已经隐藏在高级语言的API里了，还有些随着计算机硬件的发展对现在的Flash程序开发也已经不再适用了。其实对于现阶段的Flash开发，基本上数组和Object可以搞定一切了，在Flash中的Array和Object可以组成千变万化的结构，这可能是老一辈革命战士最不能理解的，所以他们面试时总出些冷门数据结构的题来难为你，话说我又不是刚毕业，从来都用不到的东西，就算以前学过也早已忘光了，至少我没反编译哪个游戏时候惊喜的看到里边有二叉查找树。但反过来说数据结构确实是一门非常重要的课程。今天的HTML5好像在做着昨天Flash的事情，难保明天的Flash会做今天C++在做的事情。开发巨型游戏不了解数据结构是肯定不行的，所以一段时间的恶补后，我整理了一下Flash开发中有可能遇得到的数据结构。完整代码在文章结尾有下载，如有错漏请直接指出谢谢。

数组

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

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

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

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

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

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

堆栈

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

队列

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

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多毫秒。

为什么不直接用as3ds ？我个人觉得as3ds基本上是直接照搬c++的数据结构，问题就是太重量级了。实现各种接口太正规化，很多结构基本用不到，有些实现又过于复杂，有些我又看不懂。
我下边的那些数据结构，基本上针对Flasher使用，算是轻量级的实现，入门容易点，如果你是传统开发人员转型，应该用as3ds是不错的选择。
另外，我的版本很多方法都是直接抄自as3ds，有些方法却改成比较容易理解的方式，也许效率不及as3ds，提供的方法也少很多，仅供学习参考，下边不再注明了

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是一种设计模式，不懂可以搜索一下。
下边是对链表所有操作的演示。

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

哈希表

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

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

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

树

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

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

上边的代码输出如下：

[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属性，就会是这个样子。

树的遍历分为前序遍历和后序遍历，演示：

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

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

/*** 前序遍历*/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*寻路也用这个二叉堆来优化效率。具体算法见代码

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())  //8trace(priorityQueue.dequeue())  //7trace(priorityQueue.dequeue())  //6trace(priorityQueue.dequeue())  //5trace(priorityQueue.dequeue())  //4trace(priorityQueue.dequeue())  //3trace(priorityQueue.dequeue())  //2trace(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()) //1trace(p.dequeue()) //2trace(p.dequeue()) //3trace(p.dequeue()) //4trace(p.dequeue()) //5trace(p.dequeue()) //6trace(p.dequeue()) //7trace(p.dequeue()) //8trace(p.dequeue()) //9

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

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

比如原树状结构为：

      4/ \3   0/\1  2

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

2 如何永远保持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虽然已经将压线的矩形作为有可能碰撞的对象返回，但百密一疏，由于他是按照点来分配的，始终会有漏检

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

图

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

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

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

因为我用了Adobe kuler配了一下色，所以漂亮了许多 ：）

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

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

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

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

与教程不同的地方就是：

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

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

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 = 0n.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 =0open.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 =curtest.g = cur.getArc(test).weighttest.h = Astar.distance(test,graph.getNode(endIndex))// 这里使用距离启发值，原教程使用的曼哈顿启发函数//可以替换成这句  Astar.manhattan(test,graph.getNode(endIndex))test.f = test.g + test.hopen.enqueue(test);}else{//如果它已经在开启列表中，用G值为参考检查新的路径是否更好。//更低的G值意味着更好的路径。//如果是这样，就把这一格的父节点改成当前格，并且重新计算这一格的G和F值。//如果你保持你的开启列表按F值排序,改变之后你可能需要重新对开启列表排序。if( cur.g+ cur.getArc(test).weight < test.g){test.parent = curtest.g = cur.g+ cur.getArc(test).weighttest.f = test.h+test.gopen.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开发还比较实用的数据结构了，欢迎补充，以供我继续学习。

所有完整代码在此下载