Pathfinding Algorithmus optimieren? (Algorith. von Dijkstra) - Seite 2

Martin13 · 10.07.2005, 00:37

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

Martin13 · 10.07.2005, 00:47

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

*/

?>

Martin13 · 10.07.2005, 15:36

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

axo · 10.07.2005, 20:20

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.

Martin13 · 10.07.2005, 22:27

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!

axo · 10.07.2005, 23:37

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) ? 0 : I;

        if ($i == $k+1 ) {

            $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($ourMap, I);

 
 
$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.

axo · 11.07.2005, 00:01

Zitat:

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.

Zitat:

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.

Zitat:

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

Zitat:

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.

Zitat:

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

Martin13 · 11.07.2005, 00:46

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

Martin13 · 11.07.2005, 20:06

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!!

Martin13 · 04.09.2007, 19: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...

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

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


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

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

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

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

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

10.07.2005, 23:37
axo Erfahrener Benutzer Registriert seit: 24.12.2004 Beiträge: 1.818	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) ? 0 : I; if ($i == $k+1 ) { $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($ourMap, I); $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.

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

11.07.2005, 20:06
Martin13 Neuer Benutzer Registriert seit: 04.07.2005 Beiträge: 24	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!!

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