# Wegberechnung mit Java



## kali (4. Dez 2006)

Hallo Programmier!

Ich habe ein Problem:
Ich habe ein Programm welches ein kleiner Editor ist wo man auf einem Raster Start- sowie Endpunkt setzen kann und auch Hindernisse einbauen kann.
Nun versuche ich den Weg vom Start- zum Endpunkt zu berechnen.
Eine Funktion welche alle "Nachbarn" des aktuellen Punktes am Raster ausgibt hab ich bereits.
Allerdings weiß ich nicht wirklich wie so Wegberechnung funktioniert.
Gibt es da vielleicht einen geeigneten Algorithmus?


Danke im Voraus

mfG kali


----------



## SnooP (4. Dez 2006)

Eine Möglichkeit, wenn auch natürlich nicht unbedingt die Beste, ist alle Kombinationen von Pfaden zum Ziel durchzuprobieren... nennt sich Backtracking. Dazu kannst du ja mal die Wikipedia befragen.


----------



## kali (4. Dez 2006)

Danke erstmal, aber irgendwie ist das nicht unbedingt die Lösung die ich suche.

Gibts da auch noch andere Algorithmen welche vielleicht auch performanter sind oder muss ich so und so auf Backtracking zurückgreifen?

mfG kali


----------



## kali (4. Dez 2006)

den wenn ich mir dieses beispiel ansehe Backtracking Beispiel muss ich sagen, dass Backtracking nicht wirklich performant ist!

mfG kali


----------



## SnooP (4. Dez 2006)

Naja... kannst du denn zu dem Zeitpunkt wo du die Wegsuche startest bereits Aussagen über die wahrscheinliche Lage des Ziels machen? Dann kannst du beim Erzeugen des Baums mit möglichen Pfaden zum Ziel an den Kanten entsprechende Wahrscheinlichkeiten berechnen bzw. eintragen und dann nur die Kanten mit der höchsten Wahrscheinlichkeit nehmen... - da gibts halt entsprechende Verbesserungen...


----------



## kali (4. Dez 2006)

Zum Zeitpunkt der Wegberechnung weiß ich wo der Endpunkt ist denn der muss vom User gesetzt werden.
Ich weiß also wo Start und Ende sind und dann muss ich mir den (am besten kürzesten) Weg zwischen Start und Ende berechnen.

kali


----------



## byte (4. Dez 2006)

Du könntest den Backtracking etwas auf Deine Bedürfnisse anpassen. Ich stelle mir das in etwa so vor: Solange es kein Hindernis gibt, geht der Algorithmus immer den direkten weg zum Ziel (dieser ist denke ich mal berechenbar, da man ja Start und Ziel zu Beginn angibt). Sobald ein Hindernis auftaucht, wird der Algorithmus nach dem Backtracking-Prinzip rekursiv aufgerufen mit den beiden Wegen "links" und "rechts" um das Hindernis.

Wenn die Anzahl der Hindernisse nicht zu hoch ist, sollte das wesentlich performanter sein als der reine Backtracking. Bei sehr vielen Hindernissen (also einem Labyrinth) schätze ich aber mal, das der Algorithmus nicht immer terminieren wird.


----------



## kali (4. Dez 2006)

Ist ein guter Ansatz.

Werd ich mal versuchen, danke!

mfG kali


----------



## Azrahel (4. Dez 2006)

Da ich auch grad in der Richtung was baue hätt ich da auch noch was: IMO macht es nen Unterschied ob ich in einer frei begehbaren Fläche Hindernisse hab denen ich ausweichen muss oder ob ich nur auf gewissen "Strassen" gehen kann. Im Fall 2 gibts auch so was wie A*-Algorithmus, (einfach mal bei wikipedia nach suchen.)

Im anderen Fall würd ich das ganz anders berechnen. Aber ob mein weg richtig oder falsch ist weiss ich nicht, er funktioniert halt. 

Ich berechne die grade Linie zwischen beiden Punkten. Schneidet diese Linie ein Hinderniss leg ich nen zwischenwegpunkt ein, der ausserhalb des Hindernisses liegt. dann berechne ich den weg vom zwischenwegpunkt bis zum Endpunkt. und der Absatz jetzt rekursiv   gibt zwar nicht den kürzesten weg aus, berechnet aber recht schnell. war zumindest meine Meinung. 

Wenn jemand ne bessere Lösung hat her damit, Performance ist immer geil *lechz*


----------



## lebowski (4. Dez 2006)

ich hab das auch mal gemacht. und zwar so: 
die welt habe ich quasi als schachbrett implementiert also hatte felder in zwei dimensionen. 
ich schreibs mal als code hin. 

