在Lua中的A*寻路算法
2017-2-8 14:42:40
收藏:0
阅读:104
评论:1
最近我在 Lua 中实现了 A* 寻路算法,但由于在成本中使用曼哈顿方法来处理 H 值,所以我遇到了错误的路径问题。
我想了解是否有其他方法来计算节点的成本。 下面是我目前正在使用的方法:
function CalcG(A,B)
if type(A) == "table" then
A = A.Pos
end
if type(B) == "table" then
B = B.Pos
end
return (A-B).Magnitude
end
function CalcH(A,B)
if type(A) == "table" then
A = A.Pos
end
if type(B) == "table" then
B = B.Pos
end
return math.abs(A.X - B.X) + math.abs(A.Z - B.Z)
end
function GetCost(A,B,C)
return CalcG(A,B) + CalcH(B,C)
end
计算成本:
GetCost(Start,CurrentNode,End)
如果有人能指导我使用更好的启发式方法,我将不胜感激。
点赞
评论区的留言会收到邮件通知哦~
推荐文章
- 如何将两个不同的lua文件合成一个 东西有点长 大佬请耐心看完 我是小白研究几天了都没搞定
- 如何在roblox studio中1:1导入真实世界的地形?
- 求解,lua_resume的第二次调用继续执行协程问题。
- 【上海普陀区】内向猫网络招募【Skynet游戏框架Lua后端程序员】
- SF爱好求教:如何用lua实现游戏内调用数据库函数实现账号密码注册?
- Lua实现网站后台开发
- LUA错误显式返回,社区常见的规约是怎么样的
- lua5.3下载库失败
- 请问如何实现文本框内容和某个网页搜索框内容连接,并把网页输出来的结果反馈到另外一个文本框上
- lua lanes多线程使用
- 一个kv数据库
- openresty 有没有比较轻量的 docker 镜像
- 想问一下,有大佬用过luacurl吗
- 在Lua执行过程中使用Load函数出现问题
- 为什么 neovim 里没有显示一些特殊字符?
- Lua比较两个表的值(不考虑键的顺序)
- 有个lua简单的项目,外包,有意者加微信 liuheng600456详谈,最好在成都
- 如何在 Visual Studio 2022 中运行 Lua 代码?
- addEventListener 返回 nil Lua
- Lua中获取用户配置主目录的跨平台方法
只要启发式是“可接受的”(不高估路径的实际成本),正确的 A * 实现就能保证找到最短路径(有关更多详细信息,请参见Wikipedia上的A*条目)。对于一个不能对角线移动的网格,曼哈顿距离可以满足此标准。但从您的图像来看,似乎您也可以对角线移动,因此曼哈顿距离不再准确地评估距离。考虑这张图片:
蓝色是曼哈顿距离,绿色是“正确”的距离。
正如您所看到的,当我们添加对角线移动的能力时,两点之间的距离变得更短。曼哈顿距离现在高估了距离,因此不可接受,导致 A * 不总是找到最短路径。
那么,我们可以使用什么启发式来模拟对角线网格移动呢?当然有!它被称为**切比雪夫距离**。它考虑到对角线运动,因此更适合在这种情况下建模距离。想象一下在棋盘上的国王。
它的实现很简单:
function chebyshevDistance(dx, dy) return math.max(dx, dy) end