自動尋路演算法

Ⅰ 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星演算法自動尋路，如果路徑跟地圖都不是格子的，怎麼自動尋路，手

這個不行，尋路可能要遍歷到整個地圖，所以定幾個特殊點沒法得出路徑的。

Ⅳ 如何使用Unity3D做游戲中的尋路導航

現在的大部分mmo游戲都有了自動尋路功能。點擊場景上的一個位置，角色就會自動尋路過去。中間可能會有很多的障礙物，角色會自動繞過障礙物，最終達到終點。使用Unity來開發手游，自動尋路可以有很多種實現方式。
最近，一名海外開發者在博客中分享了自己用Unity引擎重做此前研發的Flash游戲尋路導航的心得，希望可以給大家帶來幫助：
大家好，最近我一直都在忙於把2006年的一款Flash游戲用Unity引擎重做出來，盡管我們在《Arrival in Hell》這個項目已經工作了一年多，但這里我希望從頭開始來寫開發者博客，因為這樣才能讓讀者們有比較完整的印象。
如果你們不太熟悉這款游戲的話，我這里做幾句話的介紹，我們在對2006年我和朋友Eardo Mojica以及Richard Rout三人研發的一款Flash游戲進行重做，這是一款點擊式操作的冒險游戲，我們將用Unity引擎進行重做。我做編程和研發游戲已經有十年左右的經驗，但這是我使用Unity引擎做的首款游戲。
在其他事情之前，我首先想要說的就是玩家角色的移動，由於這款游戲現在是真正的3D，因此玩家角色需要在3D空間里尋路。幸運的是，Unity引擎已經有了一些不錯的內置尋路功能，你只要打開窗口-導航（Navigation），選擇你想要使用的物體並且放到路徑中，然後把他們標記為『導航靜態（Navigation static）』這就會告訴Unity這些物體是靜態的（非移動），在尋路的時候應該被考慮進去。

把物體設置為『導航靜態』
這里我想要說一說這個功能有多麼強大。過去，我和大多數的游戲開發者一樣，都必須打造自己的尋路系統，我之前就做過一個A*tile和基於節點的尋路系統，在兩種情況下，特別是基於節點系統的尋路所產生的walls讓人非常頭痛。在基於節點的尋路系統中，你必須手動地把AI使用的點在兩者之間進行導航。Unity不僅做導航功能，還使用了導航網格（Navigation meshes），這比手動放置節點更有效率而且更流暢。更重要的是，你還可以一鍵重新計算整個導航網格，徹底擺脫了手動修改導航節點的做法。

我用基於節點系統做的失敗的尋路系統之一
在把靜態物體加入了導航網格之後，你可以選擇一系列的設定然後點擊bake按鈕，比如在考慮加入一堵牆之前確定坡有多陡以及台階應該多高。這樣你就可以獲得可以預覽的視圖。值得注意的一件事是，不要僅僅因為物體存在在場景中就意味著它是導航網格的一部分。比如說在這款游戲中，我不在乎玩家們是否會踩到瓦礫，所以我並沒有把任何瓦礫標識為導航靜態，這加快了當行網格的生成速度。

《Arrival in Hell》中其實是有數值的
在導航網格生成之後，我簡單地給玩家模型增加了一個NavMeshAgent組件，這款游戲現在就可以進行尋路了，唯一剩下的就是增加滑鼠輸入控制NavMeshAgent的目的地。

用NavMesh做的bake

NavMeshAgent設定
為了告訴NavMeshAgent導航我做了以下指令：
1.注意聽取滑鼠輸入
2.把滑鼠放進屏幕空間
3.把屏幕空間轉變成來自攝像頭的一束光
4.在光達到地面的時候把它移除
5.把NavMeshAgent的目的地設定到地板的對應位置。
C#代碼是這樣的：

可視化視圖下的目的地與路徑
這就解決了我這款游戲的大多數導航需求，唯一的例外就是導航網格由於游戲內的一些活動而發生改變的時候。比如第一個房間的們最開始是關閉的，後來當它打開的時候，當行網格需要更新反映此次變化，允許玩家從新開的們中走過去。我並沒有在游戲運行的時候rebake完整的靜態導航網格，而是使用了NavMeshObstacle組件，該組件可以讓你把尋路過程中的動態物體加進去，如果物體移動，Unity的尋路演算法就會根據實際情況而更新。

導航路徑會根據NavMeshObstacle的變化而自動發生改變

可視化視圖
所以，游戲尋路導航就這么做好了，這就是《Arrival in Hell》游戲中的導航工作原理，這一些只需要Unity內自帶的導航功能就可以完成了。