# .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;

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

{
}
}

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

{
}
}

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
}
}
}
``````

``````[X][X][X][X]
[ ][X][ ][ ]
[ ][X][ ][ ]
[ ][X][ ][ ]
``````

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

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

``````[ ][1][ ][ ]                  1: 1/0 -> 1/3
[2][*][2][2]                  2: 0/1 -> 3/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;

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

{
}
}

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

{
}
}

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:
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.