会员: 密码:  免费注册 | 忘记密码 | 会员登录 网页功能: 加入收藏 设为首页 网站搜索  
游戏开发 > 程序设计 > 入门基础
答softboy关于《回应Softboy之‘流星之舟地图遮挡算法’》
发表日期:2007-01-17 14:18:12作者: 出处:  


Softboy声明:我的所有问题都是根据‘天眼的“回应”一文’产生的,有些问题也许是因为天眼并未在“回应”一文中注明,或是我理解上的偏差而导致的,这里仅仅是讨论技术,并不包含任何感情因素。

下面橘黄色文字是我的“回应”一文,而墨绿色文字是softboyt提出的问题,而天蓝色文字是我的回答:

每屏大约显示20*15个格子(考虑屏幕的象素级卷轴和物体高度,实际是679个)

问题一:请教天眼兄,679是怎样计算出来的?

回答一:参见回答二。

这些格子的显示顺序可以用实时计算来确定,但我采用了更快的方法,对于每个格子
我定义一个结构对应这些格子

struct GRID
{
short int x,y; //格子在屏幕上坐标
short int m,n; //格子在数组里的坐标的偏移值
} *grid;

因为格子的数量在一定的分辨率下是固定,每个格子(结构)中的四个变量值也是
固定的,所以我先将它们算出来,顺序保存在文件中。在游戏图形初始化过程中,
将这个文件载入内存,用grid指向它,于是地图显示就变成了:

for(i=0;i<679;i++)
draw_pat(grid[i].x,grid[i].y,map[grid[i].m+map_offx][grid[i].n+map_offy]);

问题二:格子在屏幕上的坐标应该是随着屏幕卷动而改变吧,但是天眼兄为什么说“每个格子(结构)中的四个变量值也是固定的”,这一点让我非常不解?

回答二:你的不解完全是因为我的表达不清(原谅我那糟糕的表达):屏幕上显示的格子相对于屏幕的位置(屏幕坐标)是固定的(不考虑象素级卷轴),这就是GRID中的x,y;我定义屏幕左上角的那个格子为参考格子A,假定它对应数组(地图)单元(map_offx,map_offy),另一个格子B在数组中的位置相对它偏移(m,n),B格子对应数组单元就是(map_offx+m,map_offy+n),无论屏幕如何卷动(map_offx和map_offy变化),m ,n这两个值都是固定的,这也就是结构中的m,n;。

因为结构中x,y,m,n四个值都是固定的,我用TC20做了小程序计算它们,并存成二进制文件。
    程序
makexy.c 制作二进制文件
      showxy.c    演示制作出的二进制文件
程序makexy可以以命令行方式输入四个参数s1,s2,s3,s4,分别表示每屏要显示的格子相对于屏幕的限定尺寸,我采用(-32,16,672,960),因此可以使用将近一个屏幕高(480 pixels)的图形,这就是679个格子的由来(参看图2)。


我的算法和你最大的不同就在于对物体图进行了横分,如果一个物体在横向上占了n个
格子,我在显示地图时,就在相当于将这个图片横分了n份(实时划分),每份由它地
面对应的格子决定显示顺序。具体的过程入下:

对于格子(11,8)中有物体编号(map[11][8]=33),则显示这个物体位于这个格子内的
部分(就是图中分出的4,尺寸32xn)。
例如对于格子(8,8),如果它其中没有物体编号(map[8][8]=0),那么横向搜索一定
格数,如果发现有物体编号(map[11][8]=33),根据搜索的距离(11-8=3)和这个物体的大
小(4x2)判断是否应当在这个格子map[8][8]内显示物体,如果是(3<4),则根据相对于物
体编号点的偏移画出物体相应的部分(就是图中分出的1,尺寸32xn)。如果没有发现
需要显示的部分,再纵向搜索,方法相同。

问题三:天眼兄的方法的确可以正确实现物体遮挡,但不知道您有没有用程序实现过?就我认为你这种方法的效率并不一定比使用递归方法高。因为照你的方法,每个格子都要进行横向和纵向的几步搜索,而搜索的步数由你使用的最大物体决定,我先假设都是5步,那么照你的679格计算,那搜索步数就是679*(5+2)=6790,去掉左、右、下三条边附近的一些格子的判断和包含物品编号点的格子,那实际的搜索数量应该在五千次以上(这仅仅是保守估计)。而采用我的递归算法最大搜索数量不会超过一千,而且实际上根据地图的复杂度还会减少,但是你的方法却完全固定,不论地图怎么都是相同的数量。

回答三:在我写《回应》一文时,我的引擎已经采用了这个方法.采用纵横搜索十格,这种搜索只是对数组单元值的判断,速度非常之快,而且搜索到长宽均小于2格的物体,均停止这一方向(横向或纵向)上的搜索(不允许物体重叠).这种方法虽然搜索次数多,但相比递归方法还是要快很多.
      编程中有这样一条大家都认可的规律,就是对于同一问题,写起来越是简化的方法,执行速度越慢.递归也是如此,虽然写起来简单,但每次调用不但要保留原有的变量,还要开辟新的动态变量.调用完成后还要释放,效率大量的损失在这里.不信你写几个程序实验,比较一下递归和采用自己建立的堆栈的方法,看看到底那个快!

我之前说采用分图效率损失比较大,是因为不分图时效率太高(采用上面的结构
grid显示的方法),因此分图的过程占的时间相对较多。假设原来显示一屏要10ms,
采用分图的方法后为18ms,效率损失80%,但还是总体来说应该比你的方法用时少。
因为采用分图的方法后,每屏要考虑的格子只有超出屏幕下方的,而不用考虑超出屏
幕左右两侧的。

问题四:根据我的实际测试(建立了一张阻挡关系非常复杂的地图,主要是递归很多),打开遮挡计算后的速度是不开遮挡计算的80%,速度损失仅为20%,远远超过你的80%损失。而在其他一些地图(以前建立的游戏地图)中的测试,几乎无速度损失。当然效率损失仅仅是相对而言,绝对的游戏速度可能我的没有你快,但我只是想证明我的算法是可行的,而且在一定的范围内其效率也是可以接受的。

回答四:我之所以跟你反复讨论,是想通过交流知道各种方法的优缺点,以便在以后其他程序的开发中根据具体情况选择.相信无论效率优劣,你也不愿意废弃原来成熟的方法采用一个不太了解的方法,我也是如此.我的原则是尽量不修改原先定型的算法,因为我已经有过不少教训了:我原来有七八个游戏程序都是因为想要修改的更完善一些而大动干戈,最后面目全非,甚至连编译也不能通过了,结果只好放弃了,现在想起来十分可惜!

返回顶部】 【打印本页】 【关闭窗口

关于我们 / 给我留言 / 版权举报 / 意见建议 / 网站编程QQ群   
Copyright ©2003- 2024 Lihuasoft.net webmaster(at)lihuasoft.net 加载时间 0.00237