Ankündigung

Einklappen
Keine Ankündigung bisher.

Pathfinding Algorithmus optimieren? (Algorith. von Dijkstra)

Einklappen

Neue Werbung 2019

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

  • Pathfinding Algorithmus optimieren? (Algorith. von Dijkstra)

    Hallo, habe ein etwas größeres Problem, sicher nicht für Anfänger, da ich aber ein bin habe ich es doch ins Anfängerforum gepostet...

    Ich versuche mich gerade am Erstellen eines Browsergames, bei dem man als einzelne Person auf einer Insel überleben muss. Diese Insel gibt es als Karte mit ca. 600 Feldern. Diese Felder bestehen aus 5 verschiedene Gebietstypen (Strand, Wald, ...) auf denen man sich unterschiedlich gut fortbewegen kann. Mein Ziel war nun einen "pathfinding Algorithmus" zu schreiben, der von einem Punkt A den schnellsten Weg zu Punkt B findet.

    Mein Konzept war vom Ausganspunkt alle angrenzenden Felder zu überprüfen und das günstigste in einen Array aufzunehmen. Im nächsten Schritt wir vom Ausgangspunkt und von dem neuen Feld wieder das günstigeste gesucht, wobei natürlich die Gesamtkosten vom Ausgangsfeld aus der Maßstab sind. Außerdem kann ein Feld, dass bereits in dem Array steht nicht das neue Feld sein. Dieser Vorgang wird so lange fortgesezt (rekursiv aufgerufen) bis das Zielfeld im Array auftaucht. Da immer auch das Vorgängerfeld zu jedem Feld, welches sich im Array befindet, notiert wurde, kann jetzt der günstigste Weg ermittelt werden (Diese "Rüchverfolgung des Weges habe ich allerdings noch nicht umgestzt, dürfte aber kein Problem darstellen)

    Dieses Konzept habe ich auch in PHP umgestzt und an sich funktioniert es auch. Leider ist die rechenzeit bei größeren Abständen VIEL ZU HOCH, sodass der Algorithmus in der Form nicht brauchbar ist.

    Meine Frage ist also, hat jemand ein besseres Konzept? Kann man das Konzept rechenfreundlicher umsetzten (bin Anfänger und habe sicher nicht optimal geproggt)? Sollte man lieber eine andere Sprache verwenden? Oder hat sonst noch jemand Vorschläge wie ich mein Problem lösen kann?

    Allen die sich bis hierher durchgelsen haben schon mal herzlichen Dank! Und noch mehr Dank allen die konstruktive Antworten geben!


    EDIT: Habe gerade entdeckt das mein Konzept wohl als Algorithmus von Dijkstra bereits existiert, das löst aber mein Problem leider nicht...



    Hier meinen Alg. als Anhang:
    (Wenn ich ihn nochmal ausführlicher kommentieren soll, sagt bitte Bescheid!)
    PHP-Code:
    <?php

    session_start
    ();
    include
    "../../includes/connect.php";


    //----------------------------------------------------------------------------//
    //                                                                            //
    //Es soll der kürzeste Weg zum Ziel gefunden werden                           //
    //Dazu wird von Anfanspunkt aus immer der günstigeste Weg eingeschlagen       //
    //                                                                            //
    //----------------------------------------------------------------------------//


    //-----------------------------------------------------------------------
    //Funktion holt mit der Feldnummer die restliches Infos zu diesem Feld
    function getit($feldnr)
    {
    $queryname "SELECT * FROM felder where Feldnr='$feldnr'";
    $resultname mysql_query($queryname) or die($Fehler);
    $feld mysql_fetch_array($resultname);
    return 
    $feld;
    }
    //------------------------------------------------------------------------


    //------------------------------------------------------------------------
    //Funktion holt mit x und y Koordinaten die restlichen Infos zu diesem Feld
    function getit2($x,$y)
    {
    $queryname "SELECT * FROM felder where x='$x' && y='$y'";
    $resultname mysql_query($queryname) or die($Fehler);
    $feld mysql_fetch_array($resultname);
    return 
    $feld;
    }
    //-------------------------------------------------------------------------


    //-------------------------------------------------------------------------
    //Funktion berechnet die Kosten des Weges zwischen 2 benachbarten Feldern
    function kosten($starttyp,$zieltyp)
    {
    switch(
    $starttyp){
        case 
    "1":    $kosten=5;    break;
        case 
    "2":    $kosten=8;    break;
        case 
    "3":    $kosten=5;    break;
        case 
    "4":    $kosten=10;   break;
        case 
    "5":    $kosten=8;    break;
        case 
    "6":    $kosten=15;   break;
        default:    die(
    "Es ist ein Fehler aufgetreten, es konnten die nötige Zeit nicht ermittelt werden.");
        };

    switch(
    $zieltyp){
        case 
    "1":    $kosten=$kosten 5;    break;
        case 
    "2":    $kosten=$kosten 8;    break;
        case 
    "3":    $kosten=$kosten 5;    break;
        case 
    "4":    $kosten=$kosten 10;   break;
        case 
    "5":    $kosten=$kosten 8;    break;
        case 
    "6":    $kosten=$kosten 15;   break;
        default:     die(
    "Es ist ein Fehler aufgetreten");
        };
    return 
    $kosten;
    }
    //------------------------------------------------------------------------


    //------------------------------------------------------------------------
    //Funktion, der Zielvariablen, der Ausgangsfeldtyp und die bisherigen Kosten übergeben werden
    //Es werden dann die neune Kosten dazuaddiert und wenn diese die Kosten unterbieten, die aktuell
    //"geboten" werden, wird der Alte "Schritt" im Array $WEG mit dem neuen erstzt
    function pruefen($xx,$yy,$typ,$b_kosten)
    {
    $test=true;
    $j=0;
    global 
    $i,$weg;
    $feld getit2($xx,$yy);
    $zieltyp $feld[3];
    if(
    $feld[0] != ""){
    while(
    $j<$i){
    $wegj=$weg[$j];
    if (
    $wegj[2] == $feld[0])
    {
    $test=false;}
    $j++;}
    if (
    $test){$kosten kosten($typ,$zieltyp);
    $wegi=$weg[$i];
    //Zu den neuen Zeitkosten werden die bisherigen dazuaddiert
    $kosten=$kosten+$b_kosten;
    if(
    $kosten $wegi[3])
    {
    $weg_i[0]=$xx;
    $weg_i[1]=$yy;
    $weg_i[2]=$feld[0];
    $weg_i[3]=$kosten;

    $weg[$i]=$weg_i;

    }
    else
    {
    $test=true; }

    }}
    }
    //------------------------------------------------------------------------


    //------------------------------------------------------------------------
    //Rekursive Funktion die den günstigsten Weg zu einem Zielpunkt sucht,
    //welcher "global" definiert ist.
    //In dem Array $WEG sind alle Ausgangspunkte mit ihren Kosten gespeichert.
    //Zu beginn steht in diesem Array nur der Startpunkt mit den Kosten Null.
    //
    //Die Funktion überprüft dann zunächst ob das Ziel bereits im Array aufgenommen ist.
    //Ist dies nicht der Fall wird von allen Ausgangspunkten aus die umliegenden Felder
    //auf ihre absoluten Kosten vom Startpunkt aus untersucht. Das günstigste Feld wird neu
    //in den Array aufgenommen. Dies wird rekursiv solang fortgestzt, bis das Zielfeld erreicht wurde
    function pfadfinder(){
    global 
    $i$x$y$weg;
    $i++;
    $q=0;

    $weg_i[3]=1000;
    $weg[$i]=$weg_i;

    while(
    $q<$i){
    $wegq=$weg[$q];
    $x_ein=$wegq[0];
    $y_ein=$wegq[1];
    $q++;

    //Wenn das Zuletzt gefundene Feld das Zielfeld ist, so wird die Funktion abgebrochen
    if($x_ein == $x && $y_ein == $y){
    die(
    "Der Weg wurde gefunden. Die Zeikosten belaufen sich auf $wegq[3] min.");}
    else{

    //Das Ziel muss noch weiter gesucht werden
    //Die 8 Felder um das Ausgangsfeld werden überprüft und das günstigste wir mit "Preis" und Herkunft
    //in die "Tabelle" Weg eingetragen

    //Feldtyp des Ausgangsfeldes bestimmen
    $feld getit2($x_ein,$y_ein);
    $typ $feld[3];


    //Positionen 1-8 (oben, oben/rechts, rechts, unten/rechts, unten, unten/links, links, oben/links)
    pruefen($x_ein,($y_ein 1),$typ,$wegq[3]);
    pruefen(($x_ein 1),($y_ein 1),$typ,$wegq[3]);
    pruefen(($x_ein 1),($y_ein),$typ,$wegq[3]);
    pruefen(($x_ein 1),($y_ein 1),$typ,$wegq[3]);
    pruefen(($x_ein),($y_ein 1),$typ,$wegq[3]);
    pruefen(($x_ein 1),($y_ein 1),$typ,$wegq[3]);
    pruefen(($x_ein 1),($y_ein),$typ,$wegq[3]);
    pruefen(($x_ein 1),($y_ein 1),$typ,$wegq[3]);

    $wegp=$weg[$i];

    $weg_i[0]=$wegp[0];
    $weg_i[1]=$wegp[1];
    $weg_i[2]=$wegp[2];
    $weg_i[3]=$wegp[3];
    $weg_i[4]=$x_ein;
    $weg_i[5]=$y_ein;
    $weg_i[6]=$feld[0];

    $weg[$i]=$weg_i;

    }}

    pfadfinder();


    }
    //Ende der Funktion
    //----------------------------------------------------



    //-----------------------
    //Beginn der Ausführung
    //-----------------------

    //Standort des Spielers bestimmen
    $Fehler="Es ist ein Fehler mit der Datenbank aufgetreten";
    $queryname "SELECT feld FROM spieleraktuell where pid='$_SESSION[name]'";
    $resultname mysql_query($queryname) or die($Fehler);
    $feld mysql_fetch_array($resultname);
    $start getit($feld[0]);

    //Die ist die erste Zeile der "Tabelle" 'WEG'
    //Die ersten drei Daten geben den aktuellen Standpunkt auf dem Weg an, (x,y,feldnummer)
    //die vierte Angabe gibt die Zeitkosten bis zu diesem Punkt an, und die drei letzen
    //Angabe beziehen sich auf das Ausgangsfeld (x,y,feldnummer)
    $weg0[0]=$start[1];
    $weg0[1]=$start[2];
    $weg0[2]=$start[0];
    $weg0[3]=0;
    $weg0[4]=0;
    $weg0[5]=0;
    $weg0[6]=0;

    $weg[0]=$weg0;
    $i=0;

    pfadfinder();

    /*echo"
    ---- $i ----
    ---";
    print_r ($weg);
    */



    ?>


  • #2
    also das erste ist mal, dass du unbedingt deinen code einrücken solltest.

    das zweite: wenn du für jedes feld eine oder zwei datenbank-abfragen produzierst, ist der rechenaufwand natürlich viel zu hoch.
    vorgehensweise also:

    1. alle relevanten feld-daten mit einem einzigen rutsch aus der datenbank holen
    2. den weg innerhalb dieses arrays suchen
    3. gucken, ob du zwischenergebnisse speichern und wiederverwenden kannst.
    4. wenn das korrigierte ergebnis immer noch nicht schnell genug ist, mal den a*- algorithmus angucken.

    Kommentar


    • #3
      Vielen Dank!
      Werd es mal versuchen...
      Übrigens hatte ich mir das auch schon mal überlegt die gesamte Tabelle über die Felder in einen Array einzulesen und diesen dann als Datenquelle zu nehmen. Bin daruaf gekommen weil ich am Anfang noch davon ausgegangen bin, dass jede Datenbankabfrage vom User über die Internetleitung zum Server und zurück geht. Dann ist mir erst kalr geworden, dass das ja alles Serverintern abläuft und damit dachte ich mir, warum sollte das schneller sein? Ist doch egal wo es auf dem Rechner gespeichert ist... (Ja ich bin ein blutiger Anfänger... )

      Aber wird wohl bei deinem Vorschlag in den Arbeitsspeicher genommen und damit ist es schneller?

      Kommentar


      • #4
        Achja schnell nochmal ein paar Fragen zum Umgang mit Arrays. Sonst leg ich wieder los und am Ende brauch der Alg. noch länger...
        Nach deinem Vorschlag werde ich ja erstmal die gesamte Tabelle mit den Feldern in einen Array importiiren. Die Tabelle ist wie folgt aufgebaut
        Feldnummer | x-Koordinate | y-Koordinate | Feldtyp
        Es Ergibt also einen Array mit ca 600 Einträgen (habe ca. 600 Felder) bei den jeder Eintrag wiederum aus einem 4-Einträge großem Array besteht. Eine typische Aufgabe wäre es jetzt mit den beiden Koordinaten den Feldtyp zu bestimmen. Ich würde jetzt einfach mit einer Schleife das Ding durchlaufen lassen und auf Übereinstimmung hoffen. Gibt es da vielleicht günstigere Möglichkeiten? So sql-mäßig:
        Select Feldtyp where das ist so und so...
        Außerdem würde ich gerne wissen ob sowas möglich ist:
        $typ = $weg[$i][3];
        Also ich meine in einem Schritt auf den Wert eines Arrays im Array zu zugreifen.

        Kommentar


        • #5
          grr.

          weil du bereits der zweite an diesem wochenende bist, der die datenbank vergewaltigt, hier mal der beweis:

          tabellen-setup:
          Code:
          CREATE TABLE bm (
            wert tinyint(4) unsigned NOT NULL default '0'
          );
          
          INSERT INTO bm VALUES 
          (1),(2),(3),(4),(5),(6),(7),(8),(9);
          php-code:

          die start_microtime() und end_microtime() sind nur zum zeitmessen da,

          test_1() verwendet deine methode: holt jede kleinigkeit einzeln aus der datenbank.
          test_2() ist meine methode: holt alles mit einer abfrage aus der datenbank.

          PHP-Code:
          <?php

          /** 
           * start_microtime good for debugging purposes.
           * @param void
           * @return mixed
          */
          function start_microtime() {
              list(
          $low$high) = split(" "microtime());
              
          $t $high $low;
              return 
          $t;
          }

          /** 
           * benchmarking.
           * @param mixed start
           * @return string
          */
          function end_microtime($start) {
              list(
          $low$high) = split(" "microtime());
              
          $t    $high $low;
              
          $used intval(($t-$start)*1000000)/1000;
              return 
          $used;
          }

          function 
          test_1() {
              
          $result = array();
              for (
          $i=0;$i<10;$i++) {
                  
          $qry mysql_query('SELECT wert FROM bm 
                                         ORDER BY wert ASC LIMIT '
          .$i ', ' . ($i+1));
                  
          $result[] = mysql_fetch_row($qry);
              }
              return 
          $result;
          }

          function 
          test_2() {
              
          $qry mysql_query('SELECT wert FROM bm ORDER BY wert ASC LIMIT 10');
              
          $result = array();
              while (
          false !== ($result[] = mysql_fetch_row($qry)));
              return 
          $result;
          }

          $con mysql_connect('localhost','username','password');
          mysql_select_db('test',$con);

          $start1 start_microtime();

          for (
          $i=0;$i<1000;$i++) {
              
          $d test_1();
          }

          $end1 end_microtime($start1);

          $start2 start_microtime();

          for (
          $i=0;$i<1000;$i++) {
              
          $d2 test_2();
          }

          $end2 end_microtime($start2);

          assert($d === $d2); // sicherstellen, dass die beiden funktionen ein identisches ergebnis liefern - sonst wär's ja sinnlos.
          echo '<pre>';
          var_dump($end1);
          var_dump($end2);
          echo 
          '</pre>';
          die();
          ?>
          und jetzt sag mir mal, welche methode die schnellere ist.

          Kommentar


          • #6
            was du (und alle anderen datenbank-vergewaltiger hier) lernen sollst:

            1. aus der datenbank werden nur _genau die_ werte geholt, die wirklich benötigt werden.
            2. genau die werte, die gebraucht werden, holt man sich in möglichst wenigen einzel-abfragen.
            3. die datenbank wird _niemals_ rekursiv abgefragt.
            4. die datenbank ist immer gut darin, elementar-mathe zu lösen: summen, extrema, addition, subtraktion, datumsberechnung etc. macht sie mehrfach schneller als php das jemals schaffen wird. also versuchen wir, möglichst viele daten aus der datenbank gar nicht erst rauszuholen, sondern lassen mit klugen SELECTs und durchdachten UPDATEs die datenbank rechnen, zwischenergebnisse generieren - wir holen uns nach möglichkeit nur das endergebnis ab.

            Kommentar


            • #7
              *nochmal hochschieb* die aktuelle implementierung würde mich interessieren.

              Kommentar


              • #8
                So, habe leider immer nur am WE Zeit was zu tun, aber habe jetzt mal deinen ersten Tipp beherzigt und zu Beginn die Tabelle Felder komplett eingelesen. Dafür musste ich nur die Funktionen getit und getit2 ändern. Diese sind dafür vorgeshen aus der Feldnummer bzw. den beiden Kordinaten die restlichen Infos über ein feld zu suchen. Deren Datenquelle ist jezt nicht mehr die DB sondern der Array: Der neue bzw. geänderte Script sieht jetzt so aus:
                Achso das wichtigest habe ich noch gar nocht erwähnt: Die Geschwindigkeit hat sich leider nicht spürbar verbessert...

                Aber ich bin überzeugt, dass du noch ein paar Macken findest


                PHP-Code:
                <?php
                //-----------------------------------------------------------------------
                //Funktion holt mit der Feldnummer die restliches Infos zu diesem Feld
                function getit($feldnr)
                {
                global 
                $t_felder;
                $i=0;
                while (
                $t_felder[$i]!='')
                {
                   
                $reihe=$t_felder[$i];
                   if(
                $reihe[0]==$feldnr){
                         return 
                $reihe;
                         }
                         
                $i++;
                }
                }
                //------------------------------------------------------------------------


                //------------------------------------------------------------------------
                //Funktion holt mit x und y Koordinaten die restlichen Infos zu diesem Feld
                function getit2($x,$y)
                {
                global 
                $t_felder;
                $i=0;

                while (
                $t_felder[$i]!='')
                {
                   
                $reihe=$t_felder[$i];
                   if(
                $reihe[1]==$x){
                         if(
                $reihe[2]==$y){
                                  return 
                $reihe;
                                  }
                         }
                         
                $i++;
                }}
                //-------------------------------------------------------------------------
                ?>
                Außerdem noch die DB-Abfrage, die die Tabelle in dem Array speichert:
                PHP-Code:
                <?php
                $queryname 
                "SELECT * FROM felder";
                $resultname mysql_query($queryname) or die($Fehler);
                while (
                $t_felder[] = mysql_fetch_row($resultname)) {}
                ?>

                Kommentar


                • #9
                  hi, die suche getit() ist ganz schlecht gelöst und getit2() müsste man komplett anders aufsetzen.

                  zur getit():

                  PHP-Code:
                  <?php
                  $queryname 
                  "SELECT Feldnr,x,y, .... FROM felder";
                  $resultname mysql_query($queryname) or die($Fehler);
                  $t_felder = array();
                  while (
                  $d mysql_fetch_assoc($resultname)) {
                    
                  $t_felder[$d['Feldnr']] = $d// $t_felder index setzen, damit getit() das zeug finden kann.


                  function 
                  getit($feldnr){
                    global 
                  $t_felder;
                    
                  assert(array_key_exists($feldnr,$t_felder));
                   return 
                  $t_felder[$feldnr];
                  }
                  ?>
                  die sache ist jetzt erstmal aber die:

                  um die suche getit2() richtig schnell hinzubekommen, müsste es eine direkte beziehung zwischen feldnummer und den koordinaten x und y geben.

                  normalerweise macht man das so (hier am beispiel einer 2x5-matrix):
                  die indizierung sollte so sein: (hier mal die feldIDs für die matrix)
                  PHP-Code:


                  damit sind dann x und y:
                  PHP-Code:
                  y
                  0



                  0
                  1
                  1
                  1
                  1

                  das heißt, es existiert eine direkte beziehung zwischen x und y, und damit kann man mit einer einzigen rechnung aus x und y die feld-ID ermitteln, und zwar
                  PHP-Code:
                  function findIndex($x,$y) {
                    
                  $anzahlSpalten 5;
                    return (
                  $y $anzahlSpalten) + $x;

                  ... womit du nicht erst das komplette array nach x und y durchsuchen musst, um den korrekten wert zu finden.

                  eigentlich dürfte sich, wenn die matrix mal aufgebaut ist, an den feldnummern und an x und y nichts mehr ändern. schließlich wär's ja blöd, wenn plötzlich felder dazukommen.

                  wenn 'zeilen' in die matrix dazukommen, ist das ganze auch nicht wirklich schlimm - dann zählt die feldnr halt hoch. bei spalten muss man sich dann aber einen sehr guten update-algorithmus überlegen...

                  Kommentar


                  • #10
                    so... und damit ich das auch testen kann:

                    bitte ein komplette datenbank-dump posten (die felder-tabelle mit komplettem CREATE-befehl und testdaten - einfach mit phpmyadmin exportieren),
                    und den aktuellen code komplett.

                    Kommentar


                    • #11
                      Ok, die Tabelle Felder ist folgender Maßen aufgebaut:
                      Feldnummer | x-Koordinate | y-Koordinate | Feldtyp | Flusstyp

                      Flusstyp gibt an, ob sich an einer oder mehreren Kanten des quadratischen Feldes ein Fluss befinded. Die Zahl gibt die Position an und so kann dann gepüft werden, ob ein Fluss überquert werden muss, was mit zusätzlichen Zeitkosten verbunden ist. Diesen Zusatz habe ich jedoch noch nicht implementiert.

                      Zu der Karte als ganzes: Sie ist nicht quadratisch oder rechteckig aufgebaut, und daher gibt es keinen direkten Zusammenhang zwischen Feldnummer und den Koordinaten.

                      Hier erstmal die ersten 50 Datensätze der Tabelle:
                      (insgesamt sind es 662)

                      # phpMyAdmin SQL Dump
                      # version 2.5.5-pl1
                      # http://www.phpmyadmin.net
                      #
                      # Host: localhost
                      # Generation Time: Jul 10, 2005 at 12:30 AM
                      # Server version: 4.0.17
                      # PHP Version: 4.3.4
                      #
                      # Database : `inselspiel`
                      #

                      # --------------------------------------------------------

                      #
                      # Table structure for table `felder`
                      #

                      CREATE TABLE `felder` (
                      `Feldnr` smallint(5) unsigned NOT NULL default '0',
                      `x` tinyint(3) unsigned NOT NULL default '0',
                      `y` tinyint(3) unsigned NOT NULL default '0',
                      `typ` tinyint(4) NOT NULL default '0',
                      `fluss` tinyint(1) NOT NULL default '0',
                      PRIMARY KEY (`Feldnr`)
                      ) TYPE=MyISAM;

                      #
                      # Dumping data for table `felder`
                      #

                      INSERT INTO `felder` VALUES (1, 21, 1, 1, 0);
                      INSERT INTO `felder` VALUES (2, 22, 1, 1, 0);
                      INSERT INTO `felder` VALUES (3, 23, 1, 1, 0);
                      INSERT INTO `felder` VALUES (4, 18, 2, 1, 0);
                      INSERT INTO `felder` VALUES (5, 19, 2, 1, 0);
                      INSERT INTO `felder` VALUES (6, 20, 2, 1, 0);
                      INSERT INTO `felder` VALUES (7, 21, 2, 1, 0);
                      INSERT INTO `felder` VALUES (8, 22, 2, 3, 0);
                      INSERT INTO `felder` VALUES (9, 23, 2, 1, 0);
                      INSERT INTO `felder` VALUES (10, 16, 3, 1, 0);
                      INSERT INTO `felder` VALUES (11, 17, 3, 1, 0);
                      INSERT INTO `felder` VALUES (12, 18, 3, 1, 0);
                      INSERT INTO `felder` VALUES (13, 19, 3, 5, 0);
                      INSERT INTO `felder` VALUES (14, 20, 3, 3, 0);
                      INSERT INTO `felder` VALUES (15, 21, 3, 3, 0);
                      INSERT INTO `felder` VALUES (16, 22, 3, 3, 0);
                      INSERT INTO `felder` VALUES (17, 23, 3, 1, 0);
                      INSERT INTO `felder` VALUES (18, 24, 3, 1, 0);
                      INSERT INTO `felder` VALUES (19, 14, 4, 1, 4);
                      INSERT INTO `felder` VALUES (20, 15, 4, 1, 1);
                      INSERT INTO `felder` VALUES (21, 16, 4, 1, 0);
                      INSERT INTO `felder` VALUES (22, 17, 4, 2, 0);
                      INSERT INTO `felder` VALUES (23, 18, 4, 2, 0);
                      INSERT INTO `felder` VALUES (24, 19, 4, 5, 0);
                      INSERT INTO `felder` VALUES (25, 20, 4, 4, 0);
                      INSERT INTO `felder` VALUES (26, 21, 4, 4, 0);
                      INSERT INTO `felder` VALUES (27, 22, 4, 3, 0);
                      INSERT INTO `felder` VALUES (28, 23, 4, 3, 0);
                      INSERT INTO `felder` VALUES (29, 24, 4, 1, 0);
                      INSERT INTO `felder` VALUES (30, 25, 4, 1, 0);
                      INSERT INTO `felder` VALUES (31, 26, 4, 1, 0);
                      INSERT INTO `felder` VALUES (32, 13, 5, 1, 0);
                      INSERT INTO `felder` VALUES (33, 14, 5, 1, 4);
                      INSERT INTO `felder` VALUES (34, 15, 5, 4, 1);
                      INSERT INTO `felder` VALUES (35, 16, 5, 2, 0);
                      INSERT INTO `felder` VALUES (36, 17, 5, 2, 0);
                      INSERT INTO `felder` VALUES (37, 18, 5, 5, 0);
                      INSERT INTO `felder` VALUES (38, 19, 5, 5, 0);
                      INSERT INTO `felder` VALUES (39, 20, 5, 4, 0);
                      INSERT INTO `felder` VALUES (40, 21, 5, 4, 0);
                      INSERT INTO `felder` VALUES (41, 22, 5, 3, 0);
                      INSERT INTO `felder` VALUES (42, 23, 5, 3, 0);
                      INSERT INTO `felder` VALUES (43, 24, 5, 3, 0);
                      INSERT INTO `felder` VALUES (44, 25, 5, 3, 0);
                      INSERT INTO `felder` VALUES (45, 26, 5, 1, 0);
                      INSERT INTO `felder` VALUES (46, 27, 5, 1, 0);
                      INSERT INTO `felder` VALUES (47, 28, 5, 1, 0);
                      INSERT INTO `felder` VALUES (48, 29, 5, 1, 0);
                      INSERT INTO `felder` VALUES (49, 30, 5, 1, 0);
                      INSERT INTO `felder` VALUES (50, 31, 5, 1, 0);

                      Kommentar


                      • #12
                        So und nun wie gefordert den kopellten aktuellen Alg.
                        Wie gesagt er funktioniert, ist aber viel zu langsam....

                        PHP-Code:
                        <?php
                        //in der Session ist die Spielernummer gespeichert, mit deren Hilfe der
                        //Standpunkt des Spielers bestimmt werden kann, die Zielkoordinaten (x und y) 
                        //werden dem Alg. übergeben
                        session_start();
                        include
                        "../../includes/connect.php";


                        //----------------------------------------------------------------------------//
                        //                                                                            //
                        //Es soll der kürzeste Weg zum Ziel gefunden werden                           //
                        //Dazu wird von Anfanspunkt aus immer der günstigeste Weg eingeschlagen       //
                        //                                                                            //
                        //----------------------------------------------------------------------------//


                        //-----------------------------------------------------------------------
                        //Funktion holt mit der Feldnummer die restliches Infos zu diesem Feld
                        function getit($feldnr)
                        {
                        global 
                        $t_felder;
                        $i=0;
                        while (
                        $t_felder[$i]!='')
                        {
                           
                        $reihe=$t_felder[$i];
                           if(
                        $reihe[0]==$feldnr){
                                 return 
                        $reihe;
                                 }
                                 
                        $i++;
                        }
                        }
                        //------------------------------------------------------------------------


                        //------------------------------------------------------------------------
                        //Funktion holt mit x und y Koordinaten die restlichen Infos zu diesem Feld
                        function getit2($x,$y)
                        {
                        global 
                        $t_felder;
                        $i=0;

                        while (
                        $t_felder[$i]!='')
                        {
                           
                        $reihe=$t_felder[$i];
                           if(
                        $reihe[1]==$x){
                                 if(
                        $reihe[2]==$y){
                                          return 
                        $reihe;
                                          }
                                 }
                                 
                        $i++;
                        }}
                        //-------------------------------------------------------------------------


                        //-------------------------------------------------------------------------
                        //Funktion berechnet die Kosten des Weges zwischen 2 benachbarten Feldern
                        function kosten($starttyp,$zieltyp)
                        {
                        switch(
                        $starttyp){
                            case 
                        "1":    $kosten=5;    break;
                            case 
                        "2":    $kosten=8;    break;
                            case 
                        "3":    $kosten=5;    break;
                            case 
                        "4":    $kosten=10;   break;
                            case 
                        "5":    $kosten=8;    break;
                            case 
                        "6":    $kosten=15;   break;
                            default:    die(
                        "Es ist ein Fehler aufgetreten, es konnten die nötige Zeit nicht ermittelt werden.");
                            };

                        switch(
                        $zieltyp){
                            case 
                        "1":    $kosten=$kosten 5;    break;
                            case 
                        "2":    $kosten=$kosten 8;    break;
                            case 
                        "3":    $kosten=$kosten 5;    break;
                            case 
                        "4":    $kosten=$kosten 10;   break;
                            case 
                        "5":    $kosten=$kosten 8;    break;
                            case 
                        "6":    $kosten=$kosten 15;   break;
                            default:     die(
                        "Es ist ein Fehler aufgetreten");
                            };
                        return 
                        $kosten;
                        }
                        //------------------------------------------------------------------------


                        //------------------------------------------------------------------------
                        //Funktion, der Zielvariablen, der Ausgangsfeldtyp und die bisherigen Kosten übergeben werden
                        //Es werden dann die neune Kosten dazuaddiert und wenn diese die Kosten unterbieten, die aktuell
                        //"geboten" werden, wird der Alte "Schritt" im Array $WEG mit dem neuen erstzt
                        function pruefen($xx,$yy,$typ,$b_kosten)
                        {
                        $test=true;
                        $j=0;
                        global 
                        $i,$weg;
                        $feld getit2($xx,$yy);
                        $zieltyp $feld[3];
                        if(
                        $feld[0] != ""){
                        while(
                        $j<$i){
                        $wegj=$weg[$j];
                        if (
                        $wegj[2] == $feld[0])
                        {
                        $test=false;}
                        $j++;}
                        if (
                        $test){$kosten kosten($typ,$zieltyp);
                        $wegi=$weg[$i];
                        //Zu den neuen Zeitkosten werden die bisherigen dazuaddiert
                        $kosten=$kosten+$b_kosten;
                        if(
                        $kosten $wegi[3])
                        {
                        $weg_i[0]=$xx;
                        $weg_i[1]=$yy;
                        $weg_i[2]=$feld[0];
                        $weg_i[3]=$kosten;

                        $weg[$i]=$weg_i;

                        }
                        else
                        {
                        $test=true; }

                        }}
                        }
                        //------------------------------------------------------------------------


                        //------------------------------------------------------------------------
                        //Rekursive Funktion die den günstigsten Weg zu einem Zielpunkt sucht,
                        //welcher "global" definiert ist.
                        //In dem Array $WEG sind alle Ausgangspunkte mit ihren Kosten gespeichert.
                        //Zu beginn steht in diesem Array nur der Startpunkt mit den Kosten Null.
                        //
                        //Die Funktion überprüft dann zunächst ob das Ziel bereits im Array aufgenommen ist.
                        //Ist dies nicht der Fall wird von allen Ausgangspunkten aus die umliegenden Felder
                        //auf ihre absoluten Kosten vom Startpunkt aus untersucht. Das günstigste Feld wird neu
                        //in den Array aufgenommen. Dies wird rekursiv solang fortgestzt, bis das Zielfeld erreicht wurde
                        function pfadfinder(){
                        global 
                        $i$x$y$weg;
                        $i++;
                        $q=0;

                        $weg_i[3]=1000;
                        $weg[$i]=$weg_i;

                        while(
                        $q<$i){
                        $wegq=$weg[$q];
                        $x_ein=$wegq[0];
                        $y_ein=$wegq[1];
                        $q++;

                        //Wenn das Zuletzt gefundene Feld das Zielfeld ist, so wird die Funktion abgebrochen
                        if($x_ein == $x && $y_ein == $y){
                        die(
                        "Der Weg wurde gefunden. Die Zeikosten belaufen sich auf $wegq[3] min.");}
                        else{

                        //Das Ziel muss noch weiter gesucht werden
                        //Die 8 Felder um das Ausgangsfeld werden überprüft und das günstigste wir mit "Preis" und Herkunft
                        //in die "Tabelle" Weg eingetragen

                        //Feldtyp des Ausgangsfeldes bestimmen
                        $feld getit2($x_ein,$y_ein);
                        $typ $feld[3];


                        //Positionen 1-8 (oben, oben/rechts, rechts, unten/rechts, unten, unten/links, links, oben/links)
                        pruefen($x_ein,($y_ein 1),$typ,$wegq[3]);
                        pruefen(($x_ein 1),($y_ein 1),$typ,$wegq[3]);
                        pruefen(($x_ein 1),($y_ein),$typ,$wegq[3]);
                        pruefen(($x_ein 1),($y_ein 1),$typ,$wegq[3]);
                        pruefen(($x_ein),($y_ein 1),$typ,$wegq[3]);
                        pruefen(($x_ein 1),($y_ein 1),$typ,$wegq[3]);
                        pruefen(($x_ein 1),($y_ein),$typ,$wegq[3]);
                        pruefen(($x_ein 1),($y_ein 1),$typ,$wegq[3]);

                        $wegp=$weg[$i];

                        $weg_i[0]=$wegp[0];
                        $weg_i[1]=$wegp[1];
                        $weg_i[2]=$wegp[2];
                        $weg_i[3]=$wegp[3];
                        $weg_i[4]=$x_ein;
                        $weg_i[5]=$y_ein;
                        $weg_i[6]=$feld[0];

                        $weg[$i]=$weg_i;

                        }}

                        pfadfinder();


                        }
                        //Ende der Funktion
                        //----------------------------------------------------



                        //-----------------------
                        //Beginn der Ausführung
                        //-----------------------

                        $Fehler="Es ist ein Fehler mit der Datenbank aufgetreten";

                        //Gesamte Tabelle Felder aus der Datenbank exportieren um im
                        //Laufe des Programmes keine weiteren Abfragen mehr stellen zu müssen.
                        $queryname "SELECT * FROM felder";
                        $resultname mysql_query($queryname) or die($Fehler);
                        while (
                        $t_felder[] = mysql_fetch_row($resultname)) {}


                        //Standort des Spielers bestimmen
                        $queryname "SELECT feld FROM spieleraktuell where pid='$_SESSION[name]'";
                        $resultname mysql_query($queryname) or die($Fehler);
                        $feld mysql_fetch_array($resultname);
                        $start getit($feld[0]);


                        //Die ist die erste Zeile der "Tabelle" 'WEG'
                        //Die ersten drei Daten geben den aktuellen Standpunkt auf dem Weg an, (x,y,feldnummer)
                        //die vierte Angabe gibt die Zeitkosten bis zu diesem Punkt an, und die drei letzen
                        //Angabe beziehen sich auf das Ausgangsfeld (x,y,feldnummer)
                        $weg0[0]=$start[1];
                        $weg0[1]=$start[2];
                        $weg0[2]=$start[0];
                        $weg0[3]=0;
                        $weg0[4]=0;
                        $weg0[5]=0;
                        $weg0[6]=0;

                        $weg[0]=$weg0;
                        $i=0;

                        pfadfinder();

                        /*echo"
                        ---- $i ----
                        ---";
                        print_r ($weg);
                        */
                        ?>

                        Kommentar


                        • #13
                          Habe jetzt mal versucht meine Anfänge an dem Spiel bei Lycos zu veröffentlichen. Leider funktionieren die meisten Links noch nicht (konnte noch nicht ergründen warum nicht). Aber wenn ihr euch unter http://mitglied.lycos.de/muk13/Insel...iten/login.php
                          mit "Martin" und PW.: "a" anmeldet könnt ihr zumindest mal einen Blick auf die Karte werfen um die es geht...

                          @Axo: Die Scriptverbesserungen die du hier vorgeschlagen hast habe ich leider noch nicht lauffähig einbauen können...

                          Kommentar


                          • #14
                            jo, das ganze kannst völlig knicken.
                            hab jetzt mal zum spaß das actionscript-beispiel von wikipedia nach php übersetzt, und es läuft erstaunlicherweise ganz gut - allerdings nicht mit dem best-case-aufwand von O (n log m ) sondern immer noch mit O(n^2) ... das heißt, das ganze braucht bei 100 knoten 40 ms und 1 MB speicher, bei 1000 knoten aber immer noch knapp über eine sekunde zum rechnen und 60 MB speicher. deutlich zu viel.

                            ich versuche immer noch zu verstehen, was sich da noch optimieren lässt.
                            da 'hin-' und 'rückweg' in diesem fall jeweils die gleichen kosten haben, sollte es theoretisch möglich sein, mit einer dreiecksmatrix zu arbeiten und die hälfte der operationen auszusparen, aber das ist bei mir leider zu lange her. mal gucken, ob ich's noch finde.


                            die haupt-probleme, die du hast, sind erstmal folgende:

                            1. die 'kostenberechnung' darf auf keinen fall dynamisch sein, d.h. du darfst nicht jedes mal die kosten für den weg von einem knoten zum nächsten dynamisch berechnen, sonst wird der algorithmus nicht fertig. die kosten für jedes feld kann man entweder in der datenbank selbst als zusätzliche spalte speichern oder aber mit dem SELECT gleich die multiplikationen ausführen, um die kosten gleich an den dijkstra-algorithmus zu übergeben.
                            2. der dijkstra-algorithmus braucht eine ganz bestimmte struktur, um wirklich schnell zu arbeiten, und das bedeutet, dass du die in der datenbank stehenden daten erstmal umwandeln musst, um sie dem dijkstra-algorithmus zu übergeben. da bin ich grad am gucken, was man dort noch machen kann.

                            Kommentar


                            • #15
                              Vier Dinge die mir dazu einfallen und zu denen ich gerne deine Meinung wissen würde:

                              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.

                              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.

                              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.

                              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?

                              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!

                              Kommentar

                              Lädt...
                              X