一个简易的游戏2d场景管理实现

任务要求

用编程语言实现一个服务器端的游戏2d场景管理模块，场景上包括了地图的信息，以及一些游戏元素，如NPC，树，石头，建筑等静态元素，地图设计尽可能大，场景上至少包含100个活动元素（玩家、NPC等）模拟随机行走（行走方式有：1.单步移动，2.两点寻路），活动元素不能穿越静态元素的位置。 要求使用合理的数据结构及算法实现。
编程要求:

1. 无需图形界面
2. 地图尺寸为10000*10000个基础单位
3. 活动元素随机行走触发随机事件，每秒移动一次
4. 可以使用go/c++语言实现
5. Cpu利用率经可能低
6. 建议开发周期不超过2周

实现

主要思路

1. 使用网格法模拟地图
2. 随机生成10000x10000的地图
3. 地图大，要求CPU利用率低，没做内存要求，所以在合理的情况下尽量空间换时间
4. 使用A Star算法做两点间路径搜索，但是必须做量级的优化
5. 由于是静态地图，把大地图拆分为多个区块，在区块边上计算互通点，互通点描述区块间的连通性，预存区块内互通点间的路径
6. 搜索使用堆和启发函数优化
7. 经过拆分和预处理，每次寻路只需要搜索一次100x100的起始点到互通点到路径、一次100x100的区块间路径、一次100x100的互通点到目标点的路径。
8. 经过优化，搜索区域从10000x10000降至3次100x100的空间。

代码在特殊情况有bug，但是数据庞大而随机没有继续调试，实现了主要功能。

//#define Debug
#include <bits/stdc++.h>
#include <unistd.h>
#include <signal.h>


using namespace std;

#define MAP_NULL 0
#ifdef Debug
const int MAPSIZE = 100;
const int BLOCKSIZE = 10;
#else
const int MAPSIZE = 10000;
const int BLOCKSIZE = 100;  //这里按照均分设计，如果不均分需要改动
#endif
const float EVENTPROBABLITY = 5.0 / MAPSIZE;  //根据地图尺寸计算每点触发事件概率
const int BLOCKNUM = MAPSIZE / BLOCKSIZE;
char MAP[MAPSIZE][MAPSIZE];

struct Point;
struct Block;
struct PathNode;

int calcBlockId(Point a);

Point calcBlockStartPoint(int bid);

Point calcBlockEndPoint(int bid);

PathNode *findBlockPath(Point src, Point dst);

int getMhtDis(Point a, Point b);

int getMhtDis(PathNode *a, PathNode *b);

typedef struct Point
{
    int x = -1;
    int y = -1;
    
    bool isInMap()
    {
        return x >= 0 && x < MAPSIZE && y >= 0 && y < MAPSIZE;
    }
    
    bool operator<(Point a) const
    {
        return x < a.x ? true : ((x == a.x) ? y < a.y : false);
    }
    
    bool operator>(Point a) const
    {
        return x > a.x ? true : ((x == a.x) ? y > a.y : false);
    }
    
    bool operator==(Point a) const { return x == a.x && y == a.y; }    //用于hash碰撞检测
    
    Point getUp() { return {x - 1, y}; }
    
    Point getDown() { return {x + 1, y}; }
    
    Point getLeft() { return {x, y - 1}; }
    
    Point getRight() { return {x, y + 1}; }
    
} Point;


struct PointPairHash
{
    size_t operator()(const pair<Point, Point> &p) const
    {    //assume the int is 32bit
        auto h1 = hash<long long>()((long long) (p.first.x << 31) + p.first.y);
        auto h2 = hash<long long>()((long long) (p.second.x << 31) + p.second.y);
        return h1 ^ h2;
    }
    
};

struct PointHash
{
    size_t operator()(const Point &p) const
    {
        return hash<long long>()((long long) (p.x << 31) + p.y);
    }
};


