nicht angemeldet
Hallo,
ich bin gerade dabei einige PHP Funktionen meines Browsergames zu überarbeiten, um die Ablaufzeiten zu verkürzen.
Folgendes Problem hat sich mir da in den Weg gestellt:
Hintergrund: Das Spielfeld baut sich in Form einer 2 dimensionalen Karte (x/y) auf... Jeder Spieler kann eine unbegrenzte Anzahl an Feldern besitzen, wobei jeder Spieler und somit jedes Feld eine eigene Sichtweite erhält (bspw. können im Umkreis von 5 Feldern eines Feldes alle anderen Felder, ob nun besetzt oder nicht, mit eingesehen werden...).
Okay, daher lese ich aus meiner Feld-Tabelle alle Felder des/der Spieler aus, sowie die dazugehörige Sichtweite... dann lese ich die Daten in einer Schleife ein und lege für jedes Feld die minimale bzw. maximale Ausdehnung der Sichtweite des entsprechenden Feldes fest (im Quellcode mit $spyMinY, $spyMaxY, $spyMinX, $spyMaxX angegeben)...
Das eigentliche Problem stellt sich nun im füllen des Arrays $nodes (Knotenpunkte, welche ich für dem A* Path-Finding Algorithmus benötige... hierfür aber unwichtig!).
Und zwar habe ich nun ein 2 dimensionales Array ($nodes), in welchem ich die sichtbaren Felder (Bereiche) $nodes[X][Y] auf true setze... um zu sichern, ob dieses Feld für den Spieler sichtbar ist.
Achtung: Es handelt sich hierbei um extrem große Datenmengen!!!
Die MySQL Abfrage inkl. Schleifendurchläufe und Ermittlung der jeweils kleinsten und größten Ausdehnung des Sichtbereiches eines Feldes, benötigt nur rund 3 Sek.!!!
---------------------------------------------
Okay, mein erster Versuch 2 ineinander verschachtelte Schleifen zu bauen, welche das Array füllen:
for ($x = $spyMinX; $x <= $spyMaxX; $x++) for ($y = $spyMinY; $y <= $spyMaxY; $y++) $nodes[$x][$y] = true;
bringt eine Ausführungszeit von über 1 Minute, ist also nicht brauchbar!
---------------------------------------------
Mein zweiter Versuch:
$nodes = array();
$arrTmp = array(); $arrTmp = array_fill($spyMinY, $spyMaxY - $spyMinY + 1, true);
for ($x = $spyMinX; $x <= $spyMaxX; $x++) {
if (!isset($nodes[$x])) $nodes[$x] = array();
$nodes[$x] += $arrTmp;
}
Ich lege für den Y-Bereich ein separates Array $arrTmp an, welches ich dann mit dem jeweiligen X-Wert des Arrays $nodes vereine... dies verkürzt die Ausführungszeit erheblich (Test: 18 - 30 Sek.)
Das Problem ist nun, dass zu jedem X-Wert verschiedenste Y-Bereiche zugeordnet werden können.. also bspw. Bereich Y von 100 bis 200, 350 bis 400, 1000 bis 1200 usw... von daher muss ich den Operator += verwenden, um den Inhalt von $nodes[$x] nicht komplett zu überschreiben, sondern die neuen Keys mit den alten zu vereinen...
---------------------------------------------
Mein 3. Versuch:
$arrTmp = array(); $arrTmp = array_fill($spyMinY, $spyMaxY - $spyMinY + 1, true);
for ($x = $spyMinX; $x <= $spyMaxX; $x++) {
if (!isset($nodes[$x])) $nodes[$x] = array();
array_push($nodes[$x], $arrTmp);
}
Die Grundidee ist das gleiche wie bei dem 2. Versuch... jedoch verwende ich um die Arrayinhalte zu vereinen den Befehl array_push()... dies bringt eine Ausführungszeit von 8 - 10 Sek. (ist schon nicht annehmbarer...) Jedoch hat die Funktion array_push einen riesigen Nachteil: Die neuen Keys werden einfach am Ende des Arrays angehangen ohne zu prüfen ob diese evtl. schon vorhanden sind... dies bringt letztendlich ein extrem großes Array hervor, welches einen enormen Speicherplatz beansprucht...
---------------------------------------------
Da diese Funktion relativ oft verwendet wird, würde ich diese gern optimieren... leider fehlt mir hierzu noch die passende Idee, um die Ausführungszeit etwas zu beschleunigen.
Noch einmal mein Fazit:
-
Füllen des Arrays durch in zwei ineinander verschachtelte Zählschleifen bringt eine Ausführungszeit von über 1 Minute (unbrauchbar)...
-
Mit dem Operator += wird das Ganze in ca. 18 - 30 Sek. durchlaufen (meine bisher angewandte Methode)... += prüft ob ein Key bereits vorhanden ist, wenn ja überspringt er diesen...
-
Durch die Verwendung der PHP Funktion array_push() wird eine Ausführungszeit von rund 8 bis 10 Sek. erreicht (annehmbar, bei großen Datenmengen)... jedoch wird ein zu großes Array erzeugt, da neue Keys ohne Prüfung am Ende des Arrays angehangen werden.
So ich hoffe ihr habt ein wenig verstanden um was es mir geht, und hoffe ihr könnt mir ein paar Ideen zur Optimierung geben...
Beste Grüße
Stefan Richter
Hier noch einmal der vollständige Quellcode mit MySQL Abfrage:
$strSQL = " SELECT
f.pos_x, f.pos_y, if(fr.buildtime > now(), fr.stufe - 1, fr.stufe) as spy
FROM
field f
LEFT JOIN alliance a ON a.fromuser = 1 AND a.touser = f.username
LEFT JOIN field_units fu ON fu.username = 1 AND fu.fid = f.id
LEFT JOIN field_research fr ON fr.username = f.username
WHERE
(f.username = 1 OR fu.username = 1 OR a.fromuser = 1) AND fr.typ = 26 AND
((f.pos_x < ".$minX." AND f.pos_x + if(fr.buildtime > now(), fr.stufe - 1, fr.stufe) >= ".$minX.") OR (f.pos_x > ".$maxX." AND f.pos_x - if(fr.buildtime > now(), fr.stufe - 1, fr.stufe) <= ".$maxX.") OR f.pos_x BETWEEN ".$minX." AND ".$maxX.") AND
((f.pos_y < ".$minY." AND f.pos_y + if(fr.buildtime > now(), fr.stufe - 1, fr.stufe) >= ".$minY.") OR (f.pos_y > ".$maxY." AND f.pos_y - if(fr.buildtime > now(), fr.stufe - 1, fr.stufe) <= ".$maxY.") OR f.pos_y BETWEEN ".$minY." AND ".$maxY.");";
$clsDB->query($strSQL, true);
while ($row = $clsDB->getResult()) {
$spyMinX = $row['pos_x'] - $row['spy']; if ($spyMinX < $minX) $spyMinX = $minX;
$spyMinY = $row['pos_y'] - $row['spy']; if ($spyMinY < $minY) $spyMinY = $minY;
$spyMaxX = $row['pos_x'] + $row['spy']; if ($spyMaxX > $maxX) $spyMaxX = $maxX;
$spyMaxY = $row['pos_y'] + $row['spy']; if ($spyMaxY > $maxY) $spyMaxY = $maxY;
$arrTmp = array(); $arrTmp = array_fill($spyMinY, $spyMaxY - $spyMinY + 1, true);
for ($x = $spyMinX; $x <= $spyMaxX; $x++) {
if (!isset($nodes[$x])) $nodes[$x] = array();
$nodes[$x] += $arrTmp;
array_push($nodes[$x], $arrTmp);
}
}
$clsDB->free();