Weg durch ein Koordinatensystem mit Hindernissen

K

koli.bri

Hallo.

Zwar soll es als Webapplikation laufen, aber es ist eher ein alllgemeines Programmierproblem :)

Ich hab ein Feld von 10x10 Feldern, wie man auf der Grafik sieht.
einen Start und Endpunkt (Grün und rosa), ein Hinderniss (schwarz), und einen möglichen Idealweg (grau).

Ziel ist es aber, dass das Tool den Weg alleine findet. Leider steh ich vollkommen auf dem Schlauch, wie man das bewerkstelligen kann.

Gegeben ist ein Array nach folgendem Schema:
Code: 
feld[x][y]
X ist die X-Koordinate, Y die Y-Koordinate (macht ja auch Sinn :))

Zudem sind Start und Enpunkt in eigenen Variablen definiert (fromx/y und tox/y).
die Hindernisspunkte sind in dem Koordinatenarray definiert.
bisher kann ein Feld folgende Sati haben: Leer (blau), Startpunk (blau), endpunk (pink), Mauer/Hinderniss(schwarz). Und freillich Weg (grau)

wie geh ich die Sache an?
Programmiersprache ist JavaScript zusammen mit HTML.
(Ich habs deshalb nicht ins Webprogrammierungsforum gepackt, weils sich in meinen Augen problemlos in andere Sprachen portieren lässt, und eher ein allgemeines Programmier"problem" ist, als spezifisch auch JavaScript/HTML zugeschnitten. ein Moderator mag mir das nachsehen, falls ich da falsch gedacht habe :) )

Auf viele Denkanstöße und Hilfestellungen

gruß
Lukas

EDIT. Hab das Beispielbild vergessen... Pardon :)

attachment.php
 

Anhänge

  • mufred.jpg
    mufred.jpg
    20 KB · Aufrufe: 276
Zuletzt bearbeitet von einem Moderator:
Oh, das ist knifflig. Ich schrieb mal für den Psion Organizer den damals ersten Routenplaner für das X-Beyond-the-Frontier Universum. Das bestand auch aus lauter quadratischen Sektoren.

Es wäre möglich, das Programm einen Zufallsweg laufen zu lassen. Ist das Ziel erreicht, probiert es das Programm nochmal, leicht verändert, ausgehend vom ersten Versuch.

Wenn es nur wenige Felder insgesamt sind würde sich auch ein ständiges Zufallsrouting empfehlen. Einfach die Zeit messen oder die zurückgelegten Felder zählen. Je schneller oder kürzer der Weg, umso besser der Versuch. Hat das Programm 100 Schritte gemacht, Versuch abbrechen, denn dann hat es ja schon fast mehr Schritte getan als das ganze Aktionsfeld groß ist.
 
Kennst du das Programm JavaKara? Da ist es das gleiche Problem.

Ich musste in der Schule genau das machen. Ein Marienkäfer musste durch ein vorgegebenes, unbekanntes Labyrinth laufen.

So ich hab das wie folgt gelöst. Ich habe eine Richtung eingeschlagen. Also am Anfang habe ich immer versucht nach oben zu gehen. Wenn das nicht ging, habe ich den käfer um 90° gedreht und nochmal versucht. dann halt nach links oder rechts.

Verstehst du was ich mein?

So:
Code: 
if(oben kein hindernis) {
  gehNachOben();
}
else if(links kein hindernis) {
  gehNachLinks();
}
else if(unten kein hindernis) {
  gehNachUnten();
}
else if(rechts kein hindernis) {
  gehNachRechts();
}
else {
  eingesperrt!
}
 
Das ist dann doch eher so etwas wie klassisches Backtracking, oder?
Stichwort "8-Damen-Problem".
Ewig alt und immer noch ein schönes Beispiel.
 
Sofern in einem Labyrinth alle Wände miteinander verbunden sind findet sich der Ausgang denkbar leicht: Einfach so lange an einer Wand in dieselbe Richtung laufen, bis der Ausgang da ist.
 
ok du musst entweder beim backtracking die rekursionstiefe beschränken (da du ja kein echtes labyrinth hast sondern eher nur nen hindernis und du sonst sofort nen stackoverflow bekommst).

oder du optimierst den backtracking algorithmus so das er nicht in irgenteine richtung läuft sondern nur wenns nötig ist sich vom ziel entfernt.

gut so oder so musst du wenn du am ziel angekommen bist deinen weg inner var sichern, denn es gibt ja mehrere wege zum ziel und du willst ja nur den kürzesten haben.
 
falkgottschalk schrieb:
Das ist dann doch eher so etwas wie klassisches Backtracking, oder?
Stichwort "8-Damen-Problem".
Ewig alt und immer noch ein schönes Beispiel.
Zum Vergrößern anklicken....


ja, es läßt sich aber auch schön für evolutionäre Algorithmen als Beispiel nutzen ! Allerdinsg sicher nicht auf einer Web-Plattform :)
 
Oh mann...
Ich hab ja damit gerechnet, dass es kompliziert wird, aber SO kompliziert? :kopfkratz:
Grusel...
Ich glaub, dann lös ich das anders...

Dennoch, vielen lieben Dank für die Hilfestellungen, es wird sicherlich der Tag kommen, an dem ich damit auch produktiv was anfangen kann (Denn
Der A*-Algorithmus dient in der Informatik der Berechnung eines kürzesten Pfades zwischen zwei Knoten in einem Graphen mit positiven Kantengewichten.
Zum Vergrößern anklicken....
ist schon zu hoch für mein kleines Köpfchen... (Kantengewichte???)

Vielen lieben Dank.

gruß
Lukas
 
Man sollte vielleicht noch erwähnen, dass die genannten Algorithmen auf dem Sichtbarkeitsgraphen arbeiten.
 
der_Kay schrieb:
Man sollte vielleicht noch erwähnen, dass die genannten Algorithmen auf dem Sichtbarkeitsgraphen arbeiten.
Zum Vergrößern anklicken....
Interessante Lektüre.
Ich werde mich wohl mal mit meinem Vater hinsetzen müssen, um das durchzuarbeiten.
Aber ich hab mein Problem bereits so gelöst, das der Anwender nur jeweils en Feld gehen kann. :D
Dennoch vielen Dank für die Links uns Anregungen, ich werd mir auf jeden Fall mal die Zeit nehmen und das versuchen in meinen Schädel zu kloppen :)

gruß
Lukas
 
Ich würde einen Backtracking Algorythmus empfehlen, der ein paar einschränkungen hat. z.B.:
- nur die Beste Richtung verlassen wenn etwas im Weg steht.
- Abbrechen wenn der aktuelle weg länger als der kürzeste gefundene ist
 
Du musst dich einloggen oder registrieren, um hier zu antworten.
Zurück
Oben Unten