Pathfinding Algorithmus optimieren? (Algorith. von Dijkstra)

Martin13 · 04.07.2005, 00:37

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

*/

 
 
 
?>

axo · 04.07.2005, 00:54

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.

Martin13 · 04.07.2005, 01:10

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?

Martin13 · 04.07.2005, 01:27

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.

axo · 04.07.2005, 01:59

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.

axo · 04.07.2005, 02:09

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.

axo · 05.07.2005, 10:21

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

Martin13 · 09.07.2005, 18:18

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)) {}

?>

axo · 09.07.2005, 19:12

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:

  0 | 1 | 2 | 3 | 4 

5 | 6 | 7 | 8 | 9

damit sind dann x und y:

PHP-Code:

  i | x | y

0 | 0 | 0

1 | 1 | 0 

2 | 2 | 0 

3 | 3 | 0 

4 | 4 | 0

5 | 0 | 1

6 | 1 | 1

7 | 2 | 1

8 | 3 | 1

9 | 4 | 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...

axo · 09.07.2005, 19:13

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.

Themen-Optionen
Druckbare Version zeigen Jemanden per E-Mail auf dieses Thema hinweisen
Thema bewerten
Thema bewerten:

04.07.2005, 00:37
Martin13 Neuer Benutzer Registriert seit: 04.07.2005 Beiträge: 24	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); / ?>


Mister Ad PHP Code Flüsterer Registriert seit: 21.08.2005 Beiträge: 4682 PHP-Kenntnisse: Fortgeschritten

04.07.2005, 00:54
axo Erfahrener Benutzer Registriert seit: 24.12.2004 Beiträge: 1.818	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.

04.07.2005, 01:10
Martin13 Neuer Benutzer Registriert seit: 04.07.2005 Beiträge: 24	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?

04.07.2005, 01:27
Martin13 Neuer Benutzer Registriert seit: 04.07.2005 Beiträge: 24	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.

04.07.2005, 01:59
axo Erfahrener Benutzer Registriert seit: 24.12.2004 Beiträge: 1.818	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.

04.07.2005, 02:09
axo Erfahrener Benutzer Registriert seit: 24.12.2004 Beiträge: 1.818	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.

05.07.2005, 10:21
axo Erfahrener Benutzer Registriert seit: 24.12.2004 Beiträge: 1.818	nochmal hochschieb die aktuelle implementierung würde mich interessieren.

09.07.2005, 18:18
Martin13 Neuer Benutzer Registriert seit: 04.07.2005 Beiträge: 24	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)) {} ?>`

09.07.2005, 19:12
axo Erfahrener Benutzer Registriert seit: 24.12.2004 Beiträge: 1.818	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: `0 \| 1 \| 2 \| 3 \| 4 5 \| 6 \| 7 \| 8 \| 9` damit sind dann x und y: PHP-Code: `i \| x \| y 0 \| 0 \| 0 1 \| 1 \| 0 2 \| 2 \| 0 3 \| 3 \| 0 4 \| 4 \| 0 5 \| 0 \| 1 6 \| 1 \| 1 7 \| 2 \| 1 8 \| 3 \| 1 9 \| 4 \| 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...

09.07.2005, 19:13
axo Erfahrener Benutzer Registriert seit: 24.12.2004 Beiträge: 1.818	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.