地图搜索算法:续《地图遮挡算法》

Softboy:
看了你有关流星的舟地图遮挡算法及其系列文章有些看法
不过首先要声明是我没有编过什么大对你和天眼文章也看不太懂这里只是抱着学习态度(我认为我对这类算法问题比较强)
有关物体相互遮挡问题很复杂我想最完整解决方案就是建立 3维方位
实际上目前流行 3维游戏都会采用这类思路方法而且它们数据比流星的舟更复杂对于流星的舟这类游戏来说速度和内存占用方面应没有问题

不过对于流星的舟来说我们还可以简化这个问题:
1、没有物体空间重合
2、没有物体相互遮挡
例如人站在大树前面人挡住了树树叶也可能挡住人
人站在水池中水池边挡住了人人也挡住了水池(这里含有空间重合问题)
3、物体遮挡部分不扩散到周围
例如人站在房屋旁边但并不在房屋的后也可能被屋檐遮挡这会使我下面给出例子出现问题
4、没有其他穿透问题
例如桌子腿可能露出人腿、栏杆露出后面物体等
窗户半透明等等

那么我想知道下面方案是否可行？

1、首先对每种物体进行分析建立struct GameObject结构来描述各种物体
2、把不可移动物体事先处理这样可以加快运行速度
3、建立两张map图表张用于进行有关游戏各种运算张专门用于显示当然也可合而为
4、有关用于显示图表我这里给出了个简化例子这个例子要求每次都重新处理全部物体实际上应该可以找到更加技术思路方法只处理和变化有关物体
5、这里要求采用天眼所说“静态分图”？
6、合成完显示图表后再在分图基础上画出全部图案
7、对map和GameObject复杂化可能可以处理互相遮挡等问题
8、当然也可按天眼思路方法只把图形分成列但区别的处在于这里采用是覆盖而不是搜索

总的中心思想是数据和图像分开处理游戏只是在显示时才用到图像数据当然如果你不愿意分图在没有互相遮挡等问题时也可先计算出物体显示顺序再整块整块地画图不过在计算显示先后顺序时不需要用递归可先建立静止物体显示先后顺序链表再把动态人物插入列表中这种显示思路方法好处是可部分解决穿透问题
如有互相遮挡等问题你定要采用分图技术

=

struct GameObject包括Number表示该物体共占有方格数

ShelteredNumber表示该物体阴影占方格数data指向维列表,x、y分别表示该方格相对该物体位置其中前Number个元素指向该物体根部占据位置ID:该物体IDmapstruct为地图结构其中主要元素为:ID:地表元素IDCoverID:物体元素IDCoverObjectNumber:该处相对于该物体所在位置

=

A:指向GameObject结构指针ObjectID:A物体ID注意:可能有区别ObjectID的相同Ax、y是该物体所在位置对于每个物体进行如下处理: i;for (i=0; i< A->Number+A->ShelteredNumber; i)//对A物体每个区域进行处理{ mapx,mapy; struct mapstruct *mapdeal; mapx=x+A->data[i].x; mapy=y+A->data[i].y; mapdeal=&map[mapx][mapy]; //使用指针以避免重复下标计算 // TempObject=GetObjectPtr(mapdeal->CoverID);//由ID获得GameObject指针 //如CoverID=0则返回NULL (IsNotSheltered(A,mapdeal->CoverID))//A没有被TempObject遮挡 { //则应当显示A物体 mapdeal->CoverID=ObjectID; mapdeal->CoverObjectNumber=i; }}BOOL IsNotSheltered(GameObject *A,ObjectNumber ID){ BOOL judge=TRUE; (ID0) TRUE; //如果没有B物体则不被遮挡 ASSERT(没有互相遮挡,物体不能重叠)； for ( i=0; i< A->Number ; i) { (map[x+A->data[i].x][y+A->data[i].y].CoverIDID) //如果A物体根部所在位置被物体ID遮挡则A物体定在 { //物体ID的后-----参看ASSERT judge=FALSE; ; } } judge;}

延伸阅读

• 2008-12-14-- 地图搜索算法:流星的舟地图遮挡算法(第一稿)