java - 将形状连接在一起并追踪它们的轮廓

Question

编辑：找到解决方案。我在问题之后添加了它。

我正在为 Android 设计一款游戏，并试图想出一些方法来减少渲染阶段的计算。目前我有一个方法，它获取关卡中的所有金属和橡胶块并将纹理 id 存储到 int[][] 网格中，以便渲染器只读取它而不是计算每个块的平铺纹理每一帧。

这工作正常，但现在我正在尝试为关卡边缘和关卡中的激光块创建一个角和直片列表。使用一组直线激光纹理和角纹理绘制关卡边界和激光块。我不确定如何最好地解决在块与其他块和水平边缘重叠的地方不渲染激光的问题。下面的图片显示了我的意思：

绘画

在游戏中

在这里您可以看到水平边缘（L 形激光路径延伸到图片边缘之外）和三个/两个内部激光块（分别按图片顺序）。据我所知，我应该创建一个与上面类似的网格，但使用布尔值，因此任何在触摸时杀死玩家的方块（以红色突出显示）都是真的，而安全方块是假的。

然后我首先想到遍历网格中的所有真实（红色）单元格，并使用它们相邻的网格单元格计算出激光轮廓的外观，但我意识到这可能非常困难，所以我现在确定我使用了错误的方格找出来。我确信我可以通过从关卡边界的左下角开始并遍历网格直到找到错误的瓷砖（除非第一个正方形是错误的）然后通过网格向右移动直到我到达右边的一个真正的单元格，所以我会向左转并继续向上穿过网格，直到在上面找到一个 true 向左转，或者在右边找到一个 false 向右转。我会重复这个过程，直到我到达我的起始假细胞。

我在写这个问题的时候想出了这个，哈哈。这似乎是最简单的方法，所以我想我的问题是这是一种很好的方法，我将如何计算出相互接触但不接触水平边界的激光块，因为上述方法只会追踪最外面的激光小路。

感谢您花时间阅读本文。我希望我已经解释得足够好，我期待任何关于这个主题的启示。

Answer 1

解决方案：

    public static boolean[][] laserField = new boolean[(int) Static.WORLD_SIZE][(int)Static.WORLD_SIZE];
    public static List<LaserData> laserData = new ArrayList<LaserData>();
    public static void calcLaserBoundryAreas() {
        laserField = new boolean[(int) Level.levelBounds.bounds.width+5][(int) Level.levelBounds.bounds.height+5];
        for (int i=0;i<laserField.length;i++) {
            for (int j=0;j<laserField[i].length;j++) {
                if(i==0 || i==laserField.length-1 || j==0 || j==laserField[i].length-1)
                    laserField[i][j] = true;
                else
                    laserField[i][j] = false;
            }
        }
        for (LaserBlock lBlock : lBlocks) {
            int cols = (int)lBlock.bounds.width;
            int rows = (int)lBlock.bounds.height;
            float startX = lBlock.position.x - (cols-1f)/2f;
            float startY = lBlock.position.y - (rows-1f)/2f;
            for (int i=0;i<cols;i++) {
                for (int j=0;j<rows;j++) {
                    addLaserCell(startX+i, startY+j);
                }
            }
        }
        addLaserData();
    }

private static void addLaserCell(float x, float y) {
    int cellX = (int)(x- Level.levelBounds.bounds.lowerLeft.x+2);
    int cellY = (int)(y- Level.levelBounds.bounds.lowerLeft.y+2);
    if (cellX < 0 || cellX > laserField.length-1)           return;
    if (cellY < 0 || cellY > laserField[cellX].length-1)    return;
    laserField[cellX][cellY] = true;
}

private static void addLaserData() {
    laserData = new ArrayList<LaserData>();
    for (int i=1;i<laserField.length-1;i++) {
        for (int j=1;j<laserField[i].length-1;j++) {
            if (!laserField[i][j]) {
                checkNeighbours(i,j);
            }   
        }
    }
    optimiseLaserData();
}

