Geeignetes format für dynamische Daten?

Übersicht

BlitzMax, BlitzMax NG

Allgemein

	Xaymar ehemals "Cgamer" Betreff: Geeignetes format für dynamische Daten?	Mi, Jul 06, 2011 12:30 Antworten mit Zitat
Ich hänge derzeit an einem Geschwindigkeitsproblem. Meine Karte kann sich theoretisch unendlich in X, Y und Z ausbreiten, wobei alle richtungen immer in Teile aufgebaut sind(16x16x16). Wie kann ich diese optimal nach X, Y, Z im Speicher behalten? TList kommt hier ab einer größeren Liste nur noch wenig mit(Welten mit mehr als 1000 Einträgen sind nicht selten).
Warbseite

Xaymar

ehemals "Cgamer"

Betreff: Geeignetes format für dynamische Daten?

Mi, Jul 06, 2011 12:30
Antworten mit Zitat

Ich hänge derzeit an einem Geschwindigkeitsproblem. Meine Karte kann sich theoretisch unendlich in X, Y und Z ausbreiten, wobei alle richtungen immer in Teile aufgebaut sind(16x16x16).
Wie kann ich diese optimal nach X, Y, Z im Speicher behalten? TList kommt hier ab einer größeren Liste nur noch wenig mit(Welten mit mehr als 1000 Einträgen sind nicht selten).

Warbseite

	maximilian	Mi, Jul 06, 2011 12:38 Antworten mit Zitat
Zitat: TList kommt hier ab einer größeren Liste nur noch wenig mit(Welten mit mehr als 1000 Einträgen sind nicht selten). Dann machst du irgendwas falsch. Listen sind immer gleich schnell, egal ob du 1000 oder 100000 Einträge hast. Natürlich darfst du nicht auf die Idee kommen, die Listenelemente einzeln zu indexieren. Da müsstest du dir schon was besseres überlegen... Klingt irgendwie nach einem Fall für Bäume, aber so ganz ist mir das Problem leider nicht klar.
Variety is the spice of life. One day ignore people, next day annoy them.

maximilian

Mi, Jul 06, 2011 12:38
Antworten mit Zitat

Zitat:

TList kommt hier ab einer größeren Liste nur noch wenig mit(Welten mit mehr als 1000 Einträgen sind nicht selten).

Dann machst du irgendwas falsch. Listen sind immer gleich schnell, egal ob du 1000 oder 100000 Einträge hast. Natürlich darfst du nicht auf die Idee kommen, die Listenelemente einzeln zu indexieren. Da müsstest du dir schon was besseres überlegen...

Klingt irgendwie nach einem Fall für Bäume, aber so ganz ist mir das Problem leider nicht klar.

Variety is the spice of life. One day ignore people, next day annoy them.

	Xaymar ehemals "Cgamer"	Mi, Jul 06, 2011 12:43 Antworten mit Zitat
Listen sind nicht immer gleich schnell, sonst würde ich das nicht schreiben. Sie haben eine Laufzeit von O(n) und können deshalb nicht gleich schnell sein, wie denn auch, die Liste wächst ja. Aber Bäume ist schon mal nen guter Denkanstoß... Nachtrag: Du musst bedenken das das 1000x1000x1000 Durchläufe dann sind
Warbseite

Xaymar

ehemals "Cgamer"

Mi, Jul 06, 2011 12:43
Antworten mit Zitat

Listen sind nicht immer gleich schnell, sonst würde ich das nicht schreiben. Sie haben eine Laufzeit von O(n) und können deshalb nicht gleich schnell sein, wie denn auch, die Liste wächst ja.
Aber Bäume ist schon mal nen guter Denkanstoß...

Nachtrag: Du musst bedenken das das 1000x1000x1000 Durchläufe dann sind Wink

Warbseite

	PhillipK	Mi, Jul 06, 2011 12:47 Antworten mit Zitat
