Поиск минимального количества стен

Question

Я делаю игру, где стены сделаны из квадратных блоков. Стены расположены на двумерной сетке, как это:

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

Answer 1

Я бы попытался рассматривать это как форму 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][ ][ ] 

И теперь вы «Сделано. В этой версии, когда-либо «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][ ][ ] 

«*» Обозначает ячейку, покрытую двумя стенками.