搬家了，公司的新环境不错
00:21 , Qizhi
新的位置，面朝大街，春暖花开。
每个人的位置都十分有个性：这是MM的座位
我们是专注于Social Game这一新兴领域的公司。非常幸运，我们在国内尤其是国外取得了不错的成绩，将中国人的创意与游戏成功输出到了港澳台地区、俄罗斯、北美、法国、意大利和西班牙，Twofishes Interactive目前在Facebook排名全球第16名。我们也是十分有理想有抱负，立志成为国际一流的Social Game开发、运营平台。
Social Game是一个新兴的行业。我们有幸早走了一步，积累了很多宝贵的经验。接下来我们会迎来一个高速发展的时期，此时我们需要有更多优秀的人才加盟。我们目前提供行业内极有诱惑力的高额工资与一定比例的项目分红，这里将会是一个建功立业的起点机遇。目前开放的职位有：
Flash平台开发工程师 (2个)
职位要求:
1.有过多人合作项目的开发,负责过模块的编写,有较强系统分析能力；
2.精通ActionScript3，能用ActionScript3自主开发Flash组件或游戏，熟悉java开发环境更佳；
3.必须拥有良好的编码风格和面向对象的编程思想；
4.熟悉ActionScript3、0和后台Server之间的通讯与交互；
Java web开发工程师 (2个)
职位要求:
1.熟悉Java，有web应用开发经验
2.掌握sql语言,熟悉mysql数据库操作，熟悉linux开发环境
3.熟悉http协议，熟悉相关web server软件
4.有拼搏精神，沟通好，有责任心
5.会python更佳。
以上职位均接受实习生。要求计算机相关专业大三、大四或研究生。
简历投递：ezhung ( at ) gmail.com
Oct
21
2009
AVM2中的堆栈与性能优化
14:09 , Qizhi
《编译原理》讲程序运行时的内存分配策略有静态、栈式和堆式三种。 静态存储分配是指在编译时就能确定每个数据目标在运行时刻的存储空间需求，要求程序代码中不允许有可变数据结构的存在；栈式存储分配也可称为动态存储分配，程序对数据区的需求在编译时是完全未知的,只有到运行的时候才能够知道，按照先进后出的原则进行分配；而堆式存储分配则专门负责在编译时或运行时模块入口处都无法确定存储要求的数据结构的内存分配，比如可变长度串和对象实例，堆由大片的可利用块或空闲块组成，堆中的内存可以按照任意顺序分配和释放。
在编程中，例如C/C++中，所有的方法调用都是通过栈来进行的,所有的局部变量，形式参数都是从栈中分配内存空间的。堆是应用程序在运行的时候请求操作系统分配给自己内存，由于从操作系统管理的内存分配,所以在分配和销毁时都要占用时间，因此用堆的效率非常低。但是堆的 优点在于,编译器不必知道要从堆里分配多少存储空间，也不必知道存储的数据要在堆里停留多长的时间,因此,用堆保存数据时会得到更大的灵活性。事实上,面 向对象的多态性,堆内存分配是必不可少的,因为多态变量所需的存储空间只有在运行时创建了对象之后才能确定。
AVM2是一种基于堆栈的用于解释ABC字节码的虚拟机，使用JIT编译器技术以提高性能。注意Java作为另一种解释型语言，也使用了JIT编译技术。在AVM2中，写在构造函数里的语句是不会被JIT编译，所以高性能的程序应当将初始化程序写进另外一个单独的初始化函数里。
AVM2执行的对象（输入，Input）就是我们创建的一个一个编译后的Actionscript Class文件。AVM2为运行一个程序定义了几种数据区，包括：堆、函数信息( method information)、本地数据域(local data area, 由堆栈和pc寄存器组成),常量池(constant Pool)以及运行时环境(run-time environment)。操作栈( operand stack)、域栈( scope stack)、pc寄存器(local registers)组成了本地数据域。AVM2操作栈堆栈和C这样的传统编程语言中的堆栈是类似的，它保存局部变量和部分结果，并且在方法调用和返回中也担任一些职责。域栈会影响变量的作用域。使用Try、with或者创建闭包时候会影响该栈。
AVM2中堆用于所有的类实例创建。堆所存储的对象被一个自动存储管理系统回收(也就是我们所熟知的垃圾收集器(gc))。对象不能被显式的释放，AVM2假设没有特定类型的自动存储管理系统，存储管理技术可以根据实现者的系统需求进行选择。
Common Subexpression Elimination (CSE)通用子表达式消除是一种优化技术，它可以识别重复的表达式并重用它的值，而不是再次执行相应的计算。有了它，在编写代码的时候就可以不必太多考虑表达式的问题，而将优化工作交给编译器。AVM2、JVM、.NET都采用了这种技术，但是在AVM2中，这种技术并不是很完善。所以类似这样的语句“for (var i:int=0; i < arr.length; i++)”性能就不是很好。
Java中，StringBuffer类可以优化字符串操作。http://www.onflex.org/ACDS/AS3TuningInsideAVM2JIT.pdf解释说Flash曾经也考虑过写一个类似StringBuffer的类，但是最终Flash重载了"+"操作符，所以不必担心字符串的"+"带来的性能损耗。Textfield的appendText方法性能更好一些。
有关类的实现细节可以参考：http://www.onflex.org/ACDS/AS3TuningInsideAVM2JIT.pdf与http://www.adobe.com/devnet/actionscript/articles/avm2overview.pdf。
在编程中，例如C/C++中，所有的方法调用都是通过栈来进行的,所有的局部变量，形式参数都是从栈中分配内存空间的。堆是应用程序在运行的时候请求操作系统分配给自己内存，由于从操作系统管理的内存分配,所以在分配和销毁时都要占用时间，因此用堆的效率非常低。但是堆的 优点在于,编译器不必知道要从堆里分配多少存储空间，也不必知道存储的数据要在堆里停留多长的时间,因此,用堆保存数据时会得到更大的灵活性。事实上,面 向对象的多态性,堆内存分配是必不可少的,因为多态变量所需的存储空间只有在运行时创建了对象之后才能确定。
AVM2是一种基于堆栈的用于解释ABC字节码的虚拟机，使用JIT编译器技术以提高性能。注意Java作为另一种解释型语言，也使用了JIT编译技术。在AVM2中，写在构造函数里的语句是不会被JIT编译，所以高性能的程序应当将初始化程序写进另外一个单独的初始化函数里。
AVM2执行的对象（输入，Input）就是我们创建的一个一个编译后的Actionscript Class文件。AVM2为运行一个程序定义了几种数据区，包括：堆、函数信息( method information)、本地数据域(local data area, 由堆栈和pc寄存器组成),常量池(constant Pool)以及运行时环境(run-time environment)。操作栈( operand stack)、域栈( scope stack)、pc寄存器(local registers)组成了本地数据域。AVM2操作栈堆栈和C这样的传统编程语言中的堆栈是类似的，它保存局部变量和部分结果，并且在方法调用和返回中也担任一些职责。域栈会影响变量的作用域。使用Try、with或者创建闭包时候会影响该栈。
AVM2中堆用于所有的类实例创建。堆所存储的对象被一个自动存储管理系统回收(也就是我们所熟知的垃圾收集器(gc))。对象不能被显式的释放，AVM2假设没有特定类型的自动存储管理系统，存储管理技术可以根据实现者的系统需求进行选择。
Common Subexpression Elimination (CSE)通用子表达式消除是一种优化技术，它可以识别重复的表达式并重用它的值，而不是再次执行相应的计算。有了它，在编写代码的时候就可以不必太多考虑表达式的问题，而将优化工作交给编译器。AVM2、JVM、.NET都采用了这种技术，但是在AVM2中，这种技术并不是很完善。所以类似这样的语句“for (var i:int=0; i < arr.length; i++)”性能就不是很好。
Java中，StringBuffer类可以优化字符串操作。http://www.onflex.org/ACDS/AS3TuningInsideAVM2JIT.pdf解释说Flash曾经也考虑过写一个类似StringBuffer的类，但是最终Flash重载了"+"操作符，所以不必担心字符串的"+"带来的性能损耗。Textfield的appendText方法性能更好一些。
有关类的实现细节可以参考：http://www.onflex.org/ACDS/AS3TuningInsideAVM2JIT.pdf与http://www.adobe.com/devnet/actionscript/articles/avm2overview.pdf。
Sep
29
2009
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);
}
最常见的渲染优化手段是关闭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);
}
Sep
7
2009
等角(斜45度)游戏与数学
21:03 , Qizhi
1984年欧洲的玩家被一款当时发布的游 Knight Lore 震惊了。这款2d游戏居然相当真实的模拟了3d环境，而当时游戏的发布平台是 ZX Spectrum， 48K的内存。这个技术就是isometric perspective（等角投影） 。后来大菠萝、最终幻想等游戏均采用了这种投影技术。
等角投影是指在一定范围内，投影面上任何点上两个微分线段组成的角度投影前后保持不变的一类投影。任何点上二微分线段组成的角度投影前后保持不变的一类投影。是角度和形状保持正确的投影，也称正形投影。这种投影类型不同于真3D常见的透视投影，并不以物体对摄像头的远近关系而对其缩放，x，y和z轴的投影角度均为120度。但是出于计算机渲染像素图像图形的特性，和开发方便，很多游戏实际上使用的是二等角投影。
由等角坐标变换到屏幕坐标可以参考这个公式：
由屏幕坐标变换到等角坐标：
以下文章摘自http://www.compuphase.com/axometr.htm:
The figure below shows a cube in the isometric projection as defined by ISO 5456-3.The first object from the left in the figure is the cube unadorned; the second object is the same cube with angles and measures annotated around it. The third and fourth graphics are the top and side views of the perspective scene and they give the camera position that fits the perspective view. The camera position is what you would feed into a 3D renderer (or ray tracer) to create the sprites or tiles for the isometric projection.
Computer games with isometric maps are often tile-based. To make tiles match, the game designer must take into account how diagonal lines are plotted in discrete steps (Bresenham and all that). As it turns out, a line at 30 degrees (sine is 0.5) produces steps that are too irregular. A line at an angle where the tangent is 0.5 does have a nice regular pattern: two steps to the right, one step up. Thus, the isometric projection used by most games tilt the x- and z-axes with approximately 27 degrees (the exact angle is "arctangent(0.5)"). By the way, because the tangent of the angle of the rhombus is 0.5, the rhombus is twice as wide as it is high. This is why many sources mention a 1:2 scale for isometric perspectives. (To make the edges of the rhombuses match, the width of the rhombus should be a multiple of four pixels and the height should be one pixel less than ½ width. In other words, the height:width ratio of a rhombus is usually not exactly 1:2, but rather near 1:2.1. This makes no difference for the principles of the isometric perspective.)
Again, the figure below shows what this isometric projection looks like.
等角投影的限制
As with all types of parallel projection, objects drawn with axonometric projection do not appear larger or smaller as they extend closer to or away from the viewer. While advantageous for architectural drawings, this results in a perceived distortion, as unlike perspective projection, it is not how our eyes or photography normally work. It also can easily result in situations where depth and altitude are difficult to gauge, as is shown in the illustration to the right.
Once popular in sprite-based video games, most contemporary video games have avoided these sorts of situations by switching over to perspective 3D instead.
Such illusions were also popular in Op art such as M. C. Escher's "impossible architecture" drawings. Waterfall (1961), in which the drawing of the building makes use of axonometric projection, but the faded background uses perspective projection, is a well-known example. Another advantage is that, in engineering drawings, 60° angles are easier for novices to construct using only a compass and straightedge.
In this isometric drawing for example, the blue sphere is two levels higher than the red one. However, this difference in elevation is not apparent if one covers the right half of the picture, as the boxes (which serve as clues suggesting height) are then obscured.
Flash游戏采用等角投影的有PlayFish的餐厅（需要翻墙）：
等角投影是指在一定范围内，投影面上任何点上两个微分线段组成的角度投影前后保持不变的一类投影。任何点上二微分线段组成的角度投影前后保持不变的一类投影。是角度和形状保持正确的投影，也称正形投影。这种投影类型不同于真3D常见的透视投影，并不以物体对摄像头的远近关系而对其缩放，x，y和z轴的投影角度均为120度。但是出于计算机渲染像素图像图形的特性，和开发方便，很多游戏实际上使用的是二等角投影。
由等角坐标变换到屏幕坐标可以参考这个公式：
由屏幕坐标变换到等角坐标：
以下文章摘自http://www.compuphase.com/axometr.htm:
The figure below shows a cube in the isometric projection as defined by ISO 5456-3.The first object from the left in the figure is the cube unadorned; the second object is the same cube with angles and measures annotated around it. The third and fourth graphics are the top and side views of the perspective scene and they give the camera position that fits the perspective view. The camera position is what you would feed into a 3D renderer (or ray tracer) to create the sprites or tiles for the isometric projection.
Computer games with isometric maps are often tile-based. To make tiles match, the game designer must take into account how diagonal lines are plotted in discrete steps (Bresenham and all that). As it turns out, a line at 30 degrees (sine is 0.5) produces steps that are too irregular. A line at an angle where the tangent is 0.5 does have a nice regular pattern: two steps to the right, one step up. Thus, the isometric projection used by most games tilt the x- and z-axes with approximately 27 degrees (the exact angle is "arctangent(0.5)"). By the way, because the tangent of the angle of the rhombus is 0.5, the rhombus is twice as wide as it is high. This is why many sources mention a 1:2 scale for isometric perspectives. (To make the edges of the rhombuses match, the width of the rhombus should be a multiple of four pixels and the height should be one pixel less than ½ width. In other words, the height:width ratio of a rhombus is usually not exactly 1:2, but rather near 1:2.1. This makes no difference for the principles of the isometric perspective.)
Again, the figure below shows what this isometric projection looks like.
等角投影的限制
As with all types of parallel projection, objects drawn with axonometric projection do not appear larger or smaller as they extend closer to or away from the viewer. While advantageous for architectural drawings, this results in a perceived distortion, as unlike perspective projection, it is not how our eyes or photography normally work. It also can easily result in situations where depth and altitude are difficult to gauge, as is shown in the illustration to the right.
Once popular in sprite-based video games, most contemporary video games have avoided these sorts of situations by switching over to perspective 3D instead.
Such illusions were also popular in Op art such as M. C. Escher's "impossible architecture" drawings. Waterfall (1961), in which the drawing of the building makes use of axonometric projection, but the faded background uses perspective projection, is a well-known example. Another advantage is that, in engineering drawings, 60° angles are easier for novices to construct using only a compass and straightedge.
In this isometric drawing for example, the blue sphere is two levels higher than the red one. However, this difference in elevation is not apparent if one covers the right half of the picture, as the boxes (which serve as clues suggesting height) are then obscured.
Flash游戏采用等角投影的有PlayFish的餐厅（需要翻墙）：
Sep
2
2009
说说flash游戏，引擎（二）数据结构
15:56 , Qizhi
写游戏说白了就是和数据打交道，而数据结构和算法在不同语言，不同平台上原理是想通的。这篇文章只是简单回顾一下。
在Flash平台最常用的莫过于数组(Array)类型了。数组结构在实现上是一段连续的内存，所以按索引访问速度飞快。由于Flash内置的线性结构唯有Array一种，所以很多人就只用数组处理所有问题了。问题在于，虽然数组的随机访问速度快，但是其插入、移动的成本很高。但是这也不一定说传统的C/C++数据结构就可以直接照搬到Actionscript上来，因为Actionscript是一种脚本语言，其解释和执行均由AVM执行。由Actionscript定义的结构再经过AVM解释，效率往往反而不如使用Array（Flash内置并经过优化）。
使用非Array结构的一种场合可以是大量数据时。比如等角游戏，100×100格，4层地图共有100×100×4=40 000个数据，对这4万个数据如果采用Array存储并经常需要增删，那么Array的效率就不如自定义数据结构，比如链表。链表虽然是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比数组快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间。使用链表结构可以充分利用内存空间，实现灵活的内存动态管理。链表的实现和与Array的对比可以参考http://lab.polygonal.de/
幸运的是，Haxe和Alchemy的出现弥补了这一不足。Alchemy可以编译C/C++程序为Flash字节码，而Haxe编译器可以很好的编译时优化代码，并且内置了List，FastList等结构。他们也各有缺点，比如缺乏调试环境，没有好的IDE支持，Alchemy编译出的文件过大等。
面试Flash程序员时我经常会问一些基础的数据结构的知识，比如什么是哈希结构。作为一种抽象数据结构，Hash表的实现思路如下：通过某种算法，在 键--值对的存储地址和 键--值对中的key之间，建立一种映射，使得每一个key，都有一个确定的存储地址于之对应。这种算法被封装在Hash函数中。在查找时，通过Hash函数，算出和key对应的存储地址，从而找到相应的键-值对。相对于通过遍历整个键-值对列表来进行查找，Hash表的查找效率要高得多，理想的情况下算法复杂度仅为o(1)(遍历查找的复杂度为o(n))。Flash内置的哈希结构有Object和Dictionary两种。访问速度上Dictionary要快于Object（参考 Dictionary VS Object VS Array ），并且支持弱引用。Haxe的选择面则更广一些。Dictionary提供了一种泛型结构，并针对key为int型的哈希结构做了特殊优化——IntHash。
数组、链表、哈希即最常用的数据结构，实际项目需要根据需要合理运用他们，并优先选择比较简单的数据结构。其他一些数据结构则在特定环境下能发挥更大的效用，比如二叉堆在寻路中的优化、四叉树在大地图管理中的使用等。
说了这些都是针对特定问题提出解决方案。那么有没有一种通用的方案呢？
答案是没有。即使有（比如，写一个小型数据库？），也不适合在游戏中使用。最近有人问我为什么不写一个数据库给引擎用呢？这样不用写各种类型的数据结构了，直接建表即可?......我很疑惑竟还真有某Flash游戏这么做了。数据库是“按照数据结构来组织、存储和管理数据的仓库”，一般是持久化存储。其定义已经明确了其功能，所以玩家的基本数据会被存储到数据库（Server），而游戏引擎中的数据则主要是为了更快的游戏速度和更小的空间占用，针对性的完成特定任务——爱偷懒的例外。
在Flash平台最常用的莫过于数组(Array)类型了。数组结构在实现上是一段连续的内存，所以按索引访问速度飞快。由于Flash内置的线性结构唯有Array一种，所以很多人就只用数组处理所有问题了。问题在于，虽然数组的随机访问速度快，但是其插入、移动的成本很高。但是这也不一定说传统的C/C++数据结构就可以直接照搬到Actionscript上来，因为Actionscript是一种脚本语言，其解释和执行均由AVM执行。由Actionscript定义的结构再经过AVM解释，效率往往反而不如使用Array（Flash内置并经过优化）。
使用非Array结构的一种场合可以是大量数据时。比如等角游戏，100×100格，4层地图共有100×100×4=40 000个数据，对这4万个数据如果采用Array存储并经常需要增删，那么Array的效率就不如自定义数据结构，比如链表。链表虽然是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比数组快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间。使用链表结构可以充分利用内存空间，实现灵活的内存动态管理。链表的实现和与Array的对比可以参考http://lab.polygonal.de/
幸运的是，Haxe和Alchemy的出现弥补了这一不足。Alchemy可以编译C/C++程序为Flash字节码，而Haxe编译器可以很好的编译时优化代码，并且内置了List，FastList等结构。他们也各有缺点，比如缺乏调试环境，没有好的IDE支持，Alchemy编译出的文件过大等。
面试Flash程序员时我经常会问一些基础的数据结构的知识，比如什么是哈希结构。作为一种抽象数据结构，Hash表的实现思路如下：通过某种算法，在 键--值对的存储地址和 键--值对中的key之间，建立一种映射，使得每一个key，都有一个确定的存储地址于之对应。这种算法被封装在Hash函数中。在查找时，通过Hash函数，算出和key对应的存储地址，从而找到相应的键-值对。相对于通过遍历整个键-值对列表来进行查找，Hash表的查找效率要高得多，理想的情况下算法复杂度仅为o(1)(遍历查找的复杂度为o(n))。Flash内置的哈希结构有Object和Dictionary两种。访问速度上Dictionary要快于Object（参考 Dictionary VS Object VS Array ），并且支持弱引用。Haxe的选择面则更广一些。Dictionary
数组、链表、哈希即最常用的数据结构，实际项目需要根据需要合理运用他们，并优先选择比较简单的数据结构。其他一些数据结构则在特定环境下能发挥更大的效用，比如二叉堆在寻路中的优化、四叉树在大地图管理中的使用等。
说了这些都是针对特定问题提出解决方案。那么有没有一种通用的方案呢？
答案是没有。即使有（比如，写一个小型数据库？），也不适合在游戏中使用。最近有人问我为什么不写一个数据库给引擎用呢？这样不用写各种类型的数据结构了，直接建表即可?......我很疑惑竟还真有某Flash游戏这么做了。数据库是“按照数据结构来组织、存储和管理数据的仓库”，一般是持久化存储。其定义已经明确了其功能，所以玩家的基本数据会被存储到数据库（Server），而游戏引擎中的数据则主要是为了更快的游戏速度和更小的空间占用，针对性的完成特定任务——爱偷懒的例外。
Aug
12
2009
