Labyrinth via Backtracking

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • Labyrinth via Backtracking

    Hi, ich bin nicht wirklich gut im programmieren, wollte deshalb eure Hilfe..
    Ich will ein Labyrinth Programmieren und das dann auch grafisch alles schön daarstellen..
    Das er das Labyrinth aus einer Textdatei ausliest, es daarstellt, den Weg den er geht daarstellt, zeitverzögerung einstellen lässt... funktioniert alles prächtig -.-
    Jetzt liegt es wirklich nur noch am Algorithmus den ich einfach nicht hinbekomme...
    Hier mein Code ich hoffe ihr könnt mir helfen:

    Quellcode

    1. void __fastcall TForm1::FindeWeg(int x, int y)
    2. {
    3. if (lab[x][y] == 'Z')
    4. {
    5. gefunden = true;
    6. }
    7. if (!gefunden && lab[x+1][y] != '#') {
    8. Green(x+1,y);
    9. FindeWeg(x+1,y);
    10. White(x+1,y);
    11. }
    12. if (!gefunden && lab[x][y+1] != '#') {
    13. Green(x,y+1);
    14. FindeWeg(x,y+1);
    15. White(x,y+1);
    16. }
    17. if (!gefunden && lab[x][y-1] != '#') {
    18. Green(x,y-1);
    19. FindeWeg(x,y-1);
    20. White(x,y-1);
    21. }
    22. else
    23. {
    24. }
    25. }
    Alles anzeigen


    lab[][] ist das Labyrinth: '#' bedeutet eine Mauer, '~' bedeutet ein begehbares Feld, 'A' und 'Z' sind Anfang und Ziel
    Die Funktionen Green und White färben das jeweilige Feld in der Farbe.
  • Also eine Textdatei die eingelesen wird koennte zum Beispiel so aussehen:

    Quellcode

    1. ####################
    2. #A~~~~~~~~~~~~~~~~~#
    3. #~~~~~~~~~~~~~~~~~~#
    4. #~~~~~~~~~~~~~~~~~~#
    5. #~~~~~~~~~~~~~~~~~~#
    6. #~~~~~~~~~~~~~~~~~~#
    7. #~~~~~~~~~~~~~~~~~~#
    8. #~~~~~~~~~~~~~~~~~~#
    9. #~~~~~~~~~~~~~~~~~~#
    10. #~~~~~~~~~~~~~~~~~~#
    11. #~~~~~~~~~~~~~~~~~~#
    12. #~~~~~~~~~~~~~~~~~~#
    13. #~~~~~~~~~~~~~~~~~~#
    14. #~~~~~~~~~~~~~~~~~~#
    15. #~~~~~~~~~~~~~~~~~~#
    16. #~~~~~~~~~~~~~~~~###
    17. #~~~~~~~~~~~~~~~~###
    18. #~~~~~~~~~~~~~~~~~##
    19. #~~~~~~~#~~~~~~~~~Z#
    20. ####################
    Alles anzeigen


    lab[][] ist halt die Matrix in der diese Textdatei steht..
    Dann wird sie eingelesen und daargestellt, jetzt soll sie möglichst noch gelöst werden...
    So sieht das ganze aus (bis jetzt):

  • und wo genau liegt das Problem? Der Algorithmus sieht erstmal garnicht soo verkehrt aus. Nur ein paar kleine Punkte, die ich anders machen würde:
    1. Überprüfst du irgendwo, ob du nicht über die Feldgrenzen (und damit auch über Array) hinausläufst? Klar wenn das Feld immer komplett ausenrum mit # abgegrenzt ist dürfte das nicht passieren, aber ich würde es trotzdem immer überprüfen.
    2. Ich würde in alle 4 Richtungen weitersuchen, du hast ja jetzt keine Möglichkeit nach x-1 zu kommen, was in manchen labyrinths ja nötig sein kann
    3. Dann solltest du unbedingt markieren, wo du schon warst, sonst kommst du in endlosschleifen. Das machst du ja auch schon mit den Farben, allerdings sind die ja nur für die Darstellung und für den Algorithmus unerheblich. Du könntest dafür ein neues Zeichen einführen oder einfach # benutzen. Dann setzt du einfach immer wenn du gerade ein Feld überprüfst im Array an entsprechende Stelle ein # und wenn du am Ende der Funktion bist und keinen Weg gefunden hast, setzt du es wieder zurück auf ~.

    Hoffe das hilft ;)