java - Algorytm generowania losowej ścieżki w 2d tablicy char

Question

Próbuję wygenerować losowy ścieżkę od punktu do drugiego w 2 wymiarowej tablicy char, ale tak, że to według poniższych zasad:

• Jedyne znaki są dozwolone: ​​
  • O = Otwórz ścieżka
  • - = akceptuje ścieżki od lewej to lub od jego prawy
  • | = akceptuje ścieżki z jego górną lub od jego dolne
  • \ = akceptuje ścieżki od: top do lewo, lewo do top, dolny do prawo i prawo na dole.
  • / = akceptuje ścieżki z: dolny do lewej, lewo do dolny, prawo do górnej i góry do prawo
  • "akceptuje ścieżki" oznacza że inne ścieżki (/-|\) mogą łączyć się tylko z boków speficied.

Oto obraz zrozumieć znaki i co robią: (- na czerwono, \ w kolorze niebieskim, / na zielono, | w kolorze pomarańczowym)

• Ścieżka nie może się przecinać sama - może poruszać się tylko w otwartych miejscach (Ścieżki otwarte: O). Wyobraź sobie ścieżkę wyników jako węża, ukochaną grę - nie może przejść przez siebie.
• Tablica 2d może mieć dowolny rozmiar
• Zakończenie może prowadzić w dowolnym miejscu - Nie jest oznaczone przez X lub jakikolwiek znak podobny do tego, ale musi być logiczne.

prawidłowych Wyjścia:

Start: (0, 0), koniec (3, 3)

START-> - - \ O 
     O O \ \ 
     O/-/
     O \ - \ <- END 

Pierwszym przykładem jest w zasadzie to:

Początek: (1, 0), koniec: (1, 4)

START v 
    O - \ O O 
    /-/O O 
    \ - - - \ 
    O O O O | 
    O - - -/
    ^END 

Drugi przykład jest w zasadzie tak:

Próbuję accompilsh to za pomocą tego kodu, ale z jakiegoś powodu nie działa:

Kod:

int x, y, mapsize; 
char[][] map; 
public Random rand = new Random(); 
public boolean findPath(int x, int y, int xGoal, int yGoal){ 
    if(x==xGoal&&y==yGoal)return true; 
    int[] avilableMovement = avilableMovement(x, y); 
    if(avilableMovement==null)return false; 
    int moveX = avilableMovement[0]; 
    int moveY = avilableMovement[1]; 
    map[moveX][moveY]=mark(x, y, moveX, moveY); 
    if(findPath(moveX, moveY, xGoal, yGoal))return true; 
    return false; 
} 
public char mark(int fromX, int fromY, int toX, int toY){ 
    //If moved to up/down and <>, mark | 
    //If moved to <> and left/right, mark - 
    //If moved to up and left, or to down and right, mark \ 
    //If moved to up and right, or to down and left, mark/
    boolean toUp = fromY<toY; 
    boolean toDown = fromY>toY; 
    boolean toRight = fromX<toX; 
    boolean toLeft = fromX>toX; 
    if((toUp||toDown)&&!(toLeft||toRight)){ 
     return '|'; 
    } 
    if((toLeft||toRight)&&!(toUp||toDown)){ 
     return '-'; 
    } 
    if((toUp&&toLeft)||(toDown&&toRight)){ 
     return '\\'; 
    } 
    if((toUp&&toRight)||(toDown&&toLeft)){ 
     return '/'; 
    } 
    return '?'; 
} 
private boolean onMap(int x, int y){ 
    return x>0&&y>0&&x<mapsize&&y<mapsize; 
} 
private int[] avilableMovement(int x, int y){ 
    ArrayList<Integer> numsX = new ArrayList<>(Arrays.asList(-1+x, 0+x, 1+x)); 
    ArrayList<Integer> numsY = new ArrayList<>(Arrays.asList(-1+y, 0+y, 1+y)); 
    Collections.shuffle(numsX); 
    Collections.shuffle(numsY); 
    //^^ Making it random instead of going in same order every timee 
    for(int lx : numsX){ 
     for(int ly : numsY){ 
      if(onMap(y+ly, x+lx)&&map[y+ly][x+lx]=='O'){ 
       return new int[]{x+lx, y+ly}; 
      } 
     } 
    } 
    return null; 
} 

