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!)
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);
*/
?>
Kommentar