typedef struct Block
{
    int id;
    vector<Point> up, down, left, right;   //方向上的互通点
    unordered_map<pair<Point, Point>, vector<Point>*, PointPairHash> pathsMap;   //区块内互通点到其它互通点的路径
    unordered_map<Point, vector<Point>*, PointHash> connectedPointList;   //区块内一互通点可到达另一互通点的点对列表
    
    Point getStartPoint()
    {
        return calcBlockStartPoint(id);
    }
    
    Point getEndPoint()
    {
        return calcBlockEndPoint(id);
    }
    
    vector<Point> getAllConnectedPoints()
    {
        vector<Point> v;
        v.insert(v.end(), up.begin(), up.end());
        v.insert(v.end(), right.begin(), right.end());
        v.insert(v.end(), down.begin(), down.end());
        v.insert(v.end(), left.begin(), left.end());
        return v;
    }
} Block;
Block BLOCK[(BLOCKNUM) * (BLOCKNUM)];

typedef enum
{
    STATICNPC = 1, TREE = 2, STONE = 3, BUILDING = 4
} StaticItemType;
const int StaticItemTypeMaxValue = 5; //标记有几种静态元素,此处用于随机元素添加

typedef enum
{
    player = 1, ACTIVITYNPC = 2
} ActivityItemType;
const int ActivityItemTypeMaxValue = 3; //标记有几种动态元素,此处用于随机元素添加

class BoxArea
{
public:
    BoxArea()
    {
    }
    
    BoxArea(Point a, Point b)
    {
        if (a.x > b.x)
            std::swap(a, b);
        if (a.y > b.y)
            std::swap(a.y, b.y);
        L = a;
        R = b;
    }
    
    bool isInmap()
    {
        return L.isInMap() && R.isInMap();
    }
    
    int getLx() { return L.x; }
    
    int getLy() { return L.y; }
    
    int getRx() { return R.x; }
    
    int getRy() { return R.y; }
    
private:
    Point L, R;
};

typedef struct PathNode : Point
{
    int F = 0;
    int G = 0;
    int H = 0;
    PathNode *parent = nullptr;
    
    bool operator<(PathNode *a) const { return F < a->F; }
    
    bool operator>(PathNode *a) const { return F > a->F; }
    bool operator<(Point a) const
    {
        return x < a.x ? true : ((x == a.x) ? y < a.y : false);
    }
    
    bool operator>(Point a) const
    {
        return x > a.x ? true : ((x == a.x) ? y > a.y : false);
    }
    
    void operator=(Point a)
    {
        x = a.x;
        y = a.y;
    }
    
    PathNode(Point a)
    {
        x = a.x;
        y = a.y;
    }
} PathNode;
priority_queue<PathNode *, vector<PathNode *>, greater<PathNode *> > open;
set<pair<int, int> > openSet;
set<pair<int, int> > closed;
vector<PathNode *> FreeList;


void clearOpenQueue()
{
    //        while(open.empty())
    //            open.pop();
    open = priority_queue<PathNode *, vector<PathNode *>, greater<PathNode *> >();
}

int calcG(PathNode p)
{
    if (p.parent == nullptr)
        return 0;
    else
        return p.parent->G + 1;
}

int calcH(PathNode start, PathNode end)
{
    return abs(end.x - start.x) + abs(end.y - start.y);
}

int calcF(PathNode p)
{
    return p.G + p.H;
}

vector<PathNode> getRoundPoints(PathNode *loc) //remember to add it to freelist
{
    vector<PathNode> res;
    PathNode u(loc->getUp());
    PathNode d(loc->getDown());
    PathNode l(loc->getLeft());
    PathNode r(loc->getRight());
    if (u.isInMap())
        res.push_back(u);
    if (d.isInMap())
        res.push_back(d);
    if (l.isInMap())
        res.push_back(l);
    if (r.isInMap())
        res.push_back(r);
    return res;
}

