Map in Datenbank oder hartcodiert

Hio,
ich habe mir vorgenommen nen BG zu schreiben und meine auch das nötige Wissen zu besitzen ^^ Aber ich habe leider noch keine Erfahrungen was die Auslastung bei großen Userzahlen angeht. Ich habe folgendes vor:
Eine große Karte (Rollenspiel) und dann noch viele kleinere für die Städte. Momentan habe ich dafür 4 Tabellen, eine für die Außenkarte (x,y,mapstück_id, besitzer_id) und äquivalent eine Tabelle für die Stadtkarten. Dann noch eine für die Mapstücke zum identifizieren der Eigenschaften des Teiles und eine Tabelle für die Gebäude die auf der Karte stehen können, mit denen dann interagiert werden kann.
Meine Frage ist in diesem Fall, ist es besser dies alles in einer Datenbankstruktur zu belassen (es wird wohl sehr viel über die Karte laufen im Spiel, da ich geplant habe fast alle Aktionen von dort aus wählbar zu machen) oder die Karte und die Eigenschaften der Stücke etc. in die Mapklasse als mehrdimensionalen Array zu coden.
Wo seht ihr eher Probleme und oder Vor- / Nachteile ?
Bin über jede ernst gemeinte Antwort sehr dankbar,
Xerxekyran

Ich bin ja absoluter verfechter von Bitmaps für Kartenanwendungen, ich sehe absolut keinen Sinn darin, die Datenbank mit statischen Inhalten großen Ausmaßes dermaßen zu belasten.
Nähere Infos gibs im folgenden Thread:
Karte mal wieder ...

Original von Itchy

char * readmap( int x, int y, int size ) {
FILE * map;
char * ret;
int retoffset = 0;
int offset = y * WIDTH + x;
int i;
ret = (char *)malloc( size * size + 1 );
map = fopen( "map.dat", "r" );
for ( i = 0; i < size; i++ ) {
fseek( map, offset, SEEK_SET );
fread( (char *)(ret + retoffset), size, 1, map );
offset += size;
retoffset += size;
}
fclose( map );
return ret;
}

Sorry, aber ich rall diese Syntax irgendwie garnicht,
was bedeutet "FILE * map" und "char * ret"?
Welche Programmiersprache ist das überhaupt ?
Und speicherst du da auch Daten rein oder ist das wirklich nur das unbeeinflussbare Gelände?

- FILE = Datei, in diesem Falle wohl vom Datentyp Datei (PHP).
- map ist hier der Variablennamen, welcher ja vom Typ FILE ist.
- char = character... also wenn dir das nix sagt...
- ret = kurzform für return, also ein variablenname für den inhalt, den man zurückgeben möchte.
hmm.. also wenn man das alles statisch halten möchte hast du wohl recht, im endeffekt habe ich wenn ich meine ideen weiter führe eh keine anderen wahl als es in der datenbank zu machen (oder halt textdatei =_o). Denn die Spieler sollen auch die möglichkeit haben die Welt aktiv zu verändern, also neue Städte und so was bauen.
Aber der Thread war was Geschwindigkeiten bei Zugriffen angeht schon mal informativ, danke.

Dies ist C-Code, ich versuche ihn mal zu kommentieren.

// Die Funktion readmap bekommt x, y und die Variable size übergeben.
// Rückgabewert ist ein Zeiger auf eine Zeichenfolge.
char * readmap( int x, int y, int size )
{
// Dateihandle
FILE * map;
// Rückgabe wert
char * ret;
int retoffset = 0;
int offset = y * WIDTH + x;
int i;
// Reserviere Speicher ( Size * Size + 1 Bytes ) <- Dies ist dann die
// rückzugebende Zeichenfolge
ret = (char *)malloc( size * size + 1 );
// Öffne Datei map.dat im Lesemodus und speichere den Dateihandle in map
map = fopen( "map.dat", "r" );
// Schleife, sollte klar sein ;-)
for ( i = 0; i < size; i++ )
{
// Springe in der Datei zur Position offset
fseek( map, offset, SEEK_SET );
// Lese size Bytes ein und speichere diese in den Speicherbereich ret [ retoffset ]
fread( (char *)(ret + retoffset), size, 1, map );
offset += size;
retoffset += size;
}
// Datei schließen
fclose( map );
// Fertig
return ret;
}

