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.basePos[nextType])

    for i = 2, #path1 do
        table.insert(path2, 1, path1[i])
    end

    return path2
end

function AStar:margePath(paths)
    local path = {}
    for i,v in ipairs(paths) do
        for j,k in ipairs(v) do
            if not (i ~= 1 and j == 1) then
                table.insert(path, k)
            end
        end
    end
    return path
end

function AStar:findAround(type, pos, index, dir)
    local x = pos.x
    local y = pos.y
    if dir == 1 then
        x = x - step
    elseif dir == 2 then
        y = y + step
    elseif dir == 3 then
        x = x + step
    elseif dir == 4 then
        y = y - step

    elseif dir == 5 then
        x = x - step
        y = y + step
    elseif dir == 6 then
        x = x - step
        y = y - step
    elseif dir == 7 then
        x = x + step
        y = y + step
    elseif dir == 8 then
        x = x + step
        y = y - step
    end

    if x < 1 or x > max or y < 1 or y > max then
        return
    end

    local nowPos = p(x, y)
    local bool, idx = self:isPosInTb(self.open[type], nowPos)
    if bool then
        local real = self:getReal(nowPos, index)
        if real < self.dots[idx].real then
            self.dots[idx].real = real
            self.dots[idx].pDot = index
        end
        return
    end

    bool, idx = self:isPosInTb(self.close[type], nowPos)
    if bool then
        local real = self:getReal(nowPos, index)
        if real < self.dots[idx].real then
            self.dots[idx].pDot = index
            self.dots[idx].real = real
            self:addPos(type, idx)
        end
        return
    end

    if self.unDots[x] and self.unDots[x][y] then
        return
    end

    if self.checkFunc then
        if self.checkFunc(nowPos, dir) then
            return nowPos
        else
            self:addUnDot(nowPos)
        end
    elseif self.testCheck then
        if self:testCheck(nowPos) then
            return nowPos
        else
            self:addUnDot(nowPos)
        end
    end
end

-----------------cocos test
function AStar:initPos()
    self.config = {}
    self.unDots = {}
    for i = 1, max do
        for j = 1, max do
            if math.random(1, 4) == 1 then
                if not self.config[i] then
                    self.config[i] = {}
                end
                self.config[i][j] = true
            end
        end
    end
    return {p( math.floor(math.random(1, max / step) * step) , math.floor(math.random(1, max / step) * step)), p(math.floor(math.random(1, max / step) * step), math.floor(math.random(1, max / step) * step))}
end

function AStar:testCheck(pos)
    if self.config and self.config[pos.x] and self.config[pos.x][pos.y] then
        return false
    end
    return true
end

function AStar:drawPath(parent, path)
    if isEmptyTable(path) then
        return
    end

    local function isInPath(tb, x, y)
        for i,v in ipairs(tb) do
            if v.x == x and v.y == y then
                return true
            end
        end
    end

    local function isInTb(tb, x, y)
        for i,v in pairs(tb) do
            for j,k in pairs(v) do
                if self.dots[j].pos.x == x and self.dots[j].pos.y == y then
                    return true
                end
            end
        end
    end

    local node = parent:getChildByTag(666)
    if not node then
        node = cc.Node:create()
        node:setPosition(100, 100)
        parent:addChild(node, 1, 666)
    end
    local width = 20

    for x = 1, max do
        for y = 1, max do
            local drawNode = node:getChildByTag(x * max + y)
            if not drawNode then
                drawNode = cc.DrawNode:create()
                drawNode:setPosition(x * width, y * width)
                node:addChild(drawNode, 1, x * max + y)
            end
            drawNode:clear()
            if isInPath(self.basePos, x, y) then
                drawNode:drawSolidRect(cc.p(0, 0), cc.p(width, width), cc.c4f(0, 1, 0, 1))
            elseif isInPath(path, x, y) then
                drawNode:drawSolidRect(cc.p(0, 0), cc.p(width, width), cc.c4f(1, 1, 0, 1))
            elseif not self:testCheck(p(x, y)) then
                drawNode:drawSolidRect(cc.p(0, 0), cc.p(width, width), cc.c4f(0.2, 0.2, 0.2, 1))
            elseif isInTb(self.open, x, y) then
                drawNode:drawSolidRect(cc.p(0, 0), cc.p(width, width), cc.c4f(0.5, 0.7, 0.5, 1))
            elseif isInTb(self.close, x, y) then
                drawNode:drawSolidRect(cc.p(0, 0), cc.p(width, width), cc.c4f(0.5, 0.5, 0.7, 1))
            else
                drawNode:drawSolidRect(cc.p(0, 0), cc.p(width, width), cc.c4f(1, 1, 1, 1))
            end
        end
    end
end

return AStar