Project1

标题: XP如何实现A星寻路?? [打印本页]
作者: 397534736qq    时间: 2013-10-14 21:55
标题: XP如何实现A星寻路??
就是类似梦幻西游那样的走路方式,点击某个位置,可以不被限制方向走到目标地,就算点击NPC也会实现走到NPC旁边,这样的功能如何实现??
作者: 紫英晓狼1130    时间: 2013-10-14 22:13
搜索寻路应该有很多吧，这是一个比较好的
http://rpg.blue/forum.php?mod=viewthread&tid=254033
作者: yagami    时间: 2013-10-15 00:56
本帖最后由 yagami 于 2013-10-15 01:05 编辑

再了解A*前 你得先了解扩散性寻路 有2种bellman 和 dijkxxx的  bellman允许负权值 dijk在bellman的基础上用了贪心策略 效率更高 但不允许负权值
对于RM游戏 权值一般都为1  如果做的复杂点 比如不同地形 移动速度不同 权值就不同了 但不管如何 肯定是正的 所以直接介绍dijk寻路
借算法导论的一图来写个范例
白色圆圈代表没有遍历 灰色代表 开始遍历 黑色代表已经遍历  a能连b 不代表b能连a 所以箭头方向代表可通行  线上的数字代表权值 圈里的数字代表权值合
起点为s  初始s （权值合0 不需要移动）其他点因为初始并不知道总权值多少 定义为正无穷
此图的意思 s点开始遍历 找到可通行的 t 和 y 改变 t y的 总权值 并将S标记为已经遍历 选一个总权值小的开始重复此动作
  1. static Edge edge2[] = {{0, 1, 10},{0, 3, 5},{1, 2, 1},{1, 3, 2},{2, 4, 4},{3, 1, 3},{3, 2, 9},{3, 4, 2},{4, 2, 6},{4, 0, 7}};
  2. //边的结构体 具体可以无视 代表意思是 0和1相连 权值为10  后面类推 也就是和那图对应 0代表S 1代表T 具体对照aaa数组
  3. static char aaa[]={'s','t','x','y','z'};//对应字符
  4.               //    0   1   2   3   4
  5. static int s[]={0,999,999,999,999};//总权值数组  对应上面的字符
  6. static int s2[]={0,0,0,0,0};//路径数组
  7. void test2()//test函数
  8. {
  9.         Graph *p = initGraph(5);
  10.         Tree *t=treeini(999);
  11.         int edgeCount = sizeof(edge) / sizeof(edge[0]);
  12.         for(int i = 0; i < edgeCount; i++)
  13.                 insertEdge(p, &edge2[i]);
  14.         printMatrix(p->_adj, p->_V, p->_V);
  15.        
  16.         //bellman(p);
  17.         dijk(p,t);
  18.         printArray(s, 5);
  19.         //printArray(s2, 5);
  20.         int temp;
  21.         for(int i=0;i<5;i++)
  22.         {
  23.                 temp=i;
  24.                 while(temp)
  25.                 {
  26.                         cout<<aaa[temp]<<"<-";
  27.                         temp=s2[temp];
  28.                 }
  29.                 cout<<'s'<<endl;
  30.         }


  33. }

  35. void dijk(Graph *p,Tree *t)
  36. {
  37.         int count=p->_V;//图的顶点数
  38.         Tree * temp=NULL;
  39.         for(int i=0,n=0;n<count;n++)
  40.                 {
  41.                         for(int j=0;j<count;j++)
  42.                         {
  43.                                 if(p->_adj[i][j]!=0 && s[j] > s[i]+ p->_adj[i][j] )//可通行 &&三角不等式成立
  44.                                 {
  45.                                         s[j]=s[i]+p->_adj[i][j];//松弛改进最短路径
  46.                                         treepush(t ,s[j],j);//加入树节点（我用了2叉查找树 可用最小优先队列代替）
  47.                                         s2[j]=i;//移动路径
  48.                                 }
  49.                         }
  50.                         temp=t;
  51.                         while(temp->left)
  52.                         {
  53.                                 temp=temp->left;//2叉查找树找最小节点
  54.                         }
  55.                         i=temp->index;//确定下一个要遍历的顶点
  56.                         treedel(t,t,temp->num);//删除树节点
  57.                 }

  59. }
复制代码
代码运行结果

至于图的结构体 和 2叉树的 这不是关键所以不用在意   关键就是dijk函数
以下是算法导论的介绍



A*寻路是启发式寻路 Dijk是扩散式的（可理解为圆形散开） A*其实也就是在这基础上再给个估计函数 估计函数按不同情况是不同的 这函数设计的合理与否直接影响到效率
所以这个没有办法给出公式类的东西 举个简单例子 假如地图分为4象限  用dijk的话 扩散的 所以每个象限基本上遍历次数差不多  而你可以给你的A*写个估计函数 如果那个点在第几象限 优先遍历这个象限 然后再遍历其他象限 也就是把for循环拆开而已 一般情况下 肯定效率远高于原始的Dijk
但A*也不是万能的 比如 一个农民找矿 矿是随机分布在任何地方的 这种情况 一般是Dijk效率高
作者: 397534736qq    时间: 2013-10-15 01:45
yagami 发表于 2013-10-15 00:56
再了解A*前 你得先了解扩散性寻路 有2种bellman 和 dijkxxx的  bellman允许负权值 dijk在bellman的基础上用 ...

{:2_251:}感谢大手



欢迎光临 Project1 (https://rpg.blue/) Powered by Discuz! X3.1