IAPDemo/Libraries/red_utils/RhombusGrid/RUMapRhombusGrid.cpp

//
//  BIMapRhombusGrid.cpp
//  CandyCookie
//
//  Created by 冷晓霆 on 2022/2/22.
//

#include "RUMapRhombusGrid.h"
#include <queue>
#include "RUUtils.h"

NS_RU_BEGIN

#define GRID_POS_IS_VALID(x,y) ((x < _cntGridsInX*2) && (y < _cntGridsInY*2) && (x >= 0) && (y >= 0) && ((abs((int)x)+abs((int)y))%2 == 1))

MapRhombusGrid* MapRhombusGrid::_instance = nullptr;
int MapRhombusGrid::_nextId4Find = 1;


// 表示到达某个网格的花费等信息
struct OpenPoint {
    Vec2 posGrid;
    int cost;   // 耗费值
    int pred;   // 预测值
    int direction;
    OpenPoint* pFather;
    
    OpenPoint() = default;
    OpenPoint(const Vec2& posGrid, const Vec2& endPosGrid, int cost, int direction, OpenPoint* pFather)
    : cost(cost)
    , direction(direction)
    , posGrid(posGrid)
    , pFather(pFather) {
        Vec2 distance = endPosGrid - posGrid;//？
        this->pred = cost;
        //this->pred = max(abs(distance.x) ,abs(distance.y)) * 10  + (abs(distance.x)!=abs(distance.y))*50 + cost;
//        CCLOG("[rhombus] position added: (%d,%d), pred = %d", (int)posGrid.x, (int)posGrid.y, this->pred);
    }
};

struct OpenPointPtrCompare {
    bool operator()(OpenPoint* a, OpenPoint* b) {
        return a->pred > b->pred;
    }
};

MapRhombusGrid::MapRhombusGrid() {
    _occupiedFlag4Grid = nullptr;
    _pGridContainer = nullptr;
    _pDrawNode4Debug = nullptr;
    _cntGridsInX = 1;
    _cntGridsInY = 1;
    _bSupportStraight = false;
}
MapRhombusGrid::~MapRhombusGrid() {
    if (_occupiedFlag4Grid) {
        delete [] _occupiedFlag4Grid;
    }
}
void MapRhombusGrid::initialize(const cocos2d::Size& mapSize, const cocos2d::Size& rhombusSize, bool bSupportStraight) {
    _mapSize = mapSize;
    _rhombusSize = rhombusSize;
    _bSupportStraight = bSupportStraight;
    _cntGridsInX = _mapSize.width / _rhombusSize.width; // 最好考虑一下边界情况
    _cntGridsInY = _mapSize.height / _rhombusSize.height;
    _flagSize = _cntGridsInX*2 * _cntGridsInY*2 / 8;
    _occupiedFlag4Grid = new unsigned char[_flagSize];
    memset(_occupiedFlag4Grid, 0, _flagSize);
    _itemsOverlayInGrid.reserve(_cntGridsInX*_cntGridsInY/2);
    _itemsInGrid.reserve(_cntGridsInX*_cntGridsInY/2);
}

void MapRhombusGrid::addArea(const std::vector<Vec2>& area, int zOrderDefault) {
    RhomArea rhomArea;
    rhomArea.grid.insert(area.begin(), area.end());
    rhomArea.zOrderDefault = zOrderDefault;
    _areas.push_back(rhomArea);
}

void MapRhombusGrid::setDefaultZOrder(int zOrder) {
    _zOrderDefault = zOrder;
}

void MapRhombusGrid::itemRemoved(RhombusableItem* pItem) {
    for (const Vec2& pos : pItem->getPedestalArea()) {
        releaseGrid(pos);
        if (GRID_POS_IS_VALID(pos.x, pos.y)) {
            int idx = getGridIndex(pos);
            auto iter = _itemsInGrid.find(idx);
            if (iter != _itemsInGrid.end()) {
                iter->second.remove(pItem);
            }
            if (pItem->isCrossable()) {
                auto iter = _gridsCrossable.find(idx);
                if (iter != _gridsCrossable.end()) {
                    if (iter->second == 1) {
                        _gridsCrossable.erase(iter);
                    } else {
                        _gridsCrossable.insert({idx, iter->second - 1});
                    }
                }
            }
        }
    }
    for (const Vec2& pos : pItem->getVisibleArea()) {
        if (GRID_POS_IS_VALID(pos.x, pos.y)) {
            int idx = getGridIndex(pos);
            auto iter = _itemsOverlayInGrid.find(idx);
            if (iter != _itemsOverlayInGrid.end()) {
                iter->second.remove(pItem);
            }
            
            iter = _itemsInGrid.find(idx);
            if (iter != _itemsInGrid.end()) {
                iter->second.remove(pItem);
            }
        }
    }
    for (const Vec2& pos : pItem->getWalkableArea()) {
        if (GRID_POS_IS_VALID(pos.x, pos.y)) {
            int idx = getGridIndex(pos);
            auto iter = _itemsInGrid.find(idx);
            if (iter != _itemsInGrid.end()) {
                iter->second.remove(pItem);
            }
        }
    }
}