PathNode *findPath(Point src, Point dst, Point start, Point end)    //build path list
{
    PathNode *first = new PathNode(src);
    PathNode *last = new PathNode(dst);
    FreeList.push_back(first);
    FreeList.push_back(last);
    open.push(first);
    openSet.insert(make_pair(first->x, first->y));
    while (!open.empty()) {
        PathNode *cur = open.top();
        //            cout<<cur->x<<','<<cur->y<<endl;
        open.pop();
        closed.insert(make_pair(cur->x, cur->y));
        
        auto roundPoints = getRoundPoints(cur);
        for (auto point:roundPoints) {
            if (MAP[point.x][point.y] != MAP_NULL || point<start || point>end) //有静态元素不能走,超出范围不搜索
                continue;
            if (closed.count(make_pair(point.x, point.y)))   //closed表已有
                continue;
            PathNode *p = new PathNode({point.x, point.y}); //remember to add it to freelist
            FreeList.push_back(p);
            if (!openSet.count(make_pair(p->x, p->y)))   //不在open表
            {
                p->parent = cur;
                p->G = calcG(*p);
                p->H = calcH(*p, *last);
                p->F = calcF(*p);
                
                open.push(p);
                openSet.insert(make_pair(p->x, p->y));
            } else {
                int tmpG = calcG(*p);
                if (tmpG < p->G) {
                    p->parent = cur;
                    p->G = tmpG;
                    p->F = calcF(*p);
                }
            }
            if (p->x == last->x && p->y == last->y) {
                clearOpenQueue();
                openSet.clear();
                closed.clear();
                return p;
            }
        }
    }
    
    clearOpenQueue();
    openSet.clear();
    closed.clear();
    return nullptr;
}

bool getPath(Point src, Point dst, vector<Point> &path)
{
    //ToDo
    int bid1, bid2;
    bid1 = calcBlockId(src);
    bid2 = calcBlockId(dst);
    PathNode *last = nullptr;
    if (bid1 == bid2)
        last = findPath(src, dst, calcBlockStartPoint(bid1), calcBlockEndPoint(bid1));
    else
        last = findPath(src, dst, {0, 0}, {MAPSIZE - 1, MAPSIZE - 1});
    
    if (last == nullptr)
        return false;
    while (last) {
        path.push_back({last->x, last->y});
        last = last->parent;
    }
    
    for (auto p:FreeList)     //free the freelist
        delete p;
    vector<PathNode *>().swap(FreeList);
    return true;
}


class StaticItem
{
public:
    StaticItem(StaticItemType type, BoxArea box)
    {
        if (!box.isInmap())
            throw "location exceed";
        this->type = type;
        this->box = box;
    }
    
    void putItemOnMap()
    {
        for (int i = box.getLy(); i <= box.getRy(); ++i)
            for (int j = box.getLx(); j <= box.getRx(); ++j)
                MAP[i][j] = MAP[i][j] ? '#' : type; //混合区域暂用#表示，因为目前静态元素表现形式一样，不用做过多区分
    }
    
private:
    StaticItemType type;
    BoxArea box;
};

class ActivityItem
{
public:
    Point loc;
    bool isMoving;
    vector<Point> path;
    ActivityItem(int id, Point loc, ActivityItemType type)
    {
        if (!loc.isInMap())
            throw "location exceed";
        this->id = id;
        this->loc = loc;
        this->type = type;
        isMoving = false;
    }
    
    int getPathSize()
    {
        return path.size();
    }
    
    bool oneStepMove(Point dst)
    {
        //移动在地图范围内，移动慢哈顿距离为1
        if (!dst.isInMap() || getMhtDis(loc, dst) != 1)
        {
            cout<<"the Point cannot move"<<endl;
            return false;
        }
        else
            cout<<id<<"move to "<<loc.x<<','<<loc.y<<endl;
        float t = rand() % 10 / 10.0;
        if (t < EVENTPROBABLITY)   //概率触发事件
            doSomeThing();
        return true;
    }
    
    void mergePath(vector<Point> &startPath, vector<Point> &blockPath, vector<Point> &endPath, vector<Point> &path)
    {
        /*
        // 正序
        path.insert(path.end(), startPath.rbegin(), startPath.rend());
        auto src = blockPath[blockPath.size()-1];
        for(int i=blockPath.size()-2;i>=0;--i)
        {
            path.pop_back();    //避免重复
            int bid = calcBlockId(src);
            vector<Point> *p;
            if(getMhtDis(src, blockPath[i])==1) //邻接互通点
            {
                path.push_back(src);
                path.push_back(blockPath[i]);
            }
            else if(src<blockPath[i])
            {
                p = BLOCK[bid].pathsMap[make_pair(src, blockPath[i])];
                path.insert(path.end(), p->rbegin(), p->rend());
            }
            else if(src>blockPath[i])
            {
                p = BLOCK[bid].pathsMap[make_pair(blockPath[i], src)];
                path.insert(path.end(), p->begin(), p->end());
            }
            src = blockPath[i];
        }
        path.insert(path.end(), endPath.rbegin(), endPath.rend());
         */
        path.insert(path.end(), endPath.begin(), endPath.end());
        auto src = blockPath[0];
        for(int i=1;i<blockPath.size();++i)
        {
            path.pop_back();    //避免重复
            int bid = calcBlockId(src);
            vector<Point> *p;
            if(getMhtDis(src, blockPath[i])==1) //邻接互通点
            {
                path.push_back(src);
                path.push_back(blockPath[i]);
            }
            else if(src<blockPath[i])
            {
                p = BLOCK[bid].pathsMap[make_pair(src, blockPath[i])];
                path.insert(path.end(), p->begin(), p->end());
            }
            else if(src>blockPath[i])
            {
                p = BLOCK[bid].pathsMap[make_pair(blockPath[i], src)];
                path.insert(path.end(), p->rbegin(), p->rend());
            }
            src = blockPath[i];
        }
        path.insert(path.end(), startPath.begin(), startPath.end());
    }
    