So eine frage hatte ich mir auch einmal gestellt. Dazu hatte ich eine idee entwickelt, das ganze in Arrays zu speichern. Weiterverfolgt hatte ich das ganze nicht, da ich keinen großen nutzen davon hatten - aber vllt hilft dir die idee Vorraussetzung ist, das du Variablen der Aktuellen position deiner Sektoren hast (du speicherst doch als sektoren, oder wie klingt das?) Nunja - die idee ist simpel, jeden Zweiten eintrag für positive koordinaten zu nehmen, andere für negative. Hier mal ein eindimensionales beispiel: BlitzMax: [AUSKLAPPEN] [EINKLAPPEN] Local arr:Int[] = New Int[100] Local posX:Int = 0 'aktueller Sektor, in dem man sich befindet! Local momentanerWert:Int = 0 'hier eine variable, die dein Objekt oder ähnliches enhtält - Aktueller Sektor zb. arr[0] = 1 'X = 0 arr[1] = -1 'X = -1 ! arr[2] = 2 'X = 1 arr[3] = -2 'X = -2! arr[4] = 3 'X = 2! arr[5] = -3 'X = -3! If X < 0 Then momentanerWert = arr[ (Abs(x)2)-1 ] Else momentanerWert = arr[ x2 ] EndIf Mag wirr klingen, aber für mich wars die Simpelste lösung! 0,2,4,6,8,10 - also grade einträge, entsprechen immer einen schritt in positiver richtung! 0,1,2,3,4,5 <- X koordinate! 1 , 3 , 5 , 7 , 9 - also 'ungrade' einträge, entsprechend immer einen schritt in negativer richtung! -1,-2,-3,-4,-5 <- X koordinate! Abs() schaltet das vorzeichen auf positiv - Aus -1 wird 1. Das ganze * 2 ergibt 2, -1 rechnets also auf die position im array. Das ganze lässt sich sicher ohne if-abfrage mit Sgn() und Abs() als einzeiler als allgemeingültige formel schreiben, aber naja. Nachteil an dieser Art der speicherung ist, das du für jeden Neuen sektor platz für 2 anlegst. Wie gesagt, das war eine Simple idee die ich ausgeheckt aber noch nicht umgesetzt habe. Vielleicht hiflts dir ja - denn schneller als TList ists auf jedenfall! (ps: alternativ könnte man den sektoren namen geben, welche du aus ihren XYZ koordinaten als string abpackst. Beispiel: Local sektor:TSektor = New TSektor Local map:TMap = CreateMap() Local str:String = "" str[0] = x shl 24 str[1] = (x shl 16) & $00ff0000 str[2] = (x shl 8) & $0000ff00 str[3] = x & $000000ff 'Das ganze nochmal für y und für z ! map.insert(str,sektor) ------ Naja, ich schreibe hier zuviel, dabei wirds sicher noch einfachere möglichkeiten geben, die nicht grade meinem Kranken hirn entsprungen sind -.-) Vielleicht konnte ich dir ja einen anreiz geben

PhillipK

Mi, Jul 06, 2011 12:47
Antworten mit Zitat

So eine frage hatte ich mir auch einmal gestellt.
Dazu hatte ich eine idee entwickelt, das ganze in Arrays zu speichern.

Weiterverfolgt hatte ich das ganze nicht, da ich keinen großen nutzen davon hatten - aber vllt hilft dir die idee Smile

Vorraussetzung ist, das du Variablen der Aktuellen position deiner Sektoren hast (du speicherst doch als sektoren, oder wie klingt das?)

Nunja - die idee ist simpel, jeden Zweiten eintrag für positive koordinaten zu nehmen, andere für negative.

Hier mal ein eindimensionales beispiel:

BlitzMax: [AUSKLAPPEN]


Local arr:Int[] = New Int[100]

Local posX:Int = 0 'aktueller Sektor, in dem man sich befindet!
Local momentanerWert:Int = 0 'hier eine variable, die dein Objekt oder ähnliches enhtält - Aktueller Sektor zb.

arr[0] = 1 'X = 0
arr[1] = -1 'X = -1 !
arr[2] = 2 'X = 1
arr[3] = -2 'X = -2!
arr[4] = 3 'X = 2!
arr[5] = -3 'X = -3!

If X < 0 Then 
     momentanerWert = arr[ (Abs(x)*2)-1 ]
Else 
     momentanerWert = arr[ x*2 ]
EndIf

Mag wirr klingen, aber für mich wars die Simpelste lösung!
0,2,4,6,8,10 - also grade einträge, entsprechen immer einen schritt in positiver richtung!
0,1,2,3,4,5 <- X koordinate!

1 , 3 , 5 , 7 , 9 - also 'ungrade' einträge, entsprechend immer einen schritt in negativer richtung!
-1,-2,-3,-4,-5 <- X koordinate!

Abs() schaltet das vorzeichen auf positiv - Aus -1 wird 1. Das ganze * 2 ergibt 2, -1 rechnets also auf die position im array.
Das ganze lässt sich sicher ohne if-abfrage mit Sgn() und Abs() als einzeiler als allgemeingültige formel schreiben, aber naja.

Nachteil an dieser Art der speicherung ist, das du für jeden Neuen sektor platz für 2 anlegst.
Wie gesagt, das war eine Simple idee die ich ausgeheckt aber noch nicht umgesetzt habe.
Vielleicht hiflts dir ja - denn schneller als TList ists auf jedenfall!

(ps: alternativ könnte man den sektoren namen geben, welche du aus ihren XYZ koordinaten als string abpackst.

Beispiel:
Local sektor:TSektor = New TSektor
Local map:TMap = CreateMap()

Local str:String = ""
str[0] = x shl 24
str[1] = (x shl 16) & $00ff0000
str[2] = (x shl 8) & $0000ff00
str[3] = x & $000000ff
'Das ganze nochmal für y und für z !

map.insert(str,sektor)

------

Naja, ich schreibe hier zuviel, dabei wirds sicher noch einfachere möglichkeiten geben, die nicht grade meinem Kranken hirn entsprungen sind -.-)

Vielleicht konnte ich dir ja einen anreiz geben Smile

	mpmxyz	Mi, Jul 06, 2011 13:34 Antworten mit Zitat
Was sind denn deine Anforderungen? Du möchtest dynamisch Einträge anlegen. Arrays<Bäume<Listen (Arrays kann man zwar relativ effizient nutzen, aber es bleibt trotzdem bei O(n)) O(n) vs. O(log n) vs. O(1) Du möchtest durch alle Einträge iterieren. Bäume<Listen<Arrays (Arrays nur mit leichtem Vorsprung vor Listen) O_naiv(n log n)/O_rekursiv(n) vs. O(n) vs. O(n) Du möchtest gezielt auf einzelne Einträge zugreifen. (x,y,z->Eintrag) Listen<Arraylist<Bäume<direkter Arrayzugriff O(n) vs. O(n) vs. O(log n) vs. O(1) mfG mpmxyz
Moin Moin! Projekte: DBPC CodeCruncher Mandelbrot-Renderer

mpmxyz

Mi, Jul 06, 2011 13:34
Antworten mit Zitat

Was sind denn deine Anforderungen?
Du möchtest dynamisch Einträge anlegen.
Arrays<Bäume<Listen (Arrays kann man zwar relativ effizient nutzen, aber es bleibt trotzdem bei O(n))
O(n) vs. O(log n) vs. O(1)
Du möchtest durch alle Einträge iterieren.
Bäume<Listen<Arrays (Arrays nur mit leichtem Vorsprung vor Listen)
O_naiv(n log n)/O_rekursiv(n) vs. O(n) vs. O(n)
Du möchtest gezielt auf einzelne Einträge zugreifen. (x,y,z->Eintrag)
Listen<Arraylist<Bäume<direkter Arrayzugriff
O(n) vs. O(n) vs. O(log n) vs. O(1)
mfG
mpmxyz

Moin Moin!
Projekte: DBPC CodeCruncher Mandelbrot-Renderer

	Midimaster	Mi, Jul 06, 2011 14:00 Antworten mit Zitat
benötigt man denn im Spiel auch noch Elemente, die z.b. 100 Raster vom Spieler weg sind? Man könnte ja immer nur einen Teilbereich des Gesamten in eine Liste kopieren und damit arbeiten. Ähnlich wie bei Google Maps oder Flightsimulator ja auch nicht die gesamte Welt geladen wird, wenn Du nur eine Straße in Posemukel betrachten willst. In Google Maps werden immer dynamisch die Randbereiche vorbereitet, falls der User dann dort hinwill, ist schon was da.... EineWelt: 100x100x100 Felder AktWelt: 100x100x100 Felder (Kopie aus einer EineWelt) AlleWelt: 100x100x100 EineWelten schon hast du 10.000 x 10.000 x 10.000 Felder und musst dich trotzdem nur durch max. 100x100x100 = 10.000 Felder durchscannen.

Midimaster

Mi, Jul 06, 2011 14:00
Antworten mit Zitat

benötigt man denn im Spiel auch noch Elemente, die z.b. 100 Raster vom Spieler weg sind?

Man könnte ja immer nur einen Teilbereich des Gesamten in eine Liste kopieren und damit arbeiten. Ähnlich wie bei Google Maps oder Flightsimulator ja auch nicht die gesamte Welt geladen wird, wenn Du nur eine Straße in Posemukel betrachten willst. In Google Maps werden immer dynamisch die Randbereiche vorbereitet, falls der User dann dort hinwill, ist schon was da....

EineWelt: 100x100x100 Felder

AktWelt: 100x100x100 Felder (Kopie aus einer EineWelt)

AlleWelt: 100x100x100 EineWelten

schon hast du 10.000 x 10.000 x 10.000 Felder und musst dich trotzdem nur durch max. 100x100x100 = 10.000 Felder durchscannen.

	ZaP	Mi, Jul 06, 2011 14:12 Antworten mit Zitat
Hört sich für mich nach einem Problem an, das mit einer guten Hashfunktion gelöst werden kann. Chaining bietet sich hier in dem Zusammenhang an, denke ich.
Starfare: Worklog, Website (download)

ZaP

Mi, Jul 06, 2011 14:12
Antworten mit Zitat

Hört sich für mich nach einem Problem an, das mit einer guten Hashfunktion gelöst werden kann. Chaining bietet sich hier in dem Zusammenhang an, denke ich.

Starfare: Worklog, Website (download)

	Xaymar ehemals "Cgamer"	Mi, Jul 06, 2011 14:16 Antworten mit Zitat
Das Problem ist, das z.b. 16 Teile um einen Spieler geladen werden, welche aktiv sind. Nun kann die Welt aber in alle richtungen +-(LongMaximum) Teile haben, wodurch das ganze verkompliziert wird. Ähnlich Minecraft. @mpmxyz: Option 2&3, da ich aber kein Array dafür nutzen kann, ohne das komplette System erneut umzuschreiben, bleibt mir da einmal Listen und einmal Bäume. Ich nutze derzeit TMap dafür, welches sich allerdings Geschwindigkeitsmäßig mal wieder nicht eignet(3-6ms Suchvorgänge bei einer Sichtweite von 16 Teilen in alle Richtungen). Nachtrag: @Midimaster: Visuell nicht, Coding basiert wird alles bis zu einer Entfernung von 32 Teilen benötigt. Wetter, Wind, Physik usw. Sind nicht auf sehr kleinen Basen zu berechnen, auch wenn das einige Schaffen.
Warbseite

Xaymar

ehemals "Cgamer"

Mi, Jul 06, 2011 14:16
Antworten mit Zitat

Das Problem ist, das z.b. 16 Teile um einen Spieler geladen werden, welche aktiv sind. Nun kann die Welt aber in alle richtungen +-(LongMaximum) Teile haben, wodurch das ganze verkompliziert wird. Ähnlich Minecraft.
@mpmxyz: Option 2&3, da ich aber kein Array dafür nutzen kann, ohne das komplette System erneut umzuschreiben, bleibt mir da einmal Listen und einmal Bäume. Ich nutze derzeit TMap dafür, welches sich allerdings Geschwindigkeitsmäßig mal wieder nicht eignet(3-6ms Suchvorgänge bei einer Sichtweite von 16 Teilen in alle Richtungen).

Nachtrag: @Midimaster: Visuell nicht, Coding basiert wird alles bis zu einer Entfernung von 32 Teilen benötigt. Wetter, Wind, Physik usw. Sind nicht auf sehr kleinen Basen zu berechnen, auch wenn das einige Schaffen.

Warbseite

	Noobody	Mi, Jul 06, 2011 18:48 Antworten mit Zitat
Wenn du es schon wie Minecraft machen willst, dann mach es doch wie Minecraft Sprich, du unterteilst deine Landschaft in gleichgrosse Chunks (Minecraft benutzt 16x128x16, wenn du aber auch vertikale Freiheit willst, dann eher 32x32x32), welche jeweils ein Array mit ihrem Teil der Karte gespeichert haben (so machst du es ja im Moment, wenn ich das richtig verstehe). Statt dass du aber all diese Chunks gleichzeitig in einer gigantischen Liste speicherst, machst du dir einfach ein zweites Array mit der Grösse Sichtweite2xSichtweite2xSichtweite*2, in dem du alle momentan sichtbaren Chunks im Speicher hältst. Chunks ausserhalb der Sichtweite sind auf der Festplatte gespeichert. Bewegt sich der Spieler, fliegen die Chunks, die ausserhalb der Sichtweite geraten, aus dem Speicher und die neu sichtbaren Chunks werden nachgeladen. Dieses zweite Array sollte nicht besonders gross werden - wenn du z.B. eine Sichtweite von 512 Metern hast (was schon recht viel ist), sind in jede Richtung nur 512/32 = 32 Chunks sichtbar. Wenn sich also dein Spieler bewegt und eine neue Reihe Chunks sichtbar wird, sollte es nicht sehr rechenaufwändig sein, den Inhalt des Chunk-Arrays in die Bewegungsrichtung des Spielers zu verschieben und eine neue Reihe Chunks hineinzuladen. Im Extremfall kannst du ja sogar auf Ringbuffer zurückgreifen, um dir das physische Verschieben des Array-Inhalts zu ersparen. In der BMax ZauberCraft-Demo habe ich es sogar so gemacht, dass ich auf das theoretisch unendliche Terrain verzichtet habe und stattdessen beim Programmstart ein festes Array mit 1024x1024 Plätzen (~4MB, also noch verkraftbar) für die Chunks reserviert habe und einen geladenen Chunk somit an eine fixe Position im Array stecken konnte. Da die Chunk-Grösse sogar bei 64x64x64 war, kann der Spieler in jede Richtung 32km laufen (was mehrere RL-Tage benötigt), bevor er den Rand erreicht. Der Vorteil ist, dass man sich das ständige Arrayverschieben erspart, wenn sich der Spieler bewegt, und man immer weiss, wo im Array sich ein bestimmter Chunk befindet - mit der oberen Variante ist die Chunkposition im Array ja immer abhängig von der Position des Spielers. Wenn du aber vertikale Freiheit implementieren willst, wird so ein grosses Array viel zu teuer.
Man is the best computer we can put aboard a spacecraft ... and the only one that can be mass produced with unskilled labor. -- Wernher von Braun

Noobody

Mi, Jul 06, 2011 18:48
Antworten mit Zitat

Wenn du es schon wie Minecraft machen willst, dann mach es doch wie Minecraft Razz

Sprich, du unterteilst deine Landschaft in gleichgrosse Chunks (Minecraft benutzt 16x128x16, wenn du aber auch vertikale Freiheit willst, dann eher 32x32x32), welche jeweils ein Array mit ihrem Teil der Karte gespeichert haben (so machst du es ja im Moment, wenn ich das richtig verstehe). Statt dass du aber all diese Chunks gleichzeitig in einer gigantischen Liste speicherst, machst du dir einfach ein zweites Array mit der Grösse Sichtweite*2xSichtweite*2xSichtweite*2, in dem du alle momentan sichtbaren Chunks im Speicher hältst. Chunks ausserhalb der Sichtweite sind auf der Festplatte gespeichert. Bewegt sich der Spieler, fliegen die Chunks, die ausserhalb der Sichtweite geraten, aus dem Speicher und die neu sichtbaren Chunks werden nachgeladen.

Dieses zweite Array sollte nicht besonders gross werden - wenn du z.B. eine Sichtweite von 512 Metern hast (was schon recht viel ist), sind in jede Richtung nur 512/32 = 32 Chunks sichtbar. Wenn sich also dein Spieler bewegt und eine neue Reihe Chunks sichtbar wird, sollte es nicht sehr rechenaufwändig sein, den Inhalt des Chunk-Arrays in die Bewegungsrichtung des Spielers zu verschieben und eine neue Reihe Chunks hineinzuladen. Im Extremfall kannst du ja sogar auf Ringbuffer zurückgreifen, um dir das physische Verschieben des Array-Inhalts zu ersparen.

In der BMax ZauberCraft-Demo habe ich es sogar so gemacht, dass ich auf das theoretisch unendliche Terrain verzichtet habe und stattdessen beim Programmstart ein festes Array mit 1024x1024 Plätzen (~4MB, also noch verkraftbar) für die Chunks reserviert habe und einen geladenen Chunk somit an eine fixe Position im Array stecken konnte. Da die Chunk-Grösse sogar bei 64x64x64 war, kann der Spieler in jede Richtung 32km laufen (was mehrere RL-Tage benötigt), bevor er den Rand erreicht. Der Vorteil ist, dass man sich das ständige Arrayverschieben erspart, wenn sich der Spieler bewegt, und man immer weiss, wo im Array sich ein bestimmter Chunk befindet - mit der oberen Variante ist die Chunkposition im Array ja immer abhängig von der Position des Spielers. Wenn du aber vertikale Freiheit implementieren willst, wird so ein grosses Array viel zu teuer.

Man is the best computer we can put aboard a spacecraft ... and the only one that can be mass produced with unskilled labor. -- Wernher von Braun

Übersicht

BlitzMax, BlitzMax NG

Allgemein

Nach Oben

BlitzBasic Portal

Geeignetes format für dynamische Daten?

Betreff: Geeignetes format für dynamische Daten?