Labirynt i najkrotsza trasa
Strona [ 1 ] z 1
| tetrycz |
08-02-2010 16:44 |
|
Użytkownik Status: Offline Dołączył: 08-02-2010 |
Witam serdecznie. Szukalem pomocy w internecie ale nie moglem nic 1. Wczytuje z pliku labirynt w postaci: ###### E0000# ###0## ###X## gdzie: E-Start X-koniec 0-droga #-sciana Konstruktor: Labirynt z pliku zapisuje do macierzy gdzie kazde pole w macierzy sklada sie ze znaku(char) i pola(boolean) oznaczajace czy bylo odwiedzone. Labirynt(String filename){ this.filename=filename; linie=new ArrayList<String>(); try{ BufferedReader in=new BufferedReader (new FileReader(filename)); while (in.ready()){ linie.add(in.readLine()); } in.close(); }catch(Exception e){ System.out.println(e); } //tworzymy macierz o wymiarach labiryntu i wrzucamy do niej odpowiednie znaki col=linie.get(0).length(); row=linie.size(); //System.out.println(col+" "+row); tablica=new TypTablicy[row][col]; //dla kazdej komorki tworzymy obiekt typu TypTablicy() //i ustawiamy odpowiedni znak for(int i=0;i<row;i++){ for(int j=0;j<col;j++){ tablica[i][j]=new TypTablicy(); setPoint(i,j,linie.get(i).charAt(j)); } } //szukamy poczatku labiryntu for(int i=0;i<row;i++){ for(int j=0;j<col;j++){ if(getPoint(i,j)=='E'){ startX=i; startY=j; } } } } i teraz najwazniejsze, funkcja ktora szuka wyjscia z labiryntu: void szukajWyjscia(int x,int y){ //szukaj dopoki nie trafisz na X if(getPoint(x,y)!='X'){ //szuka w swoim otoceniu '0' badz 'X' i sprawdza czy nie byly juz odwiedzone if(((getPoint(x,y+1)=='0') || getPoint(x,y+1)=='X') && !checkVisited(x,y+1)){ System.out.println("prawo");//wypisuje a ekran w ktora strone w labiryncie sie poruszamy setVisited(x,y+1); szukajWyjscia(x,y+1); } if(((getPoint(x+1,y)=='0') || getPoint(x+1,y)=='X') && !checkVisited(x+1,y)){ System.out.println("dół"); setVisited(x+1,y); szukajWyjscia(x+1,y); } if(((getPoint(x-1,y)=='0') || getPoint(x-1,y)=='X') && !checkVisited(x-1,y)){ System.out.println("góra"); setVisited(x-1,y); szukajWyjscia(x-1,y); } if(((getPoint(x,y-1)=='0') || getPoint(x,y-1)=='X') && !checkVisited(x,y-1)){ System.out.println("lewo"); setVisited(x,y-1); szukajWyjscia(x,y-1); } }else{ System.out.println("Wyjscie"); System.exit(0); } } Wynik dzialania takiego programu: prawo prawo prawo prawo //jak widac tutaj wyskakuje i nie ma juz co zrobic dół //a tutaj wykonuje tak jakby osobny watek ktorym dochodzi do wyjscia dół Wyjscie no i teraz pytanie: Jak wyodrebnic z tego tylko i wylacznie poprawna sciezke tzn. zeby plik wyjsciowy wygladal tak jak ten wyzej pogrubiona czcionka. Jakby cos bylo nie jasne to pisczie, moglem cos przeoczyc. Z góry dzieki za pomoc. Ostatnio zmodyfikowany: 08-02-2010 16:52 przez tetrycz |
|
|
| konrad.g |
08-02-2010 17:46 |
![]() Użytkownik Status: Offline Dołączył: 24-12-2004 Skąd: Warszawa |
Wystarczy zastosować alg. BFS albo DFS i zatrzymac go w momencie dodarcia do odpowiedniego punktu. Do tego musisz wykasować z ostatecznej odpowiedzi "ślepe uliczki". Czyli kiedy alg. cofał się do poprzedniej ścieżki. Pisałem kiedyś taki program w C# (podobny jest do javy, myśle, że zrozumiesz). Jak chcesz mogę Ci wysłać albo wrzucić na jakąś stronkę ![]() "Wyobraźnia jest ważniejsza od wiedzy, ponieważ wiedza jest ograniczona." - AE. |
|
|
| tetrycz |
08-02-2010 18:06 |
|
Użytkownik Status: Offline Dołączył: 08-02-2010 |
Bylbym wdzieczny jakbys podeslal ten program na tetrycz[at]tlen.pl |
|
|
| Luno |
08-02-2010 20:35 |
|
Użytkownik Status: Offline Dołączył: 30-09-2007 Skąd: Wrocław |
Jesli chcesz algorytm, dajacy najkrotsza sciezke i to w sensownym czasie, to polecam A* (standardowy algorytm do problemu pathfindingu) |
|
|
|
|
|
Strona [ 1 ] z 1
| 1 użytkownik(ów) przegląda ten temat (1 gości) |
|---|
| (żadnych zarejestrowanych użytkowników) |











