-- 概念说明：
-- boder = 边界：自身可行走，但是相邻的格子里有至少1个不可行走。state~=0 且state ~=1
-- 空地/纯空地：自身可行走，且相邻所有格子也都可以行走。state=1。  纯空地不等于边界，但二者都可以行走。
-- 墙：自身不可行走就是墙，state=0。

local TablePool = require('Infrast/TablePool')
local LuaShoveManager = {}
local private =
{
    isVersionGreaterThan113100 = GameAppInfo.IsVersionGreaterThan113100(),
}

local table_insert = table.insert
local table_remove = table.remove
local math_modf = math.modf
local math_sqrt = math.sqrt
local math_abs = math.abs
local math_max =math.max
local math_floor=math.floor

local CANOT_MOVE_TEERAIN_HIGHT = -1000000 -- 地图的不可行走位置的高度（毫米）。被boss和空气墙等阻挡后地形高度是不会变的 。采样工具踩不到时的设置的就是 -1000 。

--缓存一些外部的局部变量减少消耗
local tonumberV2=FP.tonumberV2
local newV2=FP.newV2
local tonumberV1=FP.tonumberV1
local newV1=FP.newV1
local Const_Zero=FP.Const.Zero
local releaseV2=FP.releaseV2
local GreaterEquals=FP.V2.GreaterEquals
local LessEquals=FP.V2.LessEquals
local Dot=FP.V2.Dot
local Const_Vector2_One=FP.Const.Vector2_One
local Const_Vector2_Zero= FP.Const.Vector2_Zero
local Normalized=FP.V2.Normalized
local RotateAroundOriginXZ=FP.V2.RotateAroundOriginXZ
local IsPointInPolygon=FP.V2.IsPointInPolygon
local Less=FP.V2.Less
local FP_Math_Abs=FP.Math.Abs
local Const_Half=FP.Const.Half
local Const_Vector2_Half=FP.Const.Vector2_Half
local CharacterType=LuaConst.CharacterType
local LuaConst_SpecialBuffs_IgnoreShoveOthers=LuaConst.SpecialBuffs.IgnoreShoveOthers
local pairs=pairs
local ipairs=ipairs


local Zero = newV2(0,0)
local Right = newV2(1,0)
local Up = newV2(0,1)
local RightDown = Normalized(newV2(1,-1))
local RightUp = Normalized(newV2(1,1))
local Limit = newV1(0.5)
local LimitSqr = newV1(0.25)
local ForceIntensity = newV1(0.004)
local ForceIntensity10 = newV1(0.004):Mul(10)

local LimitForceNotEqPositive = (Right * Limit):Normalized():Mul(ForceIntensity10)
local LimitForceNotEqNegative = (-Right * Limit):Normalized():Mul(ForceIntensity10)
local LimitForceEqPositive = (Right * Limit):Normalized():Mul(ForceIntensity)
local LimitForceEqNegative = (-Right * Limit):Normalized():Mul(ForceIntensity)

local LimitMinRaw = -tonumberV1(Limit)
local LimitMaxRaw = tonumberV1(Limit)
local ForceIntensityRaw = tonumberV1(ForceIntensity)
local ForceIntensity10Raw = tonumberV1(ForceIntensity10)

local _shoveTempV2 = newV2(0, 0)
local _finalPosTempV2 = newV2(0, 0)
local _addPosTempV2 = newV2(0,0)



local XMax = nil
local ZMax = nil
local OffsetX = nil
local OffsetZ = nil
local OffsetXRaw = nil
local OffsetZRaw = nil
local OffsetX_WithHalf = nil
local OffsetZ_WithHalf = nil
local OffsetX_WithHalfRaw = nil
local OffsetZ_WithHalfRaw = nil

local ReservedGridCountX = 512
local ReservedGridCountZ = 512
local ReservedGridCountGeneral = 1024
--values for Orignal State/BorderParam1/BorderParam2
local _mapGridOrignalState = LuaExt.CreateTable(ReservedGridCountX * ReservedGridCountZ, 1)
local _mapGridOrignalBorderParam1 = LuaExt.CreateTable(ReservedGridCountX * ReservedGridCountZ, 1)
local _mapGridOrignalBorderParam2 = LuaExt.CreateTable(ReservedGridCountX * ReservedGridCountZ, 1)
local _mapGridOrignalHeight = LuaExt.CreateTable(ReservedGridCountX * ReservedGridCountZ, 1)
--values for Current State/BorderParam1/BorderParam2
--_mapGridCurrentState是 _mapGridOrignalState、_mapGridPriorityState和_mapGridIsObstruct的融合
local _mapGridCurrentState = LuaExt.CreateTable(ReservedGridCountX * ReservedGridCountZ, 1)
local _mapGridCurrentBorderParam1 = LuaExt.CreateTable(ReservedGridCountX * ReservedGridCountZ, 1)
local _mapGridCurrentBorderParam2 = LuaExt.CreateTable(ReservedGridCountX * ReservedGridCountZ, 1)
local _mapGridCurrentHeight = LuaExt.CreateTable(ReservedGridCountX * ReservedGridCountZ, 1)
--values for Priority State/BorderParam1/BorderParam2
local _mapGridPriority = LuaExt.CreateTable(ReservedGridCountX * ReservedGridCountZ, 1)
local _mapGridPriorityState = LuaExt.CreateTable(ReservedGridCountX * ReservedGridCountZ, 1)
local _mapGridPriorityBorderParam1 = LuaExt.CreateTable(ReservedGridCountX * ReservedGridCountZ, 1)
local _mapGridPriorityBorderParam2 = LuaExt.CreateTable(ReservedGridCountX * ReservedGridCountZ, 1)
--阻挡阵营归属(因为只会有极少数格子才会有阻挡阵营归属，且默认状态下所有格子都没有阻挡阵营归属，所以这里用普通table来储存阻挡阵营归属)
local _mapGridObstructCamp = {} --key为gridIndex，value为一个camp数组，表示这个格子的阻挡阵营归属。如果单位的阵营跟value里的所有camp都不为敌对，则可以通过
--阻挡工会归属(因为只会有极少数格子才会有阻挡工会归属，且默认状态下所有格子都没有阻挡工会归属，所以这里用普通table来储存阻挡工会归属)
local _mapGridObstructGuild = {} --key为gridIndex，value为一个guild数组，表示这个格子的阻挡归属工会id。如果单位的工会跟value里的所有工会都不为敌对，则可以通过

--about 2-4 block each level, 2*40 grid each block
local _mapGridIsObstruct = LuaExt.CreateTable(0, ReservedGridCountGeneral)
--monster with special type like boss or elite, occupy it's current grid as block
local _mapGridNotPassByPriority = LuaExt.CreateTable(0, ReservedGridCountGeneral)
--about 300 grid were occupied each level, 4 entity in each grid
local _mapShoveEntityCalcList = LuaExt.CreateTable(0, ReservedGridCountGeneral)
--average 4 entity each grid when calculate shove force
local _mapShoveEntityListPool = TablePool(
    function(list)
        return list or LuaExt.CreateTable(4, 0)
    end,
    function(list)
        for i = 1, #list do
            list[i] = nil
        end
    end,
    ReservedGridCountGeneral,
    ReservedGridCountGeneral / 2
)

local _obstructTable = {}
local _tempV2 = newV2(0, 0)
--[[
    格子序号转换为坐标
    转换的坐标为格子的中心
    前提是格子长度为1
]]--
function LuaShoveManager.GetPosByGrid(gridX, gridZ)
    --TODO：一致性问题待确认，使用定点数的版本速度有点慢，改用基础数字类型来处理
    return newV2(gridX + OffsetX_WithHalfRaw, gridZ + OffsetZ_WithHalfRaw)
end
--返回值1:是否无阻挡;  返回值2:阻挡位置(如果有阻挡时为非空值,否则为空); 
--stepBackCount:返回值2往回减几步。如果传nil则默认不回减，如果有阻挡的情况下返回值2会是墙里不可行走的位置。如果stepBackCount填1，则会Sub 1次_addPosTempV2，此时返回值2会是墙前的一个可行走位置。
function LuaShoveManager.HasObstacleTowardsPos(startPos,endPos,stepBackCount)
    local canPass = true
    local originX, originZ = LuaShoveManager.ConvertPosToGrid(startPos)
    local finalX, finalZ = LuaShoveManager.ConvertPosToGridRaw(endPos)
    local deltaX = finalX - originX
    local deltaZ = finalZ - originZ

    private.CalculateAddPos(deltaX, deltaZ, _addPosTempV2)
    local tempIntX = originX
    local tempIntZ = originZ
    _finalPosTempV2:Reset(startPos)
    while(tempIntX ~= finalX or tempIntZ ~= finalZ) do
        if private.CheckState(tempIntX, tempIntZ, 0) then
            canPass = false
            break
        end
        _finalPosTempV2:Add(_addPosTempV2)
        tempIntX,tempIntZ = LuaShoveManager.ConvertPosToGridRaw(_finalPosTempV2)
    end
    if canPass then
        return not canPass
    else
        if stepBackCount then
            _addPosTempV2:Mul(stepBackCount)
            _finalPosTempV2:Sub(_addPosTempV2)
        end
        return not canPass, _finalPosTempV2:cloneV2()
    end
end

--将aimPos的副本trim为一个不位于墙里的位置
--这个位置会是最靠近aimPos的不位于墙里的位置(存在最大为_addPosTempV2的误差，不超过1.414m)
--这个位置既不会在实墙里，也不会在优先级墙里
--下面说明中，没有加修饰的“墙”指的是优先级墙+实墙
--※注意:这个方法无法处理多道优先级墙前后排列的情况。当有多道优先级墙、且aimPos在墙里、且墙前的位置有一层优先级墙时，aimPos会被trim为第一层优先级墙前的位置
function LuaShoveManager.TrimAimPosByObstacleAndPriority(entity, aimPos)
    local priority = entity.components.move.ShovePriority
    local hasObstacle, obstaclePos, obstacleType = LuaShoveManager.HasPriorityWallOrObstacleTowardsPos(entity:GetLogicPos(), aimPos, priority, 1)
    local trimmedAimPos
    if hasObstacle then
        if obstacleType == 1 then
            --entity和aimPos之间先有实墙，则直接停在实墙前
            trimmedAimPos = obstaclePos
        else
            --entity和aimPos之间先有优先级墙，则需要分情况判断
            local hasSolidObstacle, solidObstaclePos = LuaShoveManager.HasObstacleTowardsPos(entity:GetLogicPos(), aimPos, 1)
            if hasSolidObstacle then
                --如果之间还有实墙
                local solidObstacleState = LuaShoveManager.GetStateOfPosByPriority(solidObstaclePos, priority)
                if private.StateIsMovable(solidObstacleState) then
                    --如果实墙前的位置不在墙里，则目标位置设为实墙前的位置(这个位置比一开始的优先级墙的位置更远)
                    trimmedAimPos = solidObstaclePos
                else
                   --如果实墙前的位置在墙里，则目标位置设为一开始的优先级墙前的位置
                    trimmedAimPos = obstaclePos
                end
            else
                --如果entity和aimPos之前没有实墙
                local aimState = LuaShoveManager.GetStateOfPosByPriority(aimPos, priority)
                if private.StateIsMovable(aimState) then
                    --如果aimPos没在墙里，则直接可以设为aimPos
                    trimmedAimPos = aimPos:cloneV2()
                else
                    --如果aimPos在墙里(这个else分支只可能是在优先级墙里), 则trim为一开始的优先级墙前的位置
                    trimmedAimPos = obstaclePos
                end
            end
        end
    else
        trimmedAimPos = aimPos
    end
    return trimmedAimPos
end