Po uruchomieniu kodu za pomocą t jego kod,

private void initMap(int mapsize){ 
    this.mapsize=mapsize; 
    map = new char[mapsize][mapsize]; 
    for(int i = 0; i<mapsize; i++){ 
     for(int j = 0; j<mapsize; j++){ 
      map[i][j]='O'; 
     } 
    } 
} 
public static void main(String[] args){ 
    Main main = new Main(); 
    main.initMap(4); 
    System.out.println(main.findPath(0, 0, 3, 3)); 
    for(char[] ch : main.map){ 
     System.out.println(ch); 
    } 
} 

Utrzymuje wyprowadzanie błędne & nielogiczne ścieżki, takie jak:

OOOO 
O/OO 
O-OO 
O-OO 

lub (o wielkości 6) mapy:

OOOOOO 
O/OOOO 
O-OOOO 
OOO/OO 
OOOOOO 
OOOOOO 

Nie wiem, dlaczego to dzieje się. Czy ktoś może mi powiedzieć, co jest nie tak z moim kodem i pomóc mi rozwiązać ten problem?

Z góry dziękuję!

P.S: Zanim zapytasz, nie, to nie jest zadanie domowe.

EDYCJA: Zaktualizowałem swój kod, a teraz metoda zwraca wartość true i kończy się, ale jest problem. Mój zaktualizowany kod:

public Random rand = new Random(); 
public boolean findPath(int x, int y, int xGoal, int yGoal){ 
    if(x==xGoal&&y==yGoal)return true; 
    int[] avilableMovement = avilableMovement(x, y); 
    if(avilableMovement==null)return false; 
    int moveX = avilableMovement[0]; 
    int moveY = avilableMovement[1]; 
    map[moveX][moveY]=mark(x, y, moveX, moveY); 
    if(findPath(moveX, moveY, xGoal, yGoal))return true; 
    return false; 
} 
public char mark(int fromX, int fromY, int toX, int toY){ 
    //If moved to up/down and <>, mark | 
    //If moved to <> and left/right, mark - 
    //If moved to up and left, or to down and right, mark \ 
    //If moved to up and right, or to down and left, mark/
    boolean toUp = fromY<toY; 
    boolean toDown = fromY>toY; 
    boolean toRight = fromX<toX; 
    boolean toLeft = fromX>toX; 
    if((toUp||toDown)&&!(toLeft||toRight)){ 
     return '|'; 
    } 
    if((toLeft||toRight)&&!(toUp||toDown)){ 
     return '-'; 
    } 
    if((toUp&&toLeft)||(toDown&&toRight)){ 
     return '\\'; 
    } 
    if((toUp&&toRight)||(toDown&&toLeft)){ 
     return '/'; 
    } 
    return 'O'; 
} 
private boolean onMap(int x, int y){ 
    return x>0&&y>0&&x<mapsize&&y<mapsize; 
} 
private int[] avilableMovement(int x, int y){ 
    ArrayList<Integer> numsX = new ArrayList<>(Arrays.asList(-1+x, x, 1+x)); 
    ArrayList<Integer> numsY = new ArrayList<>(Arrays.asList(-1+y, y, 1+y)); 
    Collections.shuffle(numsX); 
    Collections.shuffle(numsY); 
    //^^ Making it random instead of going in same order every timee 
    for(int lx : numsX){ 
     for(int ly : numsY){ 
      if(onMap(ly, lx)&&map[ly][lx]=='O'){ 
       return new int[]{lx, ly}; 
      } 
     } 
    } 
    return null; 
} 