bool MapRhombusGrid::itemAdded(RhombusableItem* pItem) {
    // 占用每一个底座区域  是否被占用  人物能否走过去 会从这里面取值
    for (const Vec2& pos : pItem->getPedestalArea()) {
//        drawGridWith(pos, Color4F::RED);
        
        if (GRID_POS_IS_VALID(pos.x, pos.y)) {
            int idx = getGridIndex(pos);
            // 如果该位置之前没有被占用，并且当前物件可穿行，则记录一下；否则清除
            if (pItem->isCrossable()) {
                if (!isGridOccupied(pos)) {
                    auto iter = _gridsCrossable.find(idx);
                    if (iter != _gridsCrossable.end()) {
                        _gridsCrossable.insert({idx, iter->second + 1});
                    } else {
                        _gridsCrossable.insert({idx, 1});
                    }
                }
            } else {
                _gridsCrossable.erase(idx);
            }
            occupyGrid(pos);
            auto iter = _itemsInGrid.find(idx);
            if (iter == _itemsInGrid.end()) {
                _itemsInGrid.insert(std::pair<int, std::list<RhombusableItem*>>(idx, std::list<RhombusableItem*>()));
                iter = _itemsInGrid.find(idx);
            }
            iter->second.push_back(pItem);
        }
    }
    // 记录每一个可视区域
    for (const Vec2& pos : pItem->getVisibleArea()) {
//        drawGridWith(pos, Color4F::BLUE);
        
        if (GRID_POS_IS_VALID(pos.x, pos.y)) {
            int idx = getGridIndex(pos);
            {
                auto iter = _itemsOverlayInGrid.find(idx);
                if (iter == _itemsOverlayInGrid.end()) {
                    _itemsOverlayInGrid.insert(std::pair<int, std::list<RhombusableItem*>>(idx, std::list<RhombusableItem*>()));
                    iter = _itemsOverlayInGrid.find(idx);
                }
                iter->second.push_back(pItem);
            }
            {
                // 也需要往基座中添加，但是不占用区域
                auto iter = _itemsInGrid.find(idx);
                if (iter == _itemsInGrid.end()) {
                    _itemsInGrid.insert(std::pair<int, std::list<RhombusableItem*>>(idx, std::list<RhombusableItem*>()));
                    iter = _itemsInGrid.find(idx);
                }
                iter->second.push_back(pItem);
            }
        }
    }
    // 记录可移动区域
    for (const Vec2& pos : pItem->getWalkableArea()) {
//        drawGridWith(pos, Color4F::GREEN);
        
        if (GRID_POS_IS_VALID(pos.x, pos.y)) {
            int idx = getGridIndex(pos);
            {
                // 也需要往基座中添加，但是不占用区域
                auto iter = _itemsInGrid.find(idx);
                if (iter == _itemsInGrid.end()) {
                    _itemsInGrid.insert(std::pair<int, std::list<RhombusableItem*>>(idx, std::list<RhombusableItem*>()));
                    iter = _itemsInGrid.find(idx);
                }
                iter->second.push_back(pItem);
            }
        }
    }
    
    return true;
}

