精华游戏算法整理——关于SLG中人物可到达范围计算的想法

关于SLG中人物可到达范围计算的想法

下面的没有经过实践,因此很可能是错误的,觉得有用的初学朋友读一读吧:)
希望高人指点一二

简介:
在标准的SLG游戏中,当在一个人物处按下鼠标时,会以人物为中心,向四周生成一个菱形的可移动区范围,如下:

0
000
00s00
000
0

这个图形在刚开始学习PASCAL时就应该写过一个画图的程序(是否有人怀念?)。那个图形和SLG的扩展路径一样。

一、如何生成路径:
从人物所在的位置开始,向四周的四个方向扩展,之后的点再进行扩展。即从人物所在的位置从近到远进行扩展(类似广宽优先)。

二、扩展时会遇到的问题:
1、当扩展到一个点时,人物的移动力没有了。
2、当扩展的时候遇到了一个障碍点。
3、当扩展的时候这个结点出了地图。
4、扩展的时候遇到了一个人物正好站在这个点(与2同?)。
5、扩展的点已经被扩展过了。当扩展节点的时候,每个节点都是向四周扩展,因此会产生重复的节点。

当遇到这些问题的时候,我们就不对这些节点处理了。在程序中使用ALLPATH[]数组记录下每一个等扩展的节点,不处理这些问题节点的意思就是不把它们加入到ALLPATH[]数组中。我们如何去扩展一个结点周围的四个结点,使用这个结点的坐标加上一个偏移量就可以了,方向如下:

3
0 2
1

偏移量定义如下:
int offx[4] = { -1, 0, 1, 0 };
int offy[4] = { 0, 1, 0, -1 };

扩展一个节点的相邻的四个节点的坐标为:
for(int i=0; i<4>

int nodecount=0; //AllPath数组中的点的个数(包含待扩展节点和已经扩展的节点
int cutflag=0; //用于划分已经扩展的节点和待扩展节点
NODE temp; //路径中的一个点(临时)
temp.x=pRole[cur]->x; //假设有一个关于人物的类,代表当前的人物
temp.y=pRole[cur]->y;
temp.curmp=pRole[cur]->MP; //人物的最大MP
AllPath[nodecount ]=temp; //起始点入AllPath,此时的起始点为等扩展的节点
 
while(curflag<nodecount) //数组中还有待扩展的节点
{ 
    int n=nodecount; //记录下当前的数组节点的个数。
    for(int i=cutflag;i<nodecount;i ) //遍历待扩展节点
    { 
        for(int j=0;j<4;j ) //向待扩展节点的四周各走一步
        { 
            //取得相邻点的数据
            temp.x=AllPath.x offx[j];
            temp.y=AllPath.y offy[j];
            temp.curmp=AllPath.curmp-pMap[AllPath.x][AllPath.y].decrease;
//以下为检测是否为问题点的过程,如果是问题点,不加入AllPath数组,继续处理其它的点
            if(pMap[temp.x][temp.y].block)
                continue; //有障碍,处理下一个节点
            if(temp.curmp<0)
                continue; //没有移动力了
            if(temp.x<0||temp.x>=MAP_MAX_WIDTH|| temp.y<0||temp.y>=MAP_MAX_HEIGHT)
                continue; //出了地图的范围
            if(pMap[temp.x][temp.y].flag)
                continue; //已经扩展了的结点
            //经过了上面几层的检测,没有问题的节点过滤出来,可以加入AllPath
            AllPath[nodecount]=temp;
        }
        pMap[AllPath.x][AllPath.y].flag=1; //将已经扩展的节点标记为已扩展节点
    }
    cutflag=n; //将已扩展节点和待扩展节点的分界线下标值移动到新的分界线
}
for(int i=0;i<nodecount;i )
    pMap[AllPath.x][AllPath.y].bFlag=0; //标记为已扩展节点的标记设回为待扩展节点。

http://www.eb163.com/club/thread-3497-1-4.html