.net c#寻找最小数量的墙

Finding the minimum amount of walls
2021-07-22
  •  译文(汉语)
  •  原文(英语)

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

[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
        }
    }
}
速聊1:
请向我们显示您的代码不够理想.
速聊2:
这是您想要的输出吗?(0,0)-(0,3) and (0,1)-(3,1)?
速聊3:
听起来您必须计算所有可能的组合才能找到最佳组合.如果您最终用3堵墙而不是2堵墙会很糟糕吗?还是2个重叠的?
速聊4:
如果墙交叉,那怎么办?如果水平墙在第二行呢?
速聊5:
重叠不是问题,因此它们可以交叉和重叠.
解决过程1

我会尝试将其视为洪水填充的一种形式.这个想法是,您要遍历网格的每个单元:每次碰到"墙"时,您都将开始填充洪水,只是该洪水填充仅在单个轴上起作用(因此,不会在所有四个方向上都进行洪水淹没)仅向上/向下或向左/向右).

假设您拥有初始网格,并开始从左到右,从上到下迭代单元格:

[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][ ][ ]

现在您完成了.在此版本中,"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][ ][ ]

"*"表示被两个壁覆盖的单元格.

速聊1:
谢谢,这几乎是我已经做过的,我只需要在运行搜索之前先定好墙.

I'm making a game where the walls are made of square blocks. The walls are placed on a two-dimensional grid, like this:

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

Now, as I'm optimizing my collision detection, it helps to reduce the wall count to the bare minimum. In the above case, there is seven wall blocks, but only two walls if the blocks are combined. I'm having difficult time coming up with an optimal solution for finding these combined walls and get varying results depending on which block the search starts (the blocks are stored in an unordered list, the order comes from the order in which they were laid in an editor). Any thoughts on how to solve this? It should be pretty rudimentary stuff, but, y'know, it's friday and I can't function correctly. :)

Here's my sub-optimal code at the moment, it basically does two checks, both for horizontal and vertical "continuity" and then checks which one is better. It also stores the "already handled" blocks of walls so they won't be recognized twice, but this of course makes it go funky in crossing points.

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
        }
    }
}
Talk1:
Show us your less-than-optimal code please.
Talk2:
Is this the output you want? (0,0)-(0,3) and (0,1)-(3,1) ?
Talk3:
Sounds like you'd have to calculate all possible combinations to find the optimal one. Would it be so bad if you end up with 3 walls instead of 2? Or 2 overlapping ones?
Talk4:
What if the walls cross, so what if the horizontal wall would be on the second row?
Talk5:
Overlapping is not a problem, so they can cross and overlap.
Solutions1

I'd try to treat this as a form of flood fill. The idea is that you walk over ever cell of the grid: every time you hit a 'wall' you start a flood fill, except that the flood fill only works on a single axis (so instead of flooding int o all four directions you either only go up/down or left/right).

Assuming you have your initial grid, and start iterating the cells left to right, top to bottom:

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

You start with the top-left cell, notice it's a wall, start flooding. Since you can only flood to the right, you do a horizontal flood. You end up covering the area marked with '1' and memorize the area in a list:

[1][1][1][1]                  0/0 -> 3/0
[ ][X][ ][ ]
[ ][X][ ][ ]
[ ][X][ ][ ]

You move on, eventually hit the wall in the second row. You cannot flood left (no wall), you cannot flood up (already covered), you cannot flood right (no wall), but you can go down - so you do a vertical flood:

[1][1][1][1]                  1: 0/0 -> 3/0
[ ][2][ ][ ]                  2: 1/1 -> 1/3
[ ][2][ ][ ]
[ ][2][ ][ ]

And now you're done. In this version, ever 'X' is always only part of one wall. So if you had

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

you would have three walls:

[ ][1][ ][ ]                  1: 1/0 -> 1/3
[2][1][3][3]                  2: 0/1 -> 0/1
[ ][1][ ][ ]                  3: 2/1 -> 3/1
[ ][1][ ][ ]

If you allow flooding 'X' cells covered by other walls, you could have just two:

[ ][1][ ][ ]                  1: 1/0 -> 1/3
[2][*][2][2]                  2: 0/1 -> 3/1
[ ][1][ ][ ]
[ ][1][ ][ ]

The '*' denotes a cell covered by two walls.

Talk1:
Thanks, this was pretty much what I already had done, I just had to order the walls before running the search.
转载于:https://stackoverflow.com/questions/17361824/finding-the-minimum-amount-of-walls

本人是.net程序员,因为英语不行,使用工具翻译,希望对有需要的人有所帮助
如果本文质量不好,还请谅解,毕竟这些操作还是比较费时的,英语较好的可以看原文

留言回复
我们只提供高质量资源,素材,源码,坚持 下了就能用 原则,让客户花了钱觉得值
上班时间 : 周一至周五9:00-17:30 期待您的加入