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

javascript實(shí)現(xiàn)A星尋路算法

在游戲中常有需要主角/敵人去移動到某個物品或者追尋敵人的時候，這個時候，可以使用尋路算法

為了實(shí)現(xiàn)canvas游戲，需要尋路算法，于是便自己用JS實(shí)現(xiàn)了一下

簡化搜索區(qū)域：

為了減少資源消耗，首先需要我們將地圖分割為區(qū)塊，如下圖

2.建立起點(diǎn)和終點(diǎn)坐標(biāo)，用于尋路

維護(hù)open和close列表

我們新建兩個列表，一個open表，它記錄了所有被考慮的尋路點(diǎn)；一個close表，它記錄了所有不再被考慮的點(diǎn)

我們要做的是接下來對兩個表的維護(hù)

搜索路徑

如何尋路呢，首先我們引入3個量

G值，也就是當(dāng)前點(diǎn)到起始點(diǎn)所需的代價

H值，不考慮所有障礙等要素，該點(diǎn)到終點(diǎn)非斜線方式的估算量，也就是x+y的值

F值，也就是該點(diǎn)的G+H的值

如圖所示，左上角為F，右上角為H，左下為G：

接下來是尋路具體實(shí)現(xiàn)

首先最小F值的點(diǎn)加入open，點(diǎn)暫記為curr點(diǎn)

將curr點(diǎn)移除open，加入close

對于curr相鄰點(diǎn)，都有以下步驟

在close或者是障礙，不管它

不在open中，則計(jì)算它的各項(xiàng)值，加入open

在open中，則計(jì)算我們當(dāng)前這條路徑到達(dá)這個點(diǎn)是否有更小F值，是則更新它的F值

檢測到當(dāng)前路徑點(diǎn)和終點(diǎn)一致時候則結(jié)束尋路；如果open中為空，則代表沒有合適的尋路方案，尋路失敗

JS實(shí)現(xiàn)的具體方案

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

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

方法addNeighbors,用于添加周圍8個格子可以添加的點(diǎn)

初始化地圖所有點(diǎn)，運(yùn)行addNeighbors方法，將neighbors數(shù)組初始化

建立尋路流程

初始化地點(diǎn)、終點(diǎn)，將起點(diǎn)加入openlist

建立一個遞歸函數(shù)用于尋找路徑

尋路遞歸函數(shù)

首先判斷openlist是否長度為0，是則尋路失敗

建立一個curr代表當(dāng)前點(diǎn)初始為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，將合適點(diǎn)的parent設(shè)為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.遞歸這個函數(shù)，當(dāng)點(diǎn)和終點(diǎn)一致時，返回這個點(diǎn)，然后遞歸它的parent屬性，則能找到路線

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