西姆极客 码农 flexsim实现A*最短路径算法(AStar)

flexsim实现A*最短路径算法(AStar)

参考资料:
① 踏莎行hyx博客其中一篇《A*寻路算法C++简单实现
② 蔡鸿于博客其中一篇《堪称最好的A*算法
Xueqiao (Joe) Xu在GitHub上的一个开源寻路模拟器《PathFinding.js》(如果无法显示请用浏览器刷新几次)

一些基于C++实现的A*大多数需要构建复杂的地图关系,同时要定义新的类作为数据结构实现该算法。在仿真软件,通过建模可以很容易的构建地图,剩下的工作就是如何利用软件提供的脚本来实现这套算法了。在flexsim 2017.1之后的版本,脚本语言中提供Variant(变体)数据类型和Array数据类型使用(如下图所示),对于该版本以前的脚本语言则使用另一种实现方法,本文将分别介绍。

使用Array和Variant数据类型的实现方法(适用于flexsim 2017.1以后的版本):

var begin = param(1);
var end = param(2);
#define UNREACHABLE 1000000
if (!objectexists(begin) || !objectexists(end))
 return "unreachable";
if (!isclasstype(begin, "AGV::ControlPoint") || !isclasstype(end, "AGV::ControlPoint"))
 return "unreachable";
Variant dList;
forobjecttreeunder(model()) {
 if(isclasstype(a, "AGV::ControlPoint")) {
  dList.push(a);
 }
}
#define FA 1 //矩阵T的列代号,下面的也是
#define FF 2
#define GG 3
#define HH 4
Table T = Table(nodeinsertinto(first(model()))); //矩阵T
T.setSize(dList.length,4,DATATYPE_NUMBER,0);
Variant openList = begin;
Variant closeList;
while(true){
 int indexMin = 0;
 double Fmin = UNREACHABLE;
 for(int i=1;i<=openList.length;i++) {
  if(closeList.indexOf(openList[i])<0) {
   double F = get(T.cell(dList.indexOf(openList[i]),FF));
   if(F<Fmin) {
    indexMin = i;
    Fmin = F;
   }
  }
 }
 if(indexMin<=0) break; //If none element has been find then break
 closeList.push(openList[indexMin]);
  
 treenode current = openList[indexMin];
 for(int j=1;j<=dList.length;j++)
 {
  treenode target = dList[j];
  double dist = cmd_cpdistance(current,target);
   
  if(dist>=UNREACHABLE || closeList.indexOf(target)>=0) { continue; }//if where UNREACHABLE or elements has been traversal, then do nothing
   
  else { 
   
   double G = cpdistance(begin,target);
   double H = cpdistance(target,end);//启发因子!
   double F = G + H;
   int flag = 0;
   if(openList.indexOf(target)<0) { 
    openList.push(target);
    flag++;
    
   if(flag || G<get(T.cell(j, GG))) {  //update T
    set(T.cell(j,FA),tonum(current));//point to father
    set(T.cell(j,GG),G);
    set(T.cell(j,HH),H);
    set(T.cell(j,FF),F);   
   }
   if(target==end) {
    Variant nameList;
    while(objectexists(target)) {
     switch_selected(target,1);
     nameList.push(getname(target));
     target = tonode(get(T.cell(dList.indexOf(target),FA)));
    }
    nameList.reverse();
    string path = getname(begin);
    for(int i=2;i<=nameList.length;i++)
     path = path + "-->" + nameList[i];
      
    destroyobject(T);
    return path;
   }
  }
 }
}
destroyobject(T);
return "unreachable";

使用树结构的实现方法(适用于旧版本):

欢迎扫码转发

标签:,

2 thoughts on “flexsim实现A*最短路径算法(AStar)”

  1. 头像 oliver_xie说道:

    专业!!!!

发表评论

电子邮件地址不会被公开。 必填项已用*标注

16 + 14 =

Scroll Up