資訊專欄INFORMATION COLUMN
摘要：但再認(rèn)真想想，其實這道題目就類似我們?nèi)粘Ｓ玫膶?dǎo)航，尋找起點和終點可行的最短路線。越小時，那么起點到目標(biāo)點的可行路徑越小。首先將起點放進(jìn)中，然后搜尋起點附近可行方格放到中作記錄。
最近做到一道題，題目如下：
有 A、B 兩點，中間有一堆障礙物，求出A點到B的可行的路徑，寫出一個 DEMO 并可用任何語言實現(xiàn)（要求可以任意設(shè)置 A、B 點和障礙物的位置，需要做UI）。
首先，理解一下題意，需要求出 A、B 兩點的可行路線，要注意的是可以任意設(shè)置 A、B 兩點位置以及障礙物的位置且需要做 UI。題目需一句話帶過，但需要做不少的工作。嗯，很明顯，這是一道考算法邏輯還有 UI 的題目。
現(xiàn)在我們將主要工作放在如何去求出 A、B 兩點的可行的路徑呢？
估計看到題目，很多人都會無從下手。但再認(rèn)真想想，其實這道題目就類似我們?nèi)粘Ｓ玫膶?dǎo)航，尋找起點和終點可行的最短路線。那么，我們可以使用搜尋算法解決這一道題目。搜尋算法有很多種，如：最佳優(yōu)先搜索算法 （Best-First Search）、戴克斯特拉算法（Dijkstra）、A 搜尋算法和迭代加深 A 算法（IDA* ）等等。
先來了解一下 A* 搜尋算法：
A* 算法綜合了 最佳優(yōu)先搜索算法 （Best-First Search） 和 戴克斯特拉算法（Dijkstra）的優(yōu)點：在進(jìn)行啟發(fā)式搜索提高算法效率的同時，可以保證找到一條最優(yōu)路徑（基于評估函數(shù)） 維基百科
A* 搜尋算法的估算函數(shù)：
f(n) = g(n) + h(n)
g(n) 表示起點到任意點 n 的距離，h(n) 表示任意點 n 到目標(biāo)點的距離，f(n) 則表示任意點 n 到起點以及目標(biāo)點的和。f(n) 越小時，那么起點到目標(biāo)點的可行路徑越小。
接下來我們使用圖文來說明一下我們該如何計算：
我們可以將所有格子看作一個二維數(shù)組，里面分為可行以及不可行（即障礙物）。我們將起始點標(biāo)記為 A 以及目標(biāo)點（終點）標(biāo)記為 B，此處我們忽略可斜走的情況（因為需要做各種限制，略麻煩），本文 Open List 存放所有 A 附近可行的方格，Close List 存放已行的不需要再關(guān)注的方格。
（圖一）
可見圖一，起點 A 上下左右有四個方格，右邊格子為障礙物，再次我們則忽略它，那么起點 A 相鄰可行的格子有上左下這三個。我們設(shè)置一個 Open List 用于存放可行的方格，以及一個 Close List 用于記錄已行方格。首先將起點 A 放進(jìn) Open List 中，然后搜尋起點 A 附近可行方格放到 Open List 中作記錄。
從上面 A 搜尋算法的簡單了解，我們可知 A 搜尋算法的估算函數(shù)是：f(n) = g(n) + h(n)。
A 相鄰的長方形 f(n) 越小，則 A 到達(dá) B 的可行路徑最短，因此我們需要選擇最小 f(n) 的長方形行走。接下來看看我們?nèi)绾稳ビ嬎?f(n) 的值。
為了方便計算，我們將方格的長寬設(shè)置為 1 ，如果可斜走那么每一個的斜線為 。當(dāng)然為了方便計算可使用長寬為 10，斜線為 14 的比例來計算。
（圖二）
如圖二，起點 A 有三塊可行的方格，我們標(biāo)記為粉紅色，那么首先我們計算這三個方格的 g 值。起點 A 的上左下的方格分別離 A 點距離 g(n) 為 1 ，所以標(biāo)記粉紅色的上左下的方格 g(n) 值為 1。
那么接下來計算 h(n) 值，計算 h(n) 值時忽略障礙物，即所有方格可行的情況下計算（如果可行斜線情況下，那么在計算 h(n) 值的時候不計算斜走的情況，只計算任意點直行到終點距離）。那么可計算出起點 A 下方的方格 h(n) 等于 7，左方 h(n) 等于 9，上方 h(n) 等于 9。那么得出上左下三個方格的 f(n) 值：
起點 A 上方：f(n) = g(n) + h(n) = 1 + 9 = 10
起點 A 左方：f(n) = g(n) + h(n) = 1 + 9 = 10
起點 A 下方：f(n) = g(n) + h(n) = 1 + 7 = 8
由上面的計算可得出起點 A 下方的 f(n) 值為最小，那么我們第一步走到起點 A 下方的方格。那么將起點 A 下方的方格存到 Close List，且同時從 Open List 中移除。
（圖三）
如圖三，我們走了第一步后 A 點去到了起點的下方一個，那個繼續(xù)去計算，由于上面起點已經(jīng)存在于 Close List 以及已存在于 Open List 的格子我們不需要再關(guān)注，那么圖上可看到 A 點接著可行點只有左右兩點，那么計算 A 點到左邊格子 g(n) 為 2，h(n) 為 8，右邊格子 g(n) 為 2，h(n) 為 6。那么 A 點左邊格子 f(n) 等于 10，右邊格子 f(n) 等于 8，因此我們第二步走 A 點右邊格子，將格子從 Open List 移除，存進(jìn) Close List（如圖四）。
（圖四）
以此類推，我們最終可得出的路徑（如圖五）。
（圖五）
如圖五，綠色路徑為可行的最短路徑，紅色標(biāo)志的則是已存在于 Open List 的方格。
基本原理就是如此，代碼我就不一一列出來，我會放到 Github 或者看看 Jsfiddle 上面，有興趣的可以看一下，對應(yīng)方法也有對應(yīng)的注釋?？梢钥匆幌伦罱K實現(xiàn)的 效果
動畫演示各種算法地址：http://www.webhek.com/post/pathfinding.html
新手一枚，如果有什么寫錯的或者不好的地方，請各位大大指點探討一下，我會不斷優(yōu)化提升。
哦，最近本人在找工作，期待工作地區(qū)廣州、深圳、佛山，如有好工作或者內(nèi)推等可以私聊一下我。
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/83662.html
摘要：星算法介紹實現(xiàn)星尋路算法在游戲中常有需要主角敵人去移動到某個物品或者追尋敵人的時候，這個時候，可以使用尋路算法為了實現(xiàn)游戲，需要尋路算法，于是便自己用實現(xiàn)了一下原理思路簡化搜索區(qū)域為了減少資源消耗，首先需要我們將地圖分割為區(qū)塊，如下圖建立起 A星算法 介紹 javascript實現(xiàn)A星尋路算法 在游戲中常有需要主角/敵人去移動到某個物品或者追尋敵人的時候，這個時候，可以使用尋路算法 ...
摘要：前言偶爾看到兩年前寫的貪吃蛇，當(dāng)時沒把自動尋路的算法寫好，蛇容易掛，周末找了個時間把當(dāng)年的坑填上，寫了個不會掛的貪吃蛇。 前言 偶爾看到兩年前寫的貪吃蛇，當(dāng)時沒把自動尋路的算法寫好，蛇容易掛，周末找了個時間把當(dāng)年的坑填上，寫了個不會掛的貪吃蛇。 兩年前的版本_點擊查看 這次更新的版本_點擊查看 代碼比較簡單,使用 canvas 完成游戲的畫圖，拋開 A* 算法的實現(xiàn)，整個 html 代...
摘要：話說我的地圖就是柵格形式用點坐標(biāo)來表示格子模板模型法很容易理解，就是有幾種走法，按情況調(diào)用。 尋路模塊 (1) 終于要挑戰(zhàn)尋路模塊，雖然我是在重復(fù)造輪子，但看一下別人的輪子怎么造也是很重要的，所以在這之前首先搜索下，看看有什么現(xiàn)成的思路和代碼，收獲如下: 兩種尋路邏輯 有兩種尋路邏輯, 隨機碰撞和路徑規(guī)劃，考慮到： a. 隨機碰撞似乎需要不少經(jīng)驗/實驗數(shù)據(jù)才能達(dá)到不錯的效果，我缺經(jīng)驗/...
摘要：尋路模塊通過一番尋找，發(fā)現(xiàn)這系列文章，其不僅包含算法，連尋路算法中的一些基礎(chǔ)知識也一并介紹了，不愧是斯坦福出品，也很感謝譯者要實現(xiàn)點到點最短路徑，還需要做一些微小的工作，下面逐個說明計算曼哈頓距離的函數(shù)目的是尋路，肯定需要一個方法來估算兩點 尋路模塊 (2) 通過一番尋找，發(fā)現(xiàn)這系列文章，其不僅包含A*算法，連尋路算法中的一些基礎(chǔ)知識也一并介紹了，不愧是斯坦福出品，也很感謝譯者要實現(xiàn)點...
閱讀 3591·2021-11-24 10:19
閱讀 3730·2021-09-30 09:47
閱讀 1293·2019-08-30 15:56
閱讀 790·2019-08-29 15:11
閱讀 905·2019-08-29 13:43
閱讀 3570·2019-08-28 18:25
閱讀 2160·2019-08-26 13:27
閱讀 1439·2019-08-26 11:44