RhombusableItem* MapRhombusGrid::getItem(const std::string& itemName)
{
    for (auto items : _itemsInGrid) {
        for (auto item : items.second)
        {
            if (item->getRhombusableItemName().compare(itemName) == 0)
            {
                return item;
            }
        }
    }
    return nullptr;
}
int MapRhombusGrid::findFlyAPath(const Vec2& fromGrid, const Vec2& toGrid, std::list<RhombusPathNode>& path){
    UtilsLOG("want go to grid: %f, %f", toGrid.x, toGrid.y);
    
    if ((toGrid.x < 0 || toGrid.x > _cntGridsInX*2) || (toGrid.y < 0 || toGrid.y > _cntGridsInY*2)) {
        UtilsLOG("grid is out of sight");
        return 2;
    }
    
    findFlyAPathInternal(fromGrid, toGrid, path);
    
    return (path.size() > 0) ? 0 : 3;
}
// 找到一个最合适的路径，这里使用A*算法，具体的实现可以参见：https://www.runoob.com/data-structures/graph-theory-path.html
// 各种寻路算法的演示：http://qiao.github.io/PathFinding.js/visual/
int MapRhombusGrid::findAPath(const Vec2& fromGrid, const Vec2& toGrid, std::
                              list<RhombusPathNode>& path, bool bIgnoreCharacter, bool bFlashToEndPos) {
    UtilsLOG("want go to grid: %f, %f", toGrid.x, toGrid.y);
    // 如果某个点是被占用的，则返回-1，表示路径不可达
    if (isGridOccupied(toGrid)) {
        UtilsLOG("grid is occupied");
        if(bFlashToEndPos){
            return 4;
        }
        else{
            return 1;
        }
    }
    
    if ((toGrid.x < 0 || toGrid.x > _cntGridsInX*2) || (toGrid.y < 0 || toGrid.y > _cntGridsInY*2)) {
        UtilsLOG("grid is out of sight");
        return 2;
    }
    
    if(bIgnoreCharacter){
        findAPathInternal(fromGrid, toGrid, path, true);
        return (path.size() > 0) ? 0 : 3;
    }
    
    findAPathInternal(fromGrid, toGrid, path, false);
    if (path.size() == 0) {
        // 再次尝试，忽略掉可穿行的物件
        findAPathInternal(fromGrid, toGrid, path, true);
    }
    return (path.size() > 0) ? 0 : 3;
}

/// 实际查找可飞行路线
int MapRhombusGrid::findFlyAPathInternal(const Vec2& fromGrid, const Vec2& toGrid, std::list<RhombusPathNode>& path) {
    static Vec2 adj1[] = {Vec2(-1,1), Vec2(1,1), Vec2(1,-1), Vec2(-1,-1)};      // 斜着的上下左右四个方向
    static Vec2 adj2[] = {Vec2(-2,0), Vec2(2,0), Vec2(0,2), Vec2(0,-2)};        // 正着的上下左右四个方向
    
    std::list<OpenPoint> lstPoints;
    std::priority_queue<OpenPoint*, std::vector<OpenPoint*>, OpenPointPtrCompare> lstOpen;  // 需要处理的节点
    std::map<Vec2, int> dis;
    // 将起始点设置为开始点，以后每次都从优先队列里面取值
    lstPoints.emplace_back(fromGrid, toGrid, 0, -1, nullptr);
    dis[fromGrid] = 0;
    lstOpen.push(&lstPoints.back());
    
    bool bGot = false;
    int cntTried = 10000;
    while (!lstOpen.empty() && cntTried-- > 0) {
        OpenPoint* curPoint = lstOpen.top();
        lstOpen.pop();
      //  cout<<curPoint->posGrid.x<<" "<<curPoint->posGrid.y<<" "<<curPoint->cost<<endl;
        if(dis.find(curPoint->posGrid)!=dis.end() && dis[curPoint->posGrid]< curPoint->cost){
            continue;
        }
//        drawGridWith(curPoint->posGrid, Color4F::GREEN, true);
        if (curPoint->posGrid.equals(toGrid)) {
            bGot = true;
            lstPoints.emplace_back(curPoint->posGrid, toGrid, 0, -1, curPoint);
            lstOpen.push(&lstPoints.back());
            break;  // 得到了一条路径
        }
        
        // 将周围的直接点都放入到优先级队列中
        for (int i=0; i<sizeof(adj1)/sizeof(adj1[0]); i++) {
            Vec2 newPos = curPoint->posGrid + adj1[i];
            // 新增direction cost
            int direction_cost = 0;
            if(curPoint->direction!=-1&&curPoint->direction!=i){
                direction_cost = 50;
            }
            int now_cost = curPoint->cost + 10 + direction_cost;
            if(dis.find(newPos)!=dis.end() && dis[newPos] <= now_cost){
                continue;
            }
//                    cout<<newPos.x<<" "<<newPos.y<<" "<<now_cost;
//                    if(dis.find(newPos)!=dis.end()){
//                        cout<<" "<<dis[newPos]<<endl;
//                    }else cout<<endl;
            // 加入到优先队列里面
            dis[newPos] = now_cost;
            lstPoints.emplace_back(newPos, toGrid, now_cost, i, curPoint);
            lstOpen.push(&lstPoints.back());
        }
        if (_bSupportStraight) {
            // 将周围的跨越点都放入到优先级队列中
            for (int i=0; i<sizeof(adj2)/sizeof(adj2[0]); i++) {
                Vec2 newPos = curPoint->posGrid + adj2[i];
               // if (!isGridOccupied(newPos) && (pointClosed.find(newPos) == pointClosed.end())) {
                    
                if (!isGridOccupied(newPos)) {
                    // FIXME 还需要判断路径上面2个点是否是空的
                    // 检查该位置是否在物件点击区域范围内
                    // 新增代码
                    Vec2 mapPos = getGridCenter(newPos);
                    // 新增direction cost
                    int direction_cost = 0;
                    if(curPoint->direction!=-1&&curPoint->direction!=4+i){
                        direction_cost = 50;
                    }
                    int now_cost = curPoint->cost + 10 + direction_cost;
                    if(dis.find(newPos)!=dis.end() && dis[newPos]<=now_cost){
                        continue;
                    }
//                    cout<<newPos.x<<" "<<newPos.y<<" "<<now_cost;
//                    if(dis.find(newPos)!=dis.end()){
//                        cout<<" "<<dis[newPos]<<endl;
//                    }else cout<<endl;
                    
                    dis[newPos] = now_cost;
                    lstPoints.emplace_back(newPos, toGrid, now_cost, 4+i, curPoint);
                    lstOpen.push(&lstPoints.back());
                  //  pointClosed.insert(newPos);
                }
            }
        }
        
        // 改点已经处理过了
       // pointClosed.insert(curPoint->posGrid);
    }
    
    // 从后往前将节点都放入到路径中
    if (bGot) {
        OpenPoint* curPoint = lstOpen.top();
        while (curPoint != nullptr) {
            RhombusPathNode& front = path.front();
            RhombusPathNode pathNode;
            Vec2 pos = curPoint->posGrid;
            pathNode.posGrid = pos;
            if (!front.posGrid.equals(pathNode.posGrid)) {
                path.push_front(pathNode);
            }
            curPoint = curPoint->pFather;
        }
    } else {
        UtilsLOG("no path found");
        return 1;
    }
    return 0;
}