private static void checkNeighbours(int x, int y) {
    boolean u = laserField[x][y+1];
    boolean ul = laserField[x-1][y+1];
    boolean l = laserField[x-1][y];
    boolean bl = laserField[x-1][y-1];
    boolean b = laserField[x][y-1];
    boolean br = laserField[x+1][y-1];
    boolean r = laserField[x+1][y];
    boolean ur = laserField[x+1][y+1];

    /*
     *  TOP LEFT CORNER 
     */
    float posX, posY;
    posX = Level.levelBounds.bounds.lowerLeft.x+x-2.5f;
    posY = Level.levelBounds.bounds.lowerLeft.y+y-1.5f;
    if(u && ul && l)
        laserData.add(new LaserData(posX, posY, true, 0, 0));
    else if(!u && ul && l)
        laserData.add(new LaserData(posX, posY, false, 1, 0));
    else if(!u && ul && !l)
        laserData.add(new LaserData(posX, posY, true, 0, 2));

    /*
     *  BOTTOM LEFT CORNER 
     */
    posX = Level.levelBounds.bounds.lowerLeft.x+x-2.5f;
    posY = Level.levelBounds.bounds.lowerLeft.y+y-2.5f;
    if(l && bl && b)
        laserData.add(new LaserData(posX, posY, true, 0, 1));
    else if(!l && bl && b)
        laserData.add(new LaserData(posX, posY, false, 1, 1));
    else if(!l && bl && !b)
        laserData.add(new LaserData(posX, posY, true, 0, 3));

    /*
     *  BOTTOM RIGHT CORNER 
     */
    posX = Level.levelBounds.bounds.lowerLeft.x+x-1.5f;
    posY = Level.levelBounds.bounds.lowerLeft.y+y-2.5f;
    if(b && br && r)
        laserData.add(new LaserData(posX, posY, true, 0, 2));
    else if(!b && br && r)
        laserData.add(new LaserData(posX, posY, false, 1, 2));
    else if(!b && br && !r)
        laserData.add(new LaserData(posX, posY, true, 0, 0));

    /*
     *  TOP RIGHT CORNER 
     */
    posX = Level.levelBounds.bounds.lowerLeft.x+x-1.5f;
    posY = Level.levelBounds.bounds.lowerLeft.y+y-1.5f;
    if(r && ur && u)
        laserData.add(new LaserData(posX, posY, true, 0, 3));
    else if(!r && ur && u)
        laserData.add(new LaserData(posX, posY, false, 1, 3));
    else if(!r && ur && !u)
        laserData.add(new LaserData(posX, posY, true, 0, 1));

}

private static void optimiseLaserData() {
    List<LaserData> optiLaserData = new ArrayList<LaserData>();
    for(LaserData ld : laserData) {
        if(ld.cornerPiece)
            optiLaserData.add(ld);
        else if(ld.dir == 0 || ld.dir == 2){
            float x = ld.x;
            float bottomY = ld.y;
            float topY = ld.y;
            float count = 1;
            while (searchStraightLaserData(laserData, x, topY+1, ld.dir)) {
                count++;
                topY++;
            }
            while (searchStraightLaserData(laserData, x, bottomY-1, ld.dir)) {
                count++;
                bottomY--;
            }
            float centerY = bottomY + (topY-bottomY)/2;
            if(!searchStraightLaserData(optiLaserData, x, centerY, ld.dir))
                optiLaserData.add(new LaserData(x, centerY, false, count, ld.dir));
        } else {
            float y = ld.y;
            float leftX = ld.x;
            float rightX = ld.x;
            float count = 1;
            while (searchStraightLaserData(laserData, rightX+1, y, ld.dir)) {
                count++;
                rightX++;
            }
            while (searchStraightLaserData(laserData, leftX-1, y, ld.dir)) {
                count++;
                leftX--;
            }
            float centerX = leftX + (rightX-leftX)/2;
            if(!searchStraightLaserData(optiLaserData, centerX, y, ld.dir))
                optiLaserData.add(new LaserData(centerX, y, false, count, ld.dir));
        }
    }
    laserData = optiLaserData;
}

private static boolean searchStraightLaserData(List<LaserData> data, float x, float y, int dir) {
    for(LaserData ld : data)
        if(ld.x == x && ld.y == y && ld.dir == dir && !ld.cornerPiece)
            return true;
    return false;
}

这些方法首先创建一个布尔网格，该网格是水平边缘边界的大小，每边有一个 1 平方的额外边缘。这被初始化为 false 以表示安全区域，并且额外的边缘设置为 true 以便我们有一种空心盒子。额外的边缘通过消除在laserField上检查不正确索引的需要来帮助以后。

在将关卡范围映射到网格后，单个单元格会在被激光块覆盖的地方更改为真。

一旦布尔网格被完全映射，它就会遍历每个网格单元，当它找到一个错误的单元时，它将网格坐标传递给下一个方法，该方法查看 12 个不同的相邻模式以确定是否应该在该单元周围渲染任何激光. LaserData 构造函数采用以下参数（float x、float y、booleancornerPiece、float length、int 方向）

最后一部分进行了蛮力搜索，以检查是否任何相邻的直线段可以被单个较长的直线段替换，以节省渲染额外的精灵。

然后渲染器可以只读取每帧的laserData列表，它拥有渲染正确纹理、位置、长度等所需的所有信息……

注意：关卡边界的宽度和高度比实际游戏区域小 3 个单位，以考虑玩家在边界外的宽度。这就是 levelBounds.lowerleft+5、+2 和 +1.5f 等...的来源。我知道这有点 hacky，但它是旧代码，我不敢碰它 xD