hmm.. also wenn man das alles statisch halten möchte hast du wohl recht, im endeffekt habe ich wenn ich meine ideen weiter führe eh keine anderen wahl als es in der datenbank zu machen (oder halt textdatei =_o). Denn die Spieler sollen auch die möglichkeit haben die Welt aktiv zu verändern, also neue Städte und so was bauen.
Aber der Thread war was Geschwindigkeiten bei Zugriffen angeht schon mal informativ, danke.

Naja, das eigentliche Gelände wird sich wohl nicht ändern, oder? Also die Spieler haben keine Möglichkeit, einen Berg abzutragen oder einen Fluss trockenzulegen, oder?
Falls dem so ist, kann man ja die eigentliche Map mit dem Gelände so speichern und die "Objekte" (Städte etc.) in einer DB Tabelle halten. Solange nicht auf jedem Feld dann eine Stadt steht, sollte das schon passen.
Kommt aber halt auch immer auf die Dimensionen drauf an. Eine 100x100 Karte in einer DB zu verwalten ist kein Problem, bei einer 1000x1000 Karte wirds schon schwieriger. Eine 1000x1000 Bitmap dagegen ist Pillepalle.
Also mein Vorschlag wäre:
Karte mit dem Gelände in einer Imagemap speichern und dazu eine Tabelle "Weltobjekte" die ungefähr so aufgebaut ist:
id|x|y|[typ]|[besitzer]...
wobei auch x und y indiziert werden sollten.
P.S. Sorry wegen dem C-Code, ich dachte, der ist sowieso so PHP-ähnlich (fast alle Funktionen darin sind auch im PHP verfügbar), daß man den auch ohne C-Kenntnisse versteht.

ja die mix lösung hört sich sehr sinnvoll und gut an, danke!
keen hatte in dem anderen thread angesprochen gehabt das ein direktes auslesen der kartenstücke mit id's um einiges schneller geht, was ist wenn man einfach beide pk (also x und y) angibt, ist das dann immernoch schneller als between ?
sprich was ist schneller von den beiden verfahren bei großen datenbankinhalten, wenn x und y pk sind:

SELECT Feld_ID FROM map WHERE  (x BETWEEN 1 AND 5) AND (y BETWEEN 2 AND 6)

oder

SELECT Feld_ID FROM map WHERE (x IN (1,2,3,4,5)) AND (y IN (2,3,4,5,6))

sry wenn ich so dumm frage aber mit den ganzen geschwindigkeiten von zugriffen und engpässen bei großen userzahlen habe ich einfach noch keine erfahrung.

Ich schätze dass das hier schneller ist

SELECT Feld_ID FROM map WHERE (x BETWEEN 1 AND 5) AND (y BETWEEN 2 AND 6)

wird aber nicht der Riesenunterschied sein. Grundsätzlich wäre eine Bitmaplösung das schnellste, aber das über sharedmem und threadsicher zu machen dürfte nicht ganz einfach sein.
Bei deinen Anfragen solltest du auf jedenen Fall Indizes setzen,

Von der Perfomance her ist das hinterlegen in ner Datenbank besser als hardcodieren ganz klar. Hardcodieren würd ich eh nur statische Daten zum einmaligen Gebrauch.
Ansonsten kommt es ganz drauf wie du die Karte in deinen BG umsetzen willst ... eine Bitmaplösung muss nicht unbedingt schlecht sein deshalb kann man das so pauschal nicht sagen.

Original von Xerxekyran
sry wenn ich so dumm frage aber mit den ganzen geschwindigkeiten von zugriffen und engpässen bei großen userzahlen habe ich einfach noch keine erfahrung.

Hatten wir hier schon
Lg Kudi

Original von The-Winner
Grundsätzlich wäre eine Bitmaplösung das schnellste,

Original von LeoManiac

