A星算法JavaScript版本

AWang 發布于2019-08-23 16:17 / 2173人閱讀

摘要：星算法介紹實現星尋路算法在游戲中常有需要主角敵人去移動到某個物品或者追尋敵人的時候，這個時候，可以使用尋路算法為了實現游戲，需要尋路算法，于是便自己用實現了一下原理思路簡化搜索區域為了減少資源消耗，首先需要我們將地圖分割為區塊，如下圖建立起

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星算法

GPU云服務器云服務器 JavaScript版本 javascript算法題星巴克問卷星網站

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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