Bestimmen Sie, ob eine aus einer Reihe anderer Formen gebildete Form "ungebrochen" ist.

Ich habe ein Gitter mit Plättchen in einem Spiel und jedes Plättchen kann eine bestimmte einfache Form haben.

Ich möchte in der Lage sein zu bestimmen, ob die kombinierte Form aus einer bestimmten Anordnung dieser Kacheln zu einer "ungebrochenen" oder "gebrochenen" größeren Form führt.

Zum Beispiel; Dies ist ein Beispiel für eine "ungebrochene" Form ...

Und dies ist ein Beispiel für eine "gebrochene" Form ...

Ich werde in der Lage sein, den erforderlichen Code zu schreiben, sobald ich die Logik dieses Problems herausgefunden habe, aber bisher habe ich Probleme.

Ich habe Datentabellen ausprobiert, die jeder Kachel zugeordnet sind und deren Kanten beschreiben, zum Beispiel:

var edges = {
    top : false,
    right : true,
    bottom : true,
    left : false
}

Und daraus kann ich feststellen, ob jede Kachel mit ihren Nachbarn verbunden ist. Dies hilft jedoch nicht in allen Situationen.

EDIT 1: Mehrere Cluster von isolierten "ungebrochenen" Formen würden als "gebrochene" Form betrachtet ...

EDIT 2:

Eine "ungebrochene" Form kann auch erreicht werden, wenn die Kante einer Formkachel nicht mit jeder benachbarten Kachel verbunden ist, sondern nur eine Verbindung. Zum Beispiel würde ich dies als "ungebrochen" betrachten ...

Hat jemand Ideen dazu?

Dies ist ein grundlegendes Problem mit verbundenen Komponenten und kann mit einem einzigen Aufruf der Breitensuche oder Tiefensuche oder einem beliebigen Flood-Fill-Algorithmus gelöst werden.

bool IsOneSolidShape(TileCollection tiles)
{
    // Clear visited flags on all tiles.
    // (This can also be implemented as a temporary set/map or parallel array,
    // if you prefer not to clutter your Tile type with book-keeping data)
    foreach(var tile in tiles)
        tile.IsVisited = false;

    // Prepare a container to hold tiles whose neighbours we haven't searched yet.
    // With a stack, this is depth-first search. A queue gives breadth-first.
    var pending = new stack<Tile>();

    // Seed the search with some start tile - this choice is arbitrary.
    var startTile = tiles.GetSomeNonEmptyTile();
    startTile.IsVisited = true;
    pending.Push(startTile);
    int numVisited = 1;

    // Search for as long as we have unexplored tiles in our stack:
    while(pending.Count > 0)
    {
         var tile = pending.Pop();
         foreach(var neighbour in tile.GetNeighbours())
         {
             // Skip over tiles we've already reached.
             if(neighbour.IsVisited)
                continue;

             // Check for a valid connection between this tile and this neighbour.
             if(tile.IsConnectedTo(neighbour))
             {
                // This tile is connected.
                // Mark it visited so we don't double-count it later.
                neighbour.IsVisited = true;

                // Add it to our reached set.
                numVisited++;

                // Keep note of it so we can search its neighbours.
                pending.Push(neighbour);
             }
         }
    }

    // If we have reached every non-empty tile,
    // then they are all in one connected shape.
    return numVisited == tiles.GetNonEmptyTileCount();
}

Der obige Code sagt Ihnen nur, ob Sie genau eine Gruppe haben.

Wenn Sie zählen möchten, wie viele Gruppen es gibt, können Sie dies tun, indem Sie die äußere while-Schleife in eine Weile einschließen (numVisited <tiles.GetNonEmptyTileCount ()), wobei Sie die innere while-Schleife jedes Mal mit einer neuen nicht besuchten Kachel versehen und Ihre Gruppe erhöhen Anzahl.

Beachten Sie, dass tile.IsConnecedTo(neighbour)genau dann true zurückgegeben werden sollte, wenn beide tile und neighbourentlang ihrer gemeinsamen Kante eine Verbindung herstellen. (dh wenn eine tileVerbindung zum gemeinsam genutzten Edge hergestellt wird, dies jedoch neighbournicht der Fall ist, sollte false zurückgegeben werden.)

Bearbeiten: Hier ist eine rekursive Version:

