cocos2dx 什么是a星算法

您好，我来为您解答：

A搜寻算法俗称A星算法。这是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。常用于游戏中的NPC的移动计算，或线上游戏的BOT的移动计算上。

如果我的回答没能帮助您，请继续追问。

在项目中遇到了自动寻路的需求，于是决定开始学习一下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: PathUtillua

-- Author: bzx

-- Date: 2014-07-01

-- Purpose: 寻路

module("PathUtil", packageseeall)

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 tableisEmpty(_open_list) do

local cur_point = _open_list[1]

tableremove(_open_list, 1)

_open_map[cur_pointkey] = nil

if isEqual(cur_point, dest_point) then

return makePath(cur_point)

else

_close_map[cur_pointkey] = cur_point

local next_points = getNextPoints(cur_point)

for i = 1, #next_points do

local next_point = next_points[i]

if _open_map[next_pointkey] == nil and _close_map[next_pointkey] == nil and isObstacle(next_point) == false then

_open_map[next_pointkey] = next_point

tableinsert(_open_list, next_point)

end

end

tablesort(_open_list, compareF)

end

end

return nil

end

function init()

_open_list = {}

_open_map = {}

_close_map = {}

_path = {}

_map_data = {}

for i = 1, _delegetheight do

_map_data[i] = {}

for j = 1, _delegetwidth do

local value = _delegetgetValue(j, i)

_map_data[i][j] = value

end

end

_open_map[getKey(_start_point)] = _start_point

tableinsert(_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, #_delegetdirections do

local offset = _delegetdirections[i]

local next_point = createPoint(pointx + offset[1], pointy + offset[2])

next_point["last"] = point

if next_pointx >= 1 and next_pointx <= _delegetwidth and next_pointy >= 1 and next_pointy <= _delegetheight then

next_point["g_value"] = _delegetg(point, next_point)

next_point["h_value"] = _delegeth(point, _dest_point)--mathabs(next_pointsx - _dest_pointx) + mathabs(next_pointsy - _dest_pointy)

next_point["f_value"] = next_pointg_value + next_pointh_value

tableinsert(next_points, next_point)

end

end

return next_points

end

-- 得到路径

-- @param end_point 目标点

function makePath(end_point)

_path = {}

local point = end_point

while pointlast ~= nil do

tableinsert(_path, createPoint(pointx, pointy))

point = pointlast

end

local start_point = point

tableinsert(_path, start_point)

return _path

end

-- 两个点的代价比较器

function compareF(point1, point2)

return point1f_value < point2f_value

end

-- 是否是障碍物

function isObstacle(point)

local value = _map_data[pointy][pointx]

if value == 1 then

return true

end

return false

end

-- 两个点是否是同一个点

function isEqual(point1, point2)

return point1key == point2key

end

-- 根据点得到点的key

function getKey(point)

local key = stringformat("%d,%d", pointx, pointy)

return key

end

下面是工具类PathUtil的用法

local deleget = {}

delegetg = function(point1, point2)

return mathabs(point1x - point2x) + mathabs(point1y - point2y)

end

delegeth = delegetg

delegetgetValue = function(j, i)

local index = FindTreasureUtilgetIndex(j, i)

local map_info = _map_infomap[index]

if map_infodisplay == 0 and map_infoeid ~= 1 then

return 0

end

return 1

end

delegetdirections = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}} -- 左，上，下，右

delegetwidth = _cols

delegetheight = _rows

local dest_row, dest_col = FindTreasureUtilgetMapPosition(tag)

local dest_point = PathUtilcreatePoint(dest_col, dest_row)

local start_row, start_col = FindTreasureUtilgetMapPosition(_player_index)

local start_point = PathUtilcreatePoint(start_col, start_row)

_path = PathUtilfindPath(deleget, start_point, dest_point)

_path就是我们找到的路径，起点为最后一个元素，终点为第一个元素

1、首先我们可以在寻路类中设置一个属性变量FindIndex。

2、其次或者专门为寻路服务的静态变量也可以，而每个寻路节点中也存有一个变量FindIndex。

3、最后就可以改变其路径不贴墙了。

以上就是关于cocos2dx 什么是a星算法全部的内容，包括:cocos2dx 什么是a星算法、lua语言a星寻路算法路径怎么平滑、如何改a星算法让路径不贴墙等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！