--返回值1:是否无阻挡;  返回值2:最近的一处阻挡位置(如果有阻挡时为非空值,否则为空);  返回值3：阻挡类型 1=实墙，2=优先级墙
--stepBackCount:返回值2往回减几步。如果传nil则默认不回减，如果有阻挡的情况下返回值2会是墙里不可行走的位置。如果stepBackCount填1，则会Sub 1次_addPosTempV2，此时返回值2会是墙前的一个可行走位置。
function LuaShoveManager.HasPriorityWallOrObstacleTowardsPos(startPos, endPos, priority, stepBackCount)
    local canPass = true
    local wallType
    local originX, originZ = LuaShoveManager.ConvertPosToGrid(startPos)
    local finalX, finalZ = LuaShoveManager.ConvertPosToGridRaw(endPos)
    local deltaX = finalX - originX
    local deltaZ = finalZ - originZ

    private.CalculateAddPos(deltaX, deltaZ, _addPosTempV2)
    local tempIntX = originX
    local tempIntZ = originZ
    _finalPosTempV2:Reset(startPos)

    local wathcer = 0
    while(tempIntX ~= finalX or tempIntZ ~= finalZ) do
        if private.CheckState(tempIntX, tempIntZ, 0) then
            canPass = false
            wallType = 1
            break
        else
            local gridIndex =  tempIntX * ZMax + tempIntZ
            local gridPriority = _mapGridPriority[gridIndex]
            canPass = (not gridPriority) or priority >= gridPriority
            if not canPass then
                wallType = 2
                break
            end
        end
        _finalPosTempV2:Add(_addPosTempV2)
        tempIntX,tempIntZ = LuaShoveManager.ConvertPosToGridRaw(_finalPosTempV2)
        wathcer = wathcer + 1
        if wathcer > 1000 then
            logging.error(LTAG.ERROR, "HYW : 大概是死循环了， @LuaShoveManager.HasPriorityWallOrObstacleTowardsPos  startPos : ", startPos, "  endPos : ", endPos, "  LevelID : ", LevelManager.GetCurLevelID())
            break
        end
    end

    if canPass then
        return not canPass
    else
        if stepBackCount then
            _addPosTempV2:Mul(stepBackCount)
            _finalPosTempV2:Sub(_addPosTempV2)
        end
        return not canPass, _finalPosTempV2:cloneV2(), wallType    --3个返回值 1是否无阻挡 2阻挡位置(1为false时该项为空) 3阻挡类型(1为false时该项为空)
    end

    return not canPass, not canPass and _finalPosTempV2:cloneV2(), not canPass and wallType
end

function LuaShoveManager.InitLevel(shouldResetCSharpCache)
    local xMax, zMax, offsetX, offsetZ = BattleExt.GetCurMapInfo()
    XMax = xMax
    ZMax = zMax
    
    OffsetX = newV1(offsetX)
    OffsetZ = newV1(offsetZ)
    
    OffsetXRaw = tonumberV1(OffsetX)
    OffsetZRaw = tonumberV1(OffsetZ)
    
    OffsetX_WithHalf = OffsetX + Const_Half
    OffsetZ_WithHalf = OffsetZ + Const_Half
    
    OffsetX_WithHalfRaw = tonumberV1(OffsetX_WithHalf)
    OffsetZ_WithHalfRaw = tonumberV1(OffsetZ_WithHalf)

    assert(XMax * ZMax <= ReservedGridCountX * ReservedGridCountZ, 'map grid size is too big')
    if shouldResetCSharpCache then
        BattleExt.FindPathManagerResetPointStateCache()
    end
    --在C#中进行遍历，性能较好
    BattleExt.BatchSetMapGrid(_mapGridOrignalState, _mapGridOrignalBorderParam1, _mapGridOrignalBorderParam2,_mapGridOrignalHeight)
    for x = 0, XMax - 1 do
        for z = 0, ZMax - 1 do
            local gridIndex = x * ZMax + z
            local state = _mapGridOrignalState[gridIndex]
            local borderParam1 = _mapGridOrignalBorderParam1[gridIndex]
            local borderParam2 = _mapGridOrignalBorderParam2[gridIndex]
            local height = _mapGridOrignalHeight[gridIndex]

            _mapGridCurrentState[gridIndex] = state
            _mapGridCurrentBorderParam1[gridIndex] = borderParam1
            _mapGridCurrentBorderParam2[gridIndex] = borderParam2
            _mapGridCurrentHeight[gridIndex] = height
            
            _mapGridPriority[gridIndex] = 0
            _mapGridPriorityState[gridIndex] = state
            _mapGridPriorityBorderParam1[gridIndex] = borderParam1
            _mapGridPriorityBorderParam2[gridIndex] = borderParam2
        end
    end

    _obstructTable = {}
end

function LuaShoveManager.ExitLevel()
    for k in pairs(_mapGridIsObstruct) do
        _mapGridIsObstruct[k] = nil
    end
    for k in pairs(_mapGridNotPassByPriority) do
        _mapGridNotPassByPriority[k] = nil
    end

    for k, list in pairs(_mapShoveEntityCalcList) do
        if list then
            _mapShoveEntityListPool.Recycle(list)
            _mapShoveEntityCalcList[k] = nil
        end
    end
end

function LuaShoveManager.CheatFlattenTerrain()
    for k in pairs(_mapGridOrignalState) do
        _mapGridOrignalState[k] = 1
    end

    for k in pairs(_mapGridCurrentState) do
        _mapGridCurrentState[k] = 1
    end

    for k in pairs(_mapGridPriorityState) do
        _mapGridPriorityState[k] = 1
    end

    for k in pairs(_mapGridIsObstruct) do
        _mapGridIsObstruct[k] = false
    end

    for k in pairs(_mapGridNotPassByPriority) do
        _mapGridNotPassByPriority[k] = false
    end
end

