local AStar = {}

-- 配置参数，地图大小，方向数量，步长
local max = 20
local dir = 4
local step = 1

local function isEmptyTable(tb)
if not tb or type(tb) ~= "table" then
return true
end
for k, v in pairs(tb) do
return false
end
return true
end

local function p(x, y)
return {x = x, y = y}
end

function AStar:init(poss)
-- 阻挡点缓存，优先判断阻挡点缓存
if not self.unDots then
self.unDots = {}
end

self.dots = {}
self.open = {}
self.close = {}
self.basePos = {}
for i,v in ipairs(poss) do
self.open[i] = {}
self.close[i] = {}
self.basePos[i] = v
end
end

function AStar:addDot(pos, pDot, type, dis)
local real = self:getReal(pos, pDot)
local fore = self:getFore(pos, type, 3, dis)
table.insert(self.dots, {
pos = pos,
pDot = pDot,
real = real,
fore = fore
})
self.open[type][#self.dots] = true
end

function AStar:getReal(pos, pDot)
local real = 0
if pDot then
local x, y = pos.x - self.dots[pDot].pos.x, pos.y - self.dots[pDot].pos.y
real = self.dots[pDot].real + math.sqrt(x * x + y * y)
end
return real
end

--估值，fun = 1，最短; fun = 3, 最长; fun = 2, 中等
function AStar:getFore(pos, type, fun, dis)
local fore = max + max
local realType = type + dis
if realType > #self.basePos then
realType = 1
elseif realType < 0 then
realType = #self.basePos
end
local targetPos = self.basePos[realType]
local x, y = math.abs(pos.x - targetPos.x), math.abs(pos.y - targetPos.y)
if fun == 1 then
fore = math.sqrt(x * x + y * y)
elseif fun == 2 then
if x > y then
fore = math.sqrt(step * step * 2) * y + x - y
else
fore = math.sqrt(step * step * 2) * x + y - x
end
else
fore = x + y
end
return fore
end

function AStar:addPos(type, index)
self.open[type][index] = true
self.close[type][index] = nil
end

function AStar:delPos(type, index)
self.open[type][index] = nil
self.close[type][index] = true
end

function AStar:addUnDot(pos)
if not self.unDots[pos.x] then
self.unDots[pos.x] = {}
end
self.unDots[pos.x][pos.y] = true
end

function AStar:delUnDot(pos)
if self.unDots[pos.x] and self.unDots[pos.x][pos.y] then
self.unDots[pos.x][pos.y] = nil
if isEmptyTable(self.unDots[pos.x]) then
self.unDots[pos.x] = nil
end
end
end

function AStar:getMinDot(type)
local dot, index
for k, _ in pairs(self.open[type]) do
if not dot then
dot = self.dots[k]
index = k
else
if self.dots[k].real + self.dots[k].fore < dot.real + dot.fore then
dot = self.dots[k]
index = k
end
end
end
return dot, index
end

function AStar:isPosInTb(tb, pos)
for k, _ in pairs(tb) do
if self.dots[k].pos.x == pos.x and self.dots[k].pos.y == pos.y then
return true, k
end
end
return false
end

function AStar:pathFind(poss, checkFunc)
if not checkFunc then
poss = self:initPos()
end

self.checkFunc = checkFunc
self:init(poss)

local startTime = os.clock()
local paths = {}
for type = 1, #poss - 1 do
local nextType = type + 1
if nextType > #poss then
nextType = 1
end
self.dots = {}
self.open[type] = {}
self.open[nextType] = {}
self.close[type] = {}
self.close[nextType] = {}

self:addDot(self.basePos[type], nil, type, 1)
self:addDot(self.basePos[nextType], nil, nextType, -1)

local path
while true do
if self:findAroundByTb(type, 1) then
break
end
path = self:checkPath(type, nextType)
if path then
break
end
if self:findAroundByTb(nextType, -1) then
break
end
path = self:checkPath(type, nextType)
if path then
break
end
end
table.insert(paths, path)
end

local path = self:margePath(paths)
print(os.clock() - startTime)
print(isEmptyTable(path))
return path
end

function AStar:findAroundByTb(type, dis)
if not isEmptyTable(self.open[type]) then
local dot, index = self:getMinDot(type)
self:delPos(type, index)
for i = 1, dir do
local pos = self:findAround(type, dot.pos, index, i)
if pos then
self:addDot(pos, index, type, dis)
end
end
else
return true
end
end

function AStar:checkPath(type, nextType)
local a, b
local minReal = max + max
for i,v in pairs(self.open[type]) do
for j,k in pairs(self.open[nextType]) do
if self.dots[i].pos.x == self.dots[j].pos.x and self.dots[i].pos.y == self.dots[j].pos.y then
local doti = self.dots[i]
local dotj = self.dots[j]
local nowReal = doti.real - self.dots[doti.pDot or 1].real + dotj.real - self.dots[dotj.pDot or 1].real
if nowReal < minReal then
minReal = nowReal
a = i
b = j
end
end
end
end
if not (a and b) then
return
end
local path = self:getPath(self.dots[a], self.dots[b], type, nextType)
return path
end

function AStar:getPath(aDot, bDot, type, nextType)
local path1 = {}
while aDot.pDot do
table.insert(path1, aDot.pos)
aDot = self.dots[aDot.pDot]
end
table.insert(path1, self.basePos[type])

local path2 = {}
while bDot.pDot do
table.insert(path2, bDot.pos)
bDot = self.dots[bDot.pDot]
end
table.insert(path2, self.