游戏邦在:
杂志专栏:
gamerboom.com订阅到鲜果订阅到抓虾google reader订阅到有道订阅到QQ邮箱订阅到帮看

基于组块设计执行开放世界等距游戏引擎

发布时间:2015-06-09 14:57:05 Tags:,,,,

作者:Benedikt S. Vogler

过去今年里我一直在开发一款名为Wurfel Engine的游戏引擎。以下大部分内容是对于我在学校中的最后一次考试所发现的一些算式与解决方法的解释并在过去2年里得到完善的论文摘录。

你们可以在Wurfel Engine SDK,即我基于Java所编写的开放源游戏引擎中找到以下的大多数算式。现在的我正使用该引擎创造名《Caveland》的商业游戏。

储存地图数据块

储存砖块的一种简单的方式便是使用钻石地图。钻石地图就是一个旋转的固定网格(如图1)。

fig1(from gamasutra)

fig1(from gamasutra)

如果整款游戏都是发生在一张小小的地图上的话这便很适合。然而如果你需要执行一个更大的(开放)游戏世界或生成地图内容,你便需要“流出”数据。为此你需要加载数据块。使用钻石地图是否能够完成流传播?如果你使用钻石地图格式,你的数据块只会如下无缝地进行排列:

fig2(from gamasutra)

fig2(from gamasutra)

灰色矩形代表的是屏幕。你可以发现你需要更多组块去覆盖屏幕。然而你希望组块能够像这样组合在一起:

fig3(from gamasutra)

fig3(from gamasutra)

因此Wurfel Engine使用了一排移动的网格,通常被叫做“错列地图”,这非常适合地图流传播。在错列地图中每个第二排都会移动半个砖块。

fig4(from gamasutra)

fig4(from gamasutra)

拥有数据组块的RAM将遭遇只能模仿接近摄像机的实体的问题。这适合于大多数游戏。如果该区域外部的某些内容(游戏邦注:对于游戏玩法来说可能很重要)出现,你就需要在RAM中添加更多数据块。

访问并储存数据块

存在多种储存数据的方式,在这种情况下数据块总是包含组块。我们想要更快速地访问数据,这意味着基于0(1)进行访问。做到这点的一种简单方式便是使用一个3D数组。很长一段时间我都在使用一个巨大的3D数组,它将被插入一个巨大的地图模型中,如果它们被移除可视区域,那么剩下的数据将被移出内存。

这一解决方法也带有自身的缺陷,因为它允许一个视窗的存在。如果你想要在一个开放世界中执行分屏的话会怎样?摄像机可以设置在完全不同的地方,但只有你处于同一个场所时地图才会运行。我通过将各自带有一个3D模型的数据块储存在一起而解决了这一问题(现在我正在使用一个简单的列表)。为了找到并获得归属于游戏坐标的单元格内容,你需要为每个数据块和维度储存一个固定点。之后你可以在列表上反复进行迭代并判断哪个数据块覆盖了这一坐标。如果是这种情况的话,你便可以通过在角落减去固定点而估算指标的位置。

自定义迭代器是贯穿这张地图的一种有效工具。

fig5(from gamasutra)

fig5(from gamasutra)

基于不为了海量储存减少RAM的使用同游戏,你需要在内存中储存许多数据块或组块。如果你在每个数据块中都包含数千个组块,那么储存每个伴随着多个字段的组块将快速消耗内存容量。现在我正在尝试一个版本,即我只会储存3个字节去代表一个组块。如果它们处于摄像机视窗中,它们便会被转换成带有更多字段且能够用于渲染方法中的对象。这一方法能够帮助我们节省不少空间,即我们可以使用200兆的空间去储存一个1800平方千米的区域。

执行屏幕的一种更好的方法

如果你正在使用一张钻石地图,你的行数将不会发生改变,你也不需要如下的方法,因为你可以通过旋转并改变屏幕空间坐标获得备选单元,然后再离散化数值。

使用错列地图离散化屏幕空间的x和y坐标将会呈现出两个砖块间模糊的结果。

存在两种用于识别正确砖块的常见方法。一种方法便是使用一些颜色编码图像(图6)去识别你的鼠标所点击的角落。这更像是一个难以执行的黑客,有可能改变砖块的维度,并且会创造出错误的结果。还有一种方法是估算砖块中心位置间的距离并使用最接近的那个。我发现这一方法拥有一些意外的结果。这是一种动态的方法,能够通过使用一些不等式去检测侧面而支持不同的砖块大小。

fig6(from gamasutra)

fig6(from gamasutra)

如果你使用如下方程式,你便能够获得与一些图形计算器中的图像方法一样的结果:

fig7(from gamasutra)

fig7(from gamasutra)

