Karte - dynamische Territorien

Ich moechte gern die Moeglichkeit haben dynamische Territorien auf meiner Karte zu haben. Nun ist die Frage, wie ich dies technisch realisiere.

Bei einer Mindestgroesse von 3000x3000 Einheiten, eher 3000x(9000+), ist eine vollstaendige Rasterkarte wohl kaum moeglich, da 10-30 Millionen Eintraege dann doch alles andere als performant sind.

Spielerisch soll es so ablaufen, dass der Benutzer mit einem Gebiet von z.B. 20x20 Einheiten mit dem Mittelpunkt auf seiner Basis startet. Faehrt er nun mit einem Geschwader 10 Einheiten weiter hinaus, annektiert diese Position und kann sie mindestens 2 Stunden lang halten, so soll sich sein Gebiet erweitern.

Technisch sehe ich im Moment nur 2 Moeglichkeiten das effizient zu implementieren...

1. Die Karte in Rastersegmente unterteilen (z.B. je 50x50, dann komme ich immerhin bei 3000x9000 auf nur gut 100k Eintraege, wenn alles belegt ist). Das ist mit Abstand der einfachste Weg, auch hinsichtlich der Praesentation (kein GD noetig, nur ein "paar" divs / tabellenfelder mit opacity...).

Allerdings sieht das auch nicht sonderlich elegant aus...

2. Polygone und Vertices. Ist ein neuer Punkt nah an einem bestehenden, wird der bestehende durch ihn ersetzt, ist er von 2 bestehenden aehnlich weit entfernt, wird ein neuer Punkt angelegt. Dann muesste man natuerlich noch etwaige Schnittpunkte beruecksichtigen...

Fuer die Ausgabelogik bietet sich die Polygon-Klasse an.

Allerdings erwarte ich, dass diese Loesung sehr hardwarelastig ist. Zudem waere die Berechnung der Flaechen inhalte (fuer die Punkteverteilung / Belohnung / Ehre innerhalb der eigenen Koalition) ziemlich aufwendig. Da dies nur alle 6 Stunden passieren muss, ist das aber nicht so relevant...

Wichtiger ist da der Aufwand bei jedem View.. ich muesste alle Polygone eines Kartensegmentes als Objekte erzeugen, und sie mit GD zeichnen (also z.B. eine PNG mit Alpha transparenz, die dann ueber den normalen Kartenhintergrund gelegt wird).

Man koennte natuerlich den Zeichenvorgang mit in das 6 stuendige Update verlagern, dann wirkt die Karte jedoch sehr undynamisch, weil der User kein wirkliches Feedback zu seinen Aktionen bekommt...

Hat jemand Ideen und kann mir helfen eine optimale Loesung zu finden?

Evtl der Quadtree?

http://en.wikipedia.org/wiki/Quadtree

Ist nun auch nicht eleganter als die Sektorenversion. Vielleicht ein wenig speicherschonender, dafuer jedoch um einiges aufwendiger.

Die ersten Fragen sollten lauten:
* Brauche ich wirklich genau diese Größe innerhalb einer Partie? Wieviel Platz kalkuliere ich für einen Spieler, wieviele Spieler sollen in die Partie passen.
* Wieviel Information muss pro Feld gespeichert werden? Wenn es viel mehr als 1 Byte Geländeinformation ist, hast du vermutlich wirklich ein Problem.

Ansonsten kann ich zum Sektorenansatz sagen, dass der sich für mich bewährt hat. Ich verwende den bei jeder Art Karte, selbst wenn die Datensatzmenge deutlich kleiner ist. Und zwar alleine schon deshalb, weil sonst der Datenoverhead einfach viel zu groß wäre.
Allerdings verwende ich derzeit Sektoren á 4x4 Felder, also deutlich kleinere als die von dir angedachten 50x50.
Gut gefallen mir auch Sektorgrößen von 5x5 bzw. 10x10, da ich einfach sehr im Dezimalsystem eingewöhnt bin und die Karte auch noch "lesen" können möchte..

Ja, die Groesse hat sich in 2 Jahren bewaehrt und da ich im kompletten Redesign des Spiels so ziemlich ALLES umwerfe, koennen einige Dinge ja noch bestehen bleiben. :-)

Bei 1500x1500 Einheiten je Quadrant, sind das ja bei 50x50 Sektoren 30x30 Felder.. 900 Felder verteilt auf 50-200 Spieler pro Quadrant (skaliert unbegrenzt nach "Sueden", wenn kein Userlimit vorgegeben ist).. ist schon in Ordnung.