int MapRhombusGrid::findAPathInternal(const Vec2& fromGrid, const Vec2& toGrid, std::list<RhombusPathNode>& path, bool bIgnoreCrossable) {
    static Vec2 adj1[] = {Vec2(-1,1), Vec2(1,1), Vec2(1,-1), Vec2(-1,-1)};      // 斜着的上下左右四个方向
    static Vec2 adj2[] = {Vec2(-2,0), Vec2(2,0), Vec2(0,2), Vec2(0,-2)};        // 正着的上下左右四个方向
    //std::set<Vec2> pointClosed;  // 处理过的网格位置
    std::list<OpenPoint> lstPoints;
    std::priority_queue<OpenPoint*, std::vector<OpenPoint*>, OpenPointPtrCompare> lstOpen;  // 需要处理的节点
    std::map<Vec2, int> dis;
    // 将起始点设置为开始点，以后每次都从优先队列里面取值
    lstPoints.emplace_back(fromGrid, toGrid, 0, -1, nullptr);
    dis[fromGrid] = 0;
    lstOpen.push(&lstPoints.back());
  //  pointClosed.insert(fromGrid);
    bool bGot = false;
    int cntTried = 10000;
    while (!lstOpen.empty() && cntTried-- > 0) {
        OpenPoint* curPoint = lstOpen.top();
        lstOpen.pop();
      //  cout<<curPoint->posGrid.x<<" "<<curPoint->posGrid.y<<" "<<curPoint->cost<<endl;
        if(dis.find(curPoint->posGrid)!=dis.end() && dis[curPoint->posGrid]< curPoint->cost){
            continue;
        }
//        drawGridWith(curPoint->posGrid, Color4F::GREEN, true);
        if (curPoint->posGrid.equals(toGrid)) {
            bGot = true;
            lstPoints.emplace_back(curPoint->posGrid, toGrid, 0, -1, curPoint);
            lstOpen.push(&lstPoints.back());
            break;  // 得到了一条路径
        }
        
        // 将周围的直接点都放入到优先级队列中
        for (int i=0; i<sizeof(adj1)/sizeof(adj1[0]); i++) {
            Vec2 newPos = curPoint->posGrid + adj1[i];
            bool bValid = !isGridOccupied(newPos);
            if (!bValid && bIgnoreCrossable) {
                if (_gridsCrossable.find(getGridIndex(newPos)) != _gridsCrossable.end()) {
                    bValid = true;
                }
            }
            if (bValid) {
                // 新增direction cost
                int direction_cost = 0;
                if(curPoint->direction!=-1&&curPoint->direction!=i){
                    direction_cost = 50;
                }
                int now_cost = curPoint->cost + 10 + direction_cost;
                if(dis.find(newPos)!=dis.end() && dis[newPos] <= now_cost){
                    continue;
                }
//                    cout<<newPos.x<<" "<<newPos.y<<" "<<now_cost;
//                    if(dis.find(newPos)!=dis.end()){
//                        cout<<" "<<dis[newPos]<<endl;
//                    }else cout<<endl;
                // 加入到优先队列里面
                dis[newPos] = now_cost;
                lstPoints.emplace_back(newPos, toGrid, now_cost, i, curPoint);
                lstOpen.push(&lstPoints.back());
              //  pointClosed.insert(newPos);
            }
        }
        if (_bSupportStraight) {
            // 将周围的跨越点都放入到优先级队列中
            for (int i=0; i<sizeof(adj2)/sizeof(adj2[0]); i++) {
                Vec2 newPos = curPoint->posGrid + adj2[i];
               // if (!isGridOccupied(newPos) && (pointClosed.find(newPos) == pointClosed.end())) {
                    
                if (!isGridOccupied(newPos)) {
                    // FIXME 还需要判断路径上面2个点是否是空的
                    // 检查该位置是否在物件点击区域范围内
                    // 新增代码
                    Vec2 mapPos = getGridCenter(newPos);
                    // 新增direction cost
                    int direction_cost = 0;
                    if(curPoint->direction!=-1&&curPoint->direction!=4+i){
                        direction_cost = 50;
                    }
                    int now_cost = curPoint->cost + 10 + direction_cost;
                    if(dis.find(newPos)!=dis.end() && dis[newPos]<=now_cost){
                        continue;
                    }
//                    cout<<newPos.x<<" "<<newPos.y<<" "<<now_cost;
//                    if(dis.find(newPos)!=dis.end()){
//                        cout<<" "<<dis[newPos]<<endl;
//                    }else cout<<endl;
                    
                    dis[newPos] = now_cost;
                    lstPoints.emplace_back(newPos, toGrid, now_cost, 4+i, curPoint);
                    lstOpen.push(&lstPoints.back());
                  //  pointClosed.insert(newPos);
                }
            }
        }
        
        // 改点已经处理过了
       // pointClosed.insert(curPoint->posGrid);
    }
    
    // 从后往前将节点都放入到路径中
    if (bGot) {
        OpenPoint* curPoint = lstOpen.top();
        while (curPoint != nullptr) {
            RhombusPathNode pathNode;
            Vec2 pos = curPoint->posGrid;
            pathNode.posGrid = pos;
            path.push_front(pathNode);
            curPoint = curPoint->pFather;
        }
    } else {
        UtilsLOG("no path found");
        return 1;
    }
    return 0;
}

