恩佐2登录 > SEO培训 > 求教关于A算法的优化达人们请进

求教关于A算法的优化达人们请进

admin SEO培训 2020年01月26日

  以下代码只能在MFC里面运行,因为用到了mfc的CPoint之类的东西,我已经尽力优化了,但是在地图达到400*600的时候,而且阻挡点较多的时候,寻路就会达到0.5秒左右,这个太慢了,无法实际应用,有人曾经对我说过真正的A*算法用在游戏的路中是有问题的,求各位达人帮忙优化,或是有别的解决方案,还是怎么将这个A*进行变种?让小弟开开眼界。

  //将地图的周边都加一个位置,设置成障碍物,以免寻路的时候,会走的边界以外去

  //查看目标点有没有被包围,如果是的话,帮它选一个最近的目标点,要在是NPC寻路的情况下

  以上代码有任何问题请大虾们指出,比如说什么逻辑错误,或是规划不对,或是代码风格不好,总之只要你有觉得不爽的地方,请你指出来,并给出改进方法,小弟感激不尽!

  优先列队是什么东东,请大虾指出来?我那个最优点是排序的,不会一个一个的找,还有我那个排序用时间复杂度也不大,应该是o(logn)之类的,反正没有o(n)大

  代码太长,没法细看,不过如果对A*算法调用比较频繁的话,就不能用new和delete操作。

  LZ大概是用一个2D数组之类的来表示一张地图的连通性,然后给出起止位置来找最短路径吧?

  1.用短的直线段来模拟障碍物的边界,假设一共有n条障碍物线n个点画在上面,计算这2n个端点之间的两两的直线个端点之间的直线距离上会出现其它障碍物,则不必计算这2个端点之间的直线个端点之间的直线.经过上述预处理步骤,现在在白纸上已经出现了各个障碍物线段的端点的可连通图了,后面的计算主要要靠它。

  4.1如果起始点和终止点之间没有其它障碍物,计算起始点和终止点的直线如果起始点和终止点之间有其它障碍物(哪怕只有1个),则仿照第2步,分别计算起始点到各个障碍物线段端点的可连通性以及直线距离(如果起始点到该端点之间没有其它障碍物的话),对终止点也照此方式处理。

  然后在经过4.2处理的白纸上(现在这张白纸上已经画了一个包含起止点的图了)求这个图中起止点之间的最短路径(什么Dijkstra,SPFA等等)并将这个最短路径中所有经过的点拿直线连接起来就行了,新宝7恩佐登录

  从道理上来讲,这样子做的话地图的预处理需要花费比较长的时间,但那只是1次性的工作量,后面做起来就很快了。

  上面的确是使用的堆排序,恩佐2登录所以找那个最优点不会花太多的时间,还有就是我这个也没有频繁的使用net和delete,使用的是内存池,是在一开始的时候就把内存已经申请好了。还有就是8楼的那个算法好像和A*差别有点大,有点深奥。

  LZ可以设想一下,在地图上从起始点A到终点B随便画一条线,然后用力把它绷紧,结果会怎样?结果这条线肯定会变成一段一段的折线段。

  那么,如果障碍物的边缘是直线段的话,这条线是否还可能出现弧形?不可能了(这就是我一开始说要用直线段来模拟障碍物边缘的原因)

  所以,假设现在一共有n个障碍物线段(其端点编号依次为Z[1],Z[2],...,Z[2n]),则从起始点A到目标点B

  这条路径表示从先从A直线]直线],如此继续,一直连接到端点Z[ik],最后从Z[ik]直线连接到B。

  既然这样,那么实际运算的时候,只要考虑那些端点的位置以及哪些端点可以直接用直线段连接就可以了(这就是我说的为什么要重新画一个端点图的原因)

  如果LZ做的是静态地图的寻径问题,那么地图中障碍物的位置就不会发生变化,因此可以进行预先处理,以便节省实时处理的时间。

  如果有足够多的内存可用,LZ甚至可以先计算端点图中任意两个端点之间的最小代价路径(需要2n*2n个存储结构体),然后在以后的计算中就可以直接省略掉1)中Z[i1]~Z[ik]之间的路径计算了,这样更快。

标签: seo算法