--[[
    注意！会限制在行走面之内！ 如果pos超出行走面，会返回距离pos附近的一个可行走的格子的序号
    坐标转换为格子序号
    左闭右开，如 [0,1）视为序号0
--]]
function LuaShoveManager.ConvertPosToGrid(pos)
    --TODO：一致性问题待确认，使用定点数的版本速度有点慢，改用基础数字类型来处理
    local px, pz = tonumberV2(pos)
    px, pz = px - OffsetXRaw, pz - OffsetZRaw

    if 0 <= px and px <= XMax - 1 then
        px = math_modf(px)
    elseif px < 0 then
        px = 0
    else
        px = XMax - 1
    end

    if 0 <= pz and pz <= ZMax - 1 then
        pz = math_modf(pz)
    elseif pz < 0 then
        pz = 0
    else
        pz = ZMax - 1
    end
    return px, pz
end

--[[
    注意！不会限制在行走面之内！ 如果pos超出行走面，会返回一个超出行走面的格子序号，用这个序号去取数据可能取到空，或者访问越界
    坐标转换为格子序号
    左闭右开，如 [0,1）视为序号0
--]] 
function LuaShoveManager.ConvertPosToGridRaw(pos)
    local px, pz = tonumberV2(pos)
    px, pz = px - OffsetXRaw, pz - OffsetZRaw
    px = math_modf(px)
    pz = math_modf(pz)
    return px, pz
end


function private.GetStateOfGridByPriority(gridIndex,priority)
    local state = -1
    local usePriorityData = false

    state = _mapGridCurrentState[gridIndex]
    --如果_mapGridCurrentState层可通行，才判断是否要用_mapGridPriorityState层的数据，否则以_mapGridCurrentState的数据为准
    if private.StateIsMovable(state) then
        if _mapGridPriority[gridIndex] > priority then
            usePriorityData = true
            state = _mapGridPriorityState[gridIndex]
        end
    end
    return state,usePriorityData
end

--region 边缘检测
--返回值 = 是否在悬崖里
function LuaShoveManager.GetFinalPos(originPos, newPos, priority,canEnterCliff,outFinalPos)
    local originXRaw, originZRaw = LuaShoveManager.ConvertPosToGridRaw(originPos)
    local originGridIndexRaw = originXRaw * ZMax + originZRaw
    local originPriorityStateRaw = _mapGridPriorityState[originGridIndexRaw]
    local finalXRaw, finalZRaw = LuaShoveManager.ConvertPosToGridRaw(newPos)
    local gridIndexRaw = finalXRaw * ZMax + finalZRaw

    if (originPriorityStateRaw == 0 or originPriorityStateRaw == nil) 
            and (_mapGridPriority[originGridIndexRaw] and _mapGridPriority[gridIndexRaw] and _mapGridPriority[originGridIndexRaw] >= _mapGridPriority[gridIndexRaw] and _mapGridPriority[originGridIndexRaw] > priority) 
        then
        --如果卡优先级墙了
        local finalOriginStateRaw = _mapGridOrignalState[gridIndexRaw]
        local isObstruct = _mapGridIsObstruct[gridIndexRaw]
        local isWithinBound = private.IsGridIndexCorrect(finalXRaw, finalZRaw) --2022年10月18日新增，越界检测（因为state是存在1维数组里的，index会有二义性，1个index既可以对应界内的一个点，也可以对应外部的多个点，因此要做越界检测）
        if finalOriginStateRaw ~= nil and finalOriginStateRaw ~= 0 and not isObstruct and isWithinBound then
            if _mapGridPriority[gridIndexRaw] ~= nil  then
                --如果卡在优先级墙里，且目标位置不是实墙，也不是边界，且目标位置不是obstruct，就直接返回newPos
                outFinalPos:Reset(newPos)
                return false
            --else
                --如果不满足条件，则需要下面的详细判定，这里不直接return
            end
        end
    end
    local originBaseStateRaw = _mapGridOrignalState[originGridIndexRaw]
    if originBaseStateRaw == 0 or originBaseStateRaw == nil or originXRaw >= XMax or originZRaw >= ZMax then
        --如果当前就在墙里（非优先级墙），直接返回newPos（相当于单位如果卡墙了，那么他想去哪就去哪）
        outFinalPos:Reset(newPos)
        return false
    end


    local originX, originZ = LuaShoveManager.ConvertPosToGrid(originPos)
    local originGridIndex = originX * ZMax + originZ
    local finalX, finalZ = LuaShoveManager.ConvertPosToGrid(newPos)
    local gridIndex = finalX * ZMax + finalZ
    local originState = private.GetStateOfGridByPriority(originGridIndex,priority)   --当前格子
    
    
    local isInCliff = false
    --state是目标点的state
    local state = private.GetStateOfGridByPriority(gridIndex,priority)
    if canEnterCliff then
        --悬崖情况
        local isNewPosLower = _mapGridCurrentHeight[gridIndex] <= _mapGridCurrentHeight[originX * ZMax + originZ]
        if state == 0 then
            -- state为0，borderParam1为1时，代表悬崖。
            local borderParam1 = _mapGridPriorityBorderParam1[gridIndex]
            if borderParam1 == 1 then
                if isNewPosLower then
                    --如果目标悬崖的高度低于当前位置的高度，可以过去
                    isInCliff = true
                    outFinalPos:Reset(newPos)
                    return isInCliff
                else
                    isInCliff = false
                    outFinalPos:Reset(originPos)
                    return isInCliff
                end
            end
        else
            --如果当前不在不可行走区域（主要是悬崖），且要去的点更低，就去
            if isNewPosLower then
                outFinalPos:Reset(newPos)
                return isInCliff
            end
        end
    end
    -- new 多层互补
    
    
    local deltaX = finalX - originX
    local deltaZ = finalZ - originZ

    if state ~= 0 then
        local canPass = true
        local tempIntX = originX
        local tempIntZ = originZ
        private.CalculateAddPos(deltaX, deltaZ,_addPosTempV2)

        _finalPosTempV2:Reset(originPos)
        while(tempIntX ~= finalX or tempIntZ ~= finalZ) do
            if private.CheckState(tempIntX, tempIntZ, 0) then
                if tempIntX ~= originX or tempIntZ ~= originZ then --new 第一步不跳出     --（以前如果走到阻挡里，第一步的state会是0，直接跳出 ，导致走不出阻挡）
                    canPass = false
                    break
                end
            end
            _finalPosTempV2:Add(_addPosTempV2)
            tempIntX,tempIntZ = LuaShoveManager.ConvertPosToGridRaw(_finalPosTempV2)
        end

        if canPass then
            if state == 1 then --非不可行走格子，非边界格子均可通行
                outFinalPos:Reset(newPos)
                return isInCliff
            elseif private.GetBorderGridCanPass(finalX, finalZ, priority, newPos)  then --边界格子，只有部分区域可通行
                outFinalPos:Reset(newPos)
                return isInCliff
            end
        else
            state = 0
        end

    end

    --得到距离newPos最近的一个边界格子
    if state == 0 or state == 1 then
        if private.IsBorderGrid(originX, originZ, priority) then  --若原坐标在边界格子
            finalX, finalZ = originX, originZ
        else
            --这里的_shoveTempV2只是作为tempV2，并不会影响挤压力的计算，因为挤压力的计算会_shoveTempV2:Reset
            _shoveTempV2:Reset(newPos):Sub(originPos)
            local px, pz = tonumberV2(_shoveTempV2)
            private.CalculateAddPos(px, pz, _addPosTempV2)

            local tempIntX = originX
            local tempIntZ = originZ
            _finalPosTempV2:Reset(originPos)

            --动态设定贴近步长（之前是3步，3步不够，会导致不够贴近newPos）
            local approachCount = math_max(math_abs(deltaX),math_abs(deltaZ))
            local actualApproachCount = 0
            for i = 0, approachCount, 1 do
                actualApproachCount = actualApproachCount + 1
                --自己是边界格子
                if private.IsBorderGrid(tempIntX, tempIntZ, priority) then
                    break
                end

                --前后左右存在边界格子
                if tempIntX + 1 < XMax and private.IsBorderGrid(tempIntX + 1, tempIntZ, priority) then
                    tempIntX = tempIntX + 1
                    break
                end

                if tempIntX - 1 >= 0 and private.IsBorderGrid(tempIntX - 1, tempIntZ, priority) then
                    tempIntX = tempIntX - 1
                    break
                end

                if tempIntZ + 1 < ZMax and private.IsBorderGrid(tempIntX, tempIntZ + 1, priority) then
                    tempIntZ = tempIntZ + 1
                    break
                end

                if tempIntZ - 1 >= 0 and private.IsBorderGrid(tempIntX, tempIntZ - 1, priority) then
                    tempIntZ = tempIntZ - 1
                    break
                end

                _finalPosTempV2:Add(_addPosTempV2)
                tempIntX,tempIntZ = LuaShoveManager.ConvertPosToGrid(_finalPosTempV2)
            end
            
            outFinalPos:Reset(_finalPosTempV2)
            return isInCliff
        end
    end
    newPos = private.GetFinalPosInBorderGrid(finalX, finalZ, priority, newPos, originPos)
    finalX, finalZ = LuaShoveManager.ConvertPosToGrid(newPos)
    if originState ~= 0 and not private.IsMovableGrid(finalX, finalZ, priority) then
        --如果当前不在墙里，newPos在墙里，就不行走，返回originPos
        outFinalPos:Reset(originPos)
        return isInCliff
    else
        outFinalPos:Reset(newPos)
        return isInCliff
    end
    
end

function private.GetStateOfPosByPriority(pos, priority)
    local gridX, gridZ = LuaShoveManager.ConvertPosToGrid(pos)
    return private.GetStateOfGridByPriority(gridX * ZMax + gridZ, priority)
end

function LuaShoveManager.GetStateOfPosByPriority(pos, priority)
    return private.GetStateOfPosByPriority(pos, priority)
end

--[[
    判断该位置在该边界格子里是否可通行
]]--
function private.GetBorderGridCanPass(gridX, gridZ, priority, pos)
    local gridPos = LuaShoveManager.GetPosByGrid(gridX, gridZ)
    local diff = pos - gridPos
    
    local gridIndex = gridX * ZMax + gridZ

    --local usePriorityData = _mapGridPriority[gridIndex] > priority --非多层互补
    local _,usePriorityData = private.GetStateOfGridByPriority(gridIndex,priority)
    usePriorityData = usePriorityData and _mapGridCurrentState[gridIndex] == 1  --边界情况下，只有当current层为空地，才用优先级层的数据，否则以current层为准。不这样的话，会因为优先级层数据不严格导致穿透

    local state, borderParam1, borderParam2
    if usePriorityData then
        state, borderParam1, borderParam2 =
            _mapGridPriorityState[gridIndex], _mapGridPriorityBorderParam1[gridIndex], _mapGridPriorityBorderParam2[gridIndex]
    else
        state, borderParam1, borderParam2 =
            _mapGridCurrentState[gridIndex], _mapGridCurrentBorderParam1[gridIndex], _mapGridCurrentBorderParam2[gridIndex]
    end

    if state == 2 then --斜率一致
        if borderParam1 == 1 then  --水平
            return private.GetCanPass_Right(diff, borderParam2 == 0)
        elseif borderParam1 == 2 then  --竖直
            return private.GetCanPass_Top(diff, borderParam2 == 0)
        elseif borderParam1 == 3 then  --斜下
            return private.GetCanPass_RightDown(diff, borderParam2 == 0)
        elseif borderParam1 == 4 then  --斜上
            return private.GetCanPass_RightUp(diff, borderParam2 == 0)
        end

    elseif state == 3 then --左右斜率不一致
        if borderParam1 == 1 then  --左横 右斜下
            if diff.x <= Const_Zero then
                return private.GetCanPass_Right(diff, borderParam2 == 0)
            else
                return private.GetCanPass_RightDown(diff, borderParam2 == 1)
            end
        elseif borderParam1 == 2 then  --左横 右斜上
            if diff.x <= Const_Zero then
                return private.GetCanPass_Right(diff, borderParam2 == 0)
            else
                return private.GetCanPass_RightUp(diff, borderParam2 == 0)
            end
        elseif borderParam1 == 3 then  --右横 左斜下
            if diff.x >= Const_Zero then
                return private.GetCanPass_Right(diff, borderParam2 == 0)
            else
                return private.GetCanPass_RightUp(diff, borderParam2 == 0)
            end
        elseif borderParam1 == 4 then  --右横 左斜上
            if diff.x >= Const_Zero then
                return private.GetCanPass_Right(diff, borderParam2 == 0)
            else
                return private.GetCanPass_RightDown(diff, borderParam2 == 1)
            end
        elseif borderParam1 == 5 then
            if diff.x <= Const_Zero then
                return private.GetCanPass_RightUp(diff, borderParam2 == 0)
            else
                return private.GetCanPass_RightDown(diff, borderParam2 == 1)
            end
        elseif borderParam1 == 6 then
            if diff.x <= Const_Zero then
                return private.GetCanPass_RightDown(diff, borderParam2 == 1)
            else
                return private.GetCanPass_RightUp(diff, borderParam2 == 0)
            end
        end

    elseif state == 4 then --上下斜率不一致
        if borderParam1 == 1 then  --下竖 上斜左
            if diff.z <= Const_Zero then
                return private.GetCanPass_Top(diff, borderParam2 == 0)
            else
                return private.GetCanPass_RightDown(diff, borderParam2 == 0)
            end
        elseif borderParam1 == 2 then  --下竖 上斜右
            if diff.z <= Const_Zero then
                return private.GetCanPass_Top(diff, borderParam2 == 0)
            else
                return private.GetCanPass_RightUp(diff, borderParam2 == 0)
            end
        elseif borderParam1 == 3 then  --上竖 下斜左
            if diff.z >= Const_Zero then
                return private.GetCanPass_Top(diff, borderParam2 == 0)
            else
                return private.GetCanPass_RightUp(diff, borderParam2 == 0)
            end
        elseif borderParam1 == 4 then  --上竖 下斜右
            if diff.z >= Const_Zero then
                return private.GetCanPass_Top(diff, borderParam2 == 0)
            else
                return private.GetCanPass_RightDown(diff, borderParam2 == 0)
            end
        elseif borderParam1 == 5 then  --上斜左 下斜左
            if diff.z <= Const_Zero then
                return private.GetCanPass_RightUp(diff, borderParam2 == 0)
            else
                return private.GetCanPass_RightDown(diff, borderParam2 == 0)
            end
        elseif borderParam1 == 6 then  --上斜右 下斜右
            if diff.z <= Const_Zero then
                return private.GetCanPass_RightDown(diff, borderParam2 == 0)
            else
                return private.GetCanPass_RightUp(diff, borderParam2 == 0)
            end
        end

    elseif state == 5 then --直角
        if borderParam1 == 1 then  --左下
            return diff.x > Const_Zero and diff.z > Const_Zero
        elseif borderParam1 == 2 then  --右下
            return diff.x < Const_Zero and diff.z > Const_Zero
        elseif borderParam1 == 3 then  --左上
            return diff.x > Const_Zero and diff.z < Const_Zero
        elseif borderParam1 == 4 then  --右上
            return diff.x < Const_Zero and diff.z < Const_Zero
        end
    end

    releaseV2(diff)
    releaseV2(gridPos)

    return true
end

function private.GetCanPass_Right(diff, type)
    if type then  --上半部分可通行
        local _, zPass = GreaterEquals(diff, Const_Vector2_Zero)
        return zPass
    else    --下半部分可通行
        local _, zPass = LessEquals(diff, Const_Vector2_Zero)
        return zPass
    end
end

function private.GetCanPass_Top(diff, type)
    if type then  --左半部分可通行
        local xPass = LessEquals(diff, Const_Vector2_Zero)
        return xPass
    else    --右半部分可通行
        local xPass = GreaterEquals(diff, Const_Vector2_Zero)
        return xPass
    end
end

function private.GetCanPass_RightDown(diff, type)
    if type then  --左下部分可通行
        if diff.x <= Const_Zero and diff.z <= Const_Zero then
            return true
        elseif diff.x >= Const_Zero and diff.z >= Const_Zero then
            return false
        elseif diff.x <= -diff.z then
            return true
        else
            return false
        end
    else    --右上部分可通行
        if diff.x <= Const_Zero and diff.z <= Const_Zero then
            return false
        elseif diff.x >= Const_Zero and diff.z >= Const_Zero then
            return true
        elseif diff.x >= -diff.z then
            return true
        else
            return false
        end
    end
end

function private.GetCanPass_RightUp(diff, type)
    if type then  --左上部分可通行
        return diff.x <= diff.z
    else    --右下部分可通行
        return diff.x >= diff.z
    end
end

--平行于坐标轴的border，储存它们侧滑的方向的符号
local PARALLEL_2_AXIS_BORDER_SLIDE_INFO = {}
PARALLEL_2_AXIS_BORDER_SLIDE_INFO[210] = {-1, 0}
PARALLEL_2_AXIS_BORDER_SLIDE_INFO[211] = {1, 0}
PARALLEL_2_AXIS_BORDER_SLIDE_INFO[220] = {0, -1}
PARALLEL_2_AXIS_BORDER_SLIDE_INFO[221] = {0, 1}
PARALLEL_2_AXIS_BORDER_SLIDE_INFO[310] = {-1, 0}
PARALLEL_2_AXIS_BORDER_SLIDE_INFO[321] = {1, 0}
PARALLEL_2_AXIS_BORDER_SLIDE_INFO[330] = {-1, 0}
PARALLEL_2_AXIS_BORDER_SLIDE_INFO[341] = {1, 0}
PARALLEL_2_AXIS_BORDER_SLIDE_INFO[411] = {0,1}
PARALLEL_2_AXIS_BORDER_SLIDE_INFO[420] = {0, -1}
PARALLEL_2_AXIS_BORDER_SLIDE_INFO[431] = {0, 1}
PARALLEL_2_AXIS_BORDER_SLIDE_INFO[440] = {1, -1}


--获得平行于坐标轴的边界的侧滑方向             想了解什么是平行于坐标轴的边界,可见 http://confluence.taiyouxi.net/pages/viewpage.action?pageId=28480348
--目前增加了一种机制，如果向着平行于坐标轴的边界移动，会做一个侧滑，防止玩家顶着边界位置卡住
function private.GetParallelToAxisBorderSlideInfo(state, borderParam1, borderParam2)
    local key = state * 100 + borderParam1 * 10 + borderParam2
    local info = PARALLEL_2_AXIS_BORDER_SLIDE_INFO[key]
    if info then 
        return true, info[1], info[2]
    end

    return false
end

local MIN_SLIDE_AMOUNT = newV1(0.25)
local SLIDE_ANGLE_MAX = newV1(90 + 15)--大于这个夹角，不走侧滑（小于90°的实际含义是移动方向跟侧滑方向同向, 这里再加一定度数，覆盖一点点不同向的角度，此时比较垂直，也看不出来，能防止接近垂直时（比如91度）时的卡顿）
local SLIDE_ANGLE_MIN = newV1(30)
local MIN_SLIDE_AMOUNT = FP.Math.Abs(FP.Math.Cos(SLIDE_ANGLE_MAX * FP.Const.Deg2Rad))
local _tempV1 = newV1(0)
local _tempV1_2 = newV1(0)
local _tempV1_3 = newV1(0)
--[[
    获得最终位置，限制在该边界格子中
    gridX、gridZ是newPos的格子
]]--
function private.GetFinalPosInBorderGrid(gridX, gridZ, priority, newPos, originPos)
    local gridIndex = gridX * ZMax + gridZ

    --local usePriorityData = _mapGridPriority[gridIndex] > priority --非多层互补
    local _,usePriorityData = private.GetStateOfGridByPriority(gridIndex,priority) --多层互补

    local state, borderParam1, borderParam2 --state是newPos的state
    if usePriorityData then
        state, borderParam1, borderParam2 =
            _mapGridPriorityState[gridIndex], _mapGridPriorityBorderParam1[gridIndex], _mapGridPriorityBorderParam2[gridIndex]
    else
        state, borderParam1, borderParam2 =
            _mapGridCurrentState[gridIndex], _mapGridCurrentBorderParam1[gridIndex], _mapGridCurrentBorderParam2[gridIndex]
    end

    local gridPos = LuaShoveManager.GetPosByGrid(gridX, gridZ)
    local diff = newPos - gridPos
    local dir = Zero
    if state == 2 then --斜率一致
        if borderParam1 == 1 then  --水平
            dir = Right
        elseif borderParam1 == 2 then  --竖直
            dir = Up
        elseif borderParam1 == 3 then  --斜下
            dir = RightDown
        elseif borderParam1 == 4 then  --斜上
            dir = RightUp
        end

    elseif state == 3 then --左右斜率不一致
        if borderParam1 == 1 then  --左横 右斜下
            if borderParam2 == 1 and diff.x >= Const_Zero and diff.z >= Const_Zero and diff.x <= diff.z then
                return gridPos
            elseif diff.x <= Const_Zero then
                dir = Right
            else
                dir = RightDown

            end
        elseif borderParam1 == 2 then  --左横 右斜上
            if borderParam2 == 0 and diff.x >= Const_Zero and diff.z <= Const_Zero and diff.x <= -diff.z then
                return gridPos
            elseif diff.x <= Const_Zero then
                dir = Right
            else
                dir = RightUp
            end
        elseif borderParam1 == 3 then  --右横 左斜下
            if borderParam2 == 1 and diff.x <= Const_Zero and diff.z >= Const_Zero and diff.x >= -diff.z then
                return gridPos
            elseif diff.x >= Const_Zero then
                dir = Right
            else
                dir = RightUp
            end
        elseif borderParam1 == 4 then  --右横 左斜上
            if borderParam2 == 0 and diff.x <= Const_Zero and diff.z <= Const_Zero and diff.x >= diff.z then
                return gridPos
            elseif diff.x >= Const_Zero then
                dir = Right
            else
                dir = RightDown
            end
        elseif borderParam1 == 5 then
            if diff.x <= Const_Zero then
                dir = RightUp
            else
                dir = RightDown
            end
        elseif borderParam1 == 6 then
            if diff.x <= Const_Zero then
                dir = RightDown
            else
                dir = RightUp
            end

        end

    elseif state == 4 then --上下斜率不一致
        if borderParam1 == 1 then  --下竖 上斜左
            if borderParam2 == 0 and diff.x >= Const_Zero and diff.z >= Const_Zero and diff.x >= diff.z then
                return gridPos
            elseif diff.z <= Const_Zero then
                dir = Up
            else
                dir = RightDown
            end
        elseif borderParam1 == 2 then  --下竖 上斜右
            if borderParam2 == 1 and diff.x <= Const_Zero and diff.z >= Const_Zero and diff.x <= -diff.z then
                return gridPos
            elseif diff.z <= Const_Zero then
                dir = Up
            else
                dir = RightUp
            end
        elseif borderParam1 == 3 then  --上竖 下斜左
            if borderParam2 == 0 and diff.x >= Const_Zero and diff.z <= Const_Zero and diff.x >= -diff.z then
                return gridPos
            elseif diff.z >= Const_Zero then
                dir = Up
            else
                dir = RightUp
            end
        elseif borderParam1 == 4 then  --上竖 下斜右
            if borderParam2 == 1 and diff.x <= Const_Zero and diff.z <= Const_Zero and diff.x <= diff.z then
                return gridPos
            elseif diff.z >= Const_Zero then
                dir = Up
            else
                dir = RightDown
            end
        elseif borderParam1 == 5 then  --上斜左 下斜左
            if diff.z <= Const_Zero then
                dir = RightUp
            else
                dir = RightDown
            end
        elseif borderParam1 == 6 then  --上斜右 下斜右
            if diff.z <= Const_Zero then
                dir = RightDown
            else
                dir = RightUp
            end
        end
        
    elseif state == 5 then --直角
        if borderParam1 == 1 then  --左下
            if diff.x < Const_Zero and diff.z < Const_Zero then
                return gridPos
            elseif diff.x < Const_Zero then
                dir = Up
            else
                dir = Right
            end
        elseif borderParam1 == 2 then  --右下
            if diff.x > Const_Zero and diff.z < Const_Zero then
                return gridPos
            elseif diff.x > Const_Zero then
                dir = Up
            else
                dir = Right
            end
        elseif borderParam1 == 3 then  --左上
            if diff.x < Const_Zero and diff.z > Const_Zero then
                return gridPos
            elseif diff.x < Const_Zero then
                dir = Up
            else
                dir = Right
            end
        elseif borderParam1 == 4 then  --右上
            if diff.x > Const_Zero and diff.z > Const_Zero then
                return gridPos
            elseif diff.x > Const_Zero then
                dir = Up
            else
                dir = Right
            end
        end
    end

    local length = Dot(diff, dir)
    _tempV1:Reset(length) --  _tempV1储存最初的长度

    
    local shouldSlide = false
    local isBorderParallelToAxis
    local dirSignX
    local dirSignZ
    if usePriorityData then --usePriorityData为true的含义是，这块地方是怪物提供的阻挡
        --目前增加了一种机制，如果向着平行于坐标轴的边界移动，且这个边界是怪物提供的(usePriorityData为true)，会做一个侧滑，防止玩家顶着怪物跑导致卡住
        isBorderParallelToAxis, dirSignX, dirSignZ = private.GetParallelToAxisBorderSlideInfo(state, borderParam1, borderParam2)
        --如果是平行的怪物阻挡，做一个侧滑，防止堵死在这种阻挡
        if isBorderParallelToAxis then
            local moveDir = newPos - originPos
            local slideDir = newV2(dirSignX, dirSignZ)
            local angle = FP.V2.Angle(slideDir, moveDir)
            --logging.error(LTAG.ERROR, "HYW : angle : ", angle , "  dir : ", dir , "    diff : ", diff)
            if angle < SLIDE_ANGLE_MAX and angle > SLIDE_ANGLE_MIN then
                shouldSlide = true
                if length < Const_Zero then
                    length:Mul(-1)
                end

                if length < MIN_SLIDE_AMOUNT then
                    length = MIN_SLIDE_AMOUNT
                end
            end 
        end
    end
    
    local offset = dir * length
    
    if shouldSlide then
        if offset.x < Const_Zero then
            offset.x:Mul(-1)
        end

        if offset.z < Const_Zero then
            offset.z:Mul(-1)
        end

        offset.x:Mul(dirSignX)
        offset.z:Mul(dirSignZ)
    end
    

    -- local key = state * 100 + borderParam1 * 10 + borderParam2
    -- logging.error(LTAG.ERROR, "HYW :  key : ", key , "        dir : ", dir, "      offset : ", offset)

    
    local finalPos
    if shouldSlide then
        finalPos = originPos + offset
        local slidePosState = private.GetStateOfPosByPriority(finalPos, priority)
        if slidePosState == 0 then
            --如果滑行方向是墙里，就取消滑行，走老的那套规则
            offset:Reset(dir):Mul(_tempV1)
            finalPos = gridPos + offset
        end
    else
        finalPos = gridPos + offset
    end

    
    --限制在当前和相邻的两个格子中
    local gridPosMin = gridPos - Const_Vector2_One
    local gridPosMax = gridPos + Const_Vector2_One
    
    finalPos:Clamp(gridPosMin, gridPosMax)

    releaseV2(gridPosMin)
    releaseV2(gridPosMax)
    releaseV2(offset)
    releaseV2(diff)
    releaseV2(gridPos)

    return finalPos
end

function private.CalculateAddPos(x, z, outAddPos)
    if x == 0 then
        outAddPos:Reset(0, z > 0 and 1 or -1)
    elseif z == 0 then
        outAddPos:Reset(x > 0 and 1 or -1, 0)
    elseif math_abs(x) > math_abs(z) then
        outAddPos:Reset(1, z / x)
        if x <= 0 then
            outAddPos:Negative()
        end
    else
        outAddPos:Reset(x / z, 1)
        if z <= 0 then
            outAddPos:Negative()
        end
    end
end

--[[
    判断是否为边界格子
]]--
function private.IsBorderGrid(gridX, gridZ, priority)
    -- new↓  _mapGridPriorityState、_mapGridCurrentState只要有1层是border，那么就是border。（同时判断两层）
    local result = false
    local gridIndex = gridX * ZMax + gridZ
    local usePriorityData = _mapGridPriority[gridIndex] > priority
    if usePriorityData then
        result = private.StateIsBorder(_mapGridPriorityState[gridIndex])
    end
    result = result or private.StateIsBorder(_mapGridCurrentState[gridIndex]) --此处可能得换成 _mapGridOrignalState, 目前没bug，先不改了
    return result
    -- new↑
end

--对外接口，返回pos
function LuaShoveManager.IsMovablePos(pos)
    local gridX, gridZ = LuaShoveManager.ConvertPosToGrid(pos)
    return private.IsMovableGrid(gridX, gridZ, 9999999)
end

--是否是空地或border
function private.IsMovableGrid(gridX, gridZ, priority)
    local result = true
    local gridIndex = gridX * ZMax + gridZ
    local usePriorityData = _mapGridPriority[gridIndex] > priority
    if usePriorityData then
        result = private.StateIsMovable(_mapGridPriorityState[gridIndex])
    end
    result = result and private.StateIsMovable(_mapGridCurrentState[gridIndex]) --此处可能得换成 _mapGridOrignalState, 目前没bug，先不改了
    return result
end

--返回给定state是否是边界。    边界：自身可行走，但是相邻的格子里有至少1个不可行走。
function private.StateIsBorder(state)
    return state ~= 0 and state ~= 1
end

--返回是否是纯空地, 纯空地不包括边界。    纯空地：本身可行走，且相邻所有格子也都可以行走。   可行走：空地或者边界。    边界：自身可行走，但是相邻的格子里有至少1个不可行走。
function private.StateIsMovableAndNotBorder(state)
    return state == 1
end

--可行走：纯空地或者边界。   边界：自身可行走，但是相邻的格子里有至少1个不可行走。
function private.StateIsMovable(state)
    return state ~= 0
end

--[[
    判断是否可出生在这个格子上 - 地形行走面外不行、空气墙内不行 ；怪物身体内可以
]]--
function private.CanBornIn(x, z)
    local gridIndex = x * ZMax + z
    local state = _mapGridCurrentState[gridIndex]
    local isObstruct = _mapGridIsObstruct[gridIndex]
    return not (state == 0 or isObstruct)
end

--[[
    判断是否可通行
]]--
function private.CanPass(x, z)
    local gridIndex = x * ZMax + z
    local state = _mapGridCurrentState[gridIndex]
    local isObstruct = _mapGridIsObstruct[gridIndex]
    local notPassByPriority = _mapGridNotPassByPriority[gridIndex]
    return not (state == 0 or isObstruct or notPassByPriority)
end

--[[
    检查格子当前状态
]]--
function private.CheckState(gx, gz, state)
    --new↓ 2022年8月15日新增，如果越界则直接认为格子是墙，否则可能访问到_mapGridCurrentState的过期缓存，导致错误
    --（_mapGridCurrentState里的数据只有当前地图的有效区域才会被设置，越界的地方的数据会延续上一张地图的缓存）
    if gx >= XMax or gz >= ZMax then
        return state == 0 or state == nil
    end
    --new↑
    local gridIndex = gx * ZMax + gz
    if state == 0 then
        return _mapGridCurrentState[gridIndex] == 0 or _mapGridCurrentState[gridIndex] == nil
    else
        return _mapGridCurrentState[gridIndex] == state
    end
end

--[[
    重新计算边界信息
]]--
function private.SetBorderData(x, z, byPriority)
    local state = 0
    local borderParam1 = 0
    local borderParam2 = 0
    
    if private.CanPass(x,z) then
        local left = x - 1 >= 0 and private.CanPass(x - 1,z)
        local right = x + 1 < XMax and private.CanPass(x + 1,z)
        local bottom = z - 1 >= 0 and private.CanPass(x,z - 1)
        local top = z + 1 < ZMax and private.CanPass(x,z + 1)

        if not (left and right and bottom and top) then   --边界点
            local bottomLeft = x - 1 >= 0 and z - 1 >= 0 and private.CanPass(x - 1, z - 1)
            local bottomRight = x + 1 < XMax and z - 1 >= 0 and private.CanPass(x + 1, z - 1)
            local topLeft = x - 1 >= 0 and z + 1 < ZMax and private.CanPass(x - 1, z + 1)
            local topRight = x + 1 < XMax and z + 1 < ZMax and private.CanPass(x + 1, z + 1)

            if left and right and not bottom and not bottomLeft and not bottomRight then
                state = 2  --斜率一致
                borderParam1 = 1   --水平
                borderParam2 = 0   --上半部分可通行
            elseif left and right and not top and not topLeft and not topRight then
                state = 2  --斜率一致
                borderParam1 = 1   --水平
                borderParam2 = 1   --下半部分可通行
            elseif bottom and top and not right and not bottomRight and not topRight then
                state = 2  --斜率一致
                borderParam1 = 2   --竖直
                borderParam2 = 0   --左半部分可通行
            elseif bottom and top and not left and not bottomLeft and not topLeft then
                state = 2  --斜率一致
                borderParam1 = 2   --竖直
                borderParam2 = 1   --右半部分可通行
            elseif bottomRight and topLeft and not right and not top then
                state = 2  --斜率一致
                borderParam1 = 3   --斜下
                borderParam2 = 0   --左下部分可通行
            elseif bottomRight and topLeft and not left and not bottom then
                state = 2  --斜率一致
                borderParam1 = 3   --斜下
                borderParam2 = 1   --右上部分可通行
            elseif bottomLeft and topRight and not right and not bottom then
                state = 2  --斜率一致
                borderParam1 = 4  --斜上
                borderParam2 = 0   --左上部分可通行
            elseif bottomLeft and topRight and not left and not top then
                state = 2  --斜率一致
                borderParam1 = 4   --斜上
                borderParam2 = 1   --右下部分可通行
            elseif left and bottomRight and not bottom and not bottomLeft then
                if right then
                    state = 3  --斜率不一致，左右
                    borderParam1 = 1--左横 右斜下
                    borderParam2 = 0   --上 可通行
                else
                    state = 3  --斜率不一致，左右
                    borderParam1 = 2--左横 右斜上
                    borderParam2 = 0--上 可通行
                end
            elseif left and bottomRight and not right and not top then
                state = 3  --斜率不一致，左右
                borderParam1 = 1--左横 右斜下
                borderParam2 = 1 --下 可通行
            elseif left and topRight and not right and not bottom then
                state = 3  --斜率不一致，左右
                borderParam1 = 2--左横 右斜上
                borderParam2 = 0--上 可通行
            elseif left and topRight and not top and not topLeft then
                state = 3  --斜率不一致，左右
                borderParam1 = 2--左横 右斜上
                borderParam2 = 1--下 可通行
            elseif right and bottomLeft and not bottom and not bottomRight then
                if left then
                    state = 3  --斜率不一致，左右
                    borderParam1 = 3--右横 左斜下
                    borderParam2 = 0--上 可通行
                else
                    state = 3  --斜率不一致，左右
                    borderParam1 = 4--右横 左斜上
                    borderParam2 = 0--上 可通行
                end
            elseif right and bottomLeft and not left and not top then
                state = 3  --斜率不一致，左右
                borderParam1 = 3--右横 左斜下
                borderParam2 = 1--下 可通行
            elseif right and topLeft and not left and not bottom then
                state = 3  --斜率不一致，左右
                borderParam1 = 4--右横 左斜上
                borderParam2 = 0--上 可通行
            elseif right and topLeft and not top and not topRight then
                state = 3  --斜率不一致，左右
                borderParam1 = 4--右横 左斜上
                borderParam2 = 1--下 可通行
            elseif bottom and topLeft and not top and not right then
                state = 4  --斜率不一致，上下
                borderParam1 = 1  --下竖 上斜左
                borderParam2 = 0--左 可通行
            elseif bottom and topLeft and not left and not bottomLeft then
                --HYW : 2021年12月20日 这里之前会导致 not left and not top and not bottomLeft的上方可以行走，所以新增了一个if else，区分了not top的情况
                if top then
                    state = 4  --斜率不一致，上下
                    borderParam1 = 1--下竖 上斜左
                    borderParam2 = 1--右 可通行  --左边的写错了，是右下、上可通行
                else
                    state = 4  --斜率不一致，上下
                    borderParam1 = 2--下竖 上斜右
                    borderParam2 = 1--右 可通行
                end
            elseif bottom and topRight and not right and not bottomRight then
                state = 4  --斜率不一致，上下
                borderParam1 = 2--下竖 上斜右
                borderParam2 = 0--左 可通行
            elseif bottom and topRight and not top and not left then
                state = 4  --斜率不一致，上下
                borderParam1 = 2--下竖 上斜右
                borderParam2 = 1--右 可通行
            elseif top and bottomLeft and not bottom and not right then
                state = 4  --斜率不一致，上下
                borderParam1 = 3--上竖 下斜左
                borderParam2 = 0--左 可通行
            elseif top and bottomLeft and not left and not topLeft then
                if bottom then
                    state = 4  --斜率不一致，上下
                    borderParam1 = 3--上竖 下斜左
                    borderParam2 = 1--右 可通行
                else
                    state = 4  --斜率一致
                    borderParam1 = 4   --斜下
                    borderParam2 = 1   --右上部分可通行
                end
            elseif top and bottomRight and not right and not topRight then
                state = 4  --斜率不一致，上下
                borderParam1 = 4--上竖 下斜右
                borderParam2 = 0--左 可通行
            elseif top and bottomRight and not bottom and not left then
                state = 4  --斜率不一致，上下
                borderParam1 = 4 --上竖 下斜右
                borderParam2 = 1--右 可通行
            elseif bottomLeft and bottomRight and not bottom then
                state = 3  --斜率不一致，左右
                borderParam1 = 5--左斜下 右斜下
                borderParam2 = 0--上 可通行
            elseif bottomLeft and bottomRight and not topLeft and not topRight then
                state = 3  --斜率不一致，左右
                borderParam1 = 5--左斜下 右斜下
                borderParam2 = 1--上 可通行
            elseif topLeft and topRight and not bottomLeft and not bottomRight then
                state = 3  --斜率不一致，左右
                borderParam1 = 6--左斜上 右斜上
                borderParam2 = 0--上 可通行
            elseif topLeft and topRight and not top then
                state = 3  --斜率不一致，左右
                borderParam1 = 6--左斜上 右斜上
                borderParam2 = 1--下 可通行
            elseif bottomLeft and topLeft and not bottomRight and not topRight then
                state = 4  --斜率不一致，上下
                borderParam1 = 5--上斜左 下斜左
                borderParam2 = 0--左 可通行
            elseif bottomLeft and topLeft and not left then
                state = 4  --斜率不一致，上下
                borderParam1 = 5--上斜左 下斜左
                borderParam2 = 1--右 可通行
            elseif bottomRight and topRight and not right then
                state = 4  --斜率不一致，上下
                borderParam1 = 6 --上斜右 下斜右
                borderParam2 = 0--左 可通行
            elseif bottomRight and topRight and not bottomLeft and not topLeft then
                state = 4  --斜率不一致，上下
                borderParam1 = 6 --上斜右 下斜右
                borderParam2 = 1--右 可通行
            elseif right and top then   --左下直角
                state = 5
                borderParam1 = 1
            elseif left and top then   --右下直角
                state = 5
                borderParam1 = 2
            elseif right and bottom then   --左上直角
                state = 5
                borderParam1 = 3
            elseif left and bottom then   --右上直角
                state = 5
                borderParam1 = 4
            else
                state = 0
            end
        else
            state = 1    --可通行，非边界点
        end
    else
        state = 0    --不可通行
    end

    local gridIndex = x * ZMax + z
    if byPriority then
        _mapGridPriorityState[gridIndex] = state
        _mapGridPriorityBorderParam1[gridIndex] = borderParam1
        _mapGridPriorityBorderParam2[gridIndex] = borderParam2
    else
        _mapGridCurrentState[gridIndex] = state
        _mapGridCurrentBorderParam1[gridIndex] = borderParam1
        _mapGridCurrentBorderParam2[gridIndex] = borderParam2
    end

    private.ChangeGridInfo(x, z, state, borderParam1, borderParam2)
end

--[[
    还原边界信息
]]--
function private.ResetBorderData(x, z, byPriority)
    local gridIndex = x * ZMax + z

    if byPriority then
        _mapGridPriority[gridIndex] = 0
        _mapGridNotPassByPriority[gridIndex] = nil
    else
        _mapGridCurrentState[gridIndex] = _mapGridOrignalState[gridIndex]
        _mapGridCurrentBorderParam1[gridIndex] = _mapGridOrignalBorderParam1[gridIndex]
        _mapGridCurrentBorderParam2[gridIndex] = _mapGridOrignalBorderParam2[gridIndex]
    end
    if _mapGridCurrentState[gridIndex] and _mapGridCurrentBorderParam1[gridIndex] and _mapGridCurrentBorderParam2[gridIndex] then
        private.ChangeGridInfo(x, z,
            _mapGridCurrentState[gridIndex], _mapGridCurrentBorderParam1[gridIndex], _mapGridCurrentBorderParam2[gridIndex])
    --else
        --正常情况，边界的_mapGridCurrentState[gridIndex]等值会为nil，因为c#初始化的时候是按照c# index来搞的，而lua是lua index，导致边界没被塞值，为nil
    end
end

if private.isVersionGreaterThan113100 then
    private.batchGridInfoChangeBuffer = LuaExt.CreateTable(5 * 20 * 20)
    private.batchGridInfoChangeEnabled = false

    private.ChangeGridInfo = function(x, z, state, param1, param2)
        if private.batchGridInfoChangeEnabled then
            local buffer = private.batchGridInfoChangeBuffer
            local cnt = #buffer
            buffer[cnt + 1] = x
            buffer[cnt + 2] = z
            buffer[cnt + 3] = state
            buffer[cnt + 4] = param1
            buffer[cnt + 5] = param2
        else
            BattleExt.ChangeGridInfo(x, z, state, param1, param2)
        end
    end
else
    private.ChangeGridInfo = BattleExt.ChangeGridInfo
end

function private.BatchChangeGridInfo()
    if private.isVersionGreaterThan113100 then
        private.batchGridInfoChangeEnabled = true
    end
end

function private.ApplyChangeGridInfo()
    if private.isVersionGreaterThan113100 then
        if private.batchGridInfoChangeEnabled then
            local buffer = private.batchGridInfoChangeBuffer
            BattleExt.BatchChangeGridInfo(buffer)
            for k, v in pairs(buffer) do
                buffer[k] = nil
            end
            private.batchGridInfoChangeEnabled = false 
        end
    end
end

--endregion

--region 挤压

--[[
    Entity 和 Entity 之间的挤压
--]]
local function EntityShoveNotNil()
    --每4帧检测一次
    local clientFrame = LogicUpdateManager._clientHandleFrame
    if clientFrame % 4 == 0 then
        for _,entity in pairs(LogicUpdateManager._entityDic) do
            entity.components.move.ShoveForce:Reset()
        end

        private.CalculateResultForce(Const_Vector2_Zero)
        private.CalculateResultForce(Const_Vector2_Half)
        
        for k, list in pairs(_mapShoveEntityCalcList) do
            if list then
                _mapShoveEntityListPool.Recycle(list)
                _mapShoveEntityCalcList[k] = nil
            end
        end
    end
end
LuaShoveManager.EntityShove = EntityShoveNotNil

--region EntityShove的重定向
local function EntityShoveNil()

end
function LuaShoveManager.SetEntityShoveNil()
    LuaShoveManager.EntityShove = EntityShoveNil
end
function LuaShoveManager.SetEntityShoveNotNil()
    LuaShoveManager.EntityShove = EntityShoveNotNil
end
function LuaShoveManager.EntityShoveIsNil()
    return LuaShoveManager.EntityShove == EntityShoveNil
end
--endregion EntityShove的重定向

function private.CalculateResultForce(posOffset)
    for _,entity in pairs(LogicUpdateManager._entityDic) do
        local rad = entity:GetShoveRotate()
       
        if private.MatchState(entity) then
            local CurModelData=entity.components.base.CurModelData
            local sizeX = CurModelData.ShoveDiameterX
            local sizeZ = CurModelData.ShoveDiameterZ
            if rad ~= Const_Zero then
                _shoveTempV2:Reset(entity.components.move.LogicPos):Add(posOffset) --GetRotatedRectAndBoundBox方法需要接收的是LogicPos
                local rotatedRectPoints,minX,maxX,minZ,maxZ = LuaShoveManager.GetRotatedRectAndBoundBox(sizeX,sizeZ,rad,_shoveTempV2,entity.shoveOffsetZ)
                local fpPosX = _tempV1_2
                local fpPosZ = _tempV1_3
                for posZ=minZ,maxZ,1 do
                    for posX=minX,maxX,1 do
                        -- fpPosZ:Reset(posZ) inline for perf
                        -- fpPosX:Reset(posX) inline for perf
                        fpPosZ[1] = posZ * 1000
                        fpPosX[1] = posX * 1000
                        if IsPointInPolygon(fpPosX,fpPosZ,rotatedRectPoints) then
                            _tempV2:Reset(posX, posZ)
                            local gridX, gridZ = LuaShoveManager.ConvertPosToGrid(_tempV2)
                            if private.IsGridIndexCorrect(gridX, gridZ) then
                                private.CalculateForce(entity, gridX, gridZ)
                            end
                        end
                    end
                end
            else
                _shoveTempV2:Reset(entity.components.move.ShovePos):Add(posOffset)--GetRectBySize方法需要接收的是ShovePos
                local originX, originZ = LuaShoveManager.ConvertPosToGrid(_shoveTempV2)
                if sizeX > 1 and sizeZ > 1 then
                    --判断entity的面积内有没有其他单位，并尝试给其他单位施加力
                    local minAddX,maxAddX,minAddZ,maxAddZ = private.GetRectBySize(originX, originZ, sizeX, sizeZ, _shoveTempV2)
                    for addZ = minAddZ, maxAddZ do
                        local pz = originZ + addZ
                        for addX = minAddX, maxAddX do
                            local px = originX + addX
                            if 0 <= px and px < XMax and 0 <= pz and pz < ZMax then
                                private.CalculateForce(entity, px, pz)
                            end
                        end
                    end
                elseif sizeX > 0 and sizeZ > 0 then
                    --如果体积小于1，那么就只计算(originX, originZ)1个点
                    if 0 <= originX and originX < XMax and 0 <= originZ and originZ < ZMax then
                        private.CalculateForce(entity, originX, originZ)
                    end
                end
            end
        end
    end
end

--判断entity是否需要给x,z上的其他entity施加力
function private.CalculateForce(entity, x, z)
    local gridIndex = x * ZMax + z
    local gridEntityList = _mapShoveEntityCalcList[gridIndex]
    if gridEntityList == nil then
        gridEntityList = _mapShoveEntityListPool.TryGet()
        _mapShoveEntityCalcList[gridIndex] = gridEntityList
    end

    if #gridEntityList > 0 then
        local curEntityID = entity._logicInitData.EntityID
        local charaterType = entity._logicInitData.CharacterType
        local curComp_Move = entity.components.move
        local curPriority = curComp_Move.ShovePriority
        
        for _,otherEntity in ipairs(gridEntityList) do
            local otherEntityID = otherEntity._logicInitData.EntityID
            if curEntityID ~= otherEntityID and
                private.MatchMonsterType(charaterType, otherEntity._logicInitData.CharacterType) then
                
                local otherComp_Move = otherEntity.components.move
                local otherPriority = otherComp_Move.ShovePriority

                local forceResult = _shoveTempV2
                if curPriority == otherPriority then
                    private.GetShoveForce_EqualPriority(curEntityID, otherEntityID, curComp_Move, otherComp_Move, forceResult)
                    curComp_Move.ShoveForce:Add(forceResult)
                    otherComp_Move.ShoveForce:Sub(forceResult)
                elseif curPriority > otherPriority then
                    private.GetShoveForce_NotEqualPriority(curEntityID, otherEntityID, curComp_Move, otherComp_Move, forceResult)
                    otherComp_Move.ShoveForce:Sub(forceResult)
                else
                    private.GetShoveForce_NotEqualPriority(curEntityID, otherEntityID, curComp_Move, otherComp_Move, forceResult)
                    curComp_Move.ShoveForce:Add(forceResult)
                end
            end
        end
    end
	table_insert(gridEntityList, entity)
end

function private.GetShoveForce_NotEqualPriority(selfEntityID, otherEntityID, selfMoveComp, otherMoveComp, result)
    result:Reset(selfMoveComp.ShovePos):Sub(otherMoveComp.ShovePos)
    local dx, dz = tonumberV1(result.x), tonumberV1(result.z)
    --检测范围从圆换成了矩形，小区域结果差别不大，减少计算量
    if LimitMinRaw < dx and dx < LimitMaxRaw and LimitMinRaw < dz and dz < LimitMaxRaw then
        if selfEntityID > otherEntityID then
            result:Reset(LimitForceNotEqPositive)
        else
            result:Reset(LimitForceNotEqNegative)
        end
    else
        result:Normalize()
        result:Mul(ForceIntensity10Raw)
    end
end

function private.GetShoveForce_EqualPriority(selfEntityID, otherEntityID, selfMoveComp, otherMoveComp, result)
    result:Reset(selfMoveComp.ShovePos):Sub(otherMoveComp.ShovePos)
    local dx, dz = tonumberV1(result.x), tonumberV1(result.z)
    --检测范围从圆换成了矩形，小区域结果差别不大，减少计算量
    if LimitMinRaw < dx and dx < LimitMaxRaw and LimitMinRaw < dz and dz < LimitMaxRaw then
        if selfEntityID > otherEntityID then
            result:Reset(LimitForceEqPositive)
        else
            result:Reset(LimitForceEqNegative)
        end
    else
        result:Normalize()
        result:Mul(ForceIntensityRaw)
    end
end

function private.MatchState(entity)
    if not entity.components.base.IsActive --未激活
        or not entity.components.attr:IsAlive() then --死亡
        return false
    end
    
    local ignoreShoveOthers = not entity.components.buff or entity.components.buff:GetBuffUpdateData(LuaConst_SpecialBuffs_IgnoreShoveOthers)
    if ignoreShoveOthers then
        return false
    end    
    
    return true
end

function private.MatchMonsterType(self, other)
    if (self ~= CharacterType.Hero and self ~= CharacterType.NPC and self ~= CharacterType.Adjutant)
        or (other ~= CharacterType.Hero and other ~= CharacterType.NPC and other ~= CharacterType.Adjutant) then
        return true
    end
    
    return false
end

--endregion

--region 出生

-- 肉鸽玩法特殊的找出生点模式
function LuaShoveManager.CanBornIn(pos)
    local x, z = LuaShoveManager.ConvertPosToGrid(pos)
    return private.CanBornIn(x, z)
end

function LuaShoveManager.GetFinalInitPos(pos)
    local x, z = LuaShoveManager.ConvertPosToGrid(pos)
    if private.CanBornIn(x, z) then
        return pos:cloneV2()
    else
        local find = false
        local index = 0
        local repeatCount = 0
        while(not find and repeatCount < 20) do
            repeatCount = repeatCount + 1
            index = index + 1
            find, x, z = private.GetBornInGrid(x, z, index)
        end
        return LuaShoveManager.GetPosByGrid(x, z)
    end
end
-- 出生点专用
function private.GetBornInGrid(x, z, index)
    if x - index >= 0 and private.CanBornIn(x - index, z) then
        return true, x - index, z
    end
    
    if x + index < XMax and private.CanBornIn(x + index, z) then
        return true, x + index, z
    end

    if z - index >= 0 and private.CanBornIn(x, z - index) then
        return true, x, z - index
    end

    if z + index < ZMax and private.CanBornIn(x, z + index) then
        return true, x, z + index
    end
    
    return false, x, z
end

--endregion

--region 碰撞优先级

-- --[[
--     因阻挡优先级重新设置可行走状态和边界信息 (这是老版本，仅用于无旋转的正方形。不支持旋转，不支持矩形) (废弃)
-- ]]--
-- function LuaShoveManager.SetGridDataByPriority(size, priority, pos, changeState, setData)
--     if size <= 0 then
--         return
--     end
--     local originX, originZ = LuaShoveManager.ConvertPosToGrid(pos)
--     local minAddX,maxAddX,minAddZ,maxAddZ = private.GetBoxBySize(originX, originZ, size, pos)

--     if changeState then
--         for addZ = minAddZ, maxAddZ, 1 do
--             local z = originZ + addZ
--             for addX = minAddX, maxAddX, 1 do
--                 local x = originX + addX
--                 if private.IsGridIndexCorrect(x, z) then
--                     local gridIndex = x * ZMax + z
--                     if priority > _mapGridPriority[gridIndex] then
--                         _mapGridPriority[gridIndex] = priority
--                         _mapGridNotPassByPriority[gridIndex] = true
--                     end
--                 end
--             end
--         end
--     end

--     if setData then
--         for addZ = minAddZ - 1, maxAddZ + 1, 1 do
--             local z = originZ + addZ
--             for addX = minAddX - 1, maxAddX + 1, 1 do
--                 local x = originX + addX
--                 if private.IsGridIndexCorrect(x, z) then
--                     local gridIndex = x * ZMax + z
--                     if priority >= _mapGridPriority[gridIndex] then
--                         _mapGridPriority[gridIndex] = priority
--                         private.SetBorderData(x,z, true)
--                     end
--                 end
--             end
--         end
--     end
-- end

local _offsetV2 = FP.newV2(0,0)
--sizeX、sizeZ是number
--返回跟坐标轴平行的矩形旋转后的点(绝对坐标值)和包围盒(包围盒是number不是定点数，是绝对坐标值, 为整数，没有误差所以不会引发不一致)
function LuaShoveManager.GetRotatedRectAndBoundBox(sizeX,sizeZ,rad,pos,offsetZ)
    local halfSizeX = sizeX / 2
    local halfSizeZ = sizeZ / 2
    --获得旋转后的点
    local p1 = RotateAroundOriginXZ(halfSizeX,-halfSizeZ,rad)         --此时是相对pos的位置
    local p2 = RotateAroundOriginXZ(halfSizeX,halfSizeZ,rad)          --此时是相对pos的位置
    --旋转两个点后，使用对称能得到其他两个点
    local p3 = newV2(-tonumberV1(p1.x),-tonumberV1(p1.z))
    local p4 = newV2(-tonumberV1(p2.x),-tonumberV1(p2.z))

    local minX = p1.x   --包围盒的minX（包围盒无旋转）
    if p2.x < minX then
        minX = p2.x
    end
    if p3.x < minX then
        minX = p3.x
    end
    if p4.x < minX then
        minX = p4.x
    end
    minX = math_floor(0.5 + tonumberV1(minX) + tonumberV1(pos.x)) --minX是number了

    local maxX = p1.x   --包围盒的maxX（包围盒无旋转）
    if p2.x > maxX then
        maxX = p2.x
    end
    if p3.x > maxX then
        maxX = p3.x
    end
    if p4.x > maxX then
        maxX = p4.x
    end
    maxX = math_floor(0.5 + tonumberV1(maxX) + tonumberV1(pos.x))

    local minZ = p1.z   --包围盒的minZ（包围盒无旋转）
    if p2.z < minZ then
        minZ = p2.z
    end
    if p3.z < minZ then
        minZ = p3.z
    end
    if p4.z < minZ then
        minZ = p4.z
    end
    minZ = math_floor(0.5 + tonumberV1(minZ) + tonumberV1(pos.z))

    local maxZ = p1.z   --包围盒的maxZ（包围盒无旋转）
    if p2.z > maxZ then
        maxZ = p2.z
    end
    if p3.z > maxZ then
        maxZ = p3.z
    end
    if p4.z > maxZ then
        maxZ = p4.z
    end
    maxZ = math_floor(0.5 + tonumberV1(maxZ) + tonumberV1(pos.z))

    p1 = p1:Add(pos)    --加上pos变为绝对位置
    p2 = p2:Add(pos)    --加上pos变为绝对位置
    p3 = p3:Add(pos)    --加上pos变为绝对位置
    p4 = p4:Add(pos)    --加上pos变为绝对位置
    local rotatedRectPoints = {p1,p2,p3,p4}    --旋转后的矩形的4个顶点，是绝对坐标值
    local offset = nil
    --支持z轴方向上的偏移↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
    if offsetZ and offsetZ ~= 0 then
        offset = _offsetV2

        local xPlus = FP.Math.Cos(rad)
        xPlus:Mul(offsetZ)
        local zPlus = FP.Math.Sin(rad)
        zPlus:Mul(offsetZ)
        _offsetV2:Reset(tonumberV1(xPlus), tonumberV1(zPlus))
        
        for i,p in ipairs(rotatedRectPoints) do
            p:Add(_offsetV2)
        end
        _tempV1:Reset(xPlus):Add(minX):Add(0.5)
        minX = math_floor(tonumberV1(_tempV1))
        _tempV1:Reset(xPlus):Add(maxX):Add(0.5)
        maxX = math_floor(tonumberV1(_tempV1))
        _tempV1:Reset(zPlus):Add(minZ):Add(0.5)
        minZ = math_floor(tonumberV1(_tempV1))
        _tempV1:Reset(zPlus):Add(maxZ):Add(0.5)
        maxZ = math_floor(tonumberV1(_tempV1))
    end
    --支持z轴方向上的偏移↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑
    return rotatedRectPoints,minX,maxX,minZ,maxZ,offset
end

--sizeX、sizeZ是number
function LuaShoveManager.SetGridDataByPriorityWithRotate(sizeX,sizeZ,rad,priority,pos,changeState,setData,offsetZ)
    if sizeX <= 0 or sizeZ <= 0 then
        return
    end
    local rotatedRectPoints,minX,maxX,minZ,maxZ,offsetV2 = LuaShoveManager.GetRotatedRectAndBoundBox(sizeX,sizeZ,rad,pos,offsetZ)
    local fpPosX = _tempV1_2
    local fpPosZ = _tempV1_3
    if changeState then
        --遍历包围盒内所有点，如果在旋转后的矩形内，就设置
        for posZ=minZ,maxZ,1 do
            for posX=minX,maxX,1 do
                -- fpPosZ:Reset(posZ) inline for perf
                -- fpPosX:Reset(posX) inline for perf
                fpPosZ[1] = posZ * 1000
                fpPosX[1] = posX * 1000
                if rad == Const_Zero or IsPointInPolygon(fpPosX,fpPosZ,rotatedRectPoints) then
                    _tempV2:Reset(posX, posZ)
                    local gridX, gridZ = LuaShoveManager.ConvertPosToGrid(_tempV2)
                    --if private.IsGridIndexCorrect(gridX, gridZ) then
                    if gridX >= 0 and gridX < XMax and gridZ >= 0 and gridZ < ZMax then
                        local gridIndex = gridX * ZMax + gridZ
                        if priority > _mapGridPriority[gridIndex] then
                            _mapGridPriority[gridIndex] = priority
                            _mapGridNotPassByPriority[gridIndex] = true
                        end
                    end
                end
            end
        end
    end

    if setData then
        private.BatchChangeGridInfo()
        local resetPlus = 1
        for posZ=minZ-resetPlus,maxZ+resetPlus,1 do
            for posX=minX-resetPlus,maxX+resetPlus,1 do
                _tempV2:Reset(posX, posZ)
                local gridX, gridZ = LuaShoveManager.ConvertPosToGrid(_tempV2)
                --if private.IsGridIndexCorrect(gridX, gridZ) then
                if gridX >= 0 and gridX < XMax and gridZ >= 0 and gridZ < ZMax then
                    local gridIndex = gridX * ZMax + gridZ
                    if priority >= _mapGridPriority[gridIndex] then
                        _mapGridPriority[gridIndex] = priority
                        --这个方法是refreshBorder的作用
                        private.SetBorderData(gridX,gridZ, true)
                    end
                end
            end
        end
        private.ApplyChangeGridInfo()
    end

    return offsetV2 --如果有偏移(offsetZ不为空且不为0)，则offset是当前旋转(rad)下的碰撞位置偏移
end


--[[
    因阻挡优先级重新设置可行走状态和边界信息,不支持旋转，性能较好 (仅用于无旋转的矩形)
]]--
function LuaShoveManager.SetGridDataByPriorityNew(sizeX,sizeZ, priority, pos, changeState, setData)
    if sizeX <= 0 or sizeZ <= 0 then
        return
    end
    local originX, originZ = LuaShoveManager.ConvertPosToGrid(pos)
    local minAddX,maxAddX,minAddZ,maxAddZ = private.GetRectBySize(originX, originZ, sizeX,sizeZ, pos)
    if changeState then
        for addZ = minAddZ, maxAddZ, 1 do
            local z = originZ + addZ
            for addX = minAddX, maxAddX, 1 do
                local x = originX + addX
                if private.IsGridIndexCorrect(x, z) then
                    local gridIndex = x * ZMax + z
                    if priority > _mapGridPriority[gridIndex] then
                        _mapGridPriority[gridIndex] = priority
                        _mapGridNotPassByPriority[gridIndex] = true
                    end
                end
            end
        end
    end

    if setData then
        private.BatchChangeGridInfo()
        for addZ = minAddZ - 1, maxAddZ + 1, 1 do
            local z = originZ + addZ
            for addX = minAddX - 1, maxAddX + 1, 1 do
                local x = originX + addX
                if private.IsGridIndexCorrect(x, z) then
                    local gridIndex = x * ZMax + z
                    if priority >= _mapGridPriority[gridIndex] then
                        _mapGridPriority[gridIndex] = priority
                        private.SetBorderData(x,z, true)
                    end
                end
            end
        end
        private.ApplyChangeGridInfo()
    end
end

function LuaShoveManager.SetGridDataByPriorityOfEntity(entity,priority,changeState,setData)
    --新增底层规则：英雄不再可以改变阻挡优先级信息
    if entity:IsHero() then
        return
    end
    if private.MatchState(entity) then
        local sizeX = entity.components.base.CurModelData.ShoveDiameterX
        local sizeZ = entity.components.base.CurModelData.ShoveDiameterZ
        if entity:IsOpenShoveRotate() then
            local offset = LuaShoveManager.SetGridDataByPriorityWithRotate(sizeX,sizeZ,entity:GetShoveRotate(),priority, entity.components.move.LogicPos, changeState, setData, entity.shoveOffsetZ)
            if offset then
                entity.components.move:SetShovePosOffset(offset)
            end
        else
            LuaShoveManager.SetGridDataByPriorityNew(sizeX,sizeZ, priority, entity.components.move.LogicPos, changeState,setData)
        end
    end
end

function LuaShoveManager.ReSetGridDataOfEntity(entity,isCurPos)
    --新增底层规则：英雄不再可以改变阻挡优先级信息
    if entity:IsHero() then
        return
    end
    --清理不用MatchState，必须无条件清理
    local sizeX = entity.components.base.CurModelData.ShoveDiameterX
    local sizeZ = entity.components.base.CurModelData.ShoveDiameterZ
    local comp_Move = entity.components.move
    local pos = isCurPos and comp_Move.LogicPos or comp_Move.LastLogicPos
    if entity:IsOpenShoveRotate() then
        LuaShoveManager.ReSetGridDataByPriorityWithRotate(sizeX,sizeZ,entity:GetShoveRotate(),pos,entity.shoveOffsetZ)
    else
        LuaShoveManager.ReSetGridDataByPriorityNew(sizeX,sizeZ,pos)
    end
end

-- --[[
--     还原可行走状态和边界信息(这是老版本，仅用于无旋转的正方形。不支持旋转，不支持矩形)(废弃)
-- ]]--
-- function LuaShoveManager.ReSetGridDataByPriority(size, pos)
--     if size <= 0 then
--         return
--     end
    
--     local originX, originZ = LuaShoveManager.ConvertPosToGrid(pos)
    
--     local minAddX,maxAddX,minAddZ,maxAddZ = private.GetBoxBySize(originX, originZ, size, pos)
    
--     for addZ = minAddZ - 2, maxAddZ + 2, 1 do
--         local z = originZ + addZ
--         for addX = minAddX - 2, maxAddX + 2, 1 do
--             local x = originX + addX
--             if private.IsGridIndexCorrect(x, z) then
--                 private.ResetBorderData(x, z, true)
--             end
--         end
--     end
-- end

-- --[[
--     还原可行走状态和边界信息,不支持旋转，性能较好 (仅用于无旋转的矩形)
-- ]]--
function LuaShoveManager.ReSetGridDataByPriorityNew(sizeX,sizeZ,pos)
    if sizeX <= 0 or sizeZ <= 0 then
        return
    end
    
    local originX, originZ = LuaShoveManager.ConvertPosToGrid(pos)
    
    local minAddX,maxAddX,minAddZ,maxAddZ = private.GetRectBySize(originX, originZ, sizeX,sizeZ, pos)
    
    private.BatchChangeGridInfo()
    for addZ = minAddZ - 2, maxAddZ + 2, 1 do
        local z = originZ + addZ
        for addX = minAddX - 2, maxAddX + 2, 1 do
            local x = originX + addX
            if private.IsGridIndexCorrect(x, z) then
                private.ResetBorderData(x, z, true)
            end
        end
    end
    private.ApplyChangeGridInfo()
end
-- --[[
--     还原可行走状态和边界信息,支持旋转，性能较差
-- ]]--
function LuaShoveManager.ReSetGridDataByPriorityWithRotate(sizeX,sizeZ,rad,pos,offsetZ)
    if sizeX <= 0 or sizeZ <= 0 then
        return
    end
    local rotatedRectPoints,minX,maxX,minZ,maxZ = LuaShoveManager.GetRotatedRectAndBoundBox(sizeX,sizeZ,rad,pos,offsetZ)
    local resetPlus = 2 + (offsetZ or 0)  --这是个经验值 --实际resetPlus = max(sizeX/2+offsetZ, sizeZ/2+offsetZ) * 2 才100%安全,但是会特别费. (实际可以带入rad来获得真实值)
    -- ±resetPlus才清理得干净
    private.BatchChangeGridInfo()
    for posZ=minZ - resetPlus,maxZ + resetPlus,1 do
        for posX=minX - resetPlus,maxX + resetPlus,1 do
            _tempV2:Reset(posX, posZ)
            local gridX, gridZ = LuaShoveManager.ConvertPosToGrid(_tempV2)
            --if private.IsGridIndexCorrect(gridX, gridZ) then
            if gridX >= 0 and gridX < XMax and gridZ >= 0 and gridZ < ZMax then
                private.ResetBorderData(gridX, gridZ, true)
            end
        end
    end
    private.ApplyChangeGridInfo()
end


function private.GetBoxBySize(x, z, size, pos)
    return private.GetRectBySize(x,z,size,size,pos)
end

function private.GetRectBySize(x,z,sizeX,sizeZ,pos)
    local centerPos = LuaShoveManager.GetPosByGrid(x, z)

    local xLess, zLess = Less(pos, centerPos)
    local addX = xLess and (sizeX) or (sizeX - 1)
    local addZ = zLess and (sizeZ) or (sizeZ - 1)

    local minAddX = -math_modf(addX / 2)
    local maxAddX = sizeX + minAddX - 1
    local minAddZ = -math_modf(addZ / 2)
    local maxAddZ = sizeZ + minAddZ - 1
    
    releaseV2(centerPos)

    return minAddX,maxAddX,minAddZ,maxAddZ
end

--endregion

--region 动态阻挡（非地形阻挡）   包括两种：关卡阻挡（关卡编辑器配置的阻挡）、BattleEffect阻挡（BattleEffect里配置的阻挡）

--[[
    设置阻挡数据
]]--
local _tempV1_SOD = newV1(0) -- SOD 是 SetObstructData 的缩写
function LuaShoveManager.SetObstructData(id, centerPos, dir, length, width)
    if not _obstructTable[id] then
        _obstructTable[id] = { NotPassTable = {}, BorderTable = {} }
    end
    local obstructData = _obstructTable[id]
    
    local centerX,centerZ = LuaShoveManager.ConvertPosToGrid(centerPos)
    local diffPos = LuaShoveManager.GetPosByGrid(centerX, centerZ) - centerPos
    local maxLength = length > width and length or width
    _tempV1_SOD:Reset(maxLength):Mul(1.5):Mul(0.5)
    local dis = math_modf(tonumberV1(_tempV1_SOD)) + 1
    for tempX = -dis, dis, 1 do
        for tempZ = -dis, dis, 1 do
            local gx, gz = centerX + tempX, centerZ + tempZ
            local centerToPos = newV2(tempX,tempZ) + diffPos
            local tempWidth = FP_Math_Abs(Dot(centerToPos, dir) * 2)
            local tempLength = FP_Math_Abs(Dot(centerToPos, newV2(dir.z, -dir.x)) * 2)
            if tempLength <= length and tempWidth <= width and private.IsGridIndexCorrect(gx, gz) then
                table_insert(obstructData.NotPassTable, {x = gx, z = gz})
            end
        end
    end

    for _,data in pairs(obstructData.NotPassTable) do
        _mapGridIsObstruct[data.x * ZMax + data.z] = true
    end

    for tempX = -dis, dis, 1 do
        for tempZ = -dis, dis, 1 do
            local x = centerX + tempX
            local z = centerZ + tempZ
            if x >= 0 and z >= 0 then --HYW 2021年1月18日， 阻挡元素很怪，会在以max(width,length)为边长的正方形里设置数据，因此很容易出地图边界，所以要判断index必须大于0（小于0等价于出边界了，另外大于max其实也是出边界了，但是因为没出错所以暂时没判断）
                if private.CanPass(x,z) then
                    local left = x - 1 >= 0 and private.CanPass(x - 1,z)
                    local right = x + 1 < XMax and private.CanPass(x + 1,z)
                    local bottom = z - 1 >= 0 and private.CanPass(x,z - 1)
                    local top = z + 1 < ZMax and private.CanPass(x,z + 1)
                    if not (left and right and bottom and top) then   --边界点
                        local grid = {x = x, z = z}
                        table_insert(obstructData.BorderTable, grid)
                    end
                end
            end
        end
    end

    for _,data in pairs(obstructData.NotPassTable) do
        _mapGridIsObstruct[data.x * ZMax + data.z] = nil
    end
end

--[[
    开启阻挡
]]--
function LuaShoveManager.OpenObstruct(id)
    local obstructData = _obstructTable[id]
    if not obstructData then
        return
    end

    private.BatchChangeGridInfo()
    for _,data in pairs(obstructData.NotPassTable) do
        if data.x <= XMax and data.z <= ZMax then
            _mapGridIsObstruct[data.x * ZMax + data.z] = true
            private.SetBorderData(data.x, data.z, false)
        end
    end
    
    for _,data in pairs(obstructData.BorderTable) do
        if data.x <= XMax and data.z <= ZMax then
            private.SetBorderData(data.x, data.z, false)
        end
    end
    private.ApplyChangeGridInfo()
end

--[[
    关闭阻挡
]]--
function LuaShoveManager.CloseObstruct(id, clearObstructTable)
    local obstructData = _obstructTable[id]
    if not obstructData then
        return
    end

    private.BatchChangeGridInfo()
    for _,data in pairs(obstructData.NotPassTable) do
        if data.x <= XMax and data.z <= ZMax then
            _mapGridIsObstruct[data.x * ZMax + data.z] = nil
            private.ResetBorderData(data.x, data.z, false)
        end
    end

    for _,data in pairs(obstructData.BorderTable) do
        if data.x <= XMax and data.z <= ZMax then
            private.ResetBorderData(data.x, data.z, false)
        end
    end
    private.ApplyChangeGridInfo()

    if clearObstructTable then
        _obstructTable[id] = nil
    end
end

--[[
    判断是否越界
]]--
function private.IsGridIndexCorrect(x, z)
    return x >= 0 and x < XMax and z >= 0 and z < ZMax
end


--[[
    获取一个点的高度 通过坐标 ，单位：米
    FPPos : 位置
    FPLogicY ：返回的高度 
    isHoldPosY : 当遇到无地形高度时，FPLogicY是否保持传入时的值（即不设置高度）。
]]--
function LuaShoveManager.GetHeightByPos(FPPos,FPLogicY,isHoldPosY)
    local x, z = LuaShoveManager.ConvertPosToGrid(FPPos)
    local gridIndex = x * ZMax + z
    local height = _mapGridCurrentHeight[gridIndex] --这是毫米
    local hasTerrain = height ~= CANOT_MOVE_TEERAIN_HIGHT -- 采样的地形高度是否存在
    if hasTerrain or not isHoldPosY then
        FPLogicY:Rawset(height)
    end
    return hasTerrain
end

--[[
    获取一个离初始点最远的可行走点（45度斜线找）
]]--
function LuaShoveManager.GetFurthestPos(startPos,endPos ,resultV2)

    local endx, endz = LuaShoveManager.ConvertPosToGrid(endPos)
    local startx, startz = LuaShoveManager.ConvertPosToGrid(startPos)

    local resultx = startx
    local resultz = startz


    local dx = endx - startx
    local dz = endz - startz

    local nX = dx >= 0  and  1 or -1
    local nZ = dz >= 0  and  1 or -1

    local maxAbsX = math.abs(dx)
    local maxAbsZ = math.abs(dz)

    local count = math.max( maxAbsX , maxAbsZ) + 1   --这里原来没有 + 1 ,会出现就差1步就找到阻挡的情况，导致返回startPos。 所以这里新增了 + 1 (HYW, 2021年3月17日)

    local gridx = 0
    local gridz = 0    

    local index = 1
    for i= 1 ,count do      
        
        if i > maxAbsX then
            gridx = endx
        else
            gridx = startx + nX *i
        end
        if i > maxAbsZ then
            gridz = endz
        else
            gridz = startz + nZ*i
        end
       
        local gridIndex = gridx * ZMax + gridz
        local state = _mapGridCurrentState[gridIndex]
        local isObstruct = _mapGridIsObstruct[gridIndex]
        if state == 0 or isObstruct then -- 阻挡            
            index = i
            break
        else
            resultx = gridx
            resultz = gridz
        end
    end


    if index == 1 then -- 有时会出误差,所以这个强制设置为初始位置
        resultV2:Reset(startPos)
    else
        resultV2:Reset(resultx + OffsetX_WithHalfRaw, resultz + OffsetZ_WithHalfRaw)
    end
    
end

-- 圆形边缘光栅化方法，返回一个FP数组，(i,i+1)的值表示一个圆上一个点的世界坐标
-- centerX、centerZ是坐标，不是网格坐标
-- https://github.com/Summarraja/CircleRasterization/blob/master/index.js
function LuaShoveManager.GetCircleRimGrids(pos, radius)
    local result = {}
    local centerX,centerZ = LuaShoveManager.ConvertPosToGrid(pos)
    if radius > 0 then
        local x = 0
        local y = radius
        local delta = 1 - radius

        table_insert(result, centerX + x)
        table_insert(result, centerZ + y)
        table_insert(result, centerX + y)
        table_insert(result, centerZ + x)

        table_insert(result, centerX - x)
        table_insert(result, centerZ - y)
        table_insert(result, centerX - y)
        table_insert(result, centerZ - x)

        local wathcer = radius * 4
        while y > x do
            wathcer = wathcer - 1
            delta = delta + x + x
            if delta < 0 then
                delta = delta + 3
            else
                delta = delta - y - y + 5
                y = y -1
            end
            x = x + 1
            table_insert(result, centerX + x)
            table_insert(result, centerZ + y)
            table_insert(result, centerX + y)
            table_insert(result, centerZ + x)

            table_insert(result, centerX + x)
            table_insert(result, centerZ - y)
            table_insert(result, centerX + y)
            table_insert(result, centerZ - x)

            table_insert(result, centerX - x)
            table_insert(result, centerZ + y)
            table_insert(result, centerX - y)
            table_insert(result, centerZ + x)

            table_insert(result, centerX - x)
            table_insert(result, centerZ - y)
            table_insert(result, centerX - y)
            table_insert(result, centerZ - x)
        end

        if wathcer <= 0 then
            logging.error(LTAG.ERROR, "HYW : 循环次数太多了，程序有bug")
        end
    else
        logging.error(LTAG.ERROR, "HYW : radius < 0 Error!   @LuaShoveManager.GetCircleRimGrids")
    end
    
    return result
end

--BattleEffect阻挡接口
function LuaShoveManager.OpenDynamicObstruct(pos, priority, camp)
    local gridX,gridZ = LuaShoveManager.ConvertPosToGrid(pos)
    local gridIndex = gridX * ZMax + gridZ
    --logging.error(LTAG.ERROR, "HYW : gridIndex : ", gridIndex,  gridX, gridZ)
    if priority then
        _mapGridNotPassByPriority[gridIndex] = true
        _mapGridPriority[gridIndex] = priority
    else
        _mapGridIsObstruct[gridIndex] = true
    end
end

-- 对一组点进行 边界修改result数据结构{x,z,x1,z1,x2,z2... }
function LuaShoveManager.SetPosListBorderData(result)
    private.BatchChangeGridInfo()
    local finishDic = {}
    for i=1,#result / 2 do
        local gridX = result[i*2-1]
        local gridZ = result[i*2]
        for posZ=gridZ-1,gridZ+1,1 do
            for posX=gridX-1,gridX+1,1 do
                local gridIndex = posX * ZMax + posZ
                if not finishDic[gridIndex] then
                    finishDic[gridIndex] = true
                    if private.IsGridIndexCorrect(posX, posZ) then
                        private.SetBorderData(posX, posZ, false)
                    end
                end
            end
        end
    end
    private.ApplyChangeGridInfo()
end

--endregion

return LuaShoveManager