Fog of War

Hi Entwicklers,

ich grübele gerade über ein neues Konzept eines Strategie-Browsergames. Darin möchte ich gern eine Karte haben, auf der es den "Fog of War" gibt.

D.h. die Karte soll an den Stellen schwarz sein, die der Spieler noch nicht besucht hat und grau-transparent an den Stellen, die er irgendwann einmal erkundet hat und jetzt nicht mehr in seinem Sichtbereich liegen.

Der Fog of War soll sowohl Gebäuden, als auch von Einheiten beeinflusst werden und ändert sich deshalb unter Umständen alle paar Minuten.

Vor ein paar Jahren habe ich so etwas schon einmal versucht in mein damaliges Spiel zu integrieren. Jedoch war die damalige Methode (erkundete und sichtbare Felder in der Datenbank halten) alles andere als performant.

Vielleicht hat ja jemand von euch das Problem schon gelöst oder ist daran zugrunde gegangen? (So wie ich damals... ;-))

Ich suche eine Lösung, die auch für sehr große Karten funktioniert. Meine Denkansätze gehen bisher in folgende Richtungen:

• für jeden Spieler eine Bitmap speichern, die Werte [0,1,2] speichert für alle Felder der Karte (vielleicht nicht viel performanter als Datenbankansatz, da Bilder so groß wie Karte sind)
• "Fragmente" in der DB speichern: Pfade, die Einheiten zurückgelegt haben oder Punkte, an denen Gebäude stehen. Die Sichtbarkeit eines Feldes wird dann dynamisch beim Laden berechnet.

Hat noch jemand andere Ideen? Bzw. gibt es Browserspiele, wo so etwas realisiert wurde?

Von welcher Kartengröße reden wir denn da?

1000x1000? 10000x10000 oder gar noch größer?

Eigentlich musst du ja pro Feld ja nur ein Bit speichern, 1 - "erkundet" und 0 - "nicht erkundet". Welche er grade sieht würde ich dynamisch berechnen, da sich das ja auch sehr oft ändert (nehme ich mal an).

Dann hast du eine sehr sehr kleine Bitmap, bei 10000 x 10000 sind das grade mal 12 MB (wenn ich mich net verrechnet hat). Wenn du dann noch geschickt mit Caches umgehst (und dir z.B. das merkst, was ein Spieler sehr oft zu sehen bekomm, z.B. seine Region, dann dürfte das recht performant sein.

Die Frage bei der "Ich halte es in einer Datenstruktur, die alles umfässt"-Methode ist eher: Wird der Spieler jemals alle Felder erkunden, oder ist der durchschnittliche Anwedungsfall der, dass nur ein sehr kleiner Ausschnit der Karte erkundet wird.

Als erstes würde ich deine Karte in Regionen partitionieren. Somit verringerst du schonmal die Anzahl der auf einmal zu speichernden Informationen. Sinnvoll wäre es z.B. 32x32 oder 64x64 Felder grosse Ausschnitte zu wählen. Damit kannst du dann eine Region in Arrays von int(32bit) oder long(64) Bit Werten ablegen, die dann auch direkt Cachebar sind.

Wie du solch eine Region persistierst ist wieder eine andere Sache...ich würde es einfach als String in die Datenbank serialisieren(wie nun auch immer, als komma-seperierte List von Zahlen oder 1111000101010111... ). Ein schneller Key-Value-Store wäer hier sehr gut einsetzbar. Key wäre Region-Koordinate + UserId und Value das serialisierte Array.

Was mir grade auffällt...das schöne daran ist, dass du z.B. einem Clan eine Gesamtsichtbarkeit liefern kannst, indem einfach alle Regionen der Clanmitglieder per ODER zusammengerechnet werden...geht fix und ist bestimmt nen nettes Feature...wenn du sowas wie Clans in deinem Spiel hast...

So long...

Maxx

Ein alter Blog-Eintrag von mir, der sich mit dem Thema beschäftigt:

http://blog.depon.net/index.php/2006/04/19/bock-auf-groaye-karten/

Im Prinzip so ähnlich wie MrMaxx vorschlägt. Nur zusätzlich komprimiert.

Alternative wären Quad-Trees, da ja ein Großteil der 'Quader' komplett weiß oder schwarz sind.

Ah, danke für die hilfreichen Antworten.

@Kampfhoernchen:

Du hast natürlich Recht, 0 und 1 speichern reicht völlig aus. 

@MrMaxx & TheUndeadable:

Guter Blogeintrag und gute Idee mit dem Partitionieren. Da meine Karte quadratrisch ist, scheinen mir Quad-Trees als bester Einsatz. 

Die Sache mit dem Clan/Allianz/Gilde: Ich habe da geplant die sichtbaren Koordinaten nicht zu mergen, sondern in dem Fall nur einmal für alle Mitglieder zu speichern.

Danke, jetzt habe ich auf jeden Fall schon mal eine ungefähre Vorstellung, ob so etwas überhaupt möglich ist. Ich habe gerade ausgerechnet, dass sich meine Karten auf die Größe von 2048 x 2048 Feldern beschränken und immer ca. 32x32 Felder gleichzeitig sichtbar sein werden.