我在做一个游戏,墙壁是由正方形的方块组成的。墙放置在二维网格上,如下所示:

[X][X][X][X]
[ ][X][ ][ ]
[ ][X][ ][ ]
[ ][X][ ][ ]

现在,当我在优化碰撞检测时,它有助于将墙数减少到最小。在上述情况下,有七个墙块,但如果这些墙块组合在一起,则只有两个墙。我很难找到一个最优的解决方案来找到这些组合墙,并根据搜索开始的块得到不同的结果(块存储在无序列表中,顺序来自它们在编辑器中的排列顺序)。你对如何解决这个问题有什么想法吗?这应该是很基本的东西,但是,你知道,现在是星期五,我不能正常工作:)
这是我目前的次优代码,它基本上做两个检查,水平和垂直“连续性”,然后检查哪一个更好。它还存储了“已处理”的墙块,这样它们就不会被识别两次,但这当然使它在交叉点变得很时髦。
public void CreateCollidersForExport()
{
    List<Wall> handledWalls = new List<Wall>();

    foreach (Wall w in walls)
    {
        if (handledWalls.Contains(w)) continue;
        handledWalls.Add(w);

        // Search how many walls there is horizontally
        Vector3 horizontalCenter = new Vector3(w.X, w.Y, w.Z);
        List<Wall> tmpWallsHorizontal = new List<Wall>();
        tmpWallsHorizontal.Add(w);
        foreach (Wall other in walls)
        {
            if (handledWalls.Contains(other) || tmpWallsHorizontal.Contains(other)) continue;
            bool canAdd = false;
            foreach (Wall _w in tmpWallsHorizontal)
            {
                if (other.X == _w.X + Wall.size && other.Y == _w.Y && other.Z == _w.Z)
                {
                    canAdd = true;
                    horizontalCenter.X += Wall.size / 2;
                    break;
                }
                else if (other.X == _w.X - Wall.size && other.Y == _w.Y && other.Z == _w.Z)
                {
                    canAdd = true;
                    horizontalCenter.X -= Wall.size / 2;
                    break;
                }
            }

            if (canAdd)
            {
                tmpWallsHorizontal.Add(other);
            }
        }

        // Search how many walls there is vertically
        Vector3 verticalCenter = new Vector3(w.X, w.Y, w.Z);
        List<Wall> tmpWallsVertical = new List<Wall>();
        tmpWallsVertical.Add(w);
        foreach (Wall other in walls)
        {
            if (handledWalls.Contains(other) || tmpWallsVertical.Contains(other)) continue;
            bool canAdd = false;
            foreach (Wall _w in tmpWallsVertical)
            {
                if (other.X == _w.X && other.Y == _w.Y && other.Z == _w.Z + Wall.size)
                {
                    canAdd = true;
                    verticalCenter.Z += Wall.size / 2;
                    break;
                }
                else if (other.X == _w.X && other.Y == _w.Y && other.Z == _w.Z - Wall.size)
                {
                    canAdd = true;
                    verticalCenter.Z -= Wall.size / 2;
                    break;
                }
            }

            if (canAdd)
            {
                tmpWallsVertical.Add(other);
            }
        }

        if (tmpWallsHorizontal.Count > tmpWallsVertical.Count)
        {
            // tmpWallsHorizontal has the longest "wall" now
        }
        else if (tmpWallsVertical.Count > tmpWallsHorizontal.Count)
        {
            // tmpWallsVertical has the longest "wall" now
        }
        else
        {
            // Both ways are the same length
        }
    }
}

最佳答案

我试着把它当作一种flood fill。这个想法是,你走过网格的每一个单元:每次你碰到一堵墙,你就开始一次洪水填满,除了洪水填充只在一个轴上工作(所以不是泛滥所有四个方向,你要么只向上/向下,要么向左/向右)。
假设有初始网格,并开始从左到右、从上到下迭代单元格:

[X][X][X][X]
[ ][X][ ][ ]
[ ][X][ ][ ]
[ ][X][ ][ ]

从左上角的单元格开始,注意它是一面墙,开始泛洪由于只能向右洪水泛滥,因此可以进行水平洪水泛滥。你最终覆盖了标有“1”的区域,并在列表中记住该区域:
[1][1][1][1]                  0/0 -> 3/0
[ ][X][ ][ ]
[ ][X][ ][ ]
[ ][X][ ][ ]

你继续往前走,最后撞到了第二排的墙。不能向左洪水泛滥(无墙),不能向上洪水泛滥(已被覆盖),不能向右洪水泛滥(无墙),但可以向下洪水泛滥-因此可以垂直洪水泛滥:
[1][1][1][1]                  1: 0/0 -> 3/0
[ ][2][ ][ ]                  2: 1/1 -> 1/3
[ ][2][ ][ ]
[ ][2][ ][ ]

现在你完了。在这个版本中,ever'X'始终只是一面墙的一部分所以如果你有
[ ][X][ ][ ]
[X][X][X][X]
[ ][X][ ][ ]
[ ][X][ ][ ]

你会有三堵墙:
[ ][1][ ][ ]                  1: 1/0 -> 1/3
[2][1][3][3]                  2: 0/1 -> 0/1
[ ][1][ ][ ]                  3: 2/1 -> 3/1
[ ][1][ ][ ]

如果让其他墙覆盖的“X”单元淹没,则可能只有两个:
[ ][1][ ][ ]                  1: 1/0 -> 1/3
[2][*][2][2]                  2: 0/1 -> 3/1
[ ][1][ ][ ]
[ ][1][ ][ ]

“*”表示被两面墙覆盖的单元格。

10-06 13:54