Ankündigung

Einklappen
Keine Ankündigung bisher.

Pathfinding für eine x:y Karte

Einklappen

Neue Werbung 2019

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

  • Pathfinding für eine x:y Karte

    Moin,

    ich habe derzeit ein Problem bei der Realisierung eines Pathfinding Algorithmuses.

    Mein Ziel ist es, in einer x:y Karte einen kurzen und am besten auch "good looking"-Weg von a nach b zu finden und mir jedes Feld das dabei überquert wird in einem Array zurück zu geben.

    Die Felder können unterschiedlich sein. Also eines schnell zu überqueren, ein anderes langsamer. Anbieten würde sich hier ein A*-Algorithmus.
    Ich habe mir auch bereits einige gut erklärte Links durchgelesen (bsp: A* Pathfinding for Beginners) allerdings find ich keinen Anfang und auch das Verständnis der Open und Closed Lsiten etc. hält sich in Grenzen.

    Meine Frage wäre also, hat jemand schoneinmal einen solchen Pathfinding Algorithmus geschrieben (Dijkstra's Algorithmus is leider nicht das was ich suche) der aus einem Array in Form von $arr[x][y] = überquerungswertigkeit; einen schnellen und am besten gutaussehenden weg findet? Oder kann mir helfen das Verständnis für einen aufzubringen damit ich ihn selber schreiben kann ?


    Ich hoffe mir kann geholfen werden...

    Gruß,
    Deadbone


  • #2
    [MOD: verschoben]
    --

    „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


    • #3
      Einfacher als in dem Link gehts ja kaum. Ich nehme an das Angebot ist unbezahlt?

      Kommentar


      • #4
        Oh, ich wusste nicht das man hier für Hilfe eventuell bezahlen müsste.
        Ja das Angebot wäre unbezahlt, ich hoffe aber wenn es so leicht ist das es jemanden gibt der das umsonst machen würde ?

        Ich sitze selber grade dran, falls ich auf ein Ergebnis komme poste ich es auch, aber wenn es jemanden gibt der sich da mit dran setzt wär ich sehr dankbar.

        Kommentar


        • #5
          Naja es gibt da schon auch ein fertiges Script. Das ist eine Facharbeit von jemanden.

          Den Download findest du unter:
          http://www.php-einfach.de/download.p...Facharbeit.zip

          Mfg Splasch

          Kommentar


          • #6
            Ich sitze selber grade dran, nur wie gesagt ich bin immo stressbedingt etwas konfus und kriegs einfach nicht gescheit hin.
            Wenn ich sowas imnmer lese, denke ich: „Dann bastel Papierflieger und programmiere weiter, wenn Du wieder klar denken kannst“. Wem nützen solche Aussagen?
            --

            „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


            • #7
              Jeglicher privater schnickschnack wurde entfernt.

              Aber danke für die Facharbeit, sieht schonmal gut aus !

              Kommentar


              • #8
                Splasch, kannst Du vielleicht noch den Autor ergänzen (Link oder so). Finde das ein bissel unfair, das so als zip-Direktload anzubieten.

                [edit] Ach ich sehe gerade, da ist ein pdf dabei..
                --

                „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


                • #9
                  Der Autor steht in allen Php datein sowie auch in der Pdf datei. Ich denke das sollte ausreichen.
                  Es handelt sich dabei um den Besitzer der Webseite.
                  http://php-einfach.de/nav_impressum.php

                  Er hat das Script selbt dort zum Download angeboten.

                  Mfg Splasch

                  Kommentar


                  • #10
                    So ich hab das ganze nun selbst in einer hoffentlich guten Umsetzung geschafft.
                    Fals wer noch nen Verbesserungsvorschlag hat würd ich mich drüber freuen.

                    Zur Handhabung:

                    Als Karte brauch der Algorithmus einen Array in Form von:
                    $array[(x-Koordinate)][(y-Koordinate)]['value'] = (Überquerungskosten)

                    Als Rückgabe erhält man einen Array mit den Punkten die bei dem kürzesten Pfad überquert werden und die Kosten für den jeweiligen Punkt (Hab ich so eingebaut da ich die Kosten zur Zeit Berechnung brauche)

                    Und hier die Klasse:

                    PHP-Code:
                    <?php

                    class AStar {
                        private 
                    $map;
                        private 
                    $openList;
                        private 
                    $closedList;
                        private 
                    $maxFieldValue     0;
                        private 
                    $endField         = array();
                        private 
                    $startField     = array();
                        private 
                    $result         = array();

                        
                        function 
                    __construct($map$maxFieldValue) {
                            
                    $this->map                 $map;
                            
                    $this->maxFieldValue     $maxFieldValue;    
                        }
                        
                        public function 
                    getPath($startY$startX$endX$endY) {
                            unset(
                    $this->openList);
                            unset(
                    $this->closedList);
                            
                            if(
                    $startY == $endX && $startX == $endY)
                                return 
                    false;
                                
                            
                    $this->endField['x']     = $endY;
                            
                    $this->endField['y']     = $endX;
                            
                    $this->startField['x']     = $startX;
                            
                    $this->startField['y']     = $startY;
                            
                            
                    $this->addOpenListField(nullnull$startX$startY);
                            
                    $this->addClosedListField($startX$startY);
                            
                    $this->loadAdjacentFields($startX,$startY);
                            
                            while(
                    count($this->openList) > 0) {
                                
                    $newField $this->getLowestOpenField();
                                
                    $this->addClosedListField($newField['x'], $newField['y']);
                                
                                if(
                    $newField['x'] == $this->endField['x'] && $newField['y'] == $this->endField['y']) {
                                    
                    $this->backwalkPath($this->endField['x'],$this->endField['y']);
                                    return 
                    $this->result;
                                }
                                
                    $this->loadAdjacentFields($newField['x'], $newField['y']);
                            }
                            return 
                    false;    
                        }
                        
                        private function 
                    getLowestOpenField() {
                            
                    asort($this->openList);
                            return 
                    $this->getCoordinates(key($this->openList));
                        }
                        
                        private function 
                    backwalkPath($x false$y false) {
                            if(
                    $this->map[$x][$y]['mx'] == null && $this->map[$x][$y]['my'] == null) {
                                
                    $this->addFinalPathField($x$y);
                                
                    $this->result array_reverse($this->result);
                            } else {
                                
                    $this->addFinalPathField($x$y);
                                
                    $this->backwalkPath($this->map[$x][$y]['mx'], $this->map[$x][$y]['my']);    
                            }
                        }
                        
                        private function 
                    addFinalPathField($x$y) {
                            
                    $t['x']         = $x;
                            
                    $t['y']             = $y;
                            
                    $t['cost']         = $this->map[$x][$y]['g'];
                            
                    $this->result[] = $t;
                        }

                        protected function 
                    loadAdjacentFields($x$y) {
                            if(
                    $this->checkAdjacentField($x-1,$y-1))
                                
                    $this->addOpenListField($x$y$x-1$y-1,true);
                            if(
                    $this->checkAdjacentField($x,$y-1))
                                
                    $this->addOpenListField($x$y$x$y-1);
                            if(
                    $this->checkAdjacentField($x+1,$y-1))
                                
                    $this->addOpenListField($x$y$x+1$y-1true);
                            if(
                    $this->checkAdjacentField($x-1,$y))
                                
                    $this->addOpenListField($x$y$x-1$y);
                            if(
                    $this->checkAdjacentField($x+1,$y))
                                
                    $this->addOpenListField($x$y$x+1$y);
                            if(
                    $this->checkAdjacentField($x-1,$y+1))
                                
                    $this->addOpenListField($x$y$x-1$y+1true);
                            if(
                    $this->checkAdjacentField($x,$y+1))
                                
                    $this->addOpenListField($x$y$x$y+1);
                            if(
                    $this->checkAdjacentField($x+1,$y+1))
                                
                    $this->addOpenListField($x$y$x+1$y+1true);
                        }
                        
                        private function 
                    checkAdjacentField($x$y) {
                            if(isset(
                    $this->map[$x][$y]['value']) && $this->map[$x][$y]['value'] < $this->maxFieldValue)
                                return 
                    true;
                            else
                                return 
                    false;
                        }
                        
                        private function 
                    addOpenListField($masterX$masterY$childX$childY$diag false) {
                            if(!isset(
                    $this->closedList[$childX.'_'.$childY])) {
                                if(!isset(
                    $this->openList[$childX.'_'.$childY])) 
                                    
                    $this->setNewFieldData($childX$childY$this->calculateMovementCost($masterX$masterY$childX$childY$diag), $masterX$masterY);
                                else
                                    if((
                    $cost $this->calculateMovementCost($masterX$masterY$childX$childY$diag)) < $this->map[$childX][$childY]['g'])
                                        
                    $this->setNewFieldData($childX$childY$cost$masterX$masterY);
                            }
                        }
                        
                        private function 
                    setNewFieldData($x$y$g$mx$my) {
                            
                    $this->map[$x][$y]['h']     = $this->calculateHeuristic($x$y);
                            
                    $this->map[$x][$y]['g']     = $g;
                            
                    $this->map[$x][$y]['mx']     = $mx;
                            
                    $this->map[$x][$y]['my']     = $my;
                            
                    $this->openList[$x.'_'.$y]     = $this->map[$x][$y]['h'] + $this->map[$x][$y]['g'];
                        }
                        
                        private function 
                    getCoordinates($key) {
                            
                    $s         explode('_',$key);
                            
                    $r['x'] = $s[0];
                            
                    $r['y'] = $s[1];
                            return 
                    $r;
                        }
                        
                        private function 
                    addClosedListField($x$y) {
                            
                    $this->closedList[$x.'_'.$y] = $this->openList[$x.'_'.$y];
                            unset(
                    $this->openList[$x.'_'.$y]);
                        }
                        
                        private function 
                    calculateHeuristic($x$y) {
                            return (
                    abs($this->endField['x'] - $x) + abs($this->endField['y'] - $y)) * 10;
                        }
                        
                        private function 
                    calculateMovementCost($mx$my$x$y$diag false) {
                            if(
                    $mx == null && $my == null)
                                
                    $mcost $this->map[$this->startField['x']][$this->startField['y']]['value'];
                            else
                                
                    $mcost $this->map[$mx][$my]['g'];
                                
                            if(
                    $diag)
                                
                    $ccost round(sqrt(pow($this->map[$x][$y]['value'],2) + pow($this->map[$mx][$my]['value'],2)));
                            else
                                
                    $ccost $this->map[$x][$y]['value'];
                                
                            return (
                    $ccost $mcost);
                        }
                    }
                    ?>
                    Hoffe ich konnte einigen helfen die für ihr Browserspiel einen Pfandfindungsalgorithmus brauchen.
                    Nochmal danke an die netten Hilfen.

                    Deadbone

                    Kommentar


                    • #11
                      Hast du hierbei auch die Hindernisse auf einer Map bedacht also Felder die nicht begehbar sind und daher umgangen werden müssen?

                      Nett were auch gleich mal ein Anwendungs Beispiel zu deiner Klasse und welche Werte von der Klasse erwartet werden. (Array in welche form)

                      Mfg Splasch

                      Kommentar


                      • #12
                        Array in welcher Form steht ja drin, unbegehbare Felder kann man sicher mit riesigen Kosten implementieren. Nett fände ich eine allgemeine Wegfindungsklasse die nicht nur A* unterstützt.

                        Wenn es jemanden mehr interessiert kann ich "Programming Game AI by Example" nur extremst empfehlen, der Author schreibt sehr gut und es gibt einige Kapitel über Pathfindung per A*, Dijkstra etc). Ist zwar C++ und "echte Physik" anstatt Tilemaps und PHP, kann man aber gut lesen und dann auf PHP anwenden.

                        Kommentar


                        • #13
                          Bei der initialisierung der Klasse übergibt man ja die karte und zudem den wert ab wann ein feld nichtmehr überquert werden kann (es also eine Wand ist). Im Quelltext is es die maxFieldValue variable.

                          Also ja, ist bereits implementiert.

                          Ich schreib ne Example Seite damit man das ganze auch in action sieht.

                          Kommentar


                          • #14
                            Folgendes ist mir aufgefallen
                            $this->endField['x'] = $endY;
                            $this->endField['y'] = $endX;

                            $this->startField['x'] = $startX;
                            $this->startField['y'] = $startY;
                            Soll bestimmt andersrum sein

                            Mit wie großen Karten hast du es schon getestet?

                            Eine Option um diagonales Laufen zu vermeiden, wäre auch nicht schlecht.


                            Ansonsten läuft die Klasse bei mir ohne Probleme

                            Kommentar


                            • #15
                              Das mit dem endY und endX ist irgendwas was sich eingeshclichen hat, aber funktioniert. Ich weis nich wo ich was falsch habe, aber wenn ichs umdrehe (also sozusagen richtig mache) ist x nicht die spalte sondern die zeile und so wars nich geplant.

                              Ich hab bis 500x500 getestet mit einer Mauer drin. Dauert bei der Größe auf meinem rechner dann zwischen 0,5 sekunden bis knapp unter 2 sekunden.
                              Ab 1000x1000 war die HTML ausgabe zu groß das ich nen Speicheroverflow bekommen hab.

                              Die option mit dem Diagonalen Laufen bau ich noch ein, bau sonst noch bisl was ein (an Wand feldern kann man nicht diagonal vorbeigehen z.b.) und geb euch den neuen code + testingsite.

                              Deadbone

                              Kommentar

                              Lädt...
                              X