Labirynt i najkrotsza trasa

szukaj na forum nowy temat odpowiedz

Strona [ 1 ] z 1

tetrycz ten post 08-02-2010 16:44


Użytkownik
Status: Offline
Dołączył: 08-02-2010

Witam serdecznie. Szukalem pomocy w internecie ale nie moglem nic znalesc wiec wybralem wlasnie to forum zeby przedstawic swoj problem. Tak w skrocie chodzi o znalezienie drogi miedzy pocatkiem a koncem labiryntu, niekoniecznie najkrotszesz bo zalozmy ze jest jedna. Bardziej szczegolowo chodzi o to:

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
Przejdź na górę strony
cytuj
konrad.g ten post 08-02-2010 17:46
avatar

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.
Przejdź na górę strony
cytuj
tetrycz ten post 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
Przejdź na górę strony
cytuj
Luno ten post 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)
Przejdź na górę strony
cytuj
szukaj na forum nowy temat odpowiedz

Strona [ 1 ] z 1

1 użytkownik(ów) przegląda ten temat (1 gości)
(żadnych zarejestrowanych użytkowników)

Copyright © 2000-2006 by Coyote Group 0.9.3-pre3
Czas generowania strony: 0.1571 sek. (zapytań SQL: 9)