Weg durch ein Koordinatensystem mit Hindernissen

Dieses Thema im Forum "Mac OS X Entwickler, Programmierer" wurde erstellt von koli.bri, 19.10.2006.

  1. koli.bri

    koli.bri Thread Starter Gast

    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 :)

    [​IMG]
     

    Anhänge:

    Zuletzt von einem Moderator bearbeitet: 19.10.2006
  2. Omikronman

    Omikronman MacUser Mitglied

    Beiträge:
    304
    Zustimmungen:
    0
    MacUser seit:
    01.10.2006
    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.
     
  3. Winn

    Winn MacUser Mitglied

    Beiträge:
    423
    Zustimmungen:
    0
    MacUser seit:
    07.11.2002
  4. balufreak

    balufreak MacUser Mitglied

    Beiträge:
    1.560
    Zustimmungen:
    28
    MacUser seit:
    12.10.2003
    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!
    }
    
     
  5. falkgottschalk

    falkgottschalk MacUser Mitglied

    Beiträge:
    24.026
    Zustimmungen:
    1.598
    MacUser seit:
    22.08.2005
    Das ist dann doch eher so etwas wie klassisches Backtracking, oder?
    Stichwort "8-Damen-Problem".
    Ewig alt und immer noch ein schönes Beispiel.
     
  6. Omikronman

    Omikronman MacUser Mitglied

    Beiträge:
    304
    Zustimmungen:
    0
    MacUser seit:
    01.10.2006
    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.
     
  7. qfat

    qfat MacUser Mitglied

    Beiträge:
    238
    Zustimmungen:
    0
    MacUser seit:
    30.01.2005
    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.
     
  8. wegus

    wegus MacUser Mitglied

    Beiträge:
    15.041
    Zustimmungen:
    1.316
    MacUser seit:
    13.09.2004

    ja, es läßt sich aber auch schön für evolutionäre Algorithmen als Beispiel nutzen ! Allerdinsg sicher nicht auf einer Web-Plattform :)
     
  9. der_Kay

    der_Kay MacUser Mitglied

    Beiträge:
    1.693
    Zustimmungen:
    7
    MacUser seit:
    02.09.2004
  10. koli.bri

    koli.bri Thread Starter Gast

    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
    ist schon zu hoch für mein kleines Köpfchen... (Kantengewichte???)

    Vielen lieben Dank.

    gruß
    Lukas
     
Die Seite wird geladen...

Diese Seite empfehlen