Labirynt i najkrotsza trasa

0

Witam serdecznie. Szukalem pomocy w internecie ale nie moglem nic znaleŹĆ 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.

0

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ę ;)

0

Bylbym wdzieczny jakbys podeslal ten program na tetrycz[at]tlen.pl

0

Jesli chcesz algorytm, dajacy najkrotsza sciezke i to w sensownym czasie, to polecam A* (standardowy algorytm do problemu pathfindingu)

1 użytkowników online, w tym zalogowanych: 0, gości: 1