bool IsOneSolidShape(TileCollection tiles)
{
    // Clear visited flags on all tiles.
    // (This can also be implemented as a temporary set/map or parallel array,
    // if you prefer not to clutter your Tile type with book-keeping data)
    foreach(var tile in tiles)
        tile.IsVisited = false;

    // Seed the search with some start tile - this choice is arbitrary.
    var startTile = tiles.GetSomeNonEmptyTile();

    // Recursively search all tiles reachable from startTile.
    int numVisited = CountConnected(startTile);

    // If we have reached every non-empty tile,
    // then they are all in one connected shape.
    return numVisited == tiles.GetNonEmptyTileCount();
}

int CountConnected(Tile tile)
{
   // Initialize connected set to include "myself."
   tile.IsVisited = true;
   int connected = 1;

   // Check for connections to neighbours.
   foreach(Tile neighbour in tile.GetNeighbours())
   {
      // Skip tiles we've already visited, to avoid double-counting.
      if(neighbour.isVisited)
         continue;

      // Recursively search any neighbour we're connected to)
      if(tile.IsConnectedTo(neighbour))
         connected += CountConnected(neighbour);
   }

   return connected;
}

Zeichnen Sie die Scheitelpunkte als Linien an den Kanten auf, an denen Formpunkte liegen. Diese werden verwendet, um bei jedem Kartenwechsel bis zu Punkten / Linien auf den anderen Kacheln abzugleichen.

Zum Beispiel:

Über den blauen Linien auf den oberen beiden Kacheln wurden A und B für jede Kante der Kachel entsprechend der darin enthaltenen Form berechnet / gespeichert (beachten Sie, dass Sie die Linie zum Vergleich mit einer einfachen Ganzzahl extrahieren können, obwohl sie sich auf verschiedenen Seiten befinden Werte von 0 -> X.)

Im unterbrochenen Beispiel stimmen die Linien nicht überein, sodass Sie sagen können, dass das Bild unterbrochen ist. Speichern Sie die Daten als zusätzliche Informationen in der Kachel, um sie dann zum Vergleich zu verwenden. Wenn Sie eine festgelegte Anzahl von Kantentypen haben (volle Kante, halbe Kante usw.), können Sie sogar einen Enumerator für die Seiten A, B, C und D auf jeder Kachel erstellen und entsprechend vergleichen.

In unserem Beispiel können unsere Kanten mit Werten von 0 -> 10 verglichen werden.

var exampleTileA = {
    top : undefined,
    right : {0,10},
    bottom : {0,10},
    left : undefined
}

var exampleTileB = {
    top : undefined,
    right : undefined,
    bottom : {0,10},
    left : {0,10}
}

var exampleTileC = {
    top : {5,10},
    right : {5,10},
    bottom : {0,5},
    left : {0,5}
}

function compareLeftRight(leftTile, rightTile){
    return leftTile.right === rightTile.left;
}

console.log(compareLeftRight(exampleTileA, exampleTileB));
console.log(compareLeftRight(exampleTileA, exampleTileC));

//// Output
//  true
//  false

Um sich den Clustern ungebrochener Formen zu nähern, können Sie einfach jede Kachel durchlaufen und prüfen, ob sie mit einer der zuvor iterierten Kacheln verbunden ist:

var tiles = [tileA, tileB, ...];
var tempTiles = tiles;

// Loop through each tile and remove it from the temp
// tile array if it is connected to any of the previous tiles
for (var tile in tiles) {
     var currentIndex = tiles.indexOf(tile);

     for(var i = 0; currentIndex > i; i++) {
         if ( tileA.connectedTo(tile)) {             
             // remove from temp tiles
             var index = tempTiles.indexOf(tile);
             if (index > -1) {
                 tempTiles.splice(index, 1);
             }
         }
     }
}

if (tempTiles.length > 0) {
    // Some tile was not connected to the group
    console.log("There are " + tempTiles.length + " tiles not connected to the group");
}

Es hört sich so an, als ob Sie nur suchen müssen, ob Ihre Kacheln gebrochene Kanten aufweisen, und einen wahren oder falschen Rücken erhalten.

In diesem Fall müssen Sie sich nur alle Stellen ansehen, an denen Kacheln zusammengefügt werden (auf der x- und der y-Achse), und prüfen, ob die Kanten kompatibel sind.

Sie haben eine Schleife ausgeführt, bis Sie entweder eine gebrochene Kante gefunden haben (und true zurückgegeben haben) oder bis Ihnen die zu überprüfenden Kanten ausgegangen sind (und false zurückgegeben haben).

Es wäre im Grunde eine for-Schleife innerhalb einer for-Schleife (eine wäre die X-Achse, die andere wäre die Y-Achse), also wäre es ein N ^ 2-Algorithmus.

Ist es das, wonach du suchst? Hilft das?