    bool moveTo(Point dst)
    {
        int startBlockId = calcBlockId(loc);
        int endBlockId = calcBlockId(dst);
        vector<Point> startPath, endPath;
        //ToDO
        vector<Point> startAll = BLOCK[startBlockId].getAllConnectedPoints();
        vector<Point> endAll = BLOCK[endBlockId].getAllConnectedPoints();
        PathNode *last = nullptr;
        bool found = false;
        for(auto start:startAll)
        {
            for(auto end:endAll)
            {
                getPath(loc, start, startPath);
                getPath(end, dst, endPath);
//                printf("start&&end:loc:%d,%d size:%d,%d\n", loc.x, loc.y, startPath.size(), endPath.size());

                if(startPath.empty()||endPath.empty())  //前提在区块边上的点路径包括自身
                    continue;
                last = findBlockPath(start, end);
                if(last== nullptr)
                    continue;
                vector<Point> cntPointPath;
                while(last)
                {
                    cntPointPath.push_back({last->x, last->y});
                    last = last->parent;
                }
                //                printf("pathSize: %d\n", path.size());
                for(auto p:FreeList)
                    delete p;
                vector<PathNode *>().swap(FreeList);
//                cout<<startPath.size()<<' '<<cntPointPath.size()<<' '<<endPath.size()<<endl;

                mergePath(startPath, cntPointPath, endPath, path);
                
//                for(auto &p:path)
//                    cout<<p.x<<','<<p.y<<' ';
//                cout<<endl;
                
                found = true;
                break;
            }
            if(found)
                break;
        }
        if(found)
        {
            isMoving = true;
        }
            
        return found;
    }
    
    void printPath()
    {
        cout << endl;
        while (path.size()) {
            Point t = path.back();
            path.pop_back();
            cout << t.x << ',' << t.y << ' ';
        }
        cout << endl;
    }
    
    void doSomeThing()
    {
        cout << "player " << id << " handle an event" << endl;
    }
    
    int getId()
    {
        return id;
    }
    
private:
    int id;
    ActivityItemType type;
    
};

vector<ActivityItem *> PLAYERS;


int getMhtDis(Point a, Point b)
{
    return abs(a.x - b.x) + abs(a.y - b.y);
}

int getMhtDis(PathNode *a, PathNode *b)
{
    return abs(a->x - b->x) + abs(a->y - b->y);
}

void setMapZero()
{
    memset(MAP, MAP_NULL, sizeof(MAP));
}


int myRand(int l, int r)
{
    int x;
    do {
        x = rand() % (r - l) + l;
    } while (x < l);
    return x;
}

void addRandomStaticItem(int l = 1, int r = 1)  //左闭右开
{
    if (r < l || l < 1)
        throw "wrong range";
    int itemNum = myRand(l, r);
    while (itemNum--) {
        Point t1, t2;
        t1 = {myRand(0, MAPSIZE), myRand(0, MAPSIZE)};  //这里直接使用了随机坐标，静态元素面积大概率偏大，可以改用根据面积随机
        t2 = {myRand(0, MAPSIZE), myRand(0, MAPSIZE)};
        //        std::cout<<t1.x<<','<<t1.y<<','<<t2.x<<','<<t2.y<<std::endl;
        BoxArea box(t1, t2);
        //        std::cout<<box.getLx()<<','<<box.getLy()<<','<<box.getRx()<<','<<box.getRy()<<std::endl;
        StaticItemType type((StaticItemType) myRand(1, StaticItemTypeMaxValue));
        StaticItem item(type, box);
        item.putItemOnMap();
    }
}

