地图搜索算法:流星的舟地图遮挡算法(第一稿)

　　下面文字将叙述成都金点工作组所设计ＲＰＧ游戏流星的舟地图遮挡算法游戏地图采用斜４５度视角屏幕分为了２０＊１５个菱形图块每个图块大小为６４＊３２(像素点)
　　 首先看下这张图我算法是当扫描到物体编号点后先画出物体然后搜索左右两个修正区如果修正区中有其他物体编号那么先画出该物体然后搜索新找到物体两个修正区这样不断递归进行搜索直到全部搜索完毕



　　拒我测试这个算法速度还是可以但是还存在定缺陷如:有可能掉入死循环(属于特殊情况般不会发生)、对于下小上大物体(如:树冠很大树)有可能出现遮挡
　　 下面代码就是流星的舟中用到场景遮挡算法我把其中些不必要东西清除了然后加上了详细注释

//显示个场景中所有物体包括角色(我把角色当作景物进行处理)
void ShowMap
{
//画景物(pm.SX,pm.SY)是当前屏幕相对于整张地图坐标
for(j=pm.SY; j<pm.SY+16+10; j)
{
//在地图Y轴范围的内(Height:地图高度)
( j<Height )
{
//先画偶数行物体
for(i=pm.SX-6; i<pm.SX+21+6; i2)
{
//在地图X轴范围内(Width:地图宽度)
( i>=0 && i<Width )
{
Cover=Data[Width*j+i].CoverID; //取当前图块中景物数据
( Cover != 0 ) //显示物体(0:无物体)
{
Cover-=16; //这是我做个变换无实际意义
Blt(lpDDSBack, ((i-pm.SX)<<5)-pm.DX - Objects[Cover].x, ((j-pm.SY)<<5)-pm.DY - Objects[Cover].y +32 ,lpDDSObj[ Objects[Cover].Surf ], Objects[Cover].rect, TRUE); //画出物体
FixMap(i,j,Cover); //修正大物体遮挡关系(最重要部分)
}
}
}
//后画奇数行物体
for(i=pm.SX+1-6; i<pm.SX+21+6; i2)
{
//在地图X轴范围内
( i>=0 && i<Width )
{
Cover=Data[Width*j+i].CoverID;
( Cover != 0 ) //显示物体
{
Cover-=16;
Blt(lpDDSBack, ((i-pm.SX)<<5)-pm.DX - Objects[Cover].x, ((j-pm.SY)<<5)-pm.DY - Objects[Cover].y + 48 ,lpDDSObj[ Objects[Cover].Surf ], Objects[Cover].rect, TRUE);
FixMap(i,j,Cover);
}
}
}
}
}
}


//****************************
//修正物体阻挡(这个中用到了很多其他东西所以可能很难读懂不过只要你理解了我思路方法我想你可以写出更好代码来)
void FixMap( x, y, Cover)
{
Ox, Oy, Vx, Vy;
tx, ty; //临时变量
//左边
( Objects[Cover].Lx>0 )
{
//转化成斜坐标系
Ver2Oblique(x, y, Ox, Oy);
//求 3角型顶点
Ox-=Objects[Cover].Lx;
Oy1;
for( i=0; i<Objects[Cover].Lx; i)
for( j=0; j<=i; j)
{
tx=Ox+j;
ty=Oy+i-j;
//转化成直坐标系
Oblique2Ver(tx,ty, Vx, Vy);
ID=Data[Width*Vy+Vx].CoverID;
( NpcData[ Width*Vy+Vx ] != 0 )
{
ShowRoles(NpcData[ Width*Vy+Vx] );
}
( ID != 0 )
{
ID-=16;
( Vx%20 )
Blt(lpDDSBack, ((Vx-pm.SX)<<5)-pm.DX - Objects[ID].x, ((Vy-pm.SY)<<5)-pm.DY - Objects[ID].y +32 ,lpDDSObj[ Objects[ID].Surf ], Objects[ID].rect, TRUE);

Blt(lpDDSBack, ((Vx-pm.SX)<<5)-pm.DX - Objects[ID].x, ((Vy-pm.SY)<<5)-pm.DY - Objects[ID].y +48 ,lpDDSObj[ Objects[ID].Surf ], Objects[ID].rect, TRUE);
FixMap(Vx, Vy, ID); //递归
}
}
}

//右边
( Objects[Cover].Ly>0 )
{
//转化成斜坐标系
Ver2Oblique(x, y, Ox, Oy);
//求 3角型顶点
Oy-=Objects[Cover].Ly;
Ox1;
for( i=0; i<Objects[Cover].Ly; i)
for( j=0; j<=i; j)
{
tx=Ox+j;
ty=Oy+i-j;
//转化成直坐标系
Oblique2Ver(tx,ty, Vx, Vy);
ID=Data[Width*Vy+Vx].CoverID;
( NpcData[ Width*Vy+Vx ] != 0 )
{
ShowRoles( NpcData[ Width*Vy+Vx ] );
}
( ID != 0 )
{
ID-=16;
( Vx%20 )
Blt(lpDDSBack, ((Vx-pm.SX)<<5)-pm.DX - Objects[ID].x, ((Vy-pm.SY)<<5)-pm.DY - Objects[ID].y +32 ,lpDDSObj[ Objects[ID].Surf ], Objects[ID].rect, TRUE);

Blt(lpDDSBack, ((Vx-pm.SX)<<5)-pm.DX - Objects[ID].x, ((Vy-pm.SY)<<5)-pm.DY - Objects[ID].y +48 ,lpDDSObj[ Objects[ID].Surf ], Objects[ID].rect, TRUE);
FixMap(Vx, Vy, ID); //递归
}
}
}
}

　　上面代码仅仅是想帮助你更好理解算法但是如果你很难看懂话就请不要再继续浪费时间它本来就太乱了如果大家对这个算法感兴趣话我可以把上面代码规范标准化但我并不能保证这种思路方法是正确、高效这仅仅是我个人凭空想出来(流星的舟是它唯个例子你可以到http://www.gpgame.com下载范例)

延伸阅读

• 2008-12-14-- 地图搜索算法:续《地图遮挡算法》