『壹』 A星尋路演算法和Unity自帶的尋路相比有什麼優勢
並沒一種尋路適合所有場合，選擇都是基於需求而定的。
1. A* 演算法與貪婪演算法不一樣，貪婪演算法適合動態規劃，尋找局部最優解，不保證最優解。
A*是靜態網格中求解最短路最有效的方法。也是耗時的演算法，不宜尋路頻繁的場合。一般來說適合需求精確的場合。
與啟發式的搜索一樣，能夠根據改變網格密度、網格耗散來進行調整精確度。
使用的地方：
a. 策略游戲的策略搜索
b. 方塊格子游戲中的格子尋路
2. Unity 自帶的導航網格系統
Unity 內置了NavMesh導航網格系統，一般來說導航網格演算法大多是「拐角點演算法」。
效率是比較高的，但是不保證最優解演算法。
使用的地方：
a.游戲場景的怪物尋路
b.動態規避障礙
『貳』 A星尋路演算法和Unity自帶的尋路相比有什麼優勢
在理解Navigation的時候，首先要明確兩個知識點：
AStar：AStar是路點尋路演算法中的一種，同時AStar不屬於貪婪演算法，貪婪演算法適合動態規劃，尋找局部最優解，不保證最優解。AStar是靜態網格中求解最短路最有效的方法。也是耗時的演算法，不宜尋路頻繁的場合。一般來說適合需求精確的場合。
性能和內存佔用率都還行，和啟發式的搜索一樣，能夠根據改變網格密度、網格耗散來進行調整精確度。
A Star一般使用場景：
策略游戲的策略搜索
方塊格子游戲中的格子尋路
Navigation：網格尋路演算法，嚴格意義上它屬於」拐角點演算法」，效率是比較高的，但是不保證最優解演算法。Navigation相對來說消耗內存更大，性能的話還不錯。
Navigation一般使用場景：
游戲場景的怪物尋路
動態規避障礙
它們二者事件的實現方式和原理都不同。
AStar的話，
『叄』 演算法過程是什麼
『肆』 什麼是A搜索演算法
A*搜索演算法，俗稱A星演算法，作為啟發式搜索演算法中的一種，這是一種在圖形平面上，有多個節點的路徑，求出最低通過成本的演算法。常用於游戲中的NPC的移動計算，或線上游戲的BOT的移動計算上。該演算法像Dijkstra演算法一樣，可以找到一條最短路徑；也像BFS一樣，進行啟發式的搜索。
『伍』 A*演算法用於路徑規劃，有什麼缺點
缺點：A*演算法通過比較當前路徑柵格的8個鄰居的啟發式函數值F來逐步確定下一個路徑柵格，當存在多個最小值時A*演算法不能保證搜索的路徑最優。
A*演算法；A*（A-Star)演算法是一種靜態路網中求解最短路徑最有效的直接搜索方法。估價值與實際值越接近，估價函數取得就越好。A*[1] （A-Star)演算法是一種靜態路網中求解最短路最有效的直接搜索方法。注意是最有效的直接搜索演算法。之後涌現了很多預處理演算法（ALT，CH，HL等等），在線查詢效率是A*演算法的數千甚至上萬倍。公式表示為： f(n)=g(n)+h(n),其中 f(n) 是從初始點經由節點n到目標點的估價函數，g(n) 是在狀態空間中從初始節點到n節點的實際代價，h(n) 是從n到目標節點最佳路徑的估計代價。保證找到最短路徑（最優解的）條件，關鍵在於估價函數f(n)的選取：估價值h(n)<= n到目標節點的距離實際值，這種情況下，搜索的點數多，搜索范圍大，效率低。但能得到最優解。並且如果h(n)=d(n)，即距離估計h(n)等於最短距離，那麼搜索將嚴格沿著最短路徑進行， 此時的搜索效率是最高的。如果 估價值>實際值,搜索的點數少，搜索范圍小，效率高，但不能保證得到最優解。
『陸』 A星搜索演算法
A星演算法是定義了一個函數f，公式為：
f = g + h
其中g函數代表目前為止從出發地到達該節點的成本，h函數是預估的當前節點到到目的地的成本，即
g(path) = path cost
h(path) = h(s) = estimated distance to goal
朝著使函數f具有最小值的路徑拓展,該演算法可以找到消耗最小消耗的路徑
注意A星演算法並不是總能找到最優解，能否找到最優解依賴於h函數，條件是
『柒』 lua語言a星尋路演算法路徑怎麼平滑
在項目中遇到了自動尋路的需求，於是決定開始學習一下A星，對於A星我也沒有深究，只能說是勉強搞定了需求，在這和大家分享一下，相互進步，
A星有個公式 f(x) = g(x) + h(x)
,搞清楚這個公式就好辦了，f(x)就是當前位置到下一個位置的總價值，g(x)表示實際價，這是說這一部分代價是確定的，h(x)表示估價值，就是說我
從下一個位置到到終點的代價是未知的，所以叫估價值，如圖中所示，黑色格子表示當前位置，綠色格子表示下一步可能到達的位置，即上、下、左、右這幾個方
向，紅色格子表示終點，褐色表示障礙物，現在要從黑色格子到達紅色格子，那麼黑色格子的下一步肯定是綠色格子當中的一個，黑色格子到綠色格子之間是相挨著
的，所以我們可以很明確的知道它的實際代價為1（移動一步的代價）即g(x)，綠色格子到紅色格子之間隔著很長的距離，中間還有障礙物，所以這個代價是未
知的，即h(x)，所以總的代價就為f(x) = g(x) +
h(x)，我們看到周圍有4個綠色的格子，到底走那一步比較好呢，所以我們要把這4個格子的f(x)值都求出來，然後進行排序，選擇f(x)值最小的，即
總代價最少的那個格子，以此方法繼續下去，直到到達終點 或者 地圖上沒有綠色格子了
下面來看一下這個工具類，g(x)和h(x)要選的比較合適，一般就是採用的曼哈頓演算法，即兩點在x方向和y方向的距離之和，
-- Filename: PathUtil.lua
-- Author: bzx
-- Date: 2014-07-01
-- Purpose: 尋路
mole("PathUtil", package.seeall)
local _map_data -- 地圖數據
local _open_list -- 開放節點
local _open_map -- 開放節點，為了提高性能而加
local _close_map -- 關閉節點
local _deleget -- 代理
local _dest_point -- 目標點
local _start_point -- 起點
local _path -- 路徑
-- 尋找路徑
--[[
deleget = {
g = function(point1, point2)
-- add your code
-- 返回點point1到點point2的實際代價
end
h = function(point1, point2)
-- add your code
-- 返回點point1到點point2的估算代價
end
getValue = function(j, i)
-- 返回地圖中第i行，第j列的數據 1為障礙物，0為非障礙物
end
width -- 地圖寬度
height -- 地圖高度
}
--]]
function findPath(deleget, start_point, dest_point)
_deleget = deleget
_dest_point = dest_point
_start_point = start_point
init()
while not table.isEmpty(_open_list) do
local cur_point = _open_list[1]
table.remove(_open_list, 1)
_open_map[cur_point.key] = nil
if isEqual(cur_point, dest_point) then
return makePath(cur_point)
else
_close_map[cur_point.key] = cur_point
local next_points = getNextPoints(cur_point)
for i = 1, #next_points do
local next_point = next_points[i]
if _open_map[next_point.key] == nil and _close_map[next_point.key] == nil and isObstacle(next_point) == false then
_open_map[next_point.key] = next_point
table.insert(_open_list, next_point)
end
end
table.sort(_open_list, compareF)
end
end
return nil
end
function init()
_open_list = {}
_open_map = {}
_close_map = {}
_path = {}
_map_data = {}
for i = 1, _deleget.height do
_map_data[i] = {}
for j = 1, _deleget.width do
local value = _deleget.getValue(j, i)
_map_data[i][j] = value
end
end
_open_map[getKey(_start_point)] = _start_point
table.insert(_open_list, _start_point)
end
function createPoint(x, y)
local point = {
["x"] = x,
["y"] = y,
["last"] = nil,
["g_value"] = 0,
["h_value"] = 0,
["f_value"] = 0
}
point["key"] = getKey(point)
return point
end
-- 得到下一個可以移動的點
-- @param point 當前所在點
function getNextPoints(point)
local next_points = {}
for i = 1, #_deleget.directions do
local offset = _deleget.directions[i]
local next_point = createPoint(point.x + offset[1], point.y + offset[2])
next_point["last"] = point
if next_point.x >= 1 and next_point.x <= _deleget.width and next_point.y >= 1 and next_point.y <= _deleget.height then
next_point["g_value"] = _deleget.g(point, next_point)
next_point["h_value"] = _deleget.h(point, _dest_point)--math.abs(next_points.x - _dest_point.x) + math.abs(next_points.y - _dest_point.y)
next_point["f_value"] = next_point.g_value + next_point.h_value
table.insert(next_points, next_point)
end
end
return next_points
end
-- 得到路徑
-- @param end_point 目標點
function makePath(end_point)
_path = {}
local point = end_point
while point.last ~= nil do
table.insert(_path, createPoint(point.x, point.y))
point = point.last
end
local start_point = point
table.insert(_path, start_point)
return _path
end
-- 兩個點的代價比較器
function compareF(point1, point2)
return point1.f_value < point2.f_value
end
-- 是否是障礙物
function isObstacle(point)
local value = _map_data[point.y][point.x]
if value == 1 then
return true
end
return false
end
-- 兩個點是否是同一個點
function isEqual(point1, point2)
return point1.key == point2.key
end
-- 根據點得到點的key
function getKey(point)
local key = string.format("%d,%d", point.x, point.y)
return key
end
下面是工具類PathUtil的用法
local deleget = {}
deleget.g = function(point1, point2)
return math.abs(point1.x - point2.x) + math.abs(point1.y - point2.y)
end
deleget.h = deleget.g
deleget.getValue = function(j, i)
local index = FindTreasureUtil.getIndex(j, i)
local map_info = _map_info.map[index]
if map_info.display == 0 and map_info.eid ~= 1 then
return 0
end
return 1
end
deleget.directions = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}} -- 左，上，下，右
deleget.width = _cols
deleget.height = _rows
local dest_row, dest_col = FindTreasureUtil.getMapPosition(tag)
local dest_point = PathUtil.createPoint(dest_col, dest_row)
local start_row, start_col = FindTreasureUtil.getMapPosition(_player_index)
local start_point = PathUtil.createPoint(start_col, start_row)
_path = PathUtil.findPath(deleget, start_point, dest_point)
_path就是我們找到的路徑，起點為最後一個元素，終點為第一個元素
『捌』 人工智慧 A*演算法原理
A 演算法是啟發式演算法重要的一種，主要是用於在兩點之間選擇一個最優路徑，而A 的實現也是通過一個估值函數
上圖中這個熊到樹葉的 曼哈頓距離 就是藍色線所表示的距離，這其中不考慮障礙物，假如上圖每一個方格長度為1，那麼此時的熊的曼哈頓距離就為9.
起點（X1,Y1）,終點（X2,Y2）,H=|X2-X1|+|Y2-Y1|
我們也可以通過幾何坐標點來算出曼哈頓距離，還是以上圖為例，左下角為（0，0）點，熊的位置為（1，4），樹葉的位置為（7，1），那麼H=|7-1|+|1-4|=9。
還是以上圖為例，比如剛開始熊位置我們會加入到CLOSE列表中，而熊四周它可以移動到的點位我們會加入到OPEN列表中，並對熊四周的8個節點進行F=G+H這樣的估值運算，然後在這8個節點中選中一個F值為最小的節點，然後把再把這個節點從OPEN列表中刪除，加入到Close列表中，從接著在對這個節點的四周8個節點進行一個估值運算，再接著依次運算，這樣說大家可能不是太理解，我會在下邊做詳細解釋。
從起點到終點，我們通過A星演算法來找出最優路徑
我們把每一個方格的長度定義為1，那從起始點到5位置的代價就是1，到3的代價為1.41，定義好了我們接著看上圖，接著運算
第一步我們會把起始點四周的點加入OPEN列表中然後進行一個估值運算，運算結果如上圖，這其中大家看到一個小箭頭都指向了起點，這個箭頭就是指向父節點，而open列表的G值都是根據這個進行計算的，意思就是我從上一個父節點運行到此處時所需要的總代價，如果指向不一樣可能G值就不一樣，上圖中我們經過計算發現1點F值是7.41是最小的，那我們就選中這個點，並把1點從OPEN列表中刪除，加入到CLOSE列表中，但是我們在往下運算的時候發現1點的四周，2點，3點和起始點這三個要怎麼處理，首先起始點已經加入到了CLOSE，他就不需要再進行這種運算，這就是CLOSE列表的作用，而2點和3點我們也可以對他進行運算，2點的運算，我們從1移動到2點的時候，他需要的代價也就是G值會變成2.41，而H值是不會變的F=2.41+7=9.41，這個值我們發現大於原來的的F值，那我們就不能對他進行改變（把父節點指向1，把F值改為9.41，因為我們一直追求的是F值最小化），3點也同理。
在對1點四周進行運算後整個OPEN列表中有兩個點2點和3點的F值都是7.41，此時我們系統就可能隨機選擇一個點然後進行下一步運算，現在我們選中的是3點，然後對3點的四周進行運算，結果是四周的OPEN點位如果把父節點指向3點值時F值都比原來的大，所以不發生改變。我們在看整個OPEN列表中，也就2點的7.41值是最小的，那我們就選中2點接著運算。
我們在上一部運算中選中的是1點，上圖沒有把2點加入OPEN列表，因為有障礙物的阻擋從1點他移動不到2點，所以沒有把2點加入到OPEN列表中，整個OPEN列表中3的F=8是最小的，我們就選中3，我們對3點四周進行運算是我們發現4點經過計算G=1+1=2，F=2+6=8所以此時4點要進行改變，F變為8並把箭頭指向3點（就是把4點的父節點變為3），如下圖
我們就按照這種方法一直進行運算，最後 的運算結果如下圖
而我們通過目標點位根據箭頭（父節點），一步一步向前尋找最後我們發現了一條指向起點的路徑，這個就是我們所需要的最優路徑。 如下圖的白色選中區域
但是我們還要注意幾點
最優路徑有2個
這是我對A*演算法的一些理解，有些地方可能有BUG，歡迎大家指出，共同學習。