void addRandomActivityItem(int l = 1, int r = 1)
{
    int itemNum = myRand(l, r);
    for (int i = 1; i <= itemNum; ++i) {
        int id = i;
        Point t;
        do {
            t = {myRand(0, MAPSIZE), myRand(0, MAPSIZE)};
        } while (MAP[t.x][t.y] != MAP_NULL);
        ActivityItemType type((ActivityItemType) myRand(1, ActivityItemTypeMaxValue));
        ActivityItem *item = new ActivityItem(id, t, type);
        PLAYERS.push_back(item);
    }
}


void printMap()
{
    printf("%4c", ' ');
    for (int i = 0; i < MAPSIZE; ++i)
        printf("%4d", i);
    puts("");
    for (int i = 0; i < MAPSIZE; ++i) {
        printf("%4d", i);
        for (int j = 0; j < MAPSIZE; ++j) {
            printf("%4d", (int) MAP[i][j]);
        }
        puts("");
    }
}

int calcBlockId(Point a)
{
    int id = 0;
    id += BLOCKNUM * (a.x / BLOCKSIZE);
    id += a.y / BLOCKSIZE;
    return id;
}

Point calcBlockStartPoint(int bid)
{
    Point t = {bid / (BLOCKNUM) * BLOCKSIZE, (bid % BLOCKNUM) * BLOCKSIZE};
    return t;
}

Point calcBlockEndPoint(int bid)
{
    Point t = calcBlockStartPoint(bid);
    return {t.x + BLOCKSIZE - 1, t.y + BLOCKSIZE - 1};
}



void initBlock()
{
    for (int i = 0; i < BLOCKNUM * BLOCKNUM; ++i)
        BLOCK[i].id = i;
}

vector<int> getRoundBlockId(int bid)
{
    vector<int> v;
    int up, right, down, left;
    up = bid - BLOCKNUM;
    right = bid + 1;
    down = bid + BLOCKNUM;
    left = bid - 1;
    if (up >= 0 && up < BLOCKNUM * BLOCKNUM)
        v.push_back(up);
    if (right >= 0 && right < BLOCKNUM * BLOCKNUM)
        v.push_back(right);
    if (down >= 0 && down < BLOCKNUM * BLOCKNUM)
        v.push_back(down);
    if (up >= 0 && up < BLOCKNUM * BLOCKNUM)
        v.push_back(left);
    return v;
}

void getConnectPoint(Block *block1, Block *block2)
{
    if (block1->id == block2->id)
        throw "block id wrong";
    Block *b1, *b2;
    b1 = block1;
    b2 = block2;
    if (block1->id > block2->id) {
        b1 = block2;
        b2 = block1;
    }
    if (b1->id + 1 == b2->id)    //block2 on the right
    {
        Point start, end;
        start = {b1->id / (BLOCKNUM) * BLOCKSIZE, ((b1->id + 1) % (BLOCKNUM)) * BLOCKSIZE - 1};
        end = {start.x + BLOCKSIZE - 1, start.y};
        int low, high;
        low = high = start.x;
        while (high <= end.x) {
            for (int i = start.x; i <= end.x; ++i) {    //确保数组有序，后面有二分
                if (MAP[i][start.y] == MAP_NULL && MAP[i][start.y + 1] == MAP_NULL)
                    ++high;
            }
            int mid;
            mid = (low + high) >> 1;
            if (MAP[mid][start.y] == MAP_NULL && MAP[mid][start.y + 1] == MAP_NULL) {
                b1->right.push_back({mid, start.y});
                b2->left.push_back({mid, start.y + 1});
            }
            low = ++high;
        }
    } else            //block2 on the bottom, assume the data is legal
    {
        Point start, end;
        start = {(b1->id / (BLOCKNUM) + 1) * BLOCKSIZE - 1, (b1->id % (BLOCKNUM)) * BLOCKSIZE};
        end = {start.x, start.y + BLOCKSIZE - 1};
        int left, right;
        left = right = start.y;
        while (right <= end.y) {
            for (int i = start.y; i <= end.y; ++i) {    //确保数组有序，后面有二分
                if (MAP[start.x][i] == MAP_NULL && MAP[start.x + 1][i] == MAP_NULL)
                    ++right;
            }
            int mid;
            mid = (left + right) >> 1;
            if (MAP[start.x][mid] == MAP_NULL && MAP[start.x + 1][mid] == MAP_NULL) {
                b1->down.push_back({start.x, mid});
                b2->up.push_back({start.x + 1, mid});
            }
            left = ++right;
        }
    }
}

