从OI到外挂-第一集-使用并查集合并实现透视物资列表

引言

众所周知，在OI中，并查集是用来维护集合之间关系的数据结构，它能以优秀的时间复杂度完成集合的合并，元素所属集合的查找，还有种类并查集等等拓展玩法，特别有趣。

如今的大逃杀类外挂的一个重要功能就是 物资透视 ，即将地上的物品通过绘制文字的形式显示出来，让玩家能够清楚的知道物资的位置。但是这也会出现一定的问题，首先是物品堆叠问题，如果两个物品靠的太近，绘制时名字就会重叠在一起，这样两个物品的名字都看不清；其次是物品堆叠过于杂乱，玩家不能够很清楚的辨识出自己想要的物资所处位置，即便是加上了不同类型物资以不同颜色绘制，依然效果不理想。

因此，一种新的绘制方式被急切需要，我们能否想象一种方式，使之能够将隔得很近的物资自动合并，并以列表的形式绘制出来？此时，我们自然的想到了OI中的一种数据结构：并查集

并查集简介

并查集的种类有很多种，其中最广泛使用的是按秩合并并查集(也称启发式合并并查集)，还有路径压缩并查集。我们今天使用的就是路径压缩并查集。

并查集，顾名思义，有“并”和“查”两种功能。想象这样一个场景，对于每一个我们要绘制的物资，我们都知道它的三维坐标，也就自然而然知道它到其他物资的距离，我们先简化模型，把物资的位置看作二维平面上的点，如图：

1.jpg
可以发现，图中有一些聚集的点，形成了一“团”，这通常和大逃杀类游戏中，武器和子弹生成拜访在一起的逻辑是相符合的。接下来我们按照如下规则进行连线，对于任意的$A$和$B$物品，如果他们之间的距离$d < D$，(其中$D$为设定的最大合并距离阈值)，那么我们在他们之间连线，然后就得到了下面这幅图

2.jpg

我们可以看到，靠的近的物资被连成了一体，用集合的角度来看，他们就都处于了同一个集合，并查集实际上实现的功能就是这样，将两个集合合并，同时可以查询每个元素属于哪个集合

如何在外挂中使用

既然我们都知道了每个物资的三维坐标，那么我们同样也可以计算出它到每个其他物资的距离，如果这个距离小于阈值$D$，那么我们就在并查集里面把他们合并，对于每个物资都做了同样的操作过后，此时的并查集维护的信息，就是所有小堆物品的集合信息了，我们分别遍历每个集合，把集合里面的物资以列表的形式绘制出来就行了

此时存在一个问题，如何确定一堆物品的最终绘制位置？以其中任意一个物品的坐标为标准？其实，我们有更好的做法，那就是假设该集合每个物资的重量相等，那么只需要求出该集合所有物资的重心，在重心出绘制列表就可以了。怎么求重心？所有的物资的$x,y,z$坐标分别相加，然后除以物品数就得到了重心，高中物理，就不用我多说了吧。

Coding Time!

外挂中使用到的并查集

/*
        并查集
    */
    namespace BCJ{
        int fa[2000];
        void initFa() {
            for (int i = 1; i < 2000; i++) fa[i] = i;
        }
        int get(int x) {
            if (fa[x] == x) return x;
            return fa[x] = get(fa[x]);
        }
        void merge(int x,int y) {
            int fax = get(x),fay = get(y);
            if (fax == fay) return;
            fa[fax] = fay;
        }
    }

一个非常简单的路径压缩并查集，因为游戏优化，物资数不会太多，这里开2000的数组完全足够了

绘制时的调用

void 绘制物品列表() {
        float distanceInmerge = 1.5; //最小合并距离
        int margin = 2;
        BCJ::initFa();
        static std::vector<WorldObject> itemList;
        itemList.clear();
        for (WorldObject obj : worldObjs) {
            if (obj.type == Item) {
                itemList.push_back(obj);
            }
        }
        int itemCnt = itemList.size();
        std::vector< std::vector<WorldObject> > buk(itemCnt+2);
        std::vector< Vector3 > gravityCenter(itemCnt+2);
        for (int i = 0; i < itemList.size(); i++) {
            WorldObject cur = itemList[i];
            for (int j = i + 1; j < itemList.size(); j++) {
                WorldObject that = itemList[j];
                float dis = (that.location - cur.location).GetLength() / 100;
                if (dis <= distanceInmerge) {
                    BCJ::merge(i+1,j+1);
                }
            }
        }
        for (int i = 0; i < itemList.size(); i++) {
            int belongto = BCJ::get(i+1);
            buk[belongto].push_back(itemList[i]);
            gravityCenter[belongto] = gravityCenter[belongto] + itemList[i].location;
        }
        for (int i = 1; i <= itemCnt; i++) {
            if (buk[i].size() == 0) continue;
            sort(buk[i].begin(),buk[i].end(),typeCmp);
            Vector3 gc = gravityCenter[i] / buk[i].size();
            屏幕范围 pos2d = { 0,0,0,0 };
            if (数据::WorldToScreen_2d(gc, pos2d)) {
                for (int j = 0; j < buk[i].size(); j++) {
                    WorldObject cur = buk[i][j];
                    ImVec2 textsize = bigger_font->CalcTextSizeA(20, 9999, 9999, cur.objName.c_str());
                    ImVec2 start1 = ImVec2(pos2d.X - 1, pos2d.Y + textsize.y * j + margin * j) ^ gameDrawOffset;
                    ImVec2 start = ImVec2(pos2d.X, pos2d.Y + textsize.y * j + margin * j) ^ gameDrawOffset;
                    ImVec4 col = config.物品颜色选项[cur.itemType];
                    ImGui::GetOverlayDrawList()->AddText(bigger_font, 20, start1, ImGui::GetColorU32(ImVec4(1-col.x,1-col.y,1-col.z,0.8)), cur.objName.c_str());
                    ImGui::GetOverlayDrawList()->AddText(bigger_font,20,start, ImGui::GetColorU32(col),cur.objName.c_str());
                    if (是否高级物资(cur.objName)) {
                        ImGui::GetOverlayDrawList()->AddLine(ImVec2(start1.x, start1.y + textsize.y + 1), ImVec2(start1.x + textsize.x, start1.y + textsize.y + 1), ImGui::GetColorU32(ImVec4(1 - col.x, 1 - col.y, 1 - col.z, 0.8)), 2); //下划线
                        ImGui::GetOverlayDrawList()->AddLine(ImVec2(start.x,start.y + textsize.y + 1), ImVec2(start.x + textsize.x, start.y + textsize.y + 1), ImGui::GetColorU32(col),2); //下划线
                    }
                }
            }
        }
    }

这里的 $distanceInmerge$ 就是我们之前提到的阈值$D$，根据测试，在hpjy中阈值为$1.5m$比较合适

效果图

QQ截图20200422172339.jpg