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

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

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

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

簡(jiǎn)化搜索區(qū)域：

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

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

維護(hù)open和close列表

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

我們要做的是接下來(lái)對(duì)兩個(gè)表的維護(hù)

搜索路徑

如何尋路呢，首先我們引入3個(gè)量

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

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

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

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

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

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

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

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

在close或者是障礙，不管它

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

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

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

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

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

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

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

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

建立尋路流程

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

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

尋路遞歸函數(shù)

首先判斷openlist是否長(zhǎng)度為0，是則尋路失敗

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

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