Trouver le nombre minimum de murs

Question

Je crée un jeu dont les murs sont constitués de blocs carrés. Les murs sont placés sur une grille bidimensionnelle, comme ceci :

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

Maintenant que j'optimise ma détection des collisions, il est utile de réduire le nombre de murs au strict minimum. Dans le cas ci-dessus, il y a sept blocs de murs, mais seulement deux murs si les blocs sont combinés. J'ai du mal à trouver une solution optimale pour trouver ces murs combinés et j'obtiens des résultats différents selon le bloc à partir duquel la recherche commence (les blocs sont stockés dans une liste non ordonnée, l'ordre vient de l'ordre dans lequel ils ont été posés dans un éditeur). Comment résoudre ce problème ? C'est un truc assez rudimentaire, mais on est vendredi et je ne peux pas fonctionner correctement :)

Voici mon code sous-optimal pour le moment, il fait essentiellement deux vérifications, à la fois pour la "continuité" horizontale et verticale, et vérifie ensuite laquelle est la meilleure. Il stocke également les blocs de murs "déjà traités" afin qu'ils ne soient pas reconnus deux fois, mais cela rend bien sûr les points de passage bizarres.

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

J'essaierais de traiter cela comme une forme de Remplissage en cas d'inondation . L'idée est de marcher sur chaque cellule de la grille : à chaque fois que vous rencontrez un "mur", vous commencez un remplissage, sauf que le remplissage ne fonctionne que sur un seul axe (donc au lieu d'inonder dans les quatre directions, vous allez seulement vers le haut/bas ou la gauche/droite).

En supposant que vous ayez votre grille initiale, commencez à itérer les cellules de gauche à droite et de haut en bas :

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

Vous commencez par la cellule en haut à gauche, vous remarquez qu'il s'agit d'un mur et vous commencez à inonder. Comme vous ne pouvez inonder que vers la droite, vous procédez à une inondation horizontale. Vous finissez par couvrir la zone marquée d'un "1" et vous mémorisez la zone dans une liste :

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

Vous avancez, puis vous vous heurtez au mur de la deuxième rangée. Vous ne pouvez pas inonder à gauche (pas de mur), vous ne pouvez pas inonder en haut (déjà couvert), vous ne pouvez pas inonder à droite (pas de mur), mais vous pouvez descendre - vous faites donc une inondation verticale :

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

Et maintenant, vous avez terminé. Dans cette version, chaque "X" ne représente toujours qu'une partie d'un mur. Ainsi, si vous aviez

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

vous auriez trois murs :

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

Si vous autorisez l'inondation des cellules "X" couvertes par d'autres murs, vous pourriez n'en avoir que deux :

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

Le signe "*" indique une cellule couverte par deux murs.