找到最小数量的墙
本文关键字:小数 | 更新日期: 2023-09-27 18:20:11
我正在制作一个游戏,其中的墙是由方形块制成的。墙被放置在二维网格上,如下所示:
[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
}
}
}
我会尝试将其视为洪水填充的一种形式。这个想法是,你走过网格的任何一个单元:每次你碰到"墙",你都会开始泛洪填充,但泛洪填充只在一个轴上工作(所以你要么只向上/向下,要么只向左/向右,而不是向所有四个方向泛洪)。
假设您有了初始网格,并开始从左到右、从上到下迭代单元格:
[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][ ][ ]
"*"表示由两面墙覆盖的单元格。