Drag und Drop im Raster + Verschiebung belegter Felder

FipsTheThief

Erfahrenes Mitglied
Guten Tag,

ich suche hier seit 2 Tagen eine Lösung für ein Drag Drop Problem im Raster.

Um dies ein wenig zu verdeutlichen nehm ich die Beispiel Matrix, die so ziemlich genau aussieht wie das was ich habe.

4 Spalten , 3 Reihen

Code:
  a   b   c   d
1 i | k |   | m
2 j |   |   | m
3   | n   n |

Alles was als X gekennzeichnet ist ist quasi belegt, das geht von [weite, höhe] => [1 , 1] feldern bis zu [n, m]

Angenommen ich nehme den Container auf dem feld [a1] und bewege ihn auf [b1] , nun muss b1 platz machen , entweder links ( was nun frei geworden ist) , rechts wäre Alternative 2, oben -> Alternative 3 und unten alternative 4. Würde prima gehen da beide gleich groß sind und [b2] gleich in [a1] reinpasst.

Fall 2:

ich neme den Container [b3, c3] und verschiebe ihn so das er in das Feld [d2] reinragt. Es wird bereits erkannt aha da liegt was. Nun suchen wir wieder die Felder ausgehend von [d1] geht es nach links ? Ja geht es wäre möglich aber nun schneidet er sich mit dem Container den ich da hinlegen möchte, also kann er dort nicht liegen.
Die Suche geht weiter nach rechts -> nicht möglich außerhalb des grids, nach oben das gleiche also nach unten wieder ein Schnitt.

Somit müsste nun in einen Radius welcher sich ständig erweitert um das obere Feld gesucht werden und dann geprüft werden ob der Container der nun verschoben werden muss damit der Drop Container den Platz einnehmen kann.

Das ganze hab ich mir quasi so gedacht:

Code:
Schritt 1:
   a b c 
 1 o o o
 2 o x o 
 3 o o o
 
 möglich 8 Felder
 such reichweite = 1

 keine möglichkeit gefunden suche ausweiten
  a b c d e
1 o o o o o 
2 o - - - o
3 o - x - o
4 o - - - o
5 o o o o o

Dabei kann ich ja nun bereits Felder weglassen die ich bereits durchsucht hatte also bleiben nur noch potentielle 16 felder übrig.
such reichweite = 2

Das Problem dabei ist ich bringe das ich keine brauchbare allgemeingültige Form und wollte mich gern einmal erkundigen ob einer von euch da eine Idee hätte dies bezüglich.

Positionierung soll hier in folgender Reinfolge vorgenommen werden:

1. links
2. rechts
3. oben
4. unten

und dann alle anderen Felder.
 
Zuletzt bearbeitet:

FipsTheThief

Erfahrenes Mitglied
Mhm Backtracking auf den Begriff bin ich nach meiner Suche auch schon gestoßen heute wo es um das Lösen von Suduko Rätseln ging.

Ist auf jeden fall ein Begriff den ich mir mal näher anschaun werde nun.

Danke also vielmals :)
 

FipsTheThief

Erfahrenes Mitglied
So wollte nur sagen das klappt inzwischen , auch wenns noch nicht ganz ausgereift ist. Als ich dann beim Backtracking, Rucksack verfahren gelesen habe Trial and Error hab ich auch aufgehört krampfhaft nach einen Algorithmus zu suchen und mir noch ein paar Beispiele zu 8 Damen Problem , Sudoku knacken durchgelsen das hat eventuell auch noch dazu beigetragen das ich irgendwann auf eine halbwegs brauchbare Lösung gekommen bin.

Das hier ist erstmal ein prototyp und mus noch verfeinert werden, das ganze baut auf dem "Divide and Conquer" Prinzip auf nun, indem ich mir meine Hauptmatrix die um das erste Feld durchsucht werden soll aufteile und dadurch 2 While Schleifen erstelle

bsp : 3 x 3 ( wäre bei Suchweite 1 )

Code:
sR = 1; // Suchreichweite
  a b c
1 o o o 
2 o x o  Startpunkt von Reihe 0 bis sR -1 
---------- 
3 o o o  von Reihe 1  bis sR