当然了,你也可以通过将x或y乘以一个系数而扭曲砖块。

如果你着眼于图表,你将会看到一些重叠的区域。通过检查两个完整的方程式,你便可以识别每个区域并检测一些点是否位于一些邻近的位置上。

一旦你执行了这一方法,你便可以使用该方法去获得游戏中任何点数的单元坐标,该功效也使这一方法变成了一个更加强大的工具。

巧妙地裁剪等距世界

等距游戏世界通常都是扁平的。有时候砖块也是扁平的,但它们更常使用3维砖块,因为这样便可以在高度上移动它们。渲染一个扁平的世界并不会受限于性能。然而Wurfel Engine使用了一个立方体地图。你可以在彼此上方堆积许多组块,这将导致许多重叠组块的出现。因为执行碎片/像素着色器而出现的许多看不见的像素导致执行非定义隐藏界面检测(HSD)会非常致命。

提高性能的一种简单方式便是基于带有三个不同精灵的三面分割每个组块。如果没有组块在前方而遮住其它组块,你便可以只渲染上方和前方。这一算法将执行每个组块的循环并检查其直接邻近对象,从而确定最终的裁剪对象。

为了让设计高度等于设计深度(图8)而使用扭曲的四边形组块时,我们便能够执行一些有效的裁剪。

fig8(from gamasutra)

fig8(from gamasutra)

我通过面向每个组块发送三条射线而做到了这点(图9),每一面一条射线,贯穿地图并检测它们何时遇到可视的那一面。每一条射线会为了每一个半面而分裂成两条以上的射线。在有些情况中一些组块将覆盖一半的面,而有些加深了另一半面的图层将被隐藏于其它组块中(图10)。每个撞击到的面都将获得一个标志。然后渲染器将只会渲染没有标志的面。

fig9(from gamasutra)

fig9(from gamasutra)

fig10(from gamasutra)

fig10(from gamasutra)

后面组块的左边被隐藏起来了,并且没有直接的邻近组块

然而为了艺术,维度将被转换成真正的等距组块。它们是存在问题的,即当你在堆积时它们并不能排成一行,因为设计高度大于设计深度。你可以在图11中看到这点:并不是每一个角落都能够与网格对齐。射线将通过假设组块是否匀称地将其覆盖住而追踪裁剪是否有效。所以基于光线投射的裁剪算法将被更简单的算法所取代。这一算法的问题在于它并不能判断组块是否被隐藏起来以及组块之间是否存在一定的空间,如当组块被一堵墙或屋顶所覆盖住时。

fig11(from gamasutra)

fig11(from gamasutra)

当地图内容改变时,两种裁剪算法都应该被执行。

总结

基于使用案例和要求,我们知道存在更多不同方式去创造一个类似且有效的游戏引擎。每个设计选择都应该始于组块的维度。在体素引擎领域中,我们可以找到许多更快捷的内存节省方式,并且能够将其用于之后的研究中。

本文为游戏邦/gamerboom.com编译,拒绝任何不保留版权的转发,如需转载请联系:游戏邦

Implementing an Open World Isometric Game Engine Based on a Block World Design

by Benedikt S. Vogler

In the last years I have been developing a game engine called Wurfel Engine. A big part of the following is an excerpt of this paper (in German) explaining some algorithms and solutions I discovered during my final exams in school and improved in the last two years.

Most of the following algorithms can be found in the Wurfel Engine SDK, an open source game engine written in Java I have been developing the last years. Currently I am working on the commercial title Caveland using the engine.

Storing the map data with chunks

An easy approach for storing the tiles is to use a diamond map. A diamond map is just a rotated regular grid (fig. 1).

fig. 1

This is great if the whole game takes place on a small map. However, if you require to implement a huge (open) game world or generate the map content, you need to stream the data. To do so you must be able to load the data in chunks. But does streaming work with diamond maps? If you use a diamond map format, your chunks will only align seamlessly if aligned like this:

Diamod Map
fig. 2

The gray rectangle represents the screen. As you can see you need more chunks to cover the screen. However you want to have the chunks aligned like this:

Staggered map grid
fig. 3

Therefore Wurfel Engine uses a row shifted grid, usually called ?staggered map“, which is great for map streaming. In a staggered map each second row is shifted by half a tile.

fig. 4

When having only the blocks in RAM which are near the camera one encounters the problem that one can only simulate the entities which are also near the camera. This works for most games. If something outside the area currently covered should happen, which may be important for the gameplay, you must keep more chunks in RAM.

Accessing and storing the chunks