Vec2 MapRhombusGrid::getGridCenter(const Vec2& gridPos) {
    cocos2d::Vec2 ret = cocos2d::Vec2::ZERO;
    int intX = (int)gridPos.x;
    int intY = (int)gridPos.y;
    // 根据对棱形网格坐标的定义（x，y表示第几列，第几行），intX, intY 必须一个奇数，一个为偶数
    if ((((intX % 2) + (intY % 2)) % 2) != 0) {
        int signBitX = intX == 0 ? 1 : intX / std::abs(intX);
        int signBitY = intY == 0 ? 1 : intY / std::abs(intY);
        if ((intX % 2) != 0) {
            ret = cocos2d::Vec2((std::abs(intX) / 2 + 0.5) * _rhombusSize.width, std::abs(intY) / 2 * _rhombusSize.height);
        } else {
            ret = cocos2d::Vec2(std::abs(intX) / 2 * _rhombusSize.width, (std::abs(intY) / 2 + 0.5) * _rhombusSize.height);
        }
        ret.x *= signBitX;
        ret.y *= signBitY;
    }
    return ret;
}

Vec2 MapRhombusGrid::getGridPosition(const Vec2& pos) {
    // 先定位到由棱形格子一半大小分割的横竖方向的小格子里面：就是棱形网格的中心点和网格线交叉点形成的正规xy坐标系
    // 然后根据该小格子是被菱形格线正向切分还是反向切分判断出该点在切分线的上部还是下部，就可以得到该点的棱形网格的坐标
    static float halfWidth = _rhombusSize.width * 0.5f;
    static float halfHeight = _rhombusSize.height * 0.5f;
    static float aspc = _rhombusSize.height / _rhombusSize.width;

    int y = pos.y / halfHeight;
    int x = pos.x / halfWidth;

    Vec2 refPos = pos - Vec2(x * halfWidth, y * halfHeight);

    if (0 == (x + y) % 2) {
        // 这里面包含了所有的网格线的交汇点
        if(fabs(refPos.x-0.0) > 0.000001 && (refPos.y / refPos.x >= aspc)) {
            x --;
            y ++;
        }
    } else {
        static Vec2 m(halfWidth, 0);
        static Vec2 n(0, halfHeight);
        float cross = (refPos - m).cross(n - refPos);
        if(cross <= 0){
            x --;
        }else{
            y ++;
        }
    }
    return Vec2(x + 1, y);
}