Von der Perfomance her ist das hinterlegen in ner Datenbank besser als hardcodieren ganz klar.
Schön, dass sich die Experten mal wieder einig sind

Da hast was falsch verstanden Blabbo ... unter hardcodieren Versteh ich sowas wie statische Daten auf Dateiebene hinterlegen zb. als XML ... klar könnte man ne Bimtaplösung auch darunter verstehen ...

Also wenn deine Map eine Grösse von 200x200 oder mehr hat (40.000 Elemente), wäre eine XML-Datei schonmal nicht sehr gut, weil XML meist ne Menge Speicher brauch. Allein schon das sind 11 Zeichen (40K mal 11 sind alleine dafür schon 400K Speicherplatz).
Auch ist es wichtig, zu wissen, was du mit deiner Map anstellen willst.
Willst du z.B. immer nur kleine Teile anzeigen (z.B. das Feld (20|20) +/- 5 Felder), ist eine DB wahrscheinlich besser, weil du dann nicht die ganze Datei laden musst (die DB kann sowas schneller).
Willst du aber eh immer die gesamte Karte auslesen, kannst du das auch mit ner BMP-Map machen.
Je grösser die Karte wird, desto länger ist die DB beschäftigt, treffende Felder zu suchen (bei 1.000 mal 1.000 Feldern hast du schon 1.000.000 Elemente in der DB). Da wäre eine in Sektoren (100 Sektoren mit jeweils 100x100 Feldern z.B.) zerlegte BMP-Karte wahrscheinlich besser.
Ich würde sowas aber nur fürstatische Daten machen, also dynamische Daten wie Gebäude, die auf dem Feld stehen, würde ich nicht in eine Datei schreiben...

was anderes sag ich doch gar nicht ...aber 1.000.000 Datensätze ist noch so gut wie gar nix ... richtige Performanceeinbußen bei einer MySQL Datenbank hast erst im TB Datenbereich.. wichtige dabei ist halt das man bestimmte Regeln beachtet zb. NIE "SELECT *..." verwenden, Indizies festlegen usw.

Original von LeoManiac
was anderes sag ich doch gar nicht ...aber 1.000.000 Datensätze ist noch so gut wie gar nix ... richtige Performanceeinbußen bei einer MySQL Datenbank hast erst im TB Datenbereich.. wichtige dabei ist halt das man bestimmte Regeln beachtet zb. NIE "SELECT *..." verwenden, Indizies festlegen usw.

Dann erklär mir bitte was ich falsch mache: MySQL 5.0.18 Benchmark
Lg Kudi

was anderes sag ich doch gar nicht ...aber 1.000.000 Datensätze ist noch so gut wie gar nix ... richtige Performanceeinbußen bei einer MySQL Datenbank hast erst im TB Datenbereich.. wichtige dabei ist halt das man bestimmte Regeln beachtet zb. NIE "SELECT *..." verwenden, Indizies festlegen usw.

Wüßte auch gerne, was Du unter "so gut wie gar nichts" verstehst:
folgendes hab ich auf meinem System ausprobiert:
Eine megasimple Tabelle angelegt:

CREATE TABLE `test` (
`x` int(11) NOT NULL,
`y` int(11) NOT NULL,
`wert` varchar(1) NOT NULL,
KEY `x` (`x`),
KEY `y` (`y`)
)
Die Tabelle mit 1.000.000 Datensätze gefüllt der Art x,y jeweils 0-999, wert ein zufallswert von '0'-'9'.
Dann eine Abfrage gemacht
SELECT wert FROM test WHERE (x BETWEEN 100 AND 200) AND (y BETWEEN 300 AND 400)
simpler gehts also nicht.
Die ganzen Werte dann als "Ascii-Map" ausgegeben.
Dauer mit MySQL auf meinem Server: 0.4s
Das ganze als Bitmap: 0.02s
Wir haben hier also einen Performanceunterschied um Faktor 20, das ist für mich ein bißchen mehr als "so gut wie gar nix".
In der Speicherbenutzung liegt die Bitmap auch um Faktor 30 vorne (1 MB vs. 30 MB).
Also so einfach lasse ich mich von meinem Statement nicht abbringen, daß statische Inhalte, die sich nur selten ändern in einer relationalen Datenbank völlig unnütz sind, zumal da auch die "Relation" fehlt.