void preProcessBlock(Block &block)
{
    vector<Point> all;
    for (auto p:block.up)
        all.push_back(p);
    for (auto p:block.right)
        all.push_back(p);
    for (auto p:block.down)
        all.push_back(p);
    for (auto p:block.left)
        all.push_back(p);
    if(block.id%10==0)
        cout << "process block "<<block.id << ", cntPointNum:" << all.size() << endl;
    for (int i = 0; i < all.size() - block.left.size(); ++i) {
        int j;
        if (i < block.up.size())
            j = block.up.size();
        else if (i < block.up.size() + block.right.size())
            j = block.up.size() + block.right.size();
        else    //else if(i<all.size()-block.left.size())
            j = all.size() - block.left.size();
        for (; j < all.size(); ++j) {
            Point a, b;
            a = all[i];
            b = all[j];
            if (a == b)    //避免角点与自身计算
                continue;
            if (a > b) //避免重复计算路径，压缩存储空间，但是后面要判断路径方向
                swap(a, b);
            if(block.pathsMap.count({a, b}))
                continue;
            vector<Point> *path;
            path = new vector<Point> ();
            if (getPath(a, b, *path)) {
                //                cout<<a.x<<','<<a.y<<' '<<b.x<<','<<b.y<<endl;
                if(!block.connectedPointList.count(a))
                    block.connectedPointList.insert(make_pair(a, new vector<Point> ()));
                block.connectedPointList[a]->push_back(b);
                if(!block.connectedPointList.count(b))
                    block.connectedPointList.insert(make_pair(b, new vector<Point> ()));
                block.connectedPointList[b]->push_back(a);
                //                cout<<block.connectedPointList.size()<<endl;
                block.pathsMap.insert(make_pair(make_pair(a, b), path));
                //                cout<<block.pathsMap.size()<<endl;
            }
            //            printf("<%d,%d>,<%d,%d>:%d\n", a.x,a.y,b.x,b.y, path.size());
        }
    }
    //    if(block.id%100==0)
    //        cout<<block.id<<endl;
}

void preProcessMap()
{
    for (int i = 0; i < BLOCKNUM * BLOCKNUM; ++i) {
        if (i % BLOCKSIZE == BLOCKNUM - 1)
            continue;
        getConnectPoint(&BLOCK[i], &BLOCK[i + 1]);
    }
    for (int i = 0; i < BLOCKNUM * BLOCKNUM - BLOCKNUM; ++i) {
        getConnectPoint(&BLOCK[i], &BLOCK[i + BLOCKNUM]);
    }
    
    for (auto &block:BLOCK)
        preProcessBlock(block);
}

vector<Point> getRoundBLockConnectedPoints(PathNode *cur)   //要求方向上互通点数组有序
{
    Point t = {cur->x, cur->y};
    int bid = calcBlockId({cur->x, cur->y});
    vector<Point> v;
    auto test = BLOCK[bid].connectedPointList;
    if (BLOCK[bid].connectedPointList.count(t))
        v.insert(v.end(), BLOCK[bid].connectedPointList[t]->begin(), BLOCK[bid].connectedPointList[t]->end());
    //遇到角点可能会push两个点
    if (binary_search(BLOCK[bid].up.begin(), BLOCK[bid].up.end(), t))
        v.push_back({t.x - 1, t.y});
    if (binary_search(BLOCK[bid].right.begin(), BLOCK[bid].right.end(), t))
        v.push_back({t.x, t.y + 1});
    if (binary_search(BLOCK[bid].down.begin(), BLOCK[bid].down.end(), t))
        v.push_back({t.x + 1, t.y});
    if (binary_search(BLOCK[bid].left.begin(), BLOCK[bid].left.end(), t))
        v.push_back({t.x, t.y - 1});
    return v;
}

