Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Shortest path with obstacles
Grundsätzliche Frage zu der oben genannten Problemstellung:
Ist es möglich den kürzesten Pfad zu finden, ohne vorher alle durchprobiert zu haben und dann vergleichen zu müssen?
Man weiß ja an einem bestimmten Punkt nicht, ob noch Hindernisse vor einem liegen, weswegen man keine Aussage über die voraussichtliche Länge des übrigen Pfades treffen kann. Ich bekomme aber das Gefühl nicht los, dass es hier etwas besseres als Trial and Error geben muss… denk denk
Ohne jetzt wirklich darüber nachdzudenken:
Wenn du schlicht die Felder, die du nicht betreten darfst, als “sehr lang” wertest, dann sollten sich bekannte Wegplanungsalgorithmen entsprechend anwenden lassen.
Da die bekannten Wegplanungsalgorithmen iirc ein Startfeld brauchen, wirst du allerdings wohl oder übel dir für jedes mögliche Anfangsfeld auf der linken Seite den jeweils kürzesten Pfad berechnen lassen müssen und dann dich zwischen denen für den kürzesten entscheiden.
Allerdings kannst du das wiederum etwas optimieren mit der Einschränkung, dass als allererste Bewegung eine andere Richtung als rechts sinnlos ist. Nach oben oder unten erreichst du nur ein potentielles Startfeld, nur mit einem Schritt mehr als wenn du stattdessen dort anfangen würdest, und nach links kannst du sowieso nicht.
Danke für die Antworten, ich habe letzten Endes für die Startfelder eine Fallunterscheidung gemacht. Dazu habe ich den bisherigen Pfad mit (-1/-1) als Koordinaten initalisiert und konnte so rauslesen ob ich mich in der ersten Rekursion befinde oder nicht.
In Pseudocode:
if (ersteRekursion == true){
candidates = Startfelder
}
else {
candidates = …
Naja standardtrick ist ein Magisches externen Startfeld das genau mit kosten 0 zu allen valieden startpunkten verbunden ist.
und jeder standard-pfadsuch-algorithmus kommt mit ungueltigen feldern klar. einfach ned mit in den graph aufnehmen / beim suchen abarbeiten
1 „Gefällt mir“
So simpel der Trick klingt, den kannte ich noch gar nicht. Danke!