Ankündigung

Einklappen
Keine Ankündigung bisher.

A*Algorithmus (Wegfindung)

Einklappen

Neue Werbung 2019

Einklappen
X
  • Filter
  • Zeit
  • Anzeigen
Alles löschen
neue Beiträge

  • A*Algorithmus (Wegfindung)

    HeyHo,
    ich programmiere derzeit ein Browsergame, was auf der Grundideee von Travianer basiert. Nun wollte ich, wie dort, ein Männchen machen, dass zum letzten Mausklick läuft. Klappt auch alles wunderbar, nur macht mir eben die "Wegfindung" Kopfzerbrechen.
    Als erstes hatte ich es so gemacht, dass die "kurven" als Knotenpunkte gespeichert werden und dann einfach abgefragt wird, welche Knotenpunkte zwischen $start und $ziel liegen. Dann habe ich jedoch gemerkt dass es doch nicht so einfach ist ().
    Nachdem ich schon einiges gelesen hatte bin dann auf A*-Algorithmus gestoßen.
    Nur werde ich daraus nicht wirklich schlau und hab auch nicht wirklich Ahnung wie ich dass umsetzten kann. Die Javascript Umsetzung ist für mich kein Problem.

    Hat jemand eventuelle Lösungsansätze oder Tutorials bzw. links?


    Mit besten Grüßen
    Streak

    Ps.: Ich will es jedenfalls versuchen dies hinzubekommen, bevor ich vor diesem Vorhaben kapituliere


  • #2
    also ich kenne den A*Algo nicht und bin in PHP auch noch Anfänger, aber ich könnt dir folgenden Artikel empfehlen, vielleicht hilft er dir ja:
    GIS | Dijkstra's algorithm - GISWiki

    es geht um den Algorithmus von Dijkstra und bei wiki ist auch ein beispielcode in php angegeben, vielleicht trägt der zum verständnis bei...

    Kommentar


    • #3
      Das Beispiel beim Wikiartikel ist doch ganz anschaulich. Die verwendeten Werte (Kantenwiderstand, "Luftlinie") musst du eben vorliegen haben. Wobei ich in dem Artikel nicht ganz verstehe, warum der potentiell schnellste Weg als erstes berechnet werden soll, wenn doch sowieso alle Wege berechnet werden müssen.
      "Mein Name ist Lohse, ich kaufe hier ein."

      Kommentar


      • #4
        Zitat von Chriz Beitrag anzeigen
        Wobei ich in dem Artikel nicht ganz verstehe, warum der potentiell schnellste Weg als erstes berechnet werden soll, wenn doch sowieso alle Wege berechnet werden müssen.
        Weil manche Sprachen Multithreading unterstützen
        Über 90% aller Gewaltverbrechen passieren innerhalb von 24 Stunden nach dem Konsum von Brot.

        Kommentar


        • #5
          Ich muss doch trotzdem warten, bis alle Streckenergebnisse vorliegen?!
          "Mein Name ist Lohse, ich kaufe hier ein."

          Kommentar


          • #6
            Dies ist auch noch ein ganz hübsches Tut, finde ich: A* Pathfinding for Beginners

            Gruß
            http://hallophp.de

            Kommentar


            • #7
              Wobei ich in dem Artikel nicht ganz verstehe, warum der potentiell schnellste Weg als erstes berechnet werden soll, wenn doch sowieso alle Wege berechnet werden müssen.
              Deshalb?
              // wenn der Nachfolgeknoten bereits auf der Open List ist,
              // aber der neue Weg länger ist als der alte - tue nichts
              if openlist.contains(successor) and f > openlist.find(successor).f then
              continue
              Wenn während der Wegberechnung die bisher kürzeste Länge überschritten wird, kann man ja dort abbrechen.
              --

              „Emoticons machen einen Beitrag etwas freundlicher. Deine wirken zwar fachlich richtig sein, aber meist ziemlich uninteressant.
              Wenn man nur Text sieht, haben viele junge Entwickler keine interesse, diese stumpfen Texte zu lesen.“


              --

              Kommentar


              • #8
                Sind 'Dijkstra' und 'A*' sich nicht ähnlich?
                Wenn ich richtig informiert bin, dann sucht 'Dijkstra' in alle Richtungen, beim 'A*' hat man durch eine Heuristik schon die grobe Richtung und braucht die anderen Richtungen deswegen gar nicht zu beachten.

                Kommentar


                • #9
                  Zitat von wikipedia.org
                  Verwandte Algorithmen

                  Der A*-Algorithmus ist verwandt mit dem Dijkstra-Algorithmus [...]. Der Algorithmus von Dijkstra verwendet keine Heuristik (h = 0, also f = g) und wählt Knoten nur anhand der bisherigen Kosten aus.
                  http://hallophp.de

                  Kommentar


                  • #10
                    Zitat von Chriz Beitrag anzeigen
                    Ich muss doch trotzdem warten, bis alle Streckenergebnisse vorliegen?!
                    In PHP schon... da es sich um Portierungen eines Algorithmus handelt, ist das warscheinlich aus einer anderen Sprache übernommen worden.

                    In einer MT Umgebung kann ein Ergebnis bereits verwendet werden (i.e. sobald es fertig berechnet ist), während andere Ergenisse noch kalkuliert werden.
                    Über 90% aller Gewaltverbrechen passieren innerhalb von 24 Stunden nach dem Konsum von Brot.

                    Kommentar


                    • #11
                      Zitat von nikosch Beitrag anzeigen
                      Deshalb?
                      Wenn während der Wegberechnung die bisher kürzeste Länge überschritten wird, kann man ja dort abbrechen.
                      OK, macht Sinn.
                      "Mein Name ist Lohse, ich kaufe hier ein."

                      Kommentar


                      • #12
                        ok, der Link von Asipak (A* Pathfinding for Beginners) hat mich schon ein ganzes stück weiter gebracht, ich verstehe das jetzt so einigermaßen.
                        Nur eine Frage stellt sich mir noch, wie stell ich das mit so einer Karte dann an? Mache ich nur "quadrate" für die Wege?


                        Beste Grüße
                        Streak

                        Kommentar


                        • #13
                          Musst nicht unbedingt quadrate nehmen, kannst jede beliebige Form nehmen, allerdings wird es dann komplizierter mit der Berechnung

                          Kommentar

                          Lädt...
                          X