Insgesamt reicht mir zunaechst ein 1000 Spieler Limit, ich habe nichts davon mehr Spieler zu haben, lieber hoehere Qualitaet fuer weniger Leute. Wenn es skaliert ist das aber selbstverstaendlich auch schoen. Ich denke das momentane Spiel liesse sich auf dem guenstigen Hetzner.de Entry Server (3ghz Athlon, 1 gig ram..) mit ca. 4k Usern betreiben, ist aber teilweise enorm unperformant geschrieben (da habe ich einiges zu tun.. sind viele Dinge die aus der Zeit stammen als ich noch nicht Admin war).

Nur finde ich es eben vom Aussehen her ziemlich unelegant, auf Sektoren zu setzen - "echte" Polygone sind sicher enorm cool. ) Wenn es da also einen performanten Weg gaebe, waere das schon klasse. Die Karte sieht dann einfach viel viel "agiler" und lebendiger aus.

Hier - bei den Territorien - geht es ja nur um den Besitz der Flaechen. Sonst nichts. Wenn ich dann eine 5xx * 5xx Flaeche mit ein paar Punkten als Polygon beschreiben kann, ist dies Platztechnisch sicherlich recht effizient. Nur die Schnitt- und Ausgabeberechnung sind wohl der Bremsklotz des ganzen..

Echte Gelaendedaten (Gebirge usw), sind vorerst nicht geplant, eben weil das die Komplexitaet dann uebersteigen wuerde. Es soll ja doch irgendwo ein Modell bleiben und auch einigermassen skalieren koennen.

Ansonsten muss ich auf der Karte ja nur Dinge speichern, die auch existieren. Basen, Geschwader, Torpedos, Schaetze, Quest- / Eventtrigger, abgeschossene Kapitaene... Hier waeren es dann dementsprechend mehr Daten, aber eben nur verfuegbare, daher ist das ja auch in Ordnung. Der Grossteil davon hat sich ebenfalls schon bewaehrt.

Leere Koordinaten werden in den jeweiligen Tabellen natuerlich einfach nicht beruecksichtigt.

Es wird fuer die Ansicht wahrscheinlich 4 Zoomstufen geben. Die Karte wird 500x500 Pixel darstellen wo jeweils 1 px dann 1, 2, 3 oder 6 Einheiten der Gesamtkarte repraesentieren. Scrollbar usw.-

Wenn du sagst, dass wenn man mit einer Einheit wegfährt, und man dann dort einen Pukt "beschlagnahmen" kann, und das Gebiet im Radius x dem User "gehört" (wenn auch nur zeitweise), dann müsstest du nur den Mittelpunkt in der DB speichern.

Nein, weil 1. keine Gebiete einander ueberlappen duerfen, 2. "nur" ist gut..., das beschlagnahmte Gebiet waere 10-20-50 px gross, also im Grunde waere das kein Vorteil zur Sektorloesung, ausser dass es komplizierter ist.... (die Sektorloesung ist ja derselbe Ansatz weitergedacht, zumindest war das mein Denkweg) 3. Sieht auch das nicht so cool aus, wie Vektorbasierte Flaechen. :-)

War ja nur ne Idee

Ich finde die Idee mit dem Mittelpunkt nicht so abwegig.
Sollen sich Gebiete doch ruhig überlappen.
Gehört beides dem gleichen Spieler, ist das kein Problem; es ergibt sich in der Summe eine einheitliche Fläche.
Kommt es zur Überlappung mit einem anderen Spieler hast du entweder ein umkämpftes Gebiet oder du teilst es auf.

Bei deiner Lösung mit Polygonen wird es auch sehr schwierig, Überschneidungen zu verhindern und mit womöglich entstehenden Inseln sauber umzugehen.

Basen haben dann einen größeren Einflußbereich als Flotten und alles ist geritzt..
Und wenn du unbedingt willst, kannst du das Ganze mit hippen Vector-Kreisen anzeigen.

Naja ich sehe beim Mittelpunkt aber keinen Vorteil gegenueber dem Rastersystem, ausser dass es komplizierter ist und Sonderfaelle mit sich bringt (eben Ueberschneidungen). Es ist Mist wenn ich bei jedem Kampf ueberpruefen muss, ob dort eine Ueberschneidung vorliegt oder nicht...

Zudem soll das "ueberschneiden" ja quasi ein "uebernehmen" symbolisieren.