mój główny kod:

Main main = new Main(); 
    main.initMap(4); 
    boolean b = main.findPath(0, 0, 3, 3); 
    while(!b)b = main.findPath(0, 0, 3, 3); 
    for(int i = 0; i<main.mapsize; i++){ 
     for(int j = 0; j<main.mapsize; j++){ 
      System.out.print(main.map[j][i]); 
     } 
     System.out.println(); 
    } 

widzę na wyjściu, że osiągnie swój ostateczny destenation, ale nie pokazuje początek. Dlaczego?

Oto kilka przykładowych wyjścia z nowego, zaktualizowanego kodu:

OOOO 
O/OO 
O/OO 
O--- 

OOOO 
O//- 
OO/O 
OOO| 

Jak widać, wyjścia nadal nie ma sensu, ale jest bliżej niż wcześniej: P To nie dokładnie przestrzegać zasad i nie pokazuje początku. Dlaczego?

Answer 1

Widzę kilka błędów (nie uruchomiłem Twojego kodu).

1.Głównym problemem jest to, że prawdopodobnie mieszane xiy współrzędne w swojej logiki i wyjście na ekranie, spróbuj zmienić

for(char[] ch : main.map){ 
    System.out.println(ch); 
} 

coś jak

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

Tj zmienić zapętlenie przez współrzędne X i Y dla wyjścia

2. Prawdopodobnie niepoprawnie obliczyć następne współrzędne od x, y w funkcji avilableMovement. lx i ly zawiera już x i y, tj dodasz x i y 2 razy x+lx, y+ly:

ArrayList<Integer> numsX = new ArrayList<>(Arrays.asList(-1+x, 0+x, 1+x)); 
ArrayList<Integer> numsY = new ArrayList<>(Arrays.asList(-1+y, 0+y, 1+y)); 
Collections.shuffle(numsX); 
Collections.shuffle(numsY); 
for(int lx : numsX){ 
    for(int ly : numsY){ 
     if(onMap(y+ly, x+lx)&&map[y+ly][x+lx]=='O'){ 
      return new int[]{x+lx, y+ly}; 

3.You nie zwracają znak „O” na komórce, jeśli ścieżka nie jest zaczerpnięty w bieżącej komórce i nie zaznaczasz następnego możliwego ruchu:

map[moveX][moveY]=mark(x, y, moveX, moveY); 
if(findPath(moveX, moveY, xGoal, yGoal))return true; 
return false; 

Answer 2

Oto kolejny pomysł do rozważenia. Począwszy od prostej drodze, na przykład, proste wzdłuż osi x, następnie prosto wzdłuż osi Y (lub vice versa), od początku do końca,

start--\ 
     | 
     |  
     | 
     \end 

można zmodyfikować drogę przy użyciu wstępnie ustawiony słownika opcji. Dla każdej komórki znajdującej się pomiędzy dwoma innymi na ścieżce (która wyklucza komórki początkowe i końcowe), definiujemy 6 możliwości, z których każda ma dwa sposoby modyfikacji. W kolejnych dwóch przykładach mamy do czynienia jedynie z modyfikacji środkowy komórkę x:

(1) cell is connected from west and east: 

    o x o 

we can move x either north or south: 

/x \ 
    o o or o o 
      \ x/

(2) cell is connected from west and south: 

    o x 
    o 

we can move x either north or east: 

/x 
    o | or o - x 
    o  o/

Ponieważ komórki nie mogą być podłączone za pomocą przekątnych, istnieją tylko 4 choose 2 = 6 konfiguracje do rozważenia. Możemy łatwo stworzyć słownik opcji do losowego wypróbowania, w oparciu o konfiguracje delta komórek na ścieżce. Dwa powyższe przykłady będą następujące:

(dictionary key) (dictionary value) 
Δx1 Δy1 Δx2 Δy2 
1 0 -1 0 => try north or south 
1 0 0 -1 => try north or east