int MapRhombusGrid::getDefaultZOrder(const Vec2& posGrid) {
    for (const RhomArea& area : _areas) {
        if (area.grid.find(posGrid) != area.grid.end()) {
            return area.zOrderDefault;
        }
    }
    return _zOrderDefault;
}

void MapRhombusGrid::setGridObstacle(const Vec2& posGrid){
    occupyGrid(posGrid);
}

int MapRhombusGrid::getGridIndex(const Vec2& posGrid) {
    return posGrid.y * _cntGridsInX * 2.0 + posGrid.x;
}

void MapRhombusGrid::occupyGrid(const Vec2& posGrid) {
//    if (posGrid.x == 94 && posGrid.y == 117) {
//        CCLOG(" ");
//    }
    int idx = getGridIndex(posGrid);
    if (idx > (_flagSize*8)) {
        return;
    }
    
    unsigned char* pGroup = _occupiedFlag4Grid + (idx / 8);
    unsigned char value = *pGroup;
    value = value | ((unsigned char)0x1 << (idx%8));
    *pGroup = value;
}

void MapRhombusGrid::releaseGrid(const Vec2& posGrid) {
    int idx = getGridIndex(posGrid);
    if (idx > (_flagSize*8)) {
        return;
    }
    
    unsigned char* pGroup = _occupiedFlag4Grid + (idx / 8);
    unsigned char value = *pGroup;
    unsigned char tmp = (unsigned char)0x1 << (idx%8);
    value = value & (~tmp);
    *pGroup = value;
}

bool MapRhombusGrid::isGridOccupied(const Vec2& posGrid) {
    if (GRID_POS_IS_VALID(posGrid.x, posGrid.y)) {
        int idx = getGridIndex(posGrid);
        if (idx > (_flagSize*8)) {
            return true;
        }
        
        unsigned char value = _occupiedFlag4Grid[idx/8];
        return (value & (0x1 << (idx%8))) != 0;
    } else {
        return true;
    }
}

int MapRhombusGrid::getCntInOverlay(const Vec2& gridPos) {
    auto iter = _itemsOverlayInGrid.find(getGridIndex(gridPos));
    if (iter == _itemsOverlayInGrid.end()) {
        return 0;
    } else {
        return (int)(iter->second.size());
    }
}

void MapRhombusGrid::findAdjEmptyPoses(RhombusableItem* pItem, const Vec2& centerPos, std::set<Vec2>& found) {
    if (!pItem) {
        return;
    }
    
    static Vec2 adj1[] = {Vec2(-1,1), Vec2(1,1), Vec2(1,-1), Vec2(-1,-1)};      // 斜着的上下左右四个方向
    for (const Vec2& p : pItem->getPedestalArea()) {
        for (Vec2& adj : adj1) {
            Vec2 t = adj + p;
            if (!isGridOccupied(t)) {
                found.insert(t);
            }
        }
    }
    return;
}

void MapRhombusGrid::drawGridNode(const Vec2& gridPos, Color4F color, bool isTemp, float removeNodeDelay) {
    if (!_pGridContainer) {
        return;
    }
    auto pTempDN = DrawNode::create();
    _pGridContainer->addChild(pTempDN);
    pTempDN->setLocalZOrder(100001);
    pTempDN->setPosition(Vec2(0,0));
    
    std::vector<Vec2> points = getGridPointsAt(gridPos);
    pTempDN->drawLine(points[0], points[1], color);
    pTempDN->drawLine(points[1], points[2], color);
    pTempDN->drawLine(points[2], points[3], color);
    pTempDN->drawLine(points[3], points[0], color);
    
    if (isTemp) {
        pTempDN->scheduleOnce([=](float dt) {
            pTempDN->removeFromParent();
        }, removeNodeDelay, "SCH_DRAWNODE_RM");
    }
}

