答softboy有关《回应Softboy的‘流星的舟地图遮挡算法’》

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

下面橘黄色文字是我“回应”文而墨绿色文字是softboyt提出问题而天蓝色文字是我回答: 每屏大约显示20*15个格子(考虑屏幕象素级卷轴和物体高度实际是679个)

问题:请教天眼兄679是怎样计算出来？

回答:参见回答 2

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

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

格子数量在定分辨率下是固定每个格子(结构)中 4个变量值也是
固定所以我先将它们算出来顺序保存在文件中在游戏图形化过程中
将这个文件载入内存用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]);

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

回答 2:你不解完全是我表达不清(原谅我那糟糕表达):屏幕上显示格子相对于屏幕位置(屏幕坐标)是固定(不考虑象素级卷轴)这就是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;

\" width=225 border=0> \" width=225 border=0>

结构中x,y,m,n 4个值都是固定我用TC20做了小计算它们并存成 2进制文件
　　　　 makexy.c　制作 2进制文件
　　　　　　 showxy.c 演示制作出 2进制文件
makexy可以以命令行方式输入 4个参数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)如果没有发现
需要显示部分再纵向搜索思路方法相同

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

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

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



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

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

延伸阅读