There are several ways to store data, in this case the chunks containing the blocks. We want the fastest access to the data possible which means access in O(1). An easy way to achieve this for voxel worlds is by using a 3D array. For a very long time I had been using one big 3d array. Newly streamed data, the chunks, which are some smaller 3d arrays, would be inserted into the big map matrix and the rest of the data moved or was removed from memory if they were now moved outside the visible area. I used this design for a long time because it worked fine.

This solution has a flaw as it allows only one viewport. What happens if you want to implement split screen play in an open world? Both cameras can be at completely different places, but the map does only work if you are at the same place. I solved this by storing the chunks each with a 3D matrix in a pool (currently I’m using a simple list). In order to find and get the content of the cell belonging to a game coordinate you only need to store a fixed point for each chunk and the chunk dimensions. You can then iterate over the list and check if the chunk covers this coordinate. If this is the case, you can calculate the index position by subtracting the fixed point at the corner.

Custom iterators are a good tool to traverse the whole map comfortably.

fig. 5

Reducing the RAM usage for mass storage

Depending on the game you need to store a lot of chunks and / or blocks in memory. Storing each block with dozens of fields at each several bytes big can grow very fast in memory consumption if you have thousands of blocks in each chunk. Currently I am experimenting with a version where I store only three byte to represent a block. If they are covered by the viewport of the camera, they get transformed into richer objects with more fields needed for the rendering methods. This method saves so much space that it should be possible to have an area of 1800 km2 in memory with only 200 MB.

A better way to implement Screen to Game

If you are using a diamond map, your rows are not shifted and you are not in need for the following method because you can get the selected cell by rotating and distorting your screen space coordinates to game space and then discretize the values.

Using a staggered map discretizing screen space’s x and y coordinates results in ambiguous results between two tiles.

Two common approaches exist to identify the correct tile. One uses some color coded graphic (fig. 6) to identify the corner of your mouse click. This is rather a hack which is not easy to implement and very static for changes to the tiles dimensions and can result in wrong results if anti-aliasing mixes colors. The other calculates the euclidian distance between the center of the tiles and takes the closest one. I found another simple way to do this which has some nice side effects. It is dynamic and supports different tile sizes by using some inequations to detect the side.

fig. 6

You can get the same result as in the picture approach in some graphing calculator (fig. 7) if you use the following equations:

fig. 7

Of course you can also distort the tiles by multiplying x and / or y with a factor.

If you take a look at the graph, you can see overlapping areas. By checking for two fulfilled equations you can identify each of those areas and detect if some point lays in some adjacent neighbor.

Once you have this method implemented you can also use this method for getting the cell-coordinate to any point in game space which makes this a very powerful tool.

Intelligent clipping in isometric worlds

Isometric game worlds are usually flat. Sometimes tiles are also flat, but often three dimensional tiles (blocks) are used because they can be moved in height. Rendering a flat world is usually not a task limited by performance. However, Wurfel Engine uses a cubic volumetric map. You can stack many blocks on top of each other which results in many overlapping blocks. Doing no custom hidden surface detection (HSD) would be fatal because for lots of non visible pixel the fragment / pixel shader is executed.

A simple way to boost the performance is to split each block in three sides with three separate sprites. You render only the top side and both front sides only if no blocks are in front and covering them. For this algorithm a loop over every block is performed and its direct neighbors are checked and according to them the clipping is set.

When using distorted dimetric blocks so that the projected height equals the projected depth (fig. 8) it is possible to perform some efficient clipping.

fig. 8

I did this by sending three rays for each block (fig. 9), one ray for each side, through the map and check when they hit some visible side. Each ray is split into two more for each half of the side. There are some cases where some block covers one half of the side and some layers deeper the other half of the same side is hidden by another block (fig. 10).
Every hit side then gets a flag (?not clipped“). The renderer then only renders the sides which are not marked as clipped.

fig. 9

fig. 10: the back block has its left side hidden but no direct neighbor block

However, for artistic reasons the dimensions were switched to true isometric blocks. They have the problematic characteristic that they do not align in the projection if you stack them because the projected height is bigger then the projected depth. You can see this in the image (fig. 11): Not every corner is aligned in a grid. The ray tracing clipping only works with the assumption that blocks cover themselves evenly. So the clipping algorithm via ray-casting had to be dropped and replaced with the more simple algorithm I already described. The problem with this one is that it cannot detect the cases where a block is hidden and there is some space between those blocks e.g. when a block is covered by a wall or a ceiling.

fig. 11

Both of the presented clipping algorithms should only be performed when the map content changes and not at each (update) tick.

Summary

Depending on the use case and the requirements there are several more and different ways to build a similar and efficient game engine. Each design choice should be made with care starting at the dimensions of the blocks. In the field of voxel engines many approaches for fast and memory saving architectures can be found which can be used for further research.(source:gamasutra)

 


上一篇:

下一篇: