寻路算法最快
‘壹’ 急! 求一个寻路算法(最好是A*), 高分!
#include<iostream.h>
#define ALL_R 10
#define ALL_C 10
#define Start_R 1
#define Start_C 1
#define End_R 8
#define End_C 8
typedef struct stack
{
int R;
int C;
int I;
struct stack *Next;
}Stack;
void Initial(Stack **S)
{
*S=NULL;
}
void Push(Stack **S,int cur_R,int cur_C)
{
//Stack *t=(Stack *)malloc(sizeof(Stack));
Stack *t=new Stack;
t->R=cur_R;
t->C=cur_C;
t->I=0;
t->Next=*S;
*S=t;
}
void Pop(Stack **S)
{
Stack *t=*S;
*S=(*S)->Next;
delete t;
}
void Finally(Stack **S)
{
while(*S!=NULL)Pop(S);
}
void NextPosition(Stack *S,int *cur_R,int *cur_C,int K)
{
switch(S->I)
{
case 0:
++(*cur_C);
break;
case 1:
++(*cur_R);
if(K)--(*cur_C);
break;
case 2:
if(K)--(*cur_R);
--(*cur_C);
break;
case 3:
--(*cur_R);
if(K)++(*cur_C);
break;
}
++S->I;
}
void main(void)
{
Stack *S;
int FOUND=0;
int cur_R=Start_R,cur_C=Start_C;
int Maze[ALL_R][ALL_C]=
{
{0,0,0,0,0,0,0,0,0,0},
{0,1,1,0,1,1,1,0,1,0},
{0,1,1,0,1,1,1,0,1,0},
{0,1,1,1,1,0,0,1,1,0},
{0,1,0,0,0,1,1,1,1,0},
{0,1,1,1,0,1,1,1,1,0},
{0,1,0,1,1,1,0,1,1,0},
{0,1,0,0,0,1,0,0,1,0},
{0,0,1,1,1,1,1,1,1,0},
{0,0,0,0,0,0,0,0,0,0}
};
/*
for(int i=0;i<ALL_R;i++)
for(int j=0;j<ALL_C;j++)
cin>>Maze[i][j];
*/
for(int i=0;i<ALL_R;cout<<endl,i++)
for(int j=0;j<ALL_C;j++)
cout<<Maze[i][j];
int Mark[10][10]=
{
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
};
Initial(&S);
do
{
if(!Mark[cur_R][cur_C]&&Maze[cur_R][cur_C])
{
Mark[cur_R][cur_C]=1;
Push(&S,cur_R,cur_C);
if(cur_R==End_R&&cur_C==End_C)
{
FOUND=1;
break;
}
NextPosition(S,&cur_R,&cur_C,1);
}
else
{
while(S!=NULL&&S->I==4)
{
Pop(&S);
}
if(S!=NULL)
{
cur_R=S->R;
cur_C=S->C;
NextPosition(S,&cur_R,&cur_C,0);
}
}
}while(S!=NULL&&!FOUND);
if(FOUND)
{
cout<<"Great!We got it:\n";
while(S!=NULL)
{
cout<<"<"<<S->R<<S->C<<">\n";
Pop(&S);
}
}
else
{
cout<<"Sorry.Not Found.\n";
}
Finally(&S);
}
//啥叫A*?
//64维debug起来有难度，就简化到10，
//如果想初始化Maze的话
//把那段注释掉的代码拿出就可以了
//每次输入100个数太痛苦
‘贰’ 三维点最短路径寻路算法求助
题目描述得不够清楚啊，若干个点就是能作为中途点的那些点么？
如果所有的点都能作为中途点，当然走直径，直接走A到B的直线。
否则，如果只有几个，只能用启发式或者广度搜索吧，因为还有可能根本就没有解。
如果中途点不多的话，可以直接从A出发，计算不超过L距离的那些中途点，然后以那些中途点为出发点，继续计算不超过L距离的点（走过的点就不计入），直到遇到B为止。这种方法就是广度搜索，在同一层距离最短的则为最短路径。
如果中途点过多，无法这样计算的话，限定范围。
‘叁’ a*寻路算法如果f值和h值都相等怎么取最优节点
首先，G值是从开始点到当前点的移动量，H值是从当前点到终点的移动估算量。既然F=G+H.如果F值和H值都相同，那么G值也是相同的，也就是说从开始点走了同样的距离，移动到两个不同的节点，而这两个节点距离重点的距离也是相同的。那就继续往下进行算法。如果继续下去之后，这两个节点还是一样的情况，那说明有两条最优路径，不然一定会有一个节点会被淘汰。
‘肆’ C++寻路算法
迷宫寻找路径要不。。。。。。#include <iostream>
#include<iomanip>
using namespace std;
#define M 10
#define N 10
typedef enum{X=0,up,dn,rt,lt} tDir; //搜索方向
class Migong
{
public:
int tag; /*0 1*/
tDir comeDir; /*退回*/
int up,rt,dn,lt; //方向
int back;
};int m[M][N]={ //初始化通道数据
{0,0,1,1,1,1,1,1,1,1},
{1,0,1,1,1,0,1,1,1,1},
{1,0,0,0,1,0,1,1,1,1},
{1,1,1,0,1,1,1,1,1,1},
{1,0,0,0,1,0,0,0,1,1},
{1,0,1,1,1,0,1,0,1,1},
{1,0,1,0,0,0,1,0,0,1},
{1,0,0,0,1,1,0,1,0,1},
{1,1,1,1,1,1,0,1,0,1},
{1,1,1,1,1,1,1,1,0,0},
}; int ini=0,inj=0; //入点
int outi=9,outj=9; //出口
int cnt=0; //从入口到出口需多少步
int path[M][N]; //记录找到路径后的迷宫
Migong maze[10][10]; void initmaze(Migong mz[][10]) //初始化迷宫数据
{
int i;
int j;
for(i=0;i<10;i++)
for(j=0;j<10;j++)
{
mz[i][j].tag=m[i][j];
mz[i][j].comeDir=X;
mz[i][j].up=0;
mz[i][j].dn=0;
mz[i][j].rt=0;
mz[i][j].lt=0;
mz[i][j].back=0;
}
}int find(Migong mz[][10],int i,int j,tDir dir) //搜索路径
{
if(i==outi&&j==outj)
return 1; ////if 当前节点是出口 then return 1;
if(dir!=X) //if 不是是回退到本节点,then 记录来的方向 根据来的方向设定其相对方向已走
{
mz[i][j].comeDir=dir;
if(dir==up)
mz[i][j].dn=1; //向N方向没有走&&可以走，则向N递归走
if(dir==dn)
mz[i][j].up=1; //向E方向没有走&&可以走，则向N递归走
if(dir==rt)
mz[i][j].lt=1; //向S方向没有走&&可以走，则向N递归走
if(dir==lt)
mz[i][j].rt=1; //向W方向没有走&&可以走，则向N递归走
}
if(mz[i][j].up==0) //if 向up方向没走&&不越界&&可以走 则向up递归走
{
int ni;
int nj;
mz[i][j].up=1; //记录本节点
ni=i-1;
nj=j; //ni,nj表示i,j的上一个坐标
if(ni>=0 && mz[ni][nj].tag==0)
if(find(maze,ni,nj,up))
return 1;
}
if(mz[i][j].dn==0) //if 向dn方向没走&&不越界&&可以走 则向dn递归走
{
int ni;
int nj;
mz[i][j].dn=1; //记录本节点
ni=i+1;
nj=j; //ni,nj表示i,j的下一个坐标
if(ni<10 && mz[ni][nj].tag==0)
if(find(maze,ni,nj,dn))
return 1;
}
if(mz[i][j].rt==0) //if 向rt方向没走&&不越界&&可以走 则向rt递归走
{
int ni;
int nj;
mz[i][j].rt=1; //记录本节点
ni=i;
nj=j+1; //ni,nj表示i,j的右一个坐标
if(nj<10 && mz[ni][nj].tag==0)
if(find(maze,ni,nj,rt))
return 1;
}
if(mz[i][j].lt==0) //if 向lt方向没走&&不越界&&可以走 则向lt递归走
{
int ni;
int nj;
mz[i][j].lt=1; //记录本节点
ni=i;
nj=j-1; //ni,nj表示i,j的左一个坐标
if(nj>=0 && mz[ni][nj].tag==0)
if(find(maze,ni,nj,lt))
return 1;
}
//四个方向都走完了还没有结果
if(i==ini && j==inj) // if 是入口 return 0
return 0;
else // else 则回退
{
mz[i][j].back=1;
if(mz[i][j].comeDir=up) //如果回退的值等于up的值，则向up方向搜索
{
int ni;
int nj;
ni=i+1;
nj=j; //ni,nj表示i,j的下一个坐标
if(find(maze,ni,nj,X))
return 1;
}
if(mz[i][j].comeDir=dn) //如果回退的值等于dn的值，则向dn方向搜索
{
int ni;
int nj;
ni=i-1;
nj=j; //ni,nj表示i,j的上一个坐标
if(find(maze,ni,nj,X))
return 1;
}
if(mz[i][j].comeDir=rt) //如果回退的值等于rt的值，则向rt方向搜索
{
int ni;
int nj;
ni=i;
nj=j-1; //ni,nj表示i,j的左一个坐标
if(find(maze,ni,nj,X))
return 1;
}
if(mz[i][j].comeDir=lt) //如果回退的值等于lt的值，则向lt方向搜索
{
int ni;
int nj;
ni=i+1;
nj=j+1; //ni,nj表示i,j的左下角一个坐标
if(find(maze,ni,nj,X))
return 1;
}
}
return 0;
}int onway( Migong nd) //判断点是否在路径上
{
if(nd.tag!=0)
return 0; //墙
if(nd.up==0&&nd.dn==0&&nd.rt==0&&nd.lt==0)
return 0; //没访问过
if(nd.up==1&&nd.dn==1&&nd.rt==1&&nd.lt==1&&nd.back==1)
return 0; //访问过但不通
return 1;
}//打印
void print( Migong mz[][10]) //打印原迷宫
{
int i;
int j;
cout<<"0表示可通过，1表示墙"<<endl;
cout<<"-------------------------------";
cout<<endl<<" ";
cout<<"▂▂▂▂▂▂▂▂"<<endl;
for(i=0;i<10;i++)
{
cout<<setw(10)<<"▎ ";
for(j=0;j<10;j++)
cout<<mz[i][j].tag;
cout<<" ▎"<<endl;
}
cout<<" ";
cout<<"▂▂▂▂▂▂▂▂"<<endl;
}void print1( Migong mz[][10]) //打印含路径迷宫
{
int i;
int j;
cout<<endl<<" ";
cout<<"▂▂▂▂▂▂▂▂"<<endl;
for(i=0;i<10;i++)
{
cout<<setw(10)<<"▎ ";
for(j=0;j<10;j++)
{
if(i==9 && j==9) //出口
{
cnt++;
cout<<"*";
path[i][j]=0;
}
else
if(onway(mz[i][j]))
{
cout<<"*"; //*表示路径
cnt++;
path[i][j];
}
else
{
cout<<mz[i][j].tag;
path[i][j]=1; //path[i][j]=0表示可通过，path[i][j]=1表示墙
} }
cout<<" ▎"<<endl;
}cout<<" ";
cout<<"▂▂▂▂▂▂▂▂"<<endl;
}void print2( Migong mz[][10]) //打印路径坐标
{
int i;
int j;
int di;
int dj; //di,dj的值为-1，0，1，为了搜索坐标i,j附近的坐标
int pi;
int pj; //pi,pj为上一个路径坐标
int r;
int count; //统计输出了多少个坐标
i=0;
j=0;
pi=1;
pj=0;
count=0; cout<<endl<<"路径坐标为:"<<endl<<endl;
for(r=0;r<cnt;r++)
{
if(i>=10 || j>=10) //i,j的值不可能大于10
continue;
else
{
for(di=-1;di<2;di++)
for(dj=-1;dj<2;dj++)
{
if(di==dj ) //path[i][j]的下一步不可能在它的左上角和右下角
continue;
if(di==1 && dj==-1) //path[i][j]的下一步不可能在它的左下角
continue;
if(di==-1 && dj==1) //path[i][j]的下一步不可能在它的右上角
continue;
if((i+di)<0 ||(j+dj)<0) //i+di,j+dj小于0时不符
continue;
if(path[i+di][j+dj]!=0) //i+di,j+dj不是路径上的坐标
continue;
if((i+di)==i && (j+dj)==j ) //path[i][j]的下一步不可能是它本身
continue;
else
if((i+di)==pi && (j+dj)==pj) //path[i][j]的下一步不可能是它的上一步
continue;
else
{if(i==9&&j==9)<br> cout<<"(9,9)";<br> else<br> {<br> <br> cout<<"("<<i<<","<<j<<")"<<"->";<br> count++;<br> if(count%5==0)<br> cout<<endl;<br> }
pi=i;
pj=j;
i=i+di;
j=j+dj; }
}
}
}
}int main()
{
initmaze(maze); //初始化迷宫
cout<<endl<<endl<<"原迷宫如下："<<endl;
print(maze); //打印原迷宫
if (find(maze,ini,inj,rt)) //如果迷宫有路径
{
cout<<"-------------------------------";
cout<<endl<<"含路径的迷宫,*表示通道"<<endl;
cout<<"-------------------------------";
print1(maze); // 输出含路径的迷宫
cout<<endl<<"-------------------------------"<<endl;
print2(maze); //输出路径坐标
}
else
cout<<"no way!"; //如果迷宫没路径，输出no way
cout<<endl<<endl<<endl;
cout<<"从入口到出口需"<<cnt<<"步";
cout<<endl<<endl;
return 0;
}
‘伍’ 有关A* 寻路算法。 看了这个算法 大致都明白。就是有点不大清楚。
1. B的G值是指从起点A开始，到达该点的最短距离，和B在不在最短路径上没有关系。
2. 不是遍历所有路径，而是所有点。对于m*n的矩阵， 遍历所有点的复杂度是m*n（多项式复杂度），而遍历所有路径的复杂度是4的(m*n)次幂(每个点都有4个可能的方向)。从幂指数复杂度降低到多项式复杂度，这就是A*算法的意义所在。
3. 最优路径是要从终点一步步倒退回来。比如终点的G值是k，那么最多需要4*k次查找，依然是多项式复杂度。但多数问题(对于纯算法题来说)只是需要知道到达终点的步骤，很少要你找出固定路径的。
‘陆’ 梦幻西游自动寻路的寻路算法怎么算
A*寻路算法 A*（A-Star)算法是一种静态路网中求解最短路最有效的方法。
公式表示为： f(n)=g(n)+h(n),
其中f(n) 是节点n从初始点到目标点的估价函数，
g(n) 是在状态空间中从初始节点到n节点的实际代价，
h(n)是从n到目标节点最佳路径的估计代价。
保证找到最短路径（最优解的）条件，关键在于估价函数h(n)的选取：
估价值h(n)<= n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。
如果 估价值>实际值, 搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。
估价值与实际值越接近，估价函数取得就越好。
例如对于几何路网来说，可以取两节点间欧几理德距离（直线距离）做为估价值，即f=g(n)+sqrt((dx-nx)*(dx-nx)+(dy-ny)*(dy-ny))；这样估价函数f在g值一定的情况下，会或多或少的受估价值h的制约，节点距目标点近，h值小，f值相对就小，能保证最短路的搜索向终点的方向进行。明显优于Dijstra算法的毫无无方向的向四周搜索。
conditions of heuristic
Optimistic (must be less than or equal to the real cost)
As close to the real cost as possible
主要搜索过程：
创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。
遍历当前节点的各个节点，将n节点放入CLOSE中，取n节点的子节点X,->算X的估价值->
While(OPEN!=NULL)
{
从OPEN表中取估价值f最小的节点n;
if(n节点==目标节点) break;
else
{
if(X in OPEN) 比较两个X的估价值f //注意是同一个节点的两个不同路径的估价值
if( X的估价值小于OPEN表的估价值 )
更新OPEN表中的估价值; //取最小路径的估价值
if(X in CLOSE) 比较两个X的估价值 //注意是同一个节点的两个不同路径的估价值
if( X的估价值小于CLOSE表的估价值 )
更新CLOSE表中的估价值; 把X节点放入OPEN //取最小路径的估价值
if(X not in both)
求X的估价值;
并将X插入OPEN表中; //还没有排序
}
将n节点插入CLOSE表中;
按照估价值将OPEN表中的节点排序; //实际上是比较OPEN表内节点f的大小，从最小路径的节点向下进行。
启发式搜索其实有很多的算法，比如：局部择优搜索法、最好优先搜索法等等。当然A*也是。这些算法都使用了启发函数，但在具体的选取最佳搜索节点时的策略不同。象局部择优搜索法，就是在搜索的过程中选取“最佳节点”后舍弃其他的兄弟节点，父亲节点，而一直得搜索下去。这种搜索的结果很明显，由于舍弃了其他的节点，可能也把最好的
节点都舍弃了，因为求解的最佳节点只是在该阶段的最佳并不一定是全局的最佳。最好优先就聪明多了，他在搜索时，便没有舍弃节点（除非该节点是死节点），在每一步的估价
中都把当前的节点和以前的节点的估价值比较得到一个“最佳的节点”。这样可以有效的防止“最佳节点”的丢失。那么A*算法又是一种什么样的算法呢？其实A*算法也是一种最
好优先的算法。只不过要加上一些约束条件罢了。由于在一些问题求解时，我们希望能够求解出状态空间搜索的最短路径，也就是用最快的方法求解问题，A*就是干这种事情的！
我们先下个定义，如果一个估价函数可以找出最短的路径，我们称之为可采纳性。A*算法是一个可采纳的最好优先算法。A*算法的估价函数可表示为：
f'(n) = g'(n) + h'(n)
这里，f'(n)是估价函数，g'(n)是起点到终点的最短路径值，h'(n)是n到目标的最断路经的启发值。由于这个f'(n)其实是无法预先知道的，所以我们用前面的估价函数f(n)做
近似。g(n)代替g'(n)，但 g(n)>=g'(n)才可（大多数情况下都是满足的，可以不用考虑），h(n)代替h'(n)，但h(n)<=h'(n)才可（这一点特别的重要）。可以证明应用这样的估价
函数是可以找到最短路径的，也就是可采纳的。我们说应用这种估价函数的最好优先算法就是A*算法。哈。你懂了吗？肯定没懂。接着看。
举一个例子，其实广度优先算法就是A*算法的特例。其中g(n)是节点所在的层数，h(n)=0，这种h(n)肯定小于h'(n)，所以由前述可知广度优先算法是一种可采纳的。实际也是
。当然它是一种最臭的A*算法。
再说一个问题，就是有关h(n)启发函数的信息性。h(n)的信息性通俗点说其实就是在估计一个节点的值时的约束条件，如果信息越多或约束条件越多则排除的节点就越多，估价函
数越好或说这个算法越好。这就是为什么广度优先算法的那么臭的原因了，谁叫它的h(n)=0，一点启发信息都没有。但在游戏开发中由于实时性的问题，h(n)的信息越多，它的计
算量就越大，耗费的时间就越多。就应该适当的减小h(n)的信息，即减小约束条件。但算法的准确性就差了，这里就有一个平衡的问题。
}
‘柒’ 梦幻西游 寻路算法
[HOTKEY]A [NAME]压镖大大王 [CONTENT] [SCRIPT]BEGINMOVE FAST [SCRIPT]MOVETO 23 14 [SCRIPT]REM 出镖局 [SCRIPT]MOVEOUT 2 12 5 [SCRIPT]REM 长安至大唐国境线路 [SCRIPT]MOVETO 500 135 [SCRIPT]MOVETO 505 190 [SCRIPT]MOVETO 390 195 [SCRIPT]MOVETO 282 138 [SCRIPT]MOVETO 125 60 [SCRIPT]MOVETO 30 20 [SCRIPT]REM 出长安 [SCRIPT]MOVEOUT 4 3 4 [SCRIPT]REM 大唐国境至大唐境外线路 [SCRIPT]MOVETO 300 88 [SCRIPT]MOVETO 255 30 [SCRIPT]MOVETO 120 43 [SCRIPT]MOVETO 23 72 [SCRIPT]REM 出大唐国境 [SCRIPT]MOVEOUT 8 86 44 [SCRIPT]REM 大唐国境至狮陀岭线路 [SCRIPT]MOVETO 622 83 [SCRIPT]MOVETO 600 65 [SCRIPT]MOVETO 575 78 [SCRIPT]MOVETO 539 102 [SCRIPT]MOVETO 525 66 [SCRIPT]MOVETO 578 28 [SCRIPT]MOVETO 560 3 [SCRIPT]MOVETO 405 10 [SCRIPT]MOVETO 330 48 [SCRIPT]MOVETO 338 82 [SCRIPT]MOVETO 318 86 [SCRIPT]MOVETO 285 83 [SCRIPT]MOVETO 282 45 [SCRIPT]MOVETO 264 20 [SCRIPT]MOVETO 200 20 [SCRIPT]MOVETO 82 48 [SCRIPT]MOVETO 55 15 [SCRIPT]MOVETO 20 55 [SCRIPT]REM 进狮陀岭 [SCRIPT]MOVEOUT 6 49 34 [SCRIPT]REM 狮陀岭至狮王洞线路 [SCRIPT]MOVETO 108 58 [SCRIPT]MOVETO 65 35 [SCRIPT]MOVETO 65 6 [SCRIPT]MOVETO 112 20 [SCRIPT]REM 进狮王洞 [SCRIPT]MOVEOUT 118 25 35 [SCRIPT]REM 到达大大王跟前 [SCRIPT]MOVETO 22 12
－－－－－－－－－－－－－－－－－－
[HOTKEY]B [NAME]压镖二大王 [CONTENT] [SCRIPT]BEGINMOVE FAST [SCRIPT]MOVETO 23 14 [SCRIPT]REM 出镖局 [SCRIPT]MOVEOUT 2 12 5 [SCRIPT]REM 长安至大唐国境线路 [SCRIPT]MOVETO 500 135 [SCRIPT]MOVETO 505 190 [SCRIPT]MOVETO 395 195 [SCRIPT]MOVETO 282 138 [SCRIPT]MOVETO 125 60 [SCRIPT]MOVETO 30 20 [SCRIPT]REM 出长安 [SCRIPT]MOVEOUT 4 3 4 [SCRIPT]REM 大唐国境至大唐境外线路 [SCRIPT]MOVETO 300 88 [SCRIPT]MOVETO 255 30 [SCRIPT]MOVETO 120 43 [SCRIPT]MOVETO 23 72 [SCRIPT]REM 出大唐国境 [SCRIPT]MOVEOUT 8 86 44 [SCRIPT]REM 大唐国境至狮陀岭线路 [SCRIPT]MOVETO 622 83 [SCRIPT]MOVETO 600 65 [SCRIPT]MOVETO 575 78 [SCRIPT]MOVETO 539 102 [SCRIPT]MOVETO 525 66 [SCRIPT]MOVETO 578 28 [SCRIPT]MOVETO 560 3 [SCRIPT]MOVETO 405 10 [SCRIPT]MOVETO 330 48 [SCRIPT]MOVETO 338 82 [SCRIPT]MOVETO 318 86 [SCRIPT]MOVETO 285 83 [SCRIPT]MOVETO 282 45 [SCRIPT]MOVETO 264 20 [SCRIPT]MOVETO 200 20 [SCRIPT]MOVETO 82 48 [SCRIPT]MOVETO 55 15 [SCRIPT]MOVETO 20 55 [SCRIPT]REM 进狮陀岭 [SCRIPT]MOVEOUT 6 49 34 [SCRIPT]REM 狮陀岭至大象洞线路 [SCRIPT]MOVETO 108 58 [SCRIPT]MOVETO 52 78 [SCRIPT]MOVETO 20 82 [SCRIPT]REM 进大象洞 [SCRIPT]MOVEOUT 28 84 37 [SCRIPT]REM 到达二大王跟前 [SCRIPT]MOVETO 20 10
－－－－－－－－－－－－－－－－
[HOTKEY]C [NAME]压镖三大王 [CONTENT] [SCRIPT]BEGINMOVE FAST [SCRIPT]MOVETO 23 14 [SCRIPT]REM 出镖局 [SCRIPT]MOVEOUT 3 12 5 [SCRIPT]REM 长安至大唐国境线路 [SCRIPT]MOVETO 500 135 [SCRIPT]MOVETO 505 190 [SCRIPT]MOVETO 390 195 [SCRIPT]MOVETO 282 138 [SCRIPT]MOVETO 125 60 [SCRIPT]MOVETO 30 20 [SCRIPT]REM 出长安 [SCRIPT]MOVEOUT 4 3 4 [SCRIPT]REM 大唐国境至大唐境外线路 [SCRIPT]MOVETO 300 88 [SCRIPT]MOVETO 255 30 [SCRIPT]MOVETO 120 43 [SCRIPT]MOVETO 23 72 [SCRIPT]REM 出大唐国境 [SCRIPT]MOVEOUT 8 86 44 [SCRIPT]REM 大唐国境至狮陀岭线路 [SCRIPT]MOVETO 622 83 [SCRIPT]MOVETO 600 65 [SCRIPT]MOVETO 575 78 [SCRIPT]MOVETO 539 102 [SCRIPT]MOVETO 525 66 [SCRIPT]MOVETO 578 28 [SCRIPT]MOVETO 560 3 [SCRIPT]MOVETO 405 10 [SCRIPT]MOVETO 330 48 [SCRIPT]MOVETO 338 82 [SCRIPT]MOVETO 318 86 [SCRIPT]MOVETO 285 83 [SCRIPT]MOVETO 282 45 [SCRIPT]MOVETO 264 20 [SCRIPT]MOVETO 200 20 [SCRIPT]MOVETO 82 48 [SCRIPT]MOVETO 55 15 [SCRIPT]MOVETO 20 55 [SCRIPT]REM 进狮陀岭 [SCRIPT]MOVEOUT 6 49 34 [SCRIPT]REM 狮陀岭至老雕洞线路 [SCRIPT]MOVETO 108 58 [SCRIPT]MOVETO 55 60 [SCRIPT]MOVETO 30 48 [SCRIPT]REM 进老雕洞 [SCRIPT]MOVEOUT 13 43 36 [SCRIPT]REM 到达三大王跟前 [SCRIPT]MOVETO 15 12
－－－－－－－－－－－－－－－－
[HOTKEY]D [NAME]压镖牛魔王 [CONTENT] [SCRIPT]BEGINMOVE FAST [SCRIPT]MOVETO 23 14 [SCRIPT]REM 出镖局 [SCRIPT]MOVEOUT 2 12 5 [SCRIPT]REM 长安至大唐国境线路 [SCRIPT]MOVETO 500 135 [SCRIPT]MOVETO 505 190 [SCRIPT]MOVETO 395 195 [SCRIPT]MOVETO 282 138 [SCRIPT]MOVETO 125 60 [SCRIPT]MOVETO 30 20 [SCRIPT]REM 出长安 [SCRIPT]MOVEOUT 4 3 4 [SCRIPT]REM 大唐国境至大唐境外线路 [SCRIPT]MOVETO 300 88 [SCRIPT]MOVETO 255 30 [SCRIPT]MOVETO 120 43 [SCRIPT]MOVETO 23 72 [SCRIPT]REM 出大唐国境 [SCRIPT]MOVEOUT 8 86 44 [SCRIPT]REM 大唐国境至牛魔寨线路 [SCRIPT]MOVETO 622 83 [SCRIPT]MOVETO 600 65 [SCRIPT]MOVETO 575 78 [SCRIPT]MOVETO 539 102 [SCRIPT]MOVETO 525 66 [SCRIPT]MOVETO 578 28 [SCRIPT]MOVETO 560 3 [SCRIPT]MOVETO 405 10 [SCRIPT]MOVETO 330 48 [SCRIPT]MOVETO 338 82 [SCRIPT]MOVETO 318 86 [SCRIPT]MOVETO 285 83 [SCRIPT]MOVETO 282 45 [SCRIPT]MOVETO 264 20 [SCRIPT]MOVETO 200 20 [SCRIPT]MOVETO 82 48 [SCRIPT]MOVETO 55 15 [SCRIPT]MOVETO 35 42 [SCRIPT]MOVETO 72 105 [SCRIPT]REM 进牛魔寨 [SCRIPT]MOVEOUT 54 116 38 [SCRIPT]REM 狮陀岭至魔王居线路 [SCRIPT]MOVETO 35 65 [SCRIPT]MOVETO 78 65 [SCRIPT]MOVETO 88 70 [SCRIPT]REM 进魔王居 [SCRIPT]MOVEOUT 93 73 39 [SCRIPT]REM 到达牛魔王跟前 [SCRIPT]MOVETO 20 12
－－－－－－－－－－－－－－－－
[HOTKEY]E [NAME]压镖杨戬 [CONTENT] [SCRIPT]BEGINMOVE FAST [SCRIPT]MOVETO 23 14 [SCRIPT]REM 出镖局 [SCRIPT]MOVEOUT 3 13 5 [SCRIPT]REM 长安至大唐国境线路 [SCRIPT]MOVETO 500 135 [SCRIPT]MOVETO 505 190 [SCRIPT]MOVETO 395 190 [SCRIPT]MOVETO 282 138 [SCRIPT]MOVETO 125 60 [SCRIPT]MOVETO 30 20 [SCRIPT]REM 出长安 [SCRIPT]MOVEOUT 4 3 4 [SCRIPT]REM 大唐国境至大唐境外线路 [SCRIPT]MOVETO 300 88 [SCRIPT]MOVETO 255 30 [SCRIPT]MOVETO 120 43 [SCRIPT]MOVETO 23 72 [SCRIPT]REM 出大唐国境 [SCRIPT]MOVEOUT 8 86 44 [SCRIPT]REM 大唐国境至长寿郊外线路 [SCRIPT]MOVETO 622 83 [SCRIPT]MOVETO 600 65 [SCRIPT]MOVETO 575 78 [SCRIPT]MOVETO 539 102 [SCRIPT]MOVETO 525 66 [SCRIPT]MOVETO 578 28 [SCRIPT]MOVETO 560 3 [SCRIPT]MOVETO 405 10 [SCRIPT]MOVETO 330 48 [SCRIPT]MOVETO 338 82 [SCRIPT]MOVETO 318 86 [SCRIPT]MOVETO 285 83 [SCRIPT]MOVETO 282 45 [SCRIPT]MOVETO 264 20 [SCRIPT]MOVETO 200 20 [SCRIPT]MOVETO 82 48 [SCRIPT]MOVETO 55 15 [SCRIPT]REM 对话南瞻部洲土地 [SCRIPT]CLEAR TALKNPC [SCRIPT]TALKNPC 52 15 [SCRIPT]REM 长寿郊外至天宫线路 [SCRIPT]MOVETO 21 58 [SCRIPT]REM 对话天将 [SCRIPT]CLEAR TALKNPC [SCRIPT]TALKNPC 23 55 [SCRIPT]REM 天宫至灵宵宝殿线路 [SCRIPT]MOVETO 150 60 3 3 31 [SCRIPT]REM 进灵宵宝殿 [SCRIPT]MOVEOUT 144 64 32 [SCRIPT]REM 到达杨戬身旁 [SCRIPT]MOVETO 56 28
－－－－－－－－－－－－－－－－－
[HOTKEY]F [NAME]压镖李靖 [CONTENT] [SCRIPT]BEGINMOVE FAST [SCRIPT]MOVETO 23 14 [SCRIPT]REM 出镖局 [SCRIPT]MOVEOUT 3 13 5 [SCRIPT]REM 长安至大唐国境线路 [SCRIPT]MOVETO 500 135 [SCRIPT]MOVETO 505 190 [SCRIPT]MOVETO 395 190 [SCRIPT]MOVETO 282 138 [SCRIPT]MOVETO 125 60 [SCRIPT]MOVETO 30 20 [SCRIPT]REM 出长安 [SCRIPT]MOVEOUT 4 3 4 [SCRIPT]REM 大唐国境至大唐境外线路 [SCRIPT]MOVETO 300 88 [SCRIPT]MOVETO 255 30 [SCRIPT]MOVETO 120 43 [SCRIPT]MOVETO 23 72 [SCRIPT]REM 出大唐国境 [SCRIPT]MOVEOUT 8 86 44 [SCRIPT]REM 大唐国境至长寿郊外线路 [SCRIPT]MOVETO 622 83 [SCRIPT]MOVETO 600 65 [SCRIPT]MOVETO 575 78 [SCRIPT]MOVETO 539 102 [SCRIPT]MOVETO 525 66 [SCRIPT]MOVETO 578 28 [SCRIPT]MOVETO 560 3 [SCRIPT]MOVETO 405 10 [SCRIPT]MOVETO 330 48 [SCRIPT]MOVETO 338 82 [SCRIPT]MOVETO 318 86 [SCRIPT]MOVETO 285 83 [SCRIPT]MOVETO 282 45 [SCRIPT]MOVETO 264 20 [SCRIPT]MOVETO 200 20 [SCRIPT]MOVETO 82 48 [SCRIPT]MOVETO 55 15 [SCRIPT]REM 对话南瞻部洲土地 [SCRIPT]CLEAR TALKNPC [SCRIPT]TALKNPC 52 15 [SCRIPT]REM 长寿郊外至天宫线路 [SCRIPT]MOVETO 21 58 [SCRIPT]REM 对话天将 [SCRIPT]CLEAR TALKNPC [SCRIPT]TALKNPC 23 55 [SCRIPT]REM 天宫至灵宵宝殿线路 [SCRIPT]MOVETO 150 60 3 3 31 [SCRIPT]REM 进灵宵宝殿 [SCRIPT]MOVEOUT 144 64 32 [SCRIPT]REM 到达李靖身旁 [SCRIPT]MOVETO 32 36
－－－－－－－－－－－－－－－－－
[HOTKEY]G [NAME]压镖普提老祖 [CONTENT] [SCRIPT]BEGINMOVE FAST [SCRIPT]MOVETO 23 14 [SCRIPT]REM 出镖局 [SCRIPT]MOVEOUT 2 12 5 [SCRIPT]REM 长安至大唐国境线路 [SCRIPT]MOVETO 500 135 [SCRIPT]MOVETO 505 190 [SCRIPT]MOVETO 390 195 [SCRIPT]MOVETO 282 138 [SCRIPT]MOVETO 125 60 [SCRIPT]MOVETO 30 20 [SCRIPT]REM 出长安 [SCRIPT]MOVEOUT 4 3 4 [SCRIPT]REM 大唐国境至大唐境外线路 [SCRIPT]MOVETO 300 88 [SCRIPT]MOVETO 255 30 [SCRIPT]MOVETO 120 43 [SCRIPT]MOVETO 23 72 [SCRIPT]REM 出大唐国境 [SCRIPT]MOVEOUT 8 86 44 [SCRIPT]REM 大唐国境至长寿郊外线路 [SCRIPT]MOVETO 622 83 [SCRIPT]MOVETO 600 65 [SCRIPT]MOVETO 575 78 [SCRIPT]MOVETO 539 102 [SCRIPT]MOVETO 525 66 [SCRIPT]MOVETO 578 28 [SCRIPT]MOVETO 560 3 [SCRIPT]MOVETO 405 10 [SCRIPT]MOVETO 330 48 [SCRIPT]MOVETO 338 82 [SCRIPT]MOVETO 318 86 [SCRIPT]MOVETO 285 83 [SCRIPT]MOVETO 282 45 [SCRIPT]MOVETO 264 20 [SCRIPT]MOVETO 200 20 [SCRIPT]MOVETO 82 48 [SCRIPT]MOVETO 55 15 [SCRIPT]REM 对话南瞻部洲土地 [SCRIPT]CLEAR TALKNPC [SCRIPT]TALKNPC 52 15 [SCRIPT]REM 长寿郊外至长寿村线路 [SCRIPT]MOVETO 45 30 [SCRIPT]MOVETO 60 65 [SCRIPT]MOVETO 125 90 [SCRIPT]MOVETO 150 152 [SCRIPT]REM 进长寿村 [SCRIPT]MOVEOUT 154 162 28 [SCRIPT]REM 长寿村至方寸山线路 [SCRIPT]MOVETO 132 166 [SCRIPT]MOVETO 102 195 [SCRIPT]REM 出长寿村 [SCRIPT]MOVEOUT 111 206 29 [SCRIPT]REM 方寸山至灵台宫线路 [SCRIPT]MOVETO 126 26 [SCRIPT]MOVETO 135 60 [SCRIPT]MOVETO 55 90 [SCRIPT]MOVETO 125 130 [SCRIPT]REM 进灵台宫 [SCRIPT]MOVEOUT 125 136 30 [SCRIPT]MOVETO 39 25
如果是这个脚本 请采纳我的 谢谢
‘捌’ 星际争霸2的寻路算法思路是怎样的
首先地图整体开始前，会用多层可达矩阵算法，算出路径关键点
2，创建关键节点可达矩阵
3，再每个兵当前位置对关键节点进行路径计算
这样可以最小化资源占用就可以完成路径计算了，高数的离散数学，挺容易解的
‘玖’ 即时战略游戏中实用的寻路算法都有哪些
Potential Field，它是将地图用一个矩阵来表示，矩阵储存着大小不同的电势（整数）。例如，正电势表示吸引，负电势表示排斥。而游戏中的单位本身是一个负电势，游戏以一个数组储存所有单位的电势和位置。这样，在计算一个单位需要怎么从A点到B点时，我们可以用一个新的矩阵将目的地B点设成正电势，并以不同方式（如圆形、四边形等）辐射开来，离B点越远电势越低，直到0。然后将地图矩阵，目的地矩阵，和所有单位数组的电势相加，得出一个新的、反映当前游戏世界的电势矩阵，然后单位再选择周围所有电势点中的最高电势点去走。不过这里坑很多，因为它本质上是Greedy Algorithm，所以它未必能找出解。然而在某些设定中，例如在没有过于复杂地形，并且需要单位自动不相互覆盖的情况下，Potential Field还是可以完成任务。
Flocking Behavior，在对于一大群单位的寻路，计算量是很大的，而且往往会有很多的重复，这些都是可以避免的。如果单位的移动是利用Steering Behavior来实现的话，那么就可以为其中一个单位，称之为Leader，计算路径（例如用导航网格），然后其他单位按照以下Flocking原则来移动：1. 分离，避开相邻单位2. 一致，和整体的移动方向一致，这里应该是Leader的移动方向3. 聚合，向整体的平均位置靠拢这样的话，就可以降低寻路的计算量，并且得到更加真实的群体单位行进效果。
‘拾’ 寻路算法实现
用Dijkstra算法，我做的给你个参考，下面各点是有距离的（移动力），BIG表示不可通过
#define BIG 32767 //无穷大
int pre[6]={0}; //这是关键！pre数组用于记录每个点的前趋，这样算出最短路径后，就可以递归出路径经过的点
int Distance[6]; //用于记录从起点到达每个点的最短路径长度
int Cost[6][6]={{0,1450,1650,BIG,BIG,BIG}, //有向网的邻接矩阵，这里以6个点为例
{1450,0,BIG,1350,2350,BIG},
{1650,BIG,0,BIG,2550,BIG},
{BIG,1350,BIG,0,BIG,1200},
{BIG,2350,2550,BIG,0,850},
{BIG,BIG,BIG,1200,850,0},
};
//Dijkstra算法函数，求给定点到其余各点的最短路径
//参数：邻接矩阵、顶点数、出发点的下标、结果数组、每个点的前趋
void Dijkstra(int Cost[][6],int n,int v0,int Distance[],int pre[])
{
int s[6];
int mindis,dis;
int i,j,u;
//初始化
for(i=0;i<n;i++) {
Distance[i]=Cost[v0][i];
s[i]=0;
}
s[v0] =1; //标记v0
//在当前还未找到最短路径的顶点中，寻找具有最短距离的顶点
for(i=0;i<n;i++){
if(Distance[i]<BIG) pre[i]=v0;
}
for(i=1;i<n;i++) { //每循环一次，求得一个最短路径
mindis=BIG;
for (j=0;j<n;j++) //求离出发点最近的顶点
if(s[j]==0&&Distance[j]<mindis) {
mindis=Distance [j];
u=j;
}
for(j=0;j<n;j++) //修改递增路径序列（集合）
if(s[j]==0) { //对还未求得最短路径的顶点
//求出由最近的顶点 直达各顶点的距离
dis=Distance[u] +Cost[u][j];
//如果新的路径更短，就替换掉原路径
if(Distance[j]>dis){
Distance[j]=dis;
pre[j]=u;
}
}
s[u]=1; // 标记最短路径已经求得
}
}
用Dijkstra函数算出最短路径后，就可以递归出从给定顶点到各点的最短路径上的每个点了，函数如下（不含终点）：
char pathres[100]=""; //保存路径
char *Vertex[6]={"福州","上海","广州","北京","成都","西安"};
//参数：起点、终点
void shpath(int st,int ed) //起点应该为Dijkstra函数中的v0
{
if(pre[ed]!=st){
shpath(st,pre[ed]);
}
strcat(pathres,Vertex[pre[ed]]);
strcat(pathres,"-");
} //最后要在主函数中把终点加到pathres里