您所在位置：主题：突破等角贴片——再谈斜45度角游戏
小小C
[专家分：4570] 发布于 2007-09-30 12:47:00
斜45度视角游戏的思考
斜45度视角游戏,相信大家都不会佰生,经典的如《暗黑》、《星际》、《传奇》等等。这类游戏，都用2D的贴图来构造“假3D”的游戏世界。具有很强的表现力和很好的交互性。这也是这类游戏得以流行的原因。我在大学二年级时，也做过这类游戏的尝试，你可以在查看[url]http://mysticc.go1.icpcn.com/param/param_arpg_demo.html[/url]我制作的游戏演示。虽然现在3D已成王道，但是我仍忙不了wjjxjj大哥和其它曾为2D游戏有过热情的人。所以，请允许我再多说几句吧：
一谈起这类游戏，很多人都想起了“等角贴片”吧？它就是常说的Tile，也叫瓷砖。它们是一个菱形的形状，拼接起来就形成了地图。为什么要做成菱形呢？因为这更能给人一种倾斜的感觉。可是因为它们是菱形，和方形的显示区域形状不同，以及与人的思维习惯的不同，给编程时带来许多的困难，比如坐标换算的问题，以及贴图时剪裁的问题等等。这些问题增加了编程的难度。
那么，“等角贴片”是实现斜45度视角游戏的唯一方法吗？我们能不能干脆用长方形来代替菱形呢？答案是可以的。如果你和我一样，玩过《呼啸战神》并用过它的地图编辑形，就会发现《呼》的地图是用长方形的TILE拼接而成的。刚开始我也很惊牙，因为《星际》、《龙之崛起》等游戏的地图编辑器全是用菱形的TILE的。现在让我们来比较一下菱形和长方形：
1、菱形更能体现斜45度视角，而长方形则不行。
2、菱形增加编程的难度，而长方形则容易实现。
3、菱形增加了存储空间，因为菱形的TILE也是用长方形的图片做成的，图片的大小要比实际TILE大小要大。而长方形则不存在这问题。
4、菱形贴图时，要经过关健色测试，而长方形不必。所以长方形贴图速度更快。当然在今天硬件加速的情况下，这一点并不明显。
总之，我更喜欢长方形。虽然说长方形的表现能力没有菱形那么好，但可以通过美术来弥补。《呼啸战神》和其它采用菱形TILE的游戏在画面上并没有什么差别。那么，如何用长方形的TILE来组织地图呢？
你肯定立即想到了二维数组。可是它并不是一个很好的选择。如果用二维数组，我们如何在任意的显示区域中绘制地图呢？如何存储精灵呢？静态的精灵可以预先存储在数组中，但是动态的精灵怎么办？又如何实现精灵的鼠标选取呢？如何实现精灵的运动呢？
看到这些问题，你会发现，存储地图的数据结构并不仅仅是用于存储地图的，它还是其它游戏元素的平台，下面让我们来一一讨论这些问题，不过光用二维数组还不够，我们还要借助四叉树：
一、地图的绘制：
首先假定地图中最小的单位，也就是最小的格子，称为cell（叫别的也无所谓只是一个假定）。而一个长方形的TILE是比cell大许多的，比如一个cell是32 X 16，而TILE是256 X 128。下面将会解释为什么要这样
地图将用四叉树和数组来组织。一个完全四叉树，每一个分支节点存储其区域的大小，而叶子节点则存储指向数组元素的指针，而数组则存储精灵和TILE的数据。一个地图的全部区域就是四叉树的根节点，然后把地图平均的分成四块，左上，右上，左下，右下各一块。则四块区域是根节点的四个子节点。然后再分四分，一直到叶子节点。这里假定叶子节点就是一个TILE的大小，也就是说一个叶子节点有一个TILE。
这样一来，绘制地图就非常简单了。首先得到显示区域的范围大小，然后又根节点开台，判断该节点与显示区域的相交情况：如果不相交则放弃该节点，如果该节点包含显示区域或部分相交则继续判断它的四个子节点，如果该显示区域包含该节点则节点的所有叶子节点全加入渲染队列。当然也可以不用渲染队列而是直接渲染，不过这样逻辑层就不能很好的从图形层独立出来了。
二、精灵的绘制：
精灵包括建筑物、人物、NPC、怪物、魔法、特效等等元素。它们在游戏中，有不同的位置，不同的大小，不同的渲染方法。那么如何正确的渲染它们呢？
首先想一下游戏中精灵的多少，一般而言，在一个四叉树中，只有一半的叶子节点中是有精灵存在的。为什么呢？因为游戏要留出很多空的地方便于人物角色的活动，也便于渲染。如果精灵占满了地图，人物走到哪都被挡着，那么玩着肯定不爽。当然这取决于游戏的设计者了。不管如何，我都把地图的所有精灵分开存储，四叉树中的每一个节点，都有一个精灵链表，或者精灵队列。使用与绘制地图同样的方法，在得到显示区域的范围后，遍历整个树，得出和显示区域相交的叶子节点，然后，再判断叶子节点中的精灵是否在显示范围内。不过要注意的是，有些精灵只有一部分在显示区域当中的，这就要在判断时候，采用一个比显示区域更大的矩阵区域了，这个区域的大小随显示区域的大小和精灵的大小来决定。
现在已经确定了哪些精灵是要绘制的了，但是如何正确的绘制它们，而不让先后顺序弄错呢？这就要为每一个精灵设置一个渲染的优先权的变量。然后在渲染队列中，按优先权大小排序。一般的精灵，则可以按照它们的位置来确定优先权，这应该不是很难做到吧。而特殊的精灵，比如天上飞的，或者一些魔法之类的。就要分为层次考虑了。按照渲染的先后顺序，可以分为地表层，地上层，天空层等等。首先确定精灵在哪一层然后在这一层的什么位置。就可以得出优先权了。
得出优先仅后。并不是按优先权大小就一个一个的渲染了，我们可以在这里做一些优化，比如如果一个精灵完全被前面的精灵挡住了，那么后面的精灵就不必渲染了。还可以加入脏矩阵算法，至于如何优化，这里不做讨论。逻辑层决定哪些精灵要画，要画在哪里。至于怎么画，是图形层的事了。
三、精灵的选取：
如何用鼠标选取一个NPC或是一个怪物呢？在四叉树结构里面，这个也很好解决，这需要遍历树确定鼠标所指的叶子节点，再判断叶子节点的精灵是否被选取就可以了。游戏中的精灵，并非全部都可以选取的。这样可以在叶子节点里将可选取的精灵分开存储。如果节点中不存在这种精灵，就完全不并判断了。
但是这里有一个与精灵绘制同样的问题，也就是有些精灵，只有一部分是在叶子节点中的，另一部分在另一个节点中。那么，为了选取的准确性，我们不光要检测鼠标所指的那个叶子节点，它周围的几个叶子节点也要判断。为了加快速度，可以用一个二维数组把所有的叶子节点存储起来。而叶子节点则保存对数组元素的指针即可。
四、精灵的运动：
游戏中的精灵，如果从一个叶子节点走到另一个叶子节点，则需要做相应的更新和变化。精灵将从一个链表被移到另一个链表中。为了优化，我们可以将所有的精灵用同一块内存池来存储，使用内存池，可以避免频繁的内存分配和释放操作，同时也可以做到一次性释放。还有利于内存对齐。关于内存优化这里不敢多说了，以免贻笑大方。
精灵走动时，一定要首先寻路，确定走动的路线。这就用到A*算法了，为了寻路，还得用数组存储整个地图的占位情况，也就是说哪里能走，哪里不能走。可是有些情况是不可预测的，比如一个精灵寻好了路，当它走到一半时，突然杀出来另一个精灵挡在他面前，这就有可能造成“穿过”的错误。为了避免这种错误，每走一步，还得判断下一步是不是可走的，如果不可走还要重新寻路。当然还有很多其它方法解决这类问题，比如精灵排成队，一个跟着一个走等等。
这就是我的想法，希望你也像我一样，有话就说。
斜45度视角游戏,相信大家都不会佰生,经典的如《暗黑》、《星际》、《传奇》等等。这类游戏，都用2D的贴图来构造“假3D”的游戏世界。具有很强的表现力和很好的交互性。这也是这类游戏得以流行的原因。我在大学二年级时，也做过这类游戏的尝试，你可以在查看[url]http://mysticc.go1.icpcn.com/param/param_arpg_demo.html[/url]我制作的游戏演示。虽然现在3D已成王道，但是我仍忙不了wjjxjj大哥和其它曾为2D游戏有过热情的人。所以，请允许我再多说几句吧：
一谈起这类游戏，很多人都想起了“等角贴片”吧？它就是常说的Tile，也叫瓷砖。它们是一个菱形的形状，拼接起来就形成了地图。为什么要做成菱形呢？因为这更能给人一种倾斜的感觉。可是因为它们是菱形，和方形的显示区域形状不同，以及与人的思维习惯的不同，给编程时带来许多的困难，比如坐标换算的问题，以及贴图时剪裁的问题等等。这些问题增加了编程的难度。
那么，“等角贴片”是实现斜45度视角游戏的唯一方法吗？我们能不能干脆用长方形来代替菱形呢？答案是可以的。如果你和我一样，玩过《呼啸战神》并用过它的地图编辑形，就会发现《呼》的地图是用长方形的TILE拼接而成的。刚开始我也很惊牙，因为《星际》、《龙之崛起》等游戏的地图编辑器全是用菱形的TILE的。现在让我们来比较一下菱形和长方形：
1、菱形更能体现斜45度视角，而长方形则不行。
2、菱形增加编程的难度，而长方形则容易实现。
3、菱形增加了存储空间，因为菱形的TILE也是用长方形的图片做成的，图片的大小要比实际TILE大小要大。而长方形则不存在这问题。
4、菱形贴图时，要经过关健色测试，而长方形不必。所以长方形贴图速度更快。当然在今天硬件加速的情况下，这一点并不明显。
总之，我更喜欢长方形。虽然说长方形的表现能力没有菱形那么好，但可以通过美术来弥补。《呼啸战神》和其它采用菱形TILE的游戏在画面上并没有什么差别。那么，如何用长方形的TILE来组织地图呢？
你肯定立即想到了二维数组。可是它并不是一个很好的选择。如果用二维数组，我们如何在任意的显示区域中绘制地图呢？如何存储精灵呢？静态的精灵可以预先存储在数组中，但是动态的精灵怎么办？又如何实现精灵的鼠标选取呢？如何实现精灵的运动呢？
看到这些问题，你会发现，存储地图的数据结构并不仅仅是用于存储地图的，它还是其它游戏元素的平台，下面让我们来一一讨论这些问题，不过光用二维数组还不够，我们还要借助四叉树：
一、地图的绘制：
首先假定地图中最小的单位，也就是最小的格子，称为cell（叫别的也无所谓只是一个假定）。而一个长方形的TILE是比cell大许多的，比如一个cell是32 X 16，而TILE是256 X 128。下面将会解释为什么要这样
地图将用四叉树和数组来组织。一个完全四叉树，每一个分支节点存储其区域的大小，而叶子节点则存储指向数组元素的指针，而数组则存储精灵和TILE的数据。一个地图的全部区域就是四叉树的根节点，然后把地图平均的分成四块，左上，右上，左下，右下各一块。则四块区域是根节点的四个子节点。然后再分四分，一直到叶子节点。这里假定叶子节点就是一个TILE的大小，也就是说一个叶子节点有一个TILE。
这样一来，绘制地图就非常简单了。首先得到显示区域的范围大小，然后又根节点开台，判断该节点与显示区域的相交情况：如果不相交则放弃该节点，如果该节点包含显示区域或部分相交则继续判断它的四个子节点，如果该显示区域包含该节点则节点的所有叶子节点全加入渲染队列。当然也可以不用渲染队列而是直接渲染，不过这样逻辑层就不能很好的从图形层独立出来了。
二、精灵的绘制：
精灵包括建筑物、人物、NPC、怪物、魔法、特效等等元素。它们在游戏中，有不同的位置，不同的大小，不同的渲染方法。那么如何正确的渲染它们呢？
首先想一下游戏中精灵的多少，一般而言，在一个四叉树中，只有一半的叶子节点中是有精灵存在的。为什么呢？因为游戏要留出很多空的地方便于人物角色的活动，也便于渲染。如果精灵占满了地图，人物走到哪都被挡着，那么玩着肯定不爽。当然这取决于游戏的设计者了。不管如何，我都把地图的所有精灵分开存储，四叉树中的每一个节点，都有一个精灵链表，或者精灵队列。使用与绘制地图同样的方法，在得到显示区域的范围后，遍历整个树，得出和显示区域相交的叶子节点，然后，再判断叶子节点中的精灵是否在显示范围内。不过要注意的是，有些精灵只有一部分在显示区域当中的，这就要在判断时候，采用一个比显示区域更大的矩阵区域了，这个区域的大小随显示区域的大小和精灵的大小来决定。
现在已经确定了哪些精灵是要绘制的了，但是如何正确的绘制它们，而不让先后顺序弄错呢？这就要为每一个精灵设置一个渲染的优先权的变量。然后在渲染队列中，按优先权大小排序。一般的精灵，则可以按照它们的位置来确定优先权，这应该不是很难做到吧。而特殊的精灵，比如天上飞的，或者一些魔法之类的。就要分为层次考虑了。按照渲染的先后顺序，可以分为地表层，地上层，天空层等等。首先确定精灵在哪一层然后在这一层的什么位置。就可以得出优先权了。
得出优先仅后。并不是按优先权大小就一个一个的渲染了，我们可以在这里做一些优化，比如如果一个精灵完全被前面的精灵挡住了，那么后面的精灵就不必渲染了。还可以加入脏矩阵算法，至于如何优化，这里不做讨论。逻辑层决定哪些精灵要画，要画在哪里。至于怎么画，是图形层的事了。
三、精灵的选取：
如何用鼠标选取一个NPC或是一个怪物呢？在四叉树结构里面，这个也很好解决，这需要遍历树确定鼠标所指的叶子节点，再判断叶子节点的精灵是否被选取就可以了。游戏中的精灵，并非全部都可以选取的。这样可以在叶子节点里将可选取的精灵分开存储。如果节点中不存在这种精灵，就完全不并判断了。
但是这里有一个与精灵绘制同样的问题，也就是有些精灵，只有一部分是在叶子节点中的，另一部分在另一个节点中。那么，为了选取的准确性，我们不光要检测鼠标所指的那个叶子节点，它周围的几个叶子节点也要判断。为了加快速度，可以用一个二维数组把所有的叶子节点存储起来。而叶子节点则保存对数组元素的指针即可。
四、精灵的运动：
游戏中的精灵，如果从一个叶子节点走到另一个叶子节点，则需要做相应的更新和变化。精灵将从一个链表被移到另一个链表中。为了优化，我们可以将所有的精灵用同一块内存池来存储，使用内存池，可以避免频繁的内存分配和释放操作，同时也可以做到一次性释放。还有利于内存对齐。关于内存优化这里不敢多说了，以免贻笑大方。
精灵走动时，一定要首先寻路，确定走动的路线。这就用到A*算法了，为了寻路，还得用数组存储整个地图的占位情况，也就是说哪里能走，哪里不能走。可是有些情况是不可预测的，比如一个精灵寻好了路，当它走到一半时，突然杀出来另一个精灵挡在他面前，这就有可能造成“穿过”的错误。为了避免这种错误，每走一步，还得判断下一步是不是可走的，如果不可走还要重新寻路。当然还有很多其它方法解决这类问题，比如精灵排成队，一个跟着一个走等等。
这就是我的想法，希望你也像我一样，有话就说。
