nicht angemeldet
2 dimensionales Array füllen
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();
-
Hello,
ich lese das jetzt schon seit einiger Zeit mit Interesse mit.
Mal 'ne ganz dumme Frage zwischendurch:
Hat das Spielfeld eine endliche Ausdehnung oder erweitert sich das während des Spieles ständig?Für ein endliches Grid, das nur TRUE oder FALSE oder maximal eben 256 unterschiedliche Werte pro Zelle enthalten muss, nehme ich in PHP immer ein "Array of String"
Das benötigt erheblich weniger Platz, als ein PHP-Array, also eine Baumstruktur und ist um einiges schnellerDie Vergewaltigung der Typen in PHP ist mMn manchmal die Lösung.
<?php ### string_grid.php ###
error_reporting(E_ALL);
$_grid = array();
$width = 1000;
$height = 1000;$zeile = str_repeat(chr(0),$width);
for ($i = 1; $i <= $height; $i++)
{
$_grid[$i] = $zeile;
}# Um mehr Daten zu speichern, kannst Du eine zweite Plane einführen.
# Du kannst auf jede Zelle einzeln zugreifen.$zelle10_15 = $_grid[10][15];
$_grid[20][30] = "A";
echo $_grid[20][30] ."\n";
echo "fertig";
?>Ich hoffe, dasss ich Dich richtig verstanden hatte und Dir helfen konnte.
Harzliche Grüße vom Berg
http://www.annerschbarrich.deTom
--
Fortschritt entsteht nur durch die Auseinandersetzung der Kreativen
Nur selber lernen macht schlau
-
Hallo,
also erst einmal recht herzlichen Dank für deine schnelle Antwort.
Mal 'ne ganz dumme Frage zwischendurch:
Hat das Spielfeld eine endliche Ausdehnung oder erweitert sich das während des Spieles ständig?Das Spielfeld besitzt keine feste Ausdehnung... die Ausdehnung legen die Spieler fest, je nachdem wie sie sich ausbreiten... die einzigste Beschränkung dahingehend liegt im von mir gewählten Datentyp Integer in der Datenbank für die jeweilige X-Y Position...
Das macht aber in dem Falle ja relativ wenig, da ich die minimale X bzw. Y Position ja separat speichere...Für ein endliches Grid, das nur TRUE oder FALSE oder maximal eben 256 unterschiedliche Werte pro Zelle enthalten muss, nehme ich in PHP immer ein "Array of String"
Das benötigt erheblich weniger Platz, als ein PHP-Array, also eine Baumstruktur und ist um einiges schnellerOkay, über eine Mischung von Array und String habe ich noch nicht so darüber nachgedacht, aber das müsste ich mal wirklich mal testen... stimmt schon, bei einem String kann man ja dann auch auf die [x.] Position zugreifen...
Die Vergewaltigung der Typen in PHP ist mMn manchmal die Lösung.
;-) Okay, ich teste es mal aus...
-
Hab da noch eine Frage, wie kann ich da Strings verknüpfen, so dass ich folgendes erreichen kann:
Ich hab da einen String '00100'
und einen zweiten String '10001'
Wie kann ich diese verbinden, so dass '10101' ohne Zählschleife, da diese dann wieder massig Zeit benötigt... also gibts da direkt eine PHP Funktion dafür?
-
Hello,
Hab da noch eine Frage, wie kann ich da Strings verknüpfen, so dass ich folgendes erreichen kann:
Ich hab da einen String '00100'
und einen zweiten String '10001'
Wie kann ich diese verbinden, so dass '10101' ohne Zählschleife, da diese dann wieder massig Zeit benötigt... also gibts da direkt eine PHP Funktion dafür?
Ich denke, dass Du nicht wirklich "Strings verbinden" willst. Bitte beschreibe genauer, um was es geht. Sollten diese Strings in dem Grid gespeichert sein? Das ist je nun per Definition ein Byte-Array geworden...
Normale Verknüpfung wäre doch
$sammel = $string1 + $string2;
Aber das meintest Du bestimmt nicht.
Harzliche Grüße vom Berg
http://www.annerschbarrich.deTom
--
Fortschritt entsteht nur durch die Auseinandersetzung der Kreativen
Nur selber lernen macht schlau
-
Hi,
nein, ich will keine Strings verbinden, sondern halt immer wieder überschreiben können, sodass aber bereits gesetzte Stellen des Strings nicht überschrieben werden.
Die Tabelle ist ja halt in X und Y Werte (X = Spalten und Y = Zeilen) unterteilt... so die X Werte stehen somit als erstes im Array drin:
$array[X] = [...];
Nun gibt es ja zu jedem X-Wert (Spalte) die zugehörigen Y Werte.
$array[X][Y] = [...];
Angenommen ich setze nun beim ersten Durchlauf die Spalte X-1 und die dazugehörige Zeile auf '1000000000'...
$array[1][1] = '1000000000';
Jetzt kommt es halt bei zweiten oder irgendeinem anderen Durchlauf dazu, dass ich wieder die Spalte X-1 erhalte und dort die Zeile neu setzen muss... dabei dürfen aber vorhandene Werte nicht zurückgesetzt werden.
Also angenommen ich erhalte beim zweiten Durchlauf für die Spalte X-1 die Zeile '0000010000':
$array[1][1] = '0000010000';
So würde ja der gesetzte Wert von $array[1][1] = '-->1<--000000000' durch $array[1][1] = '-->0<--000010000'; wieder auf 0 gesetzt werden... von daher bräuchte ich da eine Funktion, welche halt die Strings dann miteinander verschmilzt, so dass folgendes dabei herauskommt:
$array[1][1] = '100010000';
-
Hello,
kleines Testporgamm für Dich, das alle Fragen beantworten sollte
<?php ### string_grid.php ###
error_reporting(E_ALL);
echo "<pre>\n";
$_grid = array();
$width = 1000;
$height = 1000;#$zeile = str_repeat(chr(0),$width);
$zeile = str_repeat('X',$width); ## damit man 'was siehtfor ($i = 0; $i < $height; $i++)
{
$_grid[$i] = $zeile;
}# Das Grid beginnt immer bei 0,0. Anders hat es keinen Sinn, da ein String auch bei 0 beginnt.
# Um mehr Daten zu speichern, kannst Du eine zweite Plane einführen.
# Du kannst auf jede Zelle einzeln zugreifen.$zelle10_15 = $_grid[10][15];
$_grid[20][30] = "A";
echo $_grid[20][30] ."\n";
echo "<hr>\n";
#$_grid[20][29] = "XYLOPHON"; ### PHP übernimmt hier nur das erste Zeichen!
echo $_grid[20][29] ."\n";
echo $_grid[20][30] ."\n";
echo $_grid[20][31] ."\n";
echo $_grid[20][32] ."\n";# ABER:
echo "<hr>\n";
# mixed substr_replace ( mixed $string, string $replacement, int $start [, int $length] )
###
### Bitte alle folgenden Möglichkeiten ausprobieren
###$_grid[20] = substr_replace($_grid[20],'DOSEN',29,5); # Mit Längenangabe
#$_grid[20] = substr_replace($_grid[20],'DOSEN',29); # Ohne Längenangabe
$_grid[20] = substr_replace($_grid[20],'DOSEN',29,strlen('DOSEN')); # Mit Längen-Funktionecho $_grid[20][28] ."\n";
echo $_grid[20][29] ."\n";
echo $_grid[20][30] ."\n";
echo $_grid[20][31] ."\n";
echo $_grid[20][32] ."\n";
echo $_grid[20][33] ."\n";
echo $_grid[20][34] ."\n";echo "fertig\n";
echo "</pre>\n";
?>
Harzliche Grüße vom Berg
http://www.annerschbarrich.deTom
--
Fortschritt entsteht nur durch die Auseinandersetzung der Kreativen
Nur selber lernen macht schlau
-
Erstmal nochmals vielen Dank für die Hilfe!!!!
kleines Testporgamm für Dich, das alle Fragen beantworten sollte
Okay, jetzt versteht ich es ;-) Hab eigentlich den Befehl substr_replace gesucht...
Habe gerade mal meinen Quellcode dahingehend umgeschrieben, dass er nun auch mit Strings arbeitet... die Ausführungszeit ist nun von 18 bis 30 Sek. auf ca. 8 bis 10 Sekunden gesunken, was ne Ersparnis von 200 bis 300% bedeutet... ist schon enorm.
Vielleicht könnte man jetzt hier aber nochwas verbessern:
$nodes = array();
$strSQL = [...];
$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;$strTmp = str_repeat(false, $spyMinY).
$strY = str_repeat(false, $spyMaxY - $spyMinY);
for ($y = 0; $y <= $spyMaxY - $spyMinY; $y++) $strY[$y] = true;
for ($x = $spyMinX; $x <= $spyMaxX; $x++)
$nodes[$x] = $strTmp.substr_replace($nodes[$x], $strY, 0, $spyMaxY - $spyMinY);
}
$clsDB->free();
Vielleicht hast du ja noch eine Idee!? Denn das reine Auslesen der Daten per SQL Abfrage und Durchlauf der Schleife ohne Befehle:
$strSQL = [...];
$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;}
$clsDB->free();
dauert nur ca. 2 bis 3 Sekunden...
Also benötigt der innere Teil:
$strTmp = str_repeat(false, $spyMinY).
$strY = str_repeat(false, $spyMaxY - $spyMinY);
for ($y = 0; $y <= $spyMaxY - $spyMinY; $y++) $strY[$y] = true;
for ($x = $spyMinX; $x <= $spyMaxX; $x++) $nodes[$x] = $strTmp.substr_replace($nodes[$x], $strY, 0, $spyMaxY - $spyMinY);
ca. 5 bis 6 Sekunden... vielleicht kann man da noch etwas optimieren?
Grüße
-
Hello,
erzähl bitte nochmal genau, was da in der Tabelle drinsteht und wie die Struktur der Tebelle ist.
Ich könnte mir denken, dass man z.B. den Zeilkenstring gleich vom DBMS genereieren lassen könnte.
Ich bin aber im Moment nicnt im Bilde, ob MySQL schon Kreuzabfragen (also Spalten werden zu Zeilen des Resultsets) ermöglicht.
Harzliche Grüße vom Berg
http://www.annerschbarrich.deTom
--
Fortschritt entsteht nur durch die Auseinandersetzung der Kreativen
Nur selber lernen macht schlau
-
erzähl bitte nochmal genau, was da in der Tabelle drinsteht und wie die Struktur der Tebelle ist.
Ich könnte mir denken, dass man z.B. den Zeilkenstring gleich vom DBMS genereieren lassen könnte.
Also die Tabelle ist im Grunde ganz einfach aufgebaut:
ID, USER_ID, POS_X, POS_Y
-------------------------
1 , 1 , 1000 , 1000
2 , 1 , 1001 , 1001
3 , 2 , 500 , 500
...Die Tabelle mit den Sichtweiten sieht grob so aus:
USER_ID, SICHTWEITE
-------------------
1 , 10
2 , 12
...Habe mir auch schonmal überlegt die ganze Geschichte bereits per SQL Abfrage umzusetzen... wäre auch weiter nicht das Problem... nur in der Tabelle stehen ja nur die besetzten Felder drin und nicht die unbesetzten, die ich aber für den Aufbau der Karte benötige.
Also im Grunde müsste das Ergebnis der SQL Abfrage auch Daten zurückliefern, bspw. im Bereich X von 900 bis 1000, welche nicht in der Datenbank / Tabelle vorhanden sind...
Ich könnte höchstens eine zweite (leer)Feldtabelle anlegen, wo dann bspw. im Bereich von X:0 bis X:2000 und Y:0 bis Y:2000 alle Felder gespeichert sind... ist aber auch nicht Sinn der Sache, da die Kartengröße ja dynamisch ist und diese Tabelle dann mehrere Millionen Datensätze beinhalten würde, die ich am Ende gar nicht benötige...
Grüße
P.S. habe das von mir vorhin gerade gepostete Script auf meinem Server aufgespielt und dort getestet (Linux, PHP 4)... da bringt er mir mit dieser Variante erheblich größere Ausführungszeiten 40 bis 50 Sek. und mehr, als wie mit der Array Variante... auf meinem lokalen Rechner habe ich Windows und PHP 5... da gehts relativ schnell.. kann aber auch daran liegen, das auf dem Server gleichzeitig noch andere Leute sind.
-
-
-
-
-
-
-
-
echo $begrüßung;
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!!!Du hast ein Geschwindigkeitsproblem aufgrund einer großen Datenmenge. Du kannst am Algorithmus feilen, der diese Datenmenge behandelt. Dies probierst du ja derzeit schon. Oder aber du könntest versuchen, die Datenmenge zu verkleinern.
Deshalb mal anders gefragt: Ist es denn unbedingt notwendig, dass das komplette Feld im Speicher aufgebaut wird? Oder reicht es vielleicht, nur die Felder zu speichern, die für den Nutzer aktuell sichtbar sind? Du greifst dann nicht mehr direkt auf die Koordinaten des Feldes zu, sondern befragst eine Funktion, die nachschaut, ob das Feld unter den sichtbaren ist, ansonsten ist es unsichtbar. Diese Funktion sollte aber nun nicht tausend Einzelabfragen an die Datenbank loslassen. Vielleicht kannst du ja die Zugriffswünsche zunächst sammeln und sie dann gebündelt der Datenbankabfrage übergeben.
Möglicherweise ist durch die somit erreichte Beschränkung der Datenmenge eine deutliche Geschwindigkeitserhöhung zu verzeichnen. Soweit meine Ideen. Da du aber immer nur dieses spezielle Teilproblem anschneidest, kannst nur du selbst entscheiden, ob sie in das Gesamtkonzept passen.
echo "$verabschiedung $name";
-
Hallo,
zum Aufbau der Karte benötige ich nur den aktuellen Kartenausschnitt (bspw. 14 x 14 Felder), da hast du recht... in dem Falle lade und berechne ich auch nur den Teilbereich... darum geht es ja aber auch nur indirekt.
Leider benötige ich aber für den A* Algorithmus (Pathfinding, zur Bestimmung des kürzesten Weges von A nach B, bzw. Prüfung ob 2 Felder verbunden sind) den kompletten Bereich zwischen den beiden Punkten A und B... und wenn nun diese Felder 100, 200 oder mehr Felder auseinanderliegen, so muss ich den gesamten Bereich, welcher dazwischen liegt, mit in den Arbeitsspeicher laden!
Und das können dann schon mal, wenn die Felder in X Richtung 100 Felder und in Y Richtung 100 Felder auseinanderliegen, 100 x 100 = 10.000 Felder sein, die ich laden und berechnen muss!
Grüße
-