PathNode *findBlockPath(Point src, Point dst)
{
    PathNode *first = new PathNode(src);
    PathNode *last = new PathNode(dst);
    FreeList.push_back(first);
    FreeList.push_back(last);
    open.push(first);
    openSet.insert(make_pair(first->x, first->y));
    while (!open.empty()) {
        PathNode *cur = open.top();
        //            cout<<cur->x<<','<<cur->y<<endl;
        open.pop();
        closed.insert(make_pair(cur->x, cur->y));
        
        auto roundPoints = getRoundBLockConnectedPoints(cur);
        for (auto point:roundPoints) {
            if (MAP[point.x][point.y] != MAP_NULL) //有静态元素不能走
                throw "Connected Points wrong";
            if (closed.count(make_pair(point.x, point.y)))   //closed表已有
                continue;
            PathNode *p = new PathNode({point.x, point.y}); //remember to add it to freelist
            FreeList.push_back(p);
            if (!openSet.count(make_pair(p->x, p->y)))   //不在open表
            {
                p->parent = cur;
                if (getMhtDis(p, cur) == 1) {
                    p->G = cur->G + 1;
                } else {
                    Point a = {cur->x, cur->y};
                    Point b = {p->x, p->y};
                    int bid = calcBlockId(a);
                    bool reverse = false;
                    
                    if (a > b)
                        reverse = true;
                    if (reverse)
                        p->G = BLOCK[bid].pathsMap[make_pair(b, a)]->size() -
                        1;   //pair<a,b>取自getRoundBLockConnectedPoints确保size不为0,区块间互通点曼哈顿距离大于1
                    else
                        p->G = BLOCK[bid].pathsMap[make_pair(a, b)]->size() - 1;
                }
                p->H = getMhtDis(p, last);
                p->F = p->G + p->H;
                
                open.push(p);
                openSet.insert(make_pair(p->x, p->y));
            } else {
                int tmpG;
                if (p->parent)
                {
                    if (getMhtDis(p, p->parent) == 1)
                    {
                        tmpG = p->parent->G + 1;
                    }
                    else
                    {
                        Point a = {p->parent->x, p->parent->y};
                        Point b = {p->x, p->y};
                        int bid = calcBlockId(a);
                        bool reverse = false;
                        
                        if (a > b)
                            reverse = true;
                        tmpG = p->parent->G;
                        if (reverse)
                            tmpG += BLOCK[bid].pathsMap[make_pair(b, a)]->size() -
                            1;   //pair<a,b>取自getRoundBLockConnectedPoints确保size不为0,区块间互通点曼哈顿距离大于1
                        else
                            tmpG += BLOCK[bid].pathsMap[make_pair(a, b)]->size() - 1;
                    }
                }
                else
                    tmpG = 0;
                
                if (tmpG < p->G) {
                    p->parent = cur;
                    p->G = tmpG;
                    p->F = p->G + p->H;
                }
            }
            if (p->x == last->x && p->y == last->y) {
                clearOpenQueue();
                openSet.clear();
                closed.clear();
                return p;
            }
        }
    }
    
    clearOpenQueue();
    openSet.clear();
    closed.clear();
    return nullptr;
}


void timer(int sig)
{
    if(SIGALRM == sig)
    {
        for (auto &player:PLAYERS)
        {
            int r = myRand(0, 30);
            if(player->isMoving)
            {
                if(player->getPathSize()!=0)
                    player->path.pop_back();
                else
                    player->isMoving = false;
                continue;
            }
            if(r<7)
                player->oneStepMove(player->loc.getUp());
            else if(r<14)
                player->oneStepMove(player->loc.getRight());
            else if(r<21)
                player->oneStepMove(player->loc.getDown());
            else if(r<28)
                player->oneStepMove(player->loc.getLeft());
            else
                player->moveTo({myRand(0, MAPSIZE), myRand(0, MAPSIZE)});
                
        }
        alarm(1);       //重新继续定时1s
    }
    
    return ;
}


int main(int argc, const char *argv[])
{
    srand((unsigned)time(0));
    addRandomStaticItem(50, 150);
    
    addRandomActivityItem(100, 1000);
    
    initBlock();
    preProcessMap();
    cout << "Finished" << endl;
    getchar();
    
    
#ifdef Debug
//    printMap();
#endif
    
    signal(SIGALRM, timer); //注册安装信号
    
    alarm(1);       //触发定时器
    
    getchar();
    
    return 0;
}