void MapRhombusGrid::refreshDebugGrid(bool isEnable)
{
    _isDebugEnable = isEnable;
    
    if (!_isDebugEnable)
    {
        if (_pDrawNode4Debug)
            _pDrawNode4Debug->clear();
        return;
    }
        
    if (_pDrawNode4Debug == nullptr) {
        _pDrawNode4Debug = DrawNode::create();
        _pGridContainer->addChild(_pDrawNode4Debug);
        _pDrawNode4Debug->setLocalZOrder(100000);
        _pDrawNode4Debug->setPosition(Vec2(0,0));
    } else {
        _pDrawNode4Debug->clear();
    }
    // 对于每一个网格点，绘制四条边
    for (int i=0; i<_cntGridsInX*2; i++) {
        for (int j=0; j<_cntGridsInY*2; j++) {
            // 根据对棱形网格坐标的定义（x，y表示第几列，第几行），intX, intY 必须一个奇数，一个为偶数
            if ((((i%2) + (j%2)) % 2) == 0) {
                continue;
            }
            drawGridWith(Vec2(i, j), Color4F(127, 127, 127, 100));
        }
    }
    
//    for (auto items : _itemsInGrid) {
//        for (auto pItem : items.second) {
//            // 占用每一个底座区域
//            for (const Vec2& pos : pItem->getPedestalArea()) {
//                drawGridWith(pos, Color4F::RED, true);
//            }
//            // 记录每一个可视区域
//            for (const Vec2& pos : pItem->getVisibleArea()) {
//                drawGridWith(pos, Color4F::BLUE, true);
//            }
//        }
//    }
}

void MapRhombusGrid::debugGridAt(Node* pGridContainer) {
    _pGridContainer = pGridContainer;
    if (!_isDebugEnable)
        return;
  
    if (_pDrawNode4Debug == nullptr) {
        _pDrawNode4Debug = DrawNode::create();
        pGridContainer->addChild(_pDrawNode4Debug);
        _pDrawNode4Debug->setLocalZOrder(100000000);
        _pDrawNode4Debug->setPosition(Vec2(0,0));
    }
    // 对于每一个网格点，绘制四条边
    for (int i=0; i<_cntGridsInX*2; i++) {
        for (int j=0; j<_cntGridsInY*2; j++) {
            // 根据对棱形网格坐标的定义（x，y表示第几列，第几行），intX, intY 必须一个奇数，一个为偶数
            if ((((i%2) + (j%2)) % 2) == 0) {
                continue;
            }
            drawGridWith(Vec2(i, j),Color4F::GRAY);
        }
    }
}

void MapRhombusGrid::drawGridWith(const Vec2& gridPos, Color4F color, bool fill) {
    if (!_isDebugEnable)
        return;
    std::vector<Vec2> points = getGridPointsAt(gridPos);
    if (!fill) {
        _pDrawNode4Debug->drawLine(points[0], points[1], color);
        _pDrawNode4Debug->drawLine(points[1], points[2], color);
        _pDrawNode4Debug->drawLine(points[2], points[3], color);
        _pDrawNode4Debug->drawLine(points[3], points[0], color);
    } else {
        Vec2 tmp_points[4]={points[0],points[1],points[2],points[3]};
        _pDrawNode4Debug->drawSolidPoly(tmp_points, 4, color);
    }
}

std::vector<Vec2> MapRhombusGrid::getGridPointsAt(const Vec2& gridPos) {
    std::vector<Vec2> points;
    Vec2 centerPos = getGridCenter(gridPos);
    points.push_back(Vec2(centerPos+Vec2(-_rhombusSize.width/2, 0)));
    points.push_back(Vec2(centerPos+Vec2(0, _rhombusSize.height/2)));
    points.push_back(Vec2(centerPos+Vec2(_rhombusSize.width/2, 0)));
    points.push_back(Vec2(centerPos+Vec2(0, -_rhombusSize.height/2)));
    return points;
}

