Labyrinth lösen

Faabi

Mitglied
Hi,
ich bin hier im Forum neu und hab folgendes Problem. Ich bin dabei ein Programm zu schreiben, welches ein als .png gespeichertes Labyrinth lösen soll. Der Startpunkt ist vorgegeben, das Ziel jedoch nicht.

Falls jemand das Bild mit dem Labyrinth sehen will, findet mans hier:

Meine Idee wäre gewesen vom Startpunkt aus (weißes Feld) alle anliegenden Pixel zu überprüfen, ob sie schwarz sind oder nicht. Wenn schon, dann mach nichts. Falls nicht, färbe den Pixel weiß und beginne von vorne.

Ich bin in der Programmiersprache Java noch relativ neu, deswegen weiß ich noch nicht wirklich, was es hier alles an möglichkeiten gibt. Ich hab schon im Internet geforscht und versucht ein paar Sachen aus meiner urspünglichen Programmiersprache C zu übernehmen, komme jedoch nicht weiter.

Mein bisheriger Code:
Code:
public class LindwurmLoesen {

    public static void main(String[] args) {
        
        File file = new File("/*Dateipfad*/");
        BufferedImage image = ImageIO.read(file);
        
        System.out.println("Breite:" + image.getWidth());
        System.out.println("Höhe:" + image.getHeight());
                
        
        int startx = 659;
        int starty = 488;
                
        
        for(int i = 0; i <= 10; i++) {        // andere bedingung finden
            
            // überprüfe ob anliegende pixel von start-pixel schwarz sind
            // wenn ja: mache gar nichts
            // wenn nein: färbe weiß und wiederhole prüfung
            
            if(/*anliegende pixel von aktuellem pixel != schwarz*/) {
                
                // färbe pixel weiß
                
                continue;
            }
            else if(/*anliegende pixel von aktuellem pixel == schwarz*/) {
                
                // mache nichts
                continue;
            }
            
        }
        
        
        System.out.println("Programm abschgeschlossen!");

    }

}

Bevor jetzt irgendwer fragt warum ich es nicht in C mache, wenn es schon mein urprüngliche Sprache ist: Die Vorgabe ist, dies in Java zu lösen.

Könnte mir irgendwer helfen dieses Rätsel zu lösen bzw. zumindest einen Lösungsansatz zu finden? Falls es noch irgendwelche Fragen gibt, immer her damit.
 

LimDul

Top Contributor
Was genau heißt lösen? Zeigen das es einen Ausgang gibt? Den kürzesten Pfad zum Ausgang finden? Muss nur der Weg zum Ausgang weiß eingefärbt werden? Oder dürfen alle erreichbaren Wege weiß eingefärbt werden?

Es gibt eine Menge Wegfindungs-Algorithmen, das hängt jetzt etwas von der konkreten Aufgabenstellung ab.

Ich würde aber nicht die Felder weiß färben, sondern die Daten intern verwalten (z.B. ein 2D-array anlegen in der Größe des Bildes). Damit kannst du strukturierter die Informationen verwalten.
 

Faabi

Mitglied
Ziel ist es, alle erreichbaren Wege weiß einzufärben.

Ich hab mich auch nochmal mit ein paar Freunden und Azubi-Kollegen (bin selbst einer) unterhalten, und die meinten irgendwas mit getPixel(), setPixel() und Robot. Hab aber nicht genau verstanden was damit gemeint war.
 

LimDul

Top Contributor
Aufgrund der Bildgröße würde ich keinen rekursiven Ansatz wählen, sondern einen iterativen.

In natürlicher Sprache würde der Algorithmus rekursiv so aussehen:

1. Für jeden benachbarten Pixel:
1.1 Ist er weiß oder schwarz? => Mache mit dem nächsten Pixel weiter
1.2 Färbe ihn weiß und bewege dich auf ihn. Fange erneut mit diesem Pixel bei 1 an.

Sprich, du schaust dir die nachbar Pixel an und wenn du da noch nicht warst (Also er nicht weiß ist) und du da hin darfst (also nciht schwarz ist), dann bewegst du dich da hin. Wenn du in eine Sackgasse bist, gehst du wieder zurück, bist du einem Pixel stehst, wo ein Nachbarpixel noch nicht weiß oder schwarz ist. Wenn du wieder am Start bist und alles weiß ist um den Start, weißt du bist fertig.

Rekursiv wäre es relativ einfach zu implementieren, aber ich glaube bei der Bildgröße gibt es StackOverFlowErrors.
Für einen iterativen Ansatz brauchst du:

* Eine Datenstruktur (Liste oder Stack) wo du den aktuellen Weg, den du gegangen bist (x/y-Koordinate speicherst)
* Dort wird der Startpunkt reingepackt
* Dann eine Schleife die solange läuft, bis die Liste leer ist
* Für das letzte Element aus der Liste werden alle Nachbarpixel geprüft.
* Wenn einer der Nachbarpixel nicht weiß/schwarz ist, wird er an das ende der Liste gepackt und an den Anfang der äußeren Schleife gesprungen (also die Schleife "prüfe alle Nachbarpixel") abgebrochen
* Wenn alle Nachbarpixel weiß oder schwarz sind, wird das letzte Element aus der Liste entfernt
 

MoxxiManagarm

Top Contributor
Theoretisch kannst du das Ziel eines Labyrinths immer erreichen, wenn du dich an eine Richtung hältst - z.B. immer rechts an der Wand entlang laufen. Ich bin mir nicht sicher, ob man das Gleiche Prinzip auch in jedem Fall für erreichbare Felder einsetzen kannst, aber ein Versuch wäre es wert finde ich
 

LimDul

Top Contributor
Theoretisch kannst du das Ziel eines Labyrinths immer erreichen, wenn du dich an eine Richtung hältst - z.B. immer rechts an der Wand entlang laufen. Ich bin mir nicht sicher, ob man das Gleiche Prinzip auch in jedem Fall für erreichbare Felder einsetzen kannst, aber ein Versuch wäre es wert finde ich

Nein das klappt aus mehreren Gründen nicht:

* Werden damit nur die Pixel markiert, die direkt an Wänden liegen, die anderen nicht (also die "Mitte" eines Raums
* Generell werden damit nur die äußeren Wände markiert. Stell dir ein Labyrinth vor, was vierreckig ist und außen ein Gang komplett rumführt und innen noch ganz viele Wände sind. Wenn du an der Außenwand startest kommst du nie nach inne.
 

Ähnliche Java Themen


Oben