Ankündigung

Einklappen
Keine Ankündigung bisher.

Pathfinding Algorithmus optimieren? (Algorith. von Dijkstra)

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

  • #16
    also erstmal zum algorithmus wie er implementiert gehört:
    PHP-Code:
    <?php
    /**
     * implementing dijkstra's shortes path algorithm in php.
     * @author axo
     * @access public 
     * @see [url]http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm[/url]
     *
    */
    class Dijkstra {

        var 
    $visited = array();
        var 
    $distance = array();
        var 
    $previousNode = array();
        var 
    $startnode =null;
        var 
    $map = array();
        var 
    $infiniteDistance 0;
        var 
    $numberOfNodes 0;
        var 
    $bestPath 0;

        
    /** 
         * constructor.
         * @param $ourMap array
         * @param $infiniteDistance integer
         * @access public
        */
        
    function Dijkstra(&$ourMap$infiniteDistance) {
            
    $this -> infiniteDistance $infiniteDistance;
            
    $this -> map = &$ourMap;
            
    $this -> numberOfNodes count($ourMap);
            
    $this -> bestPath 0;
        }


        
    /** 
         * finds the shortest path from $start to $to .
         * if $to is not set or null, all paths are calculated.
         * @param $start integer
         * @param $to integer
         * @return void
         * @access public
        */
        
    function findShortestPath($start,$to null) {
            
            
    $this -> startnode $start;
            for (
    $i=0;$i<$this -> numberOfNodes;$i++) {
                if (
    $i == $this -> startnode) {
                    
    $this -> visited[$i] = true;
                    
    $this -> distance[$i] = 0;
                } else {
                    
    $this -> visited[$i] = false;
                    
    $this -> distance[$i] = $this -> map[$this -> startnode][$i];
                }
                
    $this -> previousNode[$i] = $this -> startnode;
            }
            
    $maxTries $this -> numberOfNodes;
            
    $tries 0;
            while (
    in_array(false,$this -> visited,true) && $tries <= $maxTries) {
                
    $this -> bestPath $this -> findBestPath($this -> distance,array_keys($this -> visited,false,true));
                if(
    $to !== null && $this -> bestPath === $to) {
                    break;
                }
                
    $this -> updateDistanceAndPrevious($this -> bestPath);            
                
    $this -> visited[$this -> bestPath] = true;
                
    $tries++;
            }
        }

        
    /** 
         * finds the best path 
         * @access private
         * 
        */    
        
    function findBestPath(&$ourDistance$ourNodesLeft) {
            
    $bestPath $this -> infiniteDistance;
            
    $bestNode 0;
            for (
    $i 0,$m=count($ourNodesLeft); $i $m$i++) {
                if(
    $ourDistance[$ourNodesLeft[$i]] < $bestPath) {
                    
    $bestPath $ourDistance[$ourNodesLeft[$i]];
                    
    $bestNode $ourNodesLeft[$i];
                }
            }
            return 
    $bestNode;
        }

        
    /** 
         * @access private
        */
        
    function updateDistanceAndPrevious($ourBestPath) {        
            for (
    $i=0;$i<$this -> numberOfNodes;$i++) {
                if((!(
    $this -> map[$ourBestPath][$i] == $this -> infiniteDistance) ||     ($this -> map[$ourBestPath][$i] == 0))    
                    &&    ((
    $this -> distance[$ourBestPath] + $this -> map[$ourBestPath][$i]) < $this -> distance[$i]))             {
                        
    $this -> distance[$i] = $this -> distance[$ourBestPath] + $this -> map[$ourBestPath][$i];
                        
    $this -> previousNode[$i] = $ourBestPath;
                }
            }
        }

        
    /** 
         * prints a map.
         * @param $map array
         * @return string
         * @access public
        */
        
    function printMap(&$map) {
            
    $placeholder ' %' strlen($this -> infiniteDistance) .'d';
            
    $foo '';
            for(
    $i=0,$im=count($map);$i<$im;$i++) {
                for (
    $k=0,$m=count($map[$i]);$k<$m;$k++) {
                    
    $foo.= sprintf($placeholder,$map[$i][$k]);
                }
                
    $foo.= "\n";
            }
            return 
    $foo;
        }

        
    /** 
         * shows the result.
         * @return string
         * @access public
        */
        
    function getResults($to null) {
            
    $ourShortestPath = array();
            
    $foo '';
            for (
    $i 0$i $this -> numberOfNodes$i++) {
                if(
    $to !== null && $to !== $i) {
                    continue;
                }
                
    $ourShortestPath[$i] = array();
                
    $endNode null;
                
    $currNode $i;
                
    $ourShortestPath[$i][] = $i;
                while (
    $endNode === null || $endNode != $this -> startnode) {
                    
    $ourShortestPath[$i][] = $this -> previousNode[$currNode];
                    
    $endNode $this -> previousNode[$currNode];
                    
    $currNode $this -> previousNode[$currNode];
                }

                
    $ourShortestPath[$i] = array_reverse($ourShortestPath[$i]);
                
                if (
    $to === null || $to === $i) {
                if(
    $this -> distance[$i] >= $this -> infiniteDistance) {
                    
    $foo .= sprintf("no route from %d to %d. \n",$this -> startnode,$i);
                } else {
                    
    $foo .= sprintf('%d => %d = %d [%d]: (%s).'."\n" ,
                            
    $this -> startnode,$i,$this -> distance[$i],
                            
    count($ourShortestPath[$i]),
                            
    implode('-',$ourShortestPath[$i]));
                }
                
    $foo .= str_repeat('-',20) . "\n";
                    if (
    $to === $i) {
                        break;
                    }
                }
                
                
                
            }
            return 
    $foo;
        }
    }


    define('I',1000);

            
    $points = array(
        array(
    0,1,4),
        array(
    0,2,I),
        array(
    1,2,5),
        array(
    1,3,5),
        array(
    2,3,5),
        array(
    3,4,5),
        array(
    4,5,5),
        array(
    4,5,5),
        array(
    2,10,30),
        array(
    2,11,40),
        array(
    5,19,20),
        array(
    10,11,20),
        array(
    12,13,20),
        array(
    5,6,80),
        array(
    5,7,90),
        array(
    8,0,90),
        array(
    7,10,40),
        array(
    3,12,120),
        array(
    7,9,30),
        array(
    14,5,39),
        array(
    15,16,20),
        array(
    17,16,40),
        array(
    18,15,20),
        array(
    19,0,20),
        array(
    19,18,60),
        array(
    28,19,120),
        array(
    29,19,299),
        array(
    5,27,29),
        array(
    9,20,60),
        array(
    9,29,50),
        array(
    17,22,50),
        array(
    18,23,40),
        array(
    18,24,20),
        array(
    18,25,29),
        array(
    18,26,20),
        array(
    26,21,20),
    );

    // building the map
    $ourMap = array();
    $matrixWidth 30;
    for (
    $i=0;$i<$matrixWidth;$i++) {
        for (
    $k=0;$k<$matrixWidth;$k++) {
            
    $ourMap[$i][$k] = ($i == $k) ? I;
            if (
    $i == $k+) {
                
    $ourMap[$i][$k] = 10;
            }
            if(
    $k == $i+1) {
                
    $ourMap[$i][$k] = 10;
            }
        }
    }
    for (
    $i=0,$m=count($points);$i<$m;$i++) {
        
    $x =  $points[$i][0];
        
    $y =  $points[$i][1];
        
    $c =  $points[$i][2];
        
    assert($x != $y);
        
    $ourMap[$x][$y] = $c;
        
    $ourMap[$y][$x] = $c;
    }



    $dijkstra = new Dijkstra($ourMapI);


    $dijkstra -> findShortestPath(0,22);
    echo 
    '<pre>';
    echo 
    "the map looks like:\n\n";
    echo 
    $dijkstra -> printMap($ourMap);
    echo 
    "\n\nthe shortest path from 0 to 22:\n";
    echo 
    $dijkstra -> getResults(22);
    echo 
    '</pre>';

    ?>
    jetzt musst du nur noch überlegen, wie du dem ding die datenbank-daten ordentlich konvertierst, um den dijkstra-algorithmus zum laufen zu bekommen.

    Kommentar


    • #17
      Zitat von Martin13
      1. Wäre es vielleicht sinvoll die Spalte Feldnummer ganz weg zu lassen? Denn jede Zeile ist ja wenn man x und y zusammen betrachtet auch so schon einzigartig? Bin mir allerdings nicht sicher ob es wirklich Rechenzeit einspart. Man würde dann aber auf jeden Fall nur noch die getit2 Funktion benötigen.
      soweit ich das jetzt einschätze, ist dein algorithmus eh relativ verkehrt, was bedeutet, dass du deinen algorithmus eher wegwerfen solltest, wenn das ganze schneller werden soll.

      2. Ich könnte die Kosten für jeden Typ unterschiedlich machen. (Im Moment sind die Kosten für Strand und Brachland und für Hügel und Gasland gleich) Wenn das der Fall wäre könnte ich den Typ direkt über die kosten definieren und könnte so die kosten wie von dir gefordert in die Tabelle einbringen, ohne eine weiter Spalte zu benötigen.
      du kannst die kosten schon dynamisch lassen, also in der datenbank nur den typ speichern, und das 'wissen' um die kosten in php lassen; mein vorschlag wäre aber, mit einem guten SELECT-statement (stichwort CASE WHEN ) die berechnung der kosten für jedes x-y-tupel bereits von der datenbank berechnen lassen und die berechneten kosten in php nur weiterverwenden und nicht für jedes feld einzeln mit php berechnen.

      3. Ich vermute es würde den Alg. erheblich schneller machen wenn wie von dir ganz zu Anfang vorgeschalgen Zwischenergebnisse gespeichert würden. Denn nach jedenm neune Wegpunkt sind nur wenige neue Berechnungen nötig (nur die von diesem neuen aus). Alle anderen wurden bereits gemacht, werden aber im jetzigem stadium erneut gemacht.
      der 'schlimmste' aufwand ist bei weitem nicht das setup der karte - auch wenn es bei einer größeren karte durchaus sinn machen kann, zwischenergebnisse zu speichern.
      allerdings würde ich das ganze nicht so berechnen, sondern unter der prämisse, dass sich die karte eigentlich nie ändert, die 'fixkosten' von jedem punkt A zu jedem punkt B einmal vorberechnen und in der datenbank speichern. eine typische optimierung 'speicherplatz <-> programmlaufzeit'. d.h. du berechnest mit dem dijkstra-algorithmus einmal alle wege und speicherst die in der datenbank; wenn ein user sich von A nach B bewegt, brauchst du die kosten nur noch auszulesen (bzw. zusätzlich überprüfen, ob sich inzwischen auf einem punkt zwischen A und B ein hindernis befindet).

      4. Meine letzte Vermutung: Kann es sein, dass PHP einfach die falsche Sprache für dieses Problem ist? Und dass es sinvoller wäre das mit Java zu machen?
      php ist grundsätzlich mal eine skriptsprache, die auf programmiersprachen aufsetzt, d.h. du kannst php nicht mit java vergleichen.
      eine hochperformante lösung des problems ist mit php nicht wirklich machbar - php ist für wirklich rechenintensive sachen nicht wirklich gut zu gebrauchen, das stimmt schon. wenn man aber den dijkstra-algorithmus sauber implementiert, hast du aber nicht mehr den n^2-aufwand, sondern nur noch m+n log n - (dafür müsste man die updateDistance() und findBestPath() als binary heap implementieren) - was sich anscheinend aber erst ab kartengrößen mit mehr als 10.000 knoten wirklich bemerkbar macht.

      mit php hast du allerdings noch die möglichkeit, eine eigene extension in C zu schreiben, die du in php einkompilieren kannst - ist zwar eine kunst für sich, aber du könntest allein dadurch ca. 90% ausführungszeit bei den elementar-operationen sparen und vor allem die bestehenden c-implementierungen des algorithmus verwenden.

      ein großes problem ist aber der immense speicherverbrauch - ich hab leider immer noch nicht herausbekommen, warum so viel speicher benötigt wird, aber eine karte mit 1000 einträgen frisst mit der aktuellen version ca. 60 MB RAM - das kann nicht sein. ich find aber leider keine dokumentation zum speicherverhalten des dijkstra-algorithmus.

      die beste optimierung wäre aber meiner meinung nach, nicht den dijkstra- sondern den a* (a star) - algorithmus für die weg-suche zu verwenden ( http://en.wikipedia.org/wiki/A-star_algorithm ) - das ganze funktioniert für deinen anwendungsfall besser.


      Naja werde mir im Moment erstmal überlegen, wie sich die Nutzung von Zwischenergebnissen umsetzen lässt. Auf jeden Fall auch nochmal an dieser Stelle vielen Dank für deine Bemühungen!
      bitte, bitte...

      Kommentar


      • #18
        Den Vorschlag Wegzeiten in der Datenbank zu speichern halte ich für nicht praktikabel. Zum einen kommen mir 211250 Einträge, bei 650 Feldern, ein bisschen viel vor ((650^2)/2). Und außerdem soll mit dem Alg. nicht nur die Zeit sondern auch der genaue Weg gefunden werden. Denn wenn der User später im Spiel bei 50 min. wegzeit nach 30 min abbricht, muss klar sein, auf welchem Feld er sich befindet. Außerdem können ihm auch während des Weges Dinge wiederfahren, es muss also immer kalr sien, auf welchem Feld er im Moment ist.
        Diese 211250 Zeilen große Tabelle müssete damit auch eine recht große Spalte haben, in der der gesamte Weg nachgezeichnet ist...

        Hoffe soch sehr, dass das nicht nötig sein wird...

        Kommentar


        • #19
          So bin jetzt leider wieder die nächsten 2 Wochen im Dienst (Bundeswehr) aber danach kannst du sicher sein, dass ich das Thema wieder aufgreife!!

          Kommentar


          • #20
            Nun ca. 2 Jahre später schaue ich mir gerade meine alten Post an. Ich will hier kurz mal auflösen wie die Sache ausgegangen ist.

            Inzwischen habe ich die 600 großen Felder jeweils noch in 10x10 kleine Felder unterteilt. Ich habe jetzt also 60.000 Felder. Aus diesem Grund und weil ich denke, dass es eh spannender ist wenn die Spieler sich selber einen Weg suchen soll (schließlich soll sich ein guter Spieler ja durch geschickte Aktionen von einem weniger guten absetzen können) habe ich den Pathfindingalgorithmus weggelassen.

            Ich hatte den Algorithmus aber dennoch vorher so weit optimiert, dass er das hier diskutierte Problem in angemessener Zeit lösen konnte.
            Folgende Verbesserungen die hier noch nicht angesprochen wurden erinnere ich noch:

            1. Ich ahbe den Algorithmus vom Start UND vom Zielpunkt gleichzeit laufen lassen. Da mit zunehmender Entfernung die Zeit immernoch leicht exponentiell stieg war die doppelte Zeit für die halbe Strecke günstiger als die eindache Zeit für die volle Strecke.

            2. Ein weiteres Problem ist, dass der Alg. vom Startpunkt in alle Richtungen gleichmäßig sucht, also auch in die dem Ziel genau entgegengesetze. Ich habe also vorher eine die maximalen Kosten berechnet (Luftlinie mit nur den teuersten Knoten). Ich habe dann von Punkten die aktuellen Kosten genommen und überprüft, ob wenn man die Luftlienie zum Zielpunkt nimmt und davon ausgeht, dass überall die günstigsten Felder vorhanden sind, ob dann die kosten noch die Maximalkosten unterbieten. War dies nicht der Fall konnte ich diesen Punkt auf eine "inaktiv" Liste setzen und brauche von diesem aus nicht mehr weiter suchen.

            3. Genauso kamen Punkte wo schon von allen Nachbarn die Kosten errechnet wurden auf diese "inaktiv" Liste.

            Den Script in letzter Version habe ich leider nicht mehr parat. Sollte sich aber jemand dafür interessieren, einfach mich benachrichtigen, dann such ich auf meine Backup-CD mal danach.


            P.S. Vielen Dank nochmal an axo, habe bei erstellen und optimieren dieses Codes doch ne ganze Ecke dazugelernt...

            Kommentar

            Lädt...
            X