javascript
JS - A*寻路
算法核心
A*估值算法
尋路估值算法有非常多：常用的有廣度優(yōu)先算法，深度優(yōu)先算法，哈夫曼樹等等，游戲中用的比較多的如：A*估值
算法描述
- 對起點與終點進行橫縱坐標(biāo)的運算
代碼實現(xiàn)
start: 起點坐標(biāo)(point)
end: 終點坐標(biāo)(point)
Math.abs(start.getX() - end.getX()) + Math.abs(start.getY() - end.getY());
算法邏輯
尋路過程中檢索關(guān)聯(lián)點(路徑點)
對關(guān)聯(lián)點分類(分為已經(jīng)關(guān)聯(lián)與未關(guān)聯(lián))
對未關(guān)聯(lián)的點用尋路算法對其進行一次標(biāo)識(每個點需要3種標(biāo)識)
對比關(guān)聯(lián)點的標(biāo)識找出下一步的最優(yōu)路徑
循環(huán)上幾步的操作，直到終點
算法實現(xiàn)
- 定義一個容器，在js中使用數(shù)組[ ]，為了更好描述算法，在Array中實現(xiàn)幾個方法
判斷容器中是否存在該點:
// 根據(jù)對象判斷 Array.prototype.isExistByValue = function(value) {for (var i = 0; i < this.length; i++) {if (value.getX() == this[i].getX() && value.getY() == this[i].getY()) {return this[i];// 對象總是為真}}return false; } // 根據(jù)對象中的屬性值判斷 Array.prototype.isExistByProperty = function(x, y) {for (var i = 0; i < this.length; i++) {if (x == this[i].getX() && y == this[i].getY()) {return true;}}return false; }移除一個點:
// 根據(jù)點的屬性值移除點 Array.prototype.removeValue = function(x, y) {for (var i = 0; i < this.length; i++) {if (x == this[i].getX() && y == this[i].getY()) {this.splice(i,1);}} }// 根據(jù)對象刪除點 Array.prototype.remove = function(value) {for (var i = 0; i < this.length; i++) {if (value == this[i]) {this.splice(i,1);}} }添加一個點:
// 根據(jù)點的坐標(biāo)屬性添加點到容器中 Array.prototype.add = function(x, y) {var v = new pathUtils.locationPoint(x,y);this.push(v); }根據(jù)點對象從容器中拿取該點，沒有return null:
Array.prototype.getValue = function(value) {for (var i = 0; i < this.length; i++) {if (value.getX() == this[i].getX() && value.getY() == this[i].getY()) {return this[i];}}return null; }根據(jù)點的某一屬性取出該點:
// 把最小F值的point找出來 Array.prototype.getValueByProperty = function() {var minF = this[0].getF();for (var i = 0; i < this.length; i++) {if (minF > this[i].getF()) {minF = this[i].getF();}}for (var i = 0; i < this.length; i++) {if (minF == this[i].getF()) {return this[i];}}return this[0]; }- 尋路邏輯:
算法細節(jié)
需要注意的幾點
點對象中標(biāo)識G的計算
點對象中標(biāo)識H的計算
點對象已經(jīng)被關(guān)聯(lián)過
點對象未被關(guān)聯(lián)過
要點突破
當(dāng)前起點與終點的parent是為null(沒有父節(jié)點的概念)
G值計算:
相對于起點G值一直增大(橫豎走一步消耗為10,斜向走一步消耗為14)
G值有8個方向需要計算
G值總是越靠近終點值越小
H值計算:
相對于起點H值一直減小(離終點近一步-10,離終點遠一步+10)
H值有4個方向需要計算
H值相對于終點是不變的
點已被關(guān)聯(lián)過:
如果某個相鄰方格已經(jīng)在openList里了, 檢查如果用新的路徑 (就是經(jīng)過最優(yōu)點的路徑) 到達它的話, G值是否會更低一些
如果新的G值更低, 那就把它的parent改為目前選中的方格, 然后重新計算它的 F 值和 G 值 (H 值不需要重新計算, 因為對于每個方塊, H 值是不變的)
如果新的 G 值比較高, 就說明經(jīng)過最優(yōu)點再到達該相鄰點不是一個明智的選擇, 因為它需要更遠的路, 這時我們什么也不做
點未被關(guān)聯(lián)過:
- 檢查它所有相鄰并且可以到達 (障礙物和closeList的方格都不考慮) 的方格. 如果這些方格還不在openList里的話, 將它們加入openList, 計算這些方格的 G, H 和 F 值各是多少, 并設(shè)置它們的parent為該最優(yōu)點
算法總結(jié)
A*算法并非是尋路中最好的算法，但由于其實現(xiàn)簡單所以在工程中大量使用
A*尋路整體不是非常難，只要注意細節(jié)就不會出現(xiàn)bug
轉(zhuǎn)載于:https://www.cnblogs.com/Mdh1991/p/6742638.html
總結(jié)
- 上一篇： Java中的HashMap和HashTa
- 下一篇： 6升小米6——算法解题