关于SLG中人物可到达范围计算的想法(转)[@more@]

　　简介：

　　在标准的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; i )

　　{

　　temp.x = temp1.x offx[i];

　　temp.y = temp1.y offy[i];

　　}

　　三、关于地图的结构：

　　1、地图的二维坐标，用于确定每个图块在地图中的位置。

　　2、SLG中还要引入一个变量decrease表示人物经过这个图块后他的移动力的减少值。例如，一个人物现在的移动力为CurMP=5，与之相领的图块的decrease=2；这时，如果人物移动到这里，那它的移动力变成CurMP-decrease。

　　3、Flag域：宽度优先中好像都有这个变量，有了它，每一个点保证只被扩展一次。防止一个点被扩展多次。（一个点只被扩展一次真的能得到正确的结果吗？）

　　4、一个地图上的图块是否可以通过，我们使用了一个Block代表。1---不可以通过；0---可以通过。

　　这样，我们可以定义一个简单的地图结构数组了：

　　#define MAP_MAX_WIDTH 50

　　#define MAP_MAX_HEIGHT 50

　　typedef struct tagTILE{

　　int x,y,decrease,flag,block;

　　}TILE,*LPTILE;

　　TILE pMap[MAP_MAX_WIDTH][MAP_MAX_HEIGHT];

　　以上是顺序数组，是否使用动态的分配更好些？毕竟不能事先知道一个地图的宽、高。

　　四、关于路径：

　　SLG游戏中的扩展路径是一片区域（以人物为中心向四周扩展，当然，当人物移动时路径只有一个）。这些扩展的路径必须要存储起来，所有要有一个好的结构。我定义了一个结构，不是很好：

　　typedef struct tagNODE{

　　int x,y;　 //扩展路径中的一个点在地图中的坐标。

　　int curmp; //人物到了这个点以后的当前的移动力。

　　}NODE,*LPNODE;

　　上面的结构是定义扩展路径中的一个点的结构。扩展路径是点的集合，因此用如下的数组进行定义：

　　NODE AllPath[PATH_MAX_LENGTH];

　　其中的PATH_MAX_LENGTH代表扩展路径的点的个数，我们不知道这个扩展的路径中包含多少个点，因此定义一个大一点的数字使这个数组不会产生溢出：

　　#define PATH_MAX_LENGTH 200

　　上面的这个数组很有用处，以后的扩展就靠它来实现，它应该带有两个变量nodecount 代表当前的数组中有多少个点。当然，数组中的点分成两大部分，一部分是已经扩展的结点，存放在数组的前面；另一部分是等扩展的节点，放在数组的后面为什么会出现已扩展节点和待扩展节点？如下例子：

　　当前的人物坐标为x,y；移动力为mp。将它存放到AllPath数组中，这时的起始节点为等扩展的节点。这时我们扩展它的四个方向，对于合法的节点（如没有出地图，也没有障碍......），我们将它们存放入AllPath数组中，这时的新加入的节点（起始节点的子节点）就是等扩展结点，而起始节点就成了已扩展节点了。下一次再扩展节点的时候，我们不能再扩展起始节点，因为它是已经扩展的节点了。我们只扩展那几个新加入的节点（待扩展节点），之后的情况以此类推。那么我们如何知道哪些是已经扩展的结点，哪些是等扩展的节点？我们使用另一个变量cutflag，在这个变量所代表的下标以前的结点是已扩展节点，在它及它之后是待扩展结点。

　　五、下面是基本框架（只扩展一个人物的可达范围）：

　　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　　{

　　int n=nodecount; //记录下当前的数组节点的个数。

　　for(int i=cutflag;i　　{

　　for(int j=0;j<4;j ) //向待扩展节点的四周各走一步

　　{

　　//取得相邻点的数据

　　temp.x=AllPath[i].x offx[j];

　　temp.y=AllPath[i].y offy[j];

　　temp.curmp=AllPath[i].curmp-pMap[AllPath[i].x][AllPath[i].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[i].x][AllPath[i].y].flag=1; //将已经扩展的节点标记为已扩展节点

　　}

　　cutflag=n; //将已扩展节点和待扩展节点的分界线下标值移动到新的分界线

　　}

　　for(int i=0;i　　pMap[AllPath[i].x][AllPath[i].y].bFlag=0; //标记为已扩展节点的标记设回为待扩展节点