lua的A*

大标 2022年3月9日18:45:10
评论
30
摘要

A星原理到处都有,网络上的luaA星,不是写的看不懂,就是全局变量乱用(讨厌全局变量),项目中用到,简单记录下“`– 简单说明一下– 注意:1是可以走,其他是不能走– 采用4格走法(上下左右),– 采用的移动公式是 “manhattan”:曼哈顿估价法,几何估价法,对角线估价法– 可以改8格走法,1. math_list 哪里改下,2.根据斜走和直的权值,再去改下移动公式(几何估价法,

A星原理到处都有,网络上的luaA星,不是写的看不懂,就是全局变量乱用(讨厌全局变量),项目中用到,简单记录下

```
-- 简单说明一下
-- 注意:1是可以走,其他是不能走
-- 采用4格走法(上下左右),
-- 采用的移动公式是 "manhattan":曼哈顿估价法,几何估价法,对角线估价法
-- 可以改8格走法,1. math_list 哪里改下,2.根据斜走和直的权值,再去改下移动公式(几何估价法,对角线估价法)

local M = {}
local world = {}--地图格子列表
local open = {}--开放列表
local closed = {}--闭合列表
local path = {}--路径列表
local closedIndex = 0--闭合列表的下标
local targetX = 0--目标节点的坐标
local targetY = 0--目标节点的坐标
local maxCheckTime = 100 --最大检索步数
-- local isTargetFound = false -- 是否找到目标

-- 初始化
function M:init(worldMap)
--
world = worldMap
-- worldInit = clone(worldMap)
end

-- 寻路定义
function M:pathfindInit(route, targetX, targetY)
-- world = clone(worldInit)
-- -- 走过的路,设置成不能走
-- for i = 1, #route - 1 do
-- local item = route[i]
-- world[item.indexY][item.indexX] = 0
-- end

open = {}--开放列表
closed = {}--闭合列表
path = {}--路径列表
closedIndex = 0--闭合列表的下标

-- --定义起点信息
self:defineStart(route[#route].indexY, route[#route].indexX)
-- -- 目标点信息
return self:placeTarget(targetY, targetX)
end

--定义起点信息
function M:defineStart(x,y )
--定义起点信息
open[1] = {}
open[1].x = x
open[1].y = y
open[1].parent = 0
open[1].g = 0--从初始节点到当前节点的移动距离
open[1].h = 0--从这个节点到目标节点的预测距离
end

-- 目标点信息
function M:placeTarget(x, y)
-- 记录目标信息
targetX = x
targetY = y

local isTargetFound = false

-- if (myX < maxX-1) and (myX > 1) and (myY < maxY-1) and (myY > 1) then

if world[x][y] == 1 then
local time = 0
repeat
isTargetFound = self:findPath()
time = time + 1
until (isTargetFound or time >= maxCheckTime)

--获得路线图
if isTargetFound then
self:buildPath()
return path
else
return false
end
else
-- print("目标是个障碍")
return false
end
end

-- 寻找最低F
function M:findLowestF( nodeTable )
--从开放列表里寻找F(参考值)最小的节点
local count = #(nodeTable)
local minF = 1000000
local minFIndex = 0
if count > 0 then
for index = 1,count do
local curF = nodeTable[index].g + nodeTable[index].h
if curF <= minF then
minF = curF
minFIndex = index
end
end
end
return minFIndex
end

-- 过程节点
function M:processNode( newX,newY )
--对节点进行检查
local targetFound = false
local exists = self:alreadyExists(newX,newY)--检测节点是否存在于开放列表

if exists == -1 then
--不在开放列表中
if (newX == targetX) and (newY == targetY) then
--找到目标点
targetFound = true
else
--填入开放列表
self:newOpenEntry(newX,newY)
end
else
--在开放列表中,那么重新定义父节点
--G的计算是将父节点的G值与当前节点到父节点的距离相加,这里只做简单计算
local existingG = open[exists].g
local curValue = 10
local parentG = closed[closedIndex].g

local newG = parentG + curValue
if newG < existingG then
open[exists].parent = closedIndex
end
end

return targetFound
end

-- 找到路径
function M:findPath( )
--针对当前位置进行检索周边处理
local isTargetFound = false

local openIndex = self:findLowestF(open)
if not open[openIndex] then
return isTargetFound
end
closedIndex = #(closed) + 1

closed[closedIndex] = {}
closed[closedIndex].x = open[openIndex].x
closed[closedIndex].y = open[openIndex].y
closed[closedIndex].parent = open[openIndex].parent
closed[closedIndex].g = open[openIndex].g
closed[closedIndex].h = open[openIndex].h

local curX = closed[closedIndex].x
local curY = closed[closedIndex].y

local math_list = {
--遍历周边4个格子,试图寻找目标节点
[1] = {-1,0},
[2] = {0,-1},
[3] = {0,1},
[4] = {1,0},
}

for k,v in pairs(math_list) do
if not isTargetFound then
local myX = curX + v[1]
local myY = curY + v[2]
if (myX > 0) and (myY > 0) and world[myX] and world[myX][myY] and world[myX][myY]==1 then
isTargetFound = self:processNode(myX,myY)
end
else
break
end
end
table.remove(open,openIndex)
-- print("数量", #open)
-- dump(open)
return isTargetFound
end

--检测节点是否存在于开放列表
function M:alreadyExists( newX,newY )
for k,v in pairs(open) do
if v.x == newX and v.y == newY then
return k
end
end
return -1
end

--添加节点到开放列表
function M:newOpenEntry(newX, newY )
local myIndex = #(open) + 1
open[myIndex] = {}
open[myIndex].x = newX
open[myIndex].y = newY
open[myIndex].parent = closedIndex
open[myIndex].g = self:findG(open,myIndex)
open[myIndex].h = self:findH(open[myIndex].x,open[myIndex].y,targetX,targetY)
end

--G的计算是将父节点的G值与当前节点到父节点的距离相加,这里只做简单计算
function M:findG(nodeTable, node )
--从初始节点到当前节点的移动距离
local parentG = closed[nodeTable[node].parent].g
local curValue = 10
return parentG + curValue
end

--计算H值(两坐标之间的 曼哈顿距离 )
function M:findH( curX,curY,tarX,tarY )
return 10*(math.abs(curX-tarX) + math.abs(curY-tarY))
end

--节点检索结束后,构建路径列表
function M:buildPath( )
local count = 1
path[count] = {}
path[count].x = targetX
path[count].y = targetY
count = count + 1
path[count] = {}
local pathIndex = #(closed)
path[count].x = closed[pathIndex].x
path[count].y = closed[pathIndex].y
local newPathIndex = closed[pathIndex].parent
while newPathIndex > 1 do
count = count + 1
path[count] = {}
path[count].x = closed[newPathIndex].x
path[count].y = closed[newPathIndex].y
local oldPathIndex = newPathIndex
newPathIndex = closed[oldPathIndex].parent
-- print(newPathIndex)
end

path = self:reverseTable(path)--得到倒序表需要反序

return path
end

function M:reverseTable( data )
--表反序
local temp = {}
local endCount = #(data)
for index = 1,#(data) do
temp[index] = data[endCount]
endCount = endCount - 1
end
return temp
end

return M
```

  • 我的微信
  • 微信扫一扫
  • weinxin
  • 我的微信公众号
  • 微信扫一扫
  • weinxin
大标
  • 本文由 发表于 2022年3月9日18:45:10
  • 转载请务必保留本文链接:https://www.tanhuibiao.com/script/qita/1322.html
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: