Java Labyrinth

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

    • Java Labyrinth

      hey leute
      ich hab in java ein programm geschrieben, welches ein labyrinth - aufgebaut auf zeichen in einem array - erstellt
      und dann einen weg durch dieses finden soll (rekursiver algo).

      es sollte funktionieren, tut es aber nicht.
      ich kann ums verrecken keinen fehler finden.
      könnt ihr mir weiterhelfen?

      hier mein code:

      public class Maze {

      static char[][] maze =new char[10][10];
      final static int[] STEPX = { 0, 1, 0,-1 };
      final static int[] STEPY = { -1, 0, 1, 0 };
      static int step, aktX, aktY;


      static void createMaze(){

      for(int i=0;i<10;i++){
      maze[0]='X';
      maze[i][0]='X';
      maze[9][i]='X';
      maze[i][9]='X'; //erstellen der Ränder

      }

      for(int k=1; k<9;k++){
      for(int j=1;j<9;j++){
      Random rWall = new Random(0, 2);
      int wall=rWall.readInt();
      if(wall==0){
      maze[k][j]='X'; //mit zufälligen Wänden befüllen
      }else{
      maze[k][j]=' ';
      }
      }
      }

      maze[1][1]='A';
      maze[8][8]='Z'; //setzen von Anfang und Ziel

      }

      static boolean findWay(char[][] maze1, int i, int j){

      int step = -1;
      while (step != 3) {
      step ++;
      int newX = i + STEPX[step];
      int newY = j + STEPY[step];

      boolean ok = true;

      if (newX < 1 || newX >= 8) ok = false;
      if (newY < 1 || newY >= 8) ok = false;
      if (ok && maze1[newX][newY] !=' ') ok = false;

      if(ok){
      maze1[newX][newY] = '*';

      if (!ausgangGefunden(newX, newY)) {
      // rekursiver Aufruf von findWay
      if (findWay(maze1, newX, newY)) {
      // Lösung gefunden
      return true;
      } else {
      maze1[newX][newY] = ' ';
      }
      } else return true;
      }
      }//while
      return false;
      }

      private static boolean ausgangGefunden(int newX, int newY) {

      if(newX==8 && newY==8){
      return true;
      }
      return false;
      }

      static void printMaze(){

      for(int i=0;i<10;i++){
      for(int j=0;j<10;j++){
      System.out.print(maze[i][j]);
      }
      System.out.println();
      }
      System.out.println();

      }

      public static void main (String[] args) {

      createMaze();
      printMaze();
      boolean b = findWay(maze, 1, 1);
      if (b) System.out.println("Weg gefunden");
      else System.out.println("Keinen Weg gefunden");
      printMaze();


      }


      }


      MfG

    • Hallo,

      Gut wäre es, wenn du das nicht funktionieren des Programms besser beschreibst, dann kann man sich kritische Stellen anschauen, ohne sich in das ganze Programm einarbeiten zu müssen. Wenn du nicht weißt wo es hapert, kannst du entweder einen Debugger drüber laufen lassen und das Programm zeile für zeile abarbeiten lassen oder deinen Code künstlich durch Benutzereingaben anhalten und Variablen, die gerade wichtig sind ausgeben lassen. Damit solltest du die Stelle, die nicht funktioniert sehr gut einkreisen können und ggf. auch selber eine Lösung finden.

      Tray

      Quellcode

      1. main()
      2. {
      3. for(;;)
      4. printf("DotaInside - ich war dabei!\n");
      5. }


    • es sollte funktionieren, tut es aber nicht.

      Mit so einer Fehlermeldung wird dir weder hier, noch sonst in nem Java-Forum wer antworten.
      Kriegst du ne Fehlermeldung? GGF SYSOUTS printen um zu sehen, wo er hängen bleibt.
      Schonmal was von nem Debugger gehört?
      Wenn ja, Debuggen und gucken wo er hängen bleibt.
      Hast du dir überlegt, daß es einfach keine Möglichkeit geben kann zum Ziel zu finden? Wie schließt du das aus? Brauchen doch bloß zufällig 3 Wände neben dem Startblock erscheinen und schon kann man garkeinen Weg finden.

      edit:
      eben noch aufgefallen:
      if (ok && maze1[newX][newY] !=' ') ok = false;

      hier sagst du auch ganz klar, daß er seinen weg nicht zurückgehen kann, das heißt sobald er in irgendeine sackgasse läuft, gehtsnicht mehr weiter, er is in ner endlosschleife gefangen.
      du musst also * noch als Feld erlauben und solltest ne Priorität machen:
      Wand = Da darfst nicth hin
      * (da war ich schon) = Nur dann zurückgehen, wenn nix freies mehr erreichbar
      ' ' (da war ich noch nicht) = Primär hier hingehen, wenn mein Step das möchte, ansonsten neuen Step wählen.

      Du hast ja von jedem Punkt aus 8 Möglichkeiten zu laufen (weil du diagonal ja erlaubst).

      Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von henpara ()

      Ich bin nur hier weil Dotacontents!

    • ich habe das hier leider jetzt erst gelesen.

      zum einen musst du ihn auch parallel laufen lassen (ok, musst du nicht, aber läuft er nur waagerecht und senkrecht ist die wahrscheinlichkeit deutlich kleiner, dass ein weg zum ziel existiert)
      und zum anderen musst du, wie der vorposter schon erwähnt hat, prioriäten setzen und erst auf freie felder (' ') gehen und dir dann die schon begangenen felden ('*') merken.

      zudem ist mir noch aufgefallen, dass du das ziel aufgrund dieser zwei abfragen nie erreichen kannst

      Quellcode

      1. if (newX < 1 || newX >= 8) {
      2. ok = false;
      3. }
      4. if (newY < 1 || newY >= 8) {
      5. ok = false;
      6. }


      hier sagst du ja eindeutig, dass er position [8][8], wo das ziel ('Z') ja sitzt nie auf "boolean ausgangGefunden(int newX, int newY)" abfragen kann.
      der vergleich muss also auf newX/newY > 8 sein.

      ich hab den code mal überarbeitet und folgende dinge eingebaut(is auch an den stellen entsprechend kommentiert):

      - kann in 8 richtungen gehen
      - wartet wenn er ein schon begangenes feld findet erstmal ab, ob noch ein freies feld in seiner umgebung liegt und merkt sich solange wo der ausweg ('*') war
      - einige if abfragen ein wenig überarbeitet und hinzugefügt

      hier mal der komplette code jetzt (ich behaupte nicht, dass das eine optimale lösung oder sonstiges ist, aber so funktioniert der alrorithmus. er findet immer seinen weg zum ziel, auch wenn dies meist nicht der optimale weg ist, was wohl auch nicht der anspruch des algos ist wenn ich mir den so anschau ;) )

      Java-Quellcode

      1. import java.util.Random;
      3. public class Maze {
      5. static char[][] maze = new char[10][10];
      6. final static int[] STEPX = { 0, 1, 1, 1, 0, -1, -1, -1 }; // jetzt alle 8 Richtungen möglich
      7. final static int[] STEPY = { -1, -1, 0, 1, 1, 1, 0, -1 };
      8. static int step, aktX, aktY;
      9. static boolean hasResort = false;
      11. static void createMaze() {
      13. for (int i = 0; i < 10; i++) {
      14. maze[0][i] = 'X';
      15. maze[i][0] = 'X';
      16. maze[9][i] = 'X';
      17. maze[i][9] = 'X'; // erstellen der Ränder
      19. }
      21. for (int k = 1; k < 9; k++) {
      22. for (int j = 1; j < 9; j++) {
      23. Random rWall = new Random();
      24. int wall = rWall.nextInt(3);
      25. if (wall == 0) {
      26. maze[k][j] = 'X'; // mit zufälligen Wänden befüllen
      27. } else {
      28. maze[k][j] = ' ';
      29. }
      30. }
      31. }
      33. maze[1][1] = 'A';
      34. maze[8][8] = 'Z'; // setzen von Anfang und Ziel
      36. }
      38. static boolean findWay(char[][] maze1, int i, int j) {
      40. int step = -1;
      41. while (step != 7) { // nun != wegen 8 Richtungen
      42. step++;
      43. int newX = i + STEPX[step];
      44. int newY = j + STEPY[step];
      46. boolean ok = true;
      48. if (newX < 1 || newX > 8) { // Ziel darf nun auf ausgangGefunden() überprüft werden
      49. ok = false;
      50. continue; // springt sofort in die nächste iteration der schleife -> kleine performance-optimierung
      51. }
      52. if (newY < 1 || newY > 8) {
      53. ok = false;
      54. continue;
      55. }
      56. if ((maze1[newX][newY] == 'X') || (maze1[newX][newY] == 'A')) {
      57. ok = false;
      58. continue;
      59. }
      60. if (maze1[newX][newY] == '*') {
      61. if (!hasResort) { // merkt sich Ausweg falls kein freies Feld (' ') mehr kommt
      62. saveResort(newX, newY);
      63. }
      64. hasResort = true;
      65. ok = false;
      66. continue;
      67. }
      68. if (maze1[newX][newY] != ' ' && (STEPX[step] == -1 && STEPY[step] == -1)) { // nutzt Ausweg
      69. newX = aktX;
      70. newY = aktY;
      71. hasResort = false;
      72. ok = true;
      73. }
      75. if (ok) {
      76. if (maze1[newX][newY] == ' '){
      77. maze1[newX][newY] = '*';
      78. }
      79. if (!ausgangGefunden(newX, newY)) {
      80. // rekursiver Aufruf von findWay
      81. if (findWay(maze1, newX, newY)) {
      82. // Lösung gefunden
      83. return true;
      84. } else {
      85. maze1[newX][newY] = ' ';
      86. }
      87. } else {
      88. return true;
      89. }
      90. }
      91. }// while
      92. return false;
      93. }
      95. private static boolean ausgangGefunden(int newX, int newY) {
      97. if (newX == 8 && newY == 8) {
      98. return true;
      99. }
      100. return false;
      101. }
      103. private static void saveResort(int pX, int pY) {
      104. aktX = pX;
      105. aktY = pY;
      106. }
      108. static void printMaze() {
      110. for (int i = 0; i < 10; i++) {
      111. for (int j = 0; j < 10; j++) {
      112. System.out.print(maze[i][j]);
      113. }
      114. System.out.println();
      115. }
      116. System.out.println();
      118. }
      120. public static void main(String[] args) {
      122. createMaze();
      123. printMaze();
      125. boolean b = findWay(maze, 1, 1);
      127. if (b)
      128. System.out.println("Weg gefunden");
      129. else
      130. System.out.println("Keinen Weg gefunden");
      131. printMaze();
      133. }
      135. }
      Alles anzeigen


      mfg
      Dis


      edit:

      was mir eben noch eingefallen ist:

      durch die anornung von start und zielpunkt könnte man die wegfindunung in den meisten fällen wohl optimieren in dem man die zwei arrays STEPX und STEPY umsortiert.
      da er tendenziell nach rechts unten muss könnte man die arrays so sortieren, dass er zuerst die drei felder rechts( +1, 0), rechts-unten(+1,+1) und unten(0,+1) abfragt.

      mfg

      Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von Disaster ()