int MapRhombusGrid::getGridZorder(const Vec2& gridPos, bool& bIsOverlayed, RhombusableItem* pTargetItem, bool bFlyMode) {
    // 往下找3个位置，避免和可能的另外一个人物重叠，留出富余量给可能的另外的角色
    // 包括了人物本身的位置，这样如果该位置被其他物件所遮罩的话，就能正确得到zorder
    static Vec2 downwards[] = {Vec2(0,0), Vec2(0,-2), Vec2(0,-4), Vec2(0,-6)};
    RhombusableItem* pItemWithMinZOrder = nullptr;
    int zOrderMin =  0x7fffffff;
    Vec2 posWithMinZOrder(0,0);
    int defaultZOrder = getDefaultZOrder(gridPos);
    for (int i=0; i<sizeof(downwards)/sizeof(Vec2); i++) {
        // 1: 是碰到被占用的区域返回
        // 2: 是默认越近的zorder应该越小，所以只要找到就返回
        if (isGridOccupied(gridPos + downwards[i])) {
            break;
        }
        auto iter = _itemsOverlayInGrid.find(getGridIndex(gridPos + downwards[i]));
        if (iter != _itemsOverlayInGrid.end()) {
            for (RhombusableItem* pItem : iter->second) {
                if (((pItem != pTargetItem) && (pItem->getCurZOrder() < zOrderMin))) {
                    bool bItemIsOk = true;
                    if (i == 0) {
                        if (!isBehindItem(gridPos, pItem)) {
                            bItemIsOk = false;
                        }
                    }
                    if(pItem->getCurZOrder() < defaultZOrder){
                        bItemIsOk = false;
                    }
                    if (bItemIsOk) {
                        //设置一个最小的zorder
                        zOrderMin = pItem->getCurZOrder();
                        pItemWithMinZOrder = pItem;
                        posWithMinZOrder = gridPos + downwards[i];
                    }
                }
            }
            if (pItemWithMinZOrder) {
                break;
            }
        }
    }
    if (pItemWithMinZOrder != nullptr) {
        bIsOverlayed = true;
        int zOrder = pItemWithMinZOrder->getCurZOrder() - (int)(gridPos.y - posWithMinZOrder.y) - 1;
        if(zOrder < defaultZOrder) zOrder = defaultZOrder; ///家具的zorder比地毯值要大
        if(!bFlyMode) return zOrder;
    }
    
    // 如果没有，则往上找3个位置
    // 要盖住上面的元素
    static Vec2 upwards[] = {Vec2(-1,1), Vec2(1,1), Vec2(0,2), Vec2(-1,3), Vec2(1,3), Vec2(0,4), Vec2(-1,5), Vec2(1,5), Vec2(0,6), Vec2(-1,7), Vec2(1,7), Vec2(0,8)};
    RhombusableItem* pItemWithMaxZOrder = nullptr;
    int zOrderMax = getDefaultZOrder(gridPos);
    Vec2 posWithMaxZOrder(0,0);
    for (int i=0; i<sizeof(upwards)/sizeof(Vec2); i++) {
        auto iter = _itemsInGrid.find(getGridIndex(gridPos + upwards[i]));
        if (iter != _itemsInGrid.end()) {
            for (RhombusableItem* pItem : iter->second) {
                if ((pItem != pTargetItem) && (pItem->getCurZOrder() > zOrderMax)) {
                    bool bItemIsOk = true;
                    if (bItemIsOk) {
                        //设置一个最大的zorder
                        zOrderMax = pItem->getCurZOrder();
                        pItemWithMaxZOrder = pItem;
                        posWithMaxZOrder = gridPos + upwards[i];
                    }
                }
            }
        }
    }
    int zOrder = 0;
    if (pItemWithMaxZOrder != nullptr) {
        ///留50个可移动的空位
        zOrder = pItemWithMaxZOrder->getCurZOrder() + (int)(posWithMaxZOrder.y - gridPos.y) + (BLOCK_GRID_SPACE - 1);
    } else {
        // 默认的zorder, 这个值要保证比解析item时设置的最大的zorder要大
        zOrder = getDefaultZOrder(gridPos) + (BLOCK_GRID_SPACE - 1);
    }
    
    bIsOverlayed = false;
    return zOrder;
}

bool MapRhombusGrid::isBehindItem(const Vec2& posGrid, RhombusableItem* pItem) {
    // 如果该物件有某个底座网格处在posgrid的正前方，则返回true
    for (const auto& p : pItem->getPedestalArea()) {
        if (p.x == posGrid.x && p.y < posGrid.y) {
            return true;
        }
    }
    return false;
}

std::list<std::string> MapRhombusGrid::getItemsInGrid(const Vec2& gridPos) {
    std::list<std::string> items;
    auto iter = _itemsInGrid.find(getGridIndex(gridPos));
    if (iter == _itemsInGrid.end()) {
        return items;
    }
    for (auto& pItem : iter->second) {
        for (auto& p : pItem->getPedestalArea()) {
            if (gridPos.equals(p)) {
                items.push_back(pItem->getRhombusableItemName());
                break;
            }
        }
    }
    
    return items;
}

NS_RU_END