Auf Dauer koennte jede menge Datenschrott anfangen mit den ueberschneidungen und es entsteht grosser Overhead an Muell...

Kampf auf eigenem Gebiet = gewisser Bonus an Kampfkraft / Torpedotrefferchance... Mehr Gebiet unter Kontrolle = Ehre bei der eigenen Koalition...

Ueberschneidungen muessten bei den Polygonen direkt bei der "Ausweitung" interpretiert und geloest werden. Bei der Mittelpunktsvariante geht das nicht.. dadurch entstehen viele mehrfach definierten Flaechen - oder die geschnittene Flaeche wird komplett geloescht, womit wir im Grunde wieder beim Rastersystem sind.

"Inseln" wuerde ich - bei einer Polygonloesung - komplett droppen, das annektierte Gebiet sollte zusammenhaengend sein.

Es soll gar keinen "festen" Einflussbereich geben, sondern immerzu die Moeglichkeit Fremdgebiet zu uebernehmen - dauerhaft bzw. bis zur Wiederuebernahme.

Wie sieht es den mit der Spiellogik dahinter aus?
Warum gehört einem Spieler auf einmal ein Gebiet?
Welche Grundform soll das Gebiet haben?
Warum gibt es einen Bonus im eigenen Gebiet?

Ich philosophiere einfach mal (musst du nicht beachten):
Angenommen der Spieler setzt eine Boje oder Phalanx in einem Gebiet aus, dann könnte das sein Eigentum makieren und er könnte dadurch in Kämpfen Vorteile aus den Scannerdaten ziehen. Ich denke das ganze wäre dann ein Kreisförmiger Scannradius um das Objekt. Ein Erobertes gebiet könntest du ausmessen wenn du die mittelpunkte aller Punkte miteinander zu einer poligonfläche verbindest.

Durch Baukosten, leichte Zerstörbarkeit oder begrenzte Anzahl könnte man verhindern das der Spieler zuviele dieser Punkte festlegt (und damit viel rechenaufwand produziert).
Überlappungen würde ich in Kauf nehmen. Wenn du viel berechnen willst könnten sich die Objekte ja gegenseitig stören bzw aufheben, wenn genügend eigenen Objekte um ein feindliches Objekt platziert sind. Obendrein kannst du einen Sperrradius um ein Objekt festlegen in dem kein weiteres aufgestellt werden kann.

Ich gehe aber davon aus das ein Spieler recht schnell eine feindliche boje aus dem Wasser bläst wenn sie irgendwer in seinem (vermeindlichem) territorium aufstellt.
Das gibt Zündstoff fürs Spiel. :lol:

Obendrein ist es doch taktisch eine geile sache wenn man zuerst 3 bojen aussetzt um einen kampf den man in einem gewissen gebiete erwartet vorzubereiten oder um durch stöhrsender Langstreckentropedos abzwehren, flotten vor feindlichem radar zu verstecken oder um pantomflotten in dem gebiet zu erzeugen.. naturlich nur wenn der andere spieler selbst ein scannfähiges objekt im bereich hat. Vieleicht muss man ja sogar speziell bojen bauen um die gewünschten effekte zu erzeugen..
(ich glaube damit überspitze ich die idee jetzt aber masslos... :roll: )

Programmiertechnisch würde ich den mittelpunkt und radius festhalten und dann immer kreisbereich um die koordinaten eines fremden objekts berechnen und sehen ob es mit irgendeinem objekt auf der karte kollidiert (in dessen scannbereich kommt). Gleiche methode würde ich auch verwenden um festzulegen ob an einem gewissen punkt eine boje ausgesetzt werden darf oder ob man sich zu nahe an einem feindlichen objekt befindet.

Die Anzeigelogik für solche Bereiche kann man Theoretisch schon im SQL Datenbankquery implementieren, wobei die logik dann nur Objekte zurückgibt die im Radius von irgendwas (vom spieler) liegen.
Die Gebiete würde ich mit deiner Poligonformel und den mittelpunkten (koordinaten) der objekte eines spielers berechnen (vieleicht im uhrzeigersinn um die basis?). Finde es sehr lustig wenn auf einmal ein newbie kurz vor der neuberechnung der karte eine boje am anderen ende der welt aufstellt.
natürlich wird die ihm dann auch gleich weggeballert, aber für die nächsten 6 stunden steht er oben auf der Liste

Soweit mein gedankenspiel zu AP.
(hab das im übrigen in meinem spiel verworfen und setze auf feste sektoren die man erobern kann)

reg4rds
chojin