> Also so einfach lasse ich mich von meinem Statement nicht abbringen, daß statische Inhalte, die sich nur selten ändern in einer relationalen Datenbank völlig unnütz sind, zumal da auch die "Relation" fehlt.
Dem kann ich mit meiner ganzen Kompetenz nur zustimmen ;-)
Siehe auch meinem Blog auf GN.

Original von Itchy
folgendes hab ich auf meinem System ausprobiert:
Eine megasimple Tabelle angelegt:

CREATE TABLE `test` (
`x` int(11) NOT NULL,
`y` int(11) NOT NULL,
`wert` varchar(1) NOT NULL,
KEY `x` (`x`),
KEY `y` (`y`)
)

Du hast die Antwort darauf praktisch schon zitiert ... ich sehe da keine Indexes ...
dev.mysql.com/doc/refman/5.0/en/mysql-indexes.html
Wenn du aber durch indexes keine Performance mehr rausholen kannst würd ich ganz einfach sagen das der Server zu schwach ist. Normalerweise sollten DB Abfragen wesentlich performanter sein wenn die Daten öfters gebraucht werden da sie gecached werden (sollten).
Außerdem ist der Vergleich zwischen Ascii Map und Bitmap sowieso totaler blödsinn, da wirst mit Bitmaps immer die besseren Ergebnisse erzielen.
Ich hab außerdem lediglich gesagt das 1.000.000 Datensätze keine großen Performanceeinußen bringen sollten und nicht das es besser sei. Und 0.4sec sind wirklich nix.
[edit] hätte meinen Beitrag oben besser mit einen Zitat versehen weil ich hab mich lediglich auf die ersten beiden Absätze von den vorherigen Beitragsschreiber bezogen.

also, KEY ist schon nen Index
mich würde aber mal nen explain select interessieren, ob er überhaupt beide nimmt, oder ob es besser ist sie zusammenzufassen und den dann unique zu machen

+----+-------------+-------+------+---------------+------+---------+------+-------+-------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref  | rows  | Extra       |
+----+-------------+-------+------+---------------+------+---------+------+-------+-------------+
|  1 | SIMPLE      | test  | ALL  | x,y           | NULL | NULL    | NULL | 49600 | Using where |
+----+-------------+-------+------+---------------+------+---------+------+-------+-------------+

Sagt mysql zum Explain.
Das Problem bei der Geschichte ist aber nicht mal der Query, der geht einigermaßen schnell.
Das Problem ist, daß man jedes einzelne Ergebnis im Resultset erstmal einlesen muß, bevor man es weiterverarbeiten kann. Das sind also 100x100=10000 Operationen, bevor man das geschwünschte Ergebnis im Speicher hat. Bei der Bitmap reduzieren sich die Lesezugriffe um den Faktor 100, da man nur 100 mal jeweils einen Block aus 100 Resultaten lesen muß.

Trotzdem sehe ich bei dir keinen Index ... probiers aus damit holst du noch was raus...
dev.mysql.com/doc/refman/5.0/en/indexes.html
dev.mysql.com/doc/refman/5.0/en/myisam-key-cache.html
dev.mysql.com/doc/refman/5.0/en/index-preloading.html
Der letzte Link sollte intersant sein ...
LOAD INDEX INTO CACHE

Danke für die ganzen Antowrten!
Hat in diesem Zusammenhang eigentlich schon mal wer Stored Procedures gestestet? Ob und wenn wieviel so was dann ausmacht?

Ich habe nochmal einen Index über x und y zusammen gesetzt - mehr geht nun wirklich nicht, das EXPLAIN Resultat bleibt dasselbe.
Würde aber auch nichts ändern wenn doch, denn das Query selber dauert nur 0.0018 Sekunden, was Zeit verbraucht, das ist das 10.000malige Holen der Zeilen aus dem Resultset.