1. Schleife suche nach 0ben
   1.1 oberste reihe erreicht  wenn nein  1.3, wenn ja 1.2
   1.2 oberste reihe wieder splitten da ich hier alle Elemente brauche
         schleife 1 : 0 bis -sR 
         schleife 2: 1 bis sR 
   1.3 prüfe Feld ganz links -sR und Feld ganz rechts sR
          feld kann belegt werden abbruch
   1.4 wenn bisher kein Feld gefunden gehe Reihe nach oben
           
2. schleife nach unten eigentlich identisch mit 1 blos das die row++ gerechnet wird

das fertige sieht nun so aus momentan , die fast identische Schleife stört noch. Des weiteren muss ich noch schaun ob das noch weiter optimiert werden kann dann.

Code:
// in der variable range ist ein objekt das besagt wie viele spalten ich mich nach 
// links bzw rechts bewegen kann oder aber nach Reihen oben und unten
// 
// fF ist das erste feld der Matrix die verschoben werden soll

while ( sR < 3 && !found) {

            row = 0;
            fields = [];
            
            // SUCHE NACH OBEN
            do {
                if ( row === -sR ){
                    
                    for(var i = 0 ; i >= -sR; i-- ) {
                        if ( range.cols[0] > i) break;
                        
                        var field = fF + ( row * me.cols + i);
                        if ( spaceAvailable(field, cols, rows) ){
                            found = field;
                            break;
                        }
                        
                    }
                    
                    if ( !found && range.cols[1] >= 1) {
                        for(var i = 1 ; i <= sR; i++ ) {
                            var field = fF + ( row * me.cols + i);
                            if ( spaceAvailable(field, cols, rows) ){
                                found = field;
                                break;
                            }
                        }
                    }
                    
                } else {
                   /**
                    * Reihe 0 maximal 2 Felder sind zu überprüfen das Feld 
                    * in der Mitte ist das erste Feld der Matrix die verschoben
                    * werden soll und soll ja dort verschwinden
                    */
                   for(var i = -1; i < 2 ; i+=2){
                        if ( i < 0 && range.cols[0] <= i || i > 0 && range.cols[1] >= i) {
                            field  = fF + (row * me.cols + sR * i);
                            if ( spaceAvailable(field, cols, rows) ){
                                found = field;
                                break;
                            }
                        }
                   }
                }
                row--;
            } while( range.rows[0] <= row && !found);

            /*
             * @TODO
             * schaut genau so aus wie top nur mit dem Unterschied row++ und nicht row--
             */
            row = 1;
            while ( range.rows[1] >= row && !found ){
                
                if ( row === sR ){
                    
                    for(var i = 0 ; i >= -sR; i-- ) {
                        var field = fF + ( row * me.cols + i);
                        if ( spaceAvailable(field, cols, rows) ){
                            found = field;
                            break;
                        }
                        
                    }
                    
                    if ( !found && range.cols[1] >= 1) {
                        for(var i = 1 ; i <= sR; i++ ) {
                            var field = fF + ( row * me.cols + i);
                            if ( spaceAvailable(field, cols, rows) ){
                                found = field;
                                break;
                            }
                        }
                    }
                    
                } else {
                   /**
                    * Reihe 0 maximal 2 Felder sind zu überprüfen das Feld 
                    * in der Mitte ist das erste Feld der Matrix die verschoben
                    * werden soll und soll ja dort verschwinden
                    */
                   for(var i = -1; i < 2 ; i+=2){
                        if ( i < 0 && range.cols[0] <= i || i > 0 && range.cols[1] >= i) {
                            field  = fF + (row * me.cols + sR * i);
                            if ( spaceAvailable(field, cols, rows) ){
                                found = field;
                                break;
                            }
                        }
                   }
                }
                row++;
            };

            if ( found )
                break;
            
            sR++;
        }
        
        function spaceAvailable( field, cols, rows ){
            var matrix = me.calculateCellMatrix( field, cols, rows);
            return !me.calculateCellIntersection( matrix, me.tempCellhash).length;
        }