Flash中的深度排序

As for Multiplayer Games and Virtual Worlds

202
排序算法

……在世界里将对象放在正确的位置不是件难事，但是长期以来让开发者们发晕的是如何在以恶搞等角视觉里适当的将那些对象排序。“排序”这个词在这篇文章里的意思是指基于对象的3D位置将它们分在不同的图层。

图例中灌木应该在树的前面显示，而树则应显示在灌木后面（基于他们的坐标）。
在google上转了一圈，我没有发现太多在如何适当地处理等角视野的排序方面有价值的信息，却在论坛上发现一堆开发者寻找答案的帖子。我自创了一个解决排序难题的解决方案，并且依照它弄了个范例。

逻辑

我们实现排序算法取决于我们能分析所有对象的位置、所在的列数和行数，并且像我们现实生活中看到的一样去适当地排序，在这里，必须做两个假定：
所有的物件都被放在一个由砖块拼凑成的长方体里。它可以是单个方块那么小(1×1)，也可以是类似餐桌的形状(比如2×4)，我们不允许有其他形状的物件，比如L型的沙发——那样的对象需要被打散成两个长方体对象。
对象不能相互重叠，就像真实世界里你不能将一个沙发和一个餐桌放到同一个物理空间，这里我们也不允许那么做。
现在介绍算法如何工作。一开始，我们需要一个包括所有对象的原始列表。再创建一个空的列表用来存放排序之后的对象。我们将循环整个原始对象列表，并将其中的对象与已排列表中的对象比较，当比较结果显示当前的对象（来自原始列表中的）应该被排到某个已排对象的下面（也可说后面），那么在已排列表中它就会被插入到那个已排对象前面。这会持续到原始列表中的所有对象都被放到了已排列表中。如果一个物件没有被排到任何东西的后面，那么它会被放在已排列表的末端。最终，我们得到的结果就是一个已经将所有东西都排序妥当的列表。
问题的重点在这里：决定两个对象谁先谁后的比较是怎么做的？这才是使整个流程运转起来的关键。请观察下面几幅图并思考。



当我们在做比较，并假设如果Object B应该在Object A后面时，我们会问两个问题：
Object B的起始列是否小于等于Object A延伸到的最大列？
Object B的起始行是否小于等于Object A延伸到的最大行？
如果上述两者的答案均是YES，那么Object B应该排在Object A之后。你最好花些时间看着上面的图，并且尝试问自己这两个问题，以核实这个逻辑思路。

排序示例

此例中，我们会在屏幕上放满东西，并且将它们合理排序。下图就是我们这个例子没排序时的样子：
这是排序后的：

这个例子是利用以前章节中提到的网格示例建立起来的，而我们只需把注意力放在与今天主题有关的代码上。所有放在屏幕上的物件都会被放到一个叫做_itemHolder的影片剪辑里。在网格创建之后，这个影片剪辑会被intialize方法添加到舞台上：


_itemHolder = new MovieClip();
addChild(_itemHolder);

在intialize的底部加入以下代码：

for( var i:int = 0; i < 50; ++ i) {
var col:int = Math.floor(_cols * Math.random());
var row:int = Math.floor(_rows * Math.random());

var item:Item = new Item();
item.type = Math.floor(3 * Math.random());

if(testItemPlacement(item, col, row)) {
addItem(item, col, row);
}
}

SortAllItems();

这段代码用了50次迭代把物件放在任意位置。物件的行和列是随机的，同时物件的样式也是随机的。物件有三种样式，0，1或2。Item类根据type值来决定这个东西显示什么图片，并且占用多少行和列。接着是一个条件语句来检测预期的摆放位置，在摆放位置超出地图边界或者覆盖其他物件的情况下，都将是无效的。如果位置有效，那么我们用addItem方法将它加到屏幕上。随后调用SortAllItems方法。

这是addItem方法的具体代码：

private function addItem(itm:Item, col:int, row:int):void {
for(var i:int = col; i< col + itm.cols; ++i) {
for(var j:int = row; j < row + itm.rows; ++j) {
var tile:Tile = getTile(i,j);
if(tile != null) {
tile.addItem(itm);
}
}
}


var tx:Number = _tileWidth * col + _tileWidth/2;
var tz:Number = - (_tileHeight * row + _tileHeight/2);

var coord:Coordinate = iso.mapToScreen(tx, 0, tz);
itm.x = coord.x;
itm.y = coord.y;

itm.col = col;
itm.row = row;

_itemHolder.addChild(itm);

_sortedItems.push(itm);

}
这个方法做的第一件事是遍历所有物件将会放诸其上的砖块并将物件放置上去。因为之前提到的检测放置可行性的方法testItemPlacement是检测砖块是否包含物件，所以这里我们要把物件加到砖块里。之后，我们指定物件的3D坐标位置，这和指定砖块位置用的是相类似的技术，唯一的区别是，在放物件的情况下，在坐标的x和z方向上都会给一个增量，以便于物件能放在砖块中间。之后用mapToScreen方法确定屏幕上的投影位置。一个物件在确定了摆放的行列位置，并放入了_itemHolder之后，在它身上将要发生的最后一件事就是被放进_sortedItems数组中（虽然它仍没被排序）。

在继续下去之前，你要知道所有的Item实例都实现了ISortableItem接口。这很重要，因为你很可能会添加一些非物件的东西到屏幕上，但是它们需要遵循同样的排序逻辑，比如Avatar。一个avatar也可以实现这个接口，只要你希望它像其他东西一样的排序。ISortableItem接口的最小化子类需要实现以下方法：
function get col():int;
function get row():int;
function get cols():int;
function get rows():int;

现在来看SortAllItems方法：
private function sortAllItems():void {
var list:Array = _sortedItems.slice(0);

_sortedItems = [];

for(var i:int = 0; i < list.length; ++i) {
var nsi:IsortableItem = list[i];

var added:Boolean = false;
for(var j:int = 0; j < _sortedItems.length; ++j) {
var si:IsortableItem = _sortedItems[j];

if(nsi.col <= si.col + si.cols - 1 && nsi.row <= si.row + si.rows - 1) {
_sortedItems.splice(j, 0, nsi);
added = true;
break;
}
}
if(!added) {
_sortedItems.push(nsi);
}
}

for(i = 0; i< _sortedItems.length; ++i) {
var disp:DisplayObject = _sortedItems[i] as DisplayObject;
_itemHolder.addChildAt(disp, i);
}

}

此方法中，我们依照早先给出的算法。首先创建一个称之为list的数组用来复制_sortedItems。之后，置空_sortedItems数组。然后遍历list里的每一项，命名为nsi，让它和_sortedItems里的每一项si比。每个nsi都有个added属性，如果排序后它不在任何东西后面，则为flase。随后的条件语句包含了两个比较nsi和si先后位置的条件，如果都满足，那么把nsi插到_sortedItems数组中si的前面，added属性置为true，并跳出内部循环。
最后的事就是将_sortedItems中刚排序完成的物件加到屏幕上相应的深度。你的排序事业就大功告成！