```
int weltw,welth;//breite,höhe der welt in feldern
int startx,starty;//x,y wo dein weg losgehen soll
int zielx,ziely;//x,y wo es hingehen soll

boolean[][] begehbar=new boolean[weltb][welth];
//hier code ausgelassen. ordne hier jedem feld in der welt ein boolean zu, das genau dann false ist, wenn das feld nicht begehbar ist; damit das programm nicht abstürzt, müssen alle randfelder unbegehbar sein. 
byte[][] richtung=new byte[weltb][welth];
//hier code ausgelassen. alle auf 0 setzen;
final byte VONOBENLINKS=1, VONOBEN=2, VONOBENRECHTS=3, VONLINKS=4, VONRECHTS=5, VONUNTENLINKS=6, VONUNTEN=7, VONUNTENRECHTS=8;

Vector vx=new Vector();
Vector vy=new Vector();
//die vector methoden weis ich jetzt nicht. ich schreibe mal void v.tudazu(int i), dafür das [b]ans ende[/b] i drangehängt wird und int v.nehmweg() dafür, dass [b]am anfang[/b] etwas (also das erste element) weggenommen wird. 
int tempx=zielx,tempy=ziely;

while(tempx!=startx || tempy!=starty){
    if(begehbar[tempx-1][tempy-1] && richtung[tempx-1][tempy-1]==0){
        richtung[tempx-1][tempy-1]=VONUNTENRECHTS;
        vx.tudazu(tempx-1);
        vy.tudazu(tempy-1);
    }
    if(begehbar[tempx][tempy-1] && richtung[tempx][tempy-1]==0){
        richtung[tempx][tempy-1]=VONUNTEN;
        vx.tudazu(tempx);
        vy.tudazu(tempy-1);
    }
    if(begehbar[tempx+1][tempy-1] && richtung[tempx+1][tempy-1]==0){
        richtung[tempx+1][tempy-1]=VONUNTENLINKS;
        vx.tudazu(tempx+1);
        vy.tudazu(tempy-1);
    }
    if(begehbar[tempx-1][tempy] && richtung[tempx-1][tempy]==0){
        richtung[tempx-1][tempy]=VONRECHTS;
        vx.tudazu(tempx-1);
        vy.tudazu(tempy);
    }
    if(begehbar[tempx+1][tempy] && richtung[tempx+1][tempy]==0){
        richtung[tempx+1][tempy]=VONLINKS;
        vx.tudazu(tempx+1);
        vy.tudazu(tempy);
    }
    if(begehbar[tempx-1][tempy+1] && richtung[tempx-1][tempy+1]==0){
        richtung[tempx-1][tempy+1]=VONOBENRECHTS;
        vx.tudazu(tempx-1);
        vy.tudazu(tempy+1);
    }
    if(begehbar[tempx][tempy+1] && richtung[tempx][tempy+1]==0){
        richtung[tempx][tempy+1]=VONOBEN;
        vx.tudazu(tempx);
        vy.tudazu(tempy+1);
    }
    if(begehbar[tempx+1][tempy+1] && richtung[tempx+1][tempy+1]==0){
        richtung[tempx+1][tempy+1]=VONOBENLINKS;
        vx.tudazu(tempx+1);
        vy.tudazu(tempy+1);
    }
    tempx=vx.nehmweg();
    tempy=vy.nehmweg();
}

//code ausgelassen. schreib dir ne methode, die in einem fenster für jedes feld optisch die richtung zeigt, in die quasi richtung[feldx][feldy] zeigt. dann siehste, wo der kürzeste weg langgeht. jetzt musste nur noch eine methode schreiben die den weg in irgendeinem objekt speichert. das sei dir überlassen. die maximale zeitkomplexität dieses algorithmus ist gleich der anzahl der felder die es in der welt gibt.
```

wie gesagt: schreib die methode, die es diroptisch zeigt, dann siehste dass der algorithmus funktioniert. dann verstehste nach kurzem nachdenken auch wiso. der algorithmus ist wirklich sehr flott.


----------



## Illuvatar (4. Dez 2006)

Auch ein schöner Algorithmus:
http://www.java-forum.org/de/viewtopic.php?t=5540&highlight=astar
Wird afaik zum Beispiel in Warcraft III verwendet


----------



## Azrahel (5. Dez 2006)

@illuvater @lebowski cool, danke schön, werd ich mich gleich mal reinbeissen   :toll:


----------



## HLX (5. Dez 2006)

Zur Berechnung der kürzesten Wegstrecke zwischen einem Start- und Zielpunkt gilt der Dijkstra-Algorithmus als anerkannte Lösung. Wird von vielen Streckenberechnungsanwendungen implementiert:

Link


----------



## Azrahel (5. Dez 2006)

Ja, aber Dijkstra ist doch auch für auf "strassen" gedacht, oder?


----------



## WieselAc (5. Dez 2006)

Ja da hast du recht den verwendet man normalerweise wenn man gewichtete Kanten hat oder Knoten in einem Graph hat.


----------



## Leroy42 (5. Dez 2006)

byto hat gesagt.:
			
		

> Bei sehr vielen Hindernissen (also einem Labyrinth) schätze ich aber mal, das der Algorithmus nicht immer terminieren wird.



Wieso das denn?  :shock: 

Ein korrekt umgesetzter Algorithmus in einem endlichen
Suchbaum terminiert immer.  :meld:


----------



## byte (5. Dez 2006)

Grundlage des beschriebenen Problems ist aber ein Graph und die können bekanntermaßen zyklisch sein. Da der von mir salop formulierte triviale Algorithmus keine Behandlung von Zyklen enthält, habe ich das besser erwähnt.


----------



## Azrahel (5. Dez 2006)

Für mich hört sich der A* eigentlich gut an, auch wenn ich spontan echt keine Ahnung hätte wie ich ihn umsetzen sollte.


----------



## Leroy42 (5. Dez 2006)

byto hat gesagt.:
			
		

> Da der von mir salop formulierte triviale Algorithmus *keine Behandlung von Zyklen enthält*, habe ich das besser erwähnt.



Dann nehme ich meinen Einwand natürlich zurück!  :toll:


----------

