A星算法JavaScript版本

AWang 发布于2019-08-23 16:17 / 2172人阅读

摘要：星算法介绍实现星寻路算法在游戏中常有需要主角敌人去移动到某个物品或者追寻敌人的时候，这个时候，可以使用寻路算法为了实现游戏，需要寻路算法，于是便自己用实现了一下原理思路简化搜索区域为了减少资源消耗，首先需要我们将地图分割为区块，如下图建立起

A星算法 介绍

javascript实现A星寻路算法

在游戏中常有需要主角/敌人去移动到某个物品或者追寻敌人的时候，这个时候，可以使用寻路算法

为了实现canvas游戏，需要寻路算法，于是便自己用JS实现了一下

原理思路

简化搜索区域：

为了减少资源消耗，首先需要我们将地图分割为区块，如下图

2.建立起点和终点坐标，用于寻路

维护open和close列表

我们新建两个列表，一个open表，它记录了所有被考虑的寻路点；一个close表，它记录了所有不再被考虑的点

我们要做的是接下来对两个表的维护

搜索路径

如何寻路呢，首先我们引入3个量

G值，也就是当前点到起始点所需的代价

H值，不考虑所有障碍等要素，该点到终点非斜线方式的估算量，也就是x+y的值

F值，也就是该点的G+H的值

如图所示，左上角为F，右上角为H，左下为G：

接下来是寻路具体实现

首先最小F值的点加入open，点暂记为curr点

将curr点移除open，加入close

对于curr相邻点，都有以下步骤

在close或者是障碍，不管它

不在open中，则计算它的各项值，加入open

在open中，则计算我们当前这条路径到达这个点是否有更小F值，是则更新它的F值

检测到当前路径点和终点一致时候则结束寻路；如果open中为空，则代表没有合适的寻路方案，寻路失败

JS实现的具体方案

首先建立一个Sopt的类，它里面包含以下信息

属性：x,y,f,g,h,isWall,neighbors,parents，

方法addNeighbors,用于添加周围8个格子可以添加的点

初始化地图所有点，运行addNeighbors方法，将neighbors数组初始化

建立寻路流程

初始化地点、终点，将起点加入openlist

建立一个递归函数用于寻找路径

寻路递归函数

首先判断openlist是否长度为0，是则寻路失败

建立一个curr代表当前点初始为null，和currIndex序列号初始为0

let currIndex = 0;
        let curr = null;
        
        for(let i = 0; i < openList.length; i++) {
            if(openList[i].f < openList[currIndex].f) {
                currIndex = i;
            }
        }

        curr = openList[currIndex];

        if(curr === endSopt) {
            drawPath(curr);
            return true;
        }

        removeFromArray(openList, curr);
        closedList.push(curr);

3.遍历curr的neighbors，将合适点的parent设为curr

for(let i = 0; i < curr.neighbors.length; i++) {
            
            let neighbor = curr.neighbors[i];
            if(!closedList.includes(neighbor) && !neighbor.wall) {

                let tmpF =  curr.g + getG(curr, neighbor) + getH(neighbor);

                let newPath = false; // 是否是更好的路线

                if(openList.includes(neighbor)) {
                    if(tmpF <= neighbor.f) {
                        neighbor.f = tmpF;
                        newPath = true;
                    }
                } else {
                    neighbor.g = curr.g + getG(curr, neighbor);
                    neighbor.h = getH(neighbor);
                    neighbor.f = neighbor.g + neighbor.h;
                    newPath = true;
                    openList.push(neighbor);
                }

                if(newPath) {
                    neighbor.parent = curr;
                }
            }
        }

4.递归这个函数，当点和终点一致时，返回这个点，然后递归它的parent属性，则能找到路线

最后附上案例地址：a星算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/102857.html

[译]解密 Uber 数据科学团队路径选择算法的优化之路

摘要：下面是之前解决路径规划问题的方法并且讲解了我们是如何从五年以前三藩市单一的服务成长的到现在每天百万以上用车量的。在更高的层面上，星是搜索算法的启发式实现，因此星优先找到从到之间的一条可能的最优路径。 showImg(https://segmentfault.com/img/remote/1460000005162386); 概述一键用车现在已经烂大街，但是 Uber 简单的界面下又隐...

_ivan 2019-07-25 10:25 评论0 收藏0
天马行空脚踏实地，阿里巴巴有群百里挑一的天才应届生

摘要：阿里巴巴有一群天马行空脚踏实地的阿里星。天马行空脚踏实地奋斗在阿里巴巴生态圈里，阿里星们高考状元清华博士论文达人的光环早已褪去，但是不断学习，不断接受挑战，仍然是这些学霸的本色。 showImg(https://segmentfault.com/img/remote/1460000018728353); 阿里巴巴有一群天马行空脚踏实地的阿里星。阿里巴巴的春季校招已经启动。在阿里的技术...

sshe 2019-06-24 18:23 评论0 收藏0
天马行空脚踏实地，阿里巴巴有群百里挑一的天才应届生

摘要：阿里巴巴有一群天马行空脚踏实地的阿里星。天马行空脚踏实地奋斗在阿里巴巴生态圈里，阿里星们高考状元清华博士论文达人的光环早已褪去，但是不断学习，不断接受挑战，仍然是这些学霸的本色。 showImg(https://segmentfault.com/img/remote/1460000018728353); 阿里巴巴有一群天马行空脚踏实地的阿里星。阿里巴巴的春季校招已经启动。在阿里的技术...

Eidesen 2019-06-21 16:56 评论0 收藏0