自动寻路算法

Ⅰ 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内自带的导航功能就可以完成了。