Flotten bewegen - wie, wann und wo?

Habe vorhin mit einem Bekannten ein wenig diskutiert und wir sind nicht wirklich zu einer Loesung gekommen. Ich finde aber, dass es eine interessante Fragestellung ist und es da ja verschiedene Moeglichkeiten gibt.

Also erst einmal das Szenario: Ein Spieler moechte mit seiner Flotte von A nach B fahren. Alle Spieler in gewisser Reichweite mit einer gewissen Sonarstaerke sollen in der Lage sein, diese Flotte zu sehen. Es soll weiterhin gewisse Automatismen geben, so dass z.B. andere Schiffe automatisch attackieren was sich bis auf X Einheiten an sie annaehert. Beide Faelle muessen die aktuelle Position des Geschwaders zum jeweiligen Zeitpunkt kennen.

Das Event, das bei der Ankunft getriggert wird, ist komplett unabhaengig hiervon, kann also vernachlaessigt werden.

Nun ergeben sich im Grunde drei Implementationsmoeglichkeiten (wenn ich von Client spreche, meine ich nicht den Browser, sondern z.B. die KI der Schiffe im Daemon oder das Web Backend):

1. Regelmaessige Updates (minuetlich?) direkt in der Geschwaderdatenbank, also quasi x += delta_x * geschwindigkeit * differenz_seit_update und simples Auslesen der aktuellen Position ohne Logik, wobei per WHERE effizient die Datenmenge begrenzt werden kann und der Client nicht mit Daten handeln muss, die ihn nichts angehen.

Vorteil: Einfachste Implementation, wenig Berechnungen

Nachteil: Viele Datenbank Schreibzugriffe (und damit Tablelocks), Granularitaet auf Minuten begrenzt (nicht so tragisch, da dies nur ein paar Pixeln Bewegung entspricht und der Client auch per xmlhttprequest nur in minuetlichen oder groesseren Abstaenden updates bekommt).

2. Keine Updates in der Datenbank, diese enthaelt nur Start- und Zielkoordinaten, Geschwindigkeit und Starrtzeitpunkt. Der Client berechnet die aktuelle Position dabei live.

Problem dabei, man kann die Position nicht einfach einschraenken und muss erst einmal ALLE Positionen berechnen, oder zumindest einen Forecast machen, welche Geschwader in der Naehe sein koennten und dann die genaue Position all jener Berechnen. Hier gibt es dann noch zwei Alternativen:

a) Berechnung komplett im Client = Daten ueber alle Geschwader muessen transferiert werden

b) Berechnung teils im Client, teils in der Datenbank = Man kann die Daten einschraenken, belastet aber zusaetzlich die Datenbank mit der Berechnung

Vorteil: Nur Datenbank Readzugriffe, Keine Einschraenkungen bei der Granularitaet

Nachteil: Aufwendige, Komplexe Berechnungen, mehr Datenbankbelastung, der Client sieht Daten die ihn nichts angehen, unter Umstaenden umfangreiche Berechnungen in der Datenbank noetig (b)), viel mehr Aufwand beim Readzugriff, der haeufig sein kann

3. Bei Geschwaderstart wird der Kurs vorberechnet. Der Rechenaufwand von 2. wird hier auf den Missionsstart verlagert, spaetere Lesezugriffe (die wahrscheinlich mehr sein werden) sind fast so simpel wie in 1., es entfaellt jedoch das minuetliche Update, die Granularitaet ist dennoch nicht feiner.

Vorteil: Weniger Rechenaufwand als in 2, gute Read Performance, kein Locking das mit der Geschwadertabelle kollidiert

Nachteil: Bei Kursaenderungen oder Geschwindigkeitsaenderungen muss alles neu berechnet werden, viel DB Write und Berechnungsaufwand beim Missionsstart, sehr viel DB IO und damit Speicher- und Plattenbelastung, Granularitaet auf Minuten begrenzt (nicht so tragisch)

Was denkt ihr?

Achja, edit:

23:34 <+Artrey> Das betrifft vor allem das Verhaeltnis von Berechnungen in Backend, Daemon und DBMS
23:34 <+Artrey> und damit Fragen der Skalierbarkeit

4. möglichkeit: automatische reaktion nur von flotten, die statisch "auf patroullie" sind. dann brauchste nur im vorraus den schnitt kreis/gerade zu berücksichtigen, was die menge wesentlich verringert.

oder man berechnet alle möglichen ereignisse, die auftreten könnten (man weiss ja nicht ob sie auftreten.. kursänderung, kampf, ...) und schmeisst sie in eine memory-tabelle ala:

x | y | flotteid | flotte2 | zeit

und arbeitet die liste im deamon per echtzeit ab (oder übermittelt sie direkt an den deamon und spart sich die db). Der muss dann immer ein paar triviale prüfungen machen (beide flotten da, oder eine schon abgezogen/tot? feindlich/freundlich? etc. pp.) und triggert die passenden ereignisse.

ich hatte bei mir die flotten parametrisiert gespeichert (startx/y, vx/y, startzeit; position = start + (t-startzeit)*vx) und eine formel konstruiert mit der ich alle flotten bestimmen konnte, die sich zu jedem t näher als x einheiten der flotte nähern. Dieses ergebnis wäre z.b. eine prima eingabe für o.g. tabelle.

ob freund oder feind habe ich bei kontakten nie berücksichtigt (kann sich ja während des fluges ändern .. krieg ist schnell erklärt) und daher war eine echtzeitprüfung unerlässlich.

bei ner kursänderung braucht man nur ein "delete from flottenereignisse where flotteid=$fid or flotte2=$fid" und die flotte kann neu versendet werden und neue ereignisse triggern.

Wie performant die sache gerade unter last ist, weiss ich nicht. Auch steigt der aufwand und die Anzahl der ereignisse sicherlich quadritisch (oder noch schlimmer exponentiell) mit der aktivität der spieler. Sprich ein Krieg mit seinen zahlreichen flottenbewegungen kann den server schon stark zum schwitzen bringen.

Wie im IRC geschrieben, darum geht es grad leider weniger, das wuerde ich aber eh aehnlich machen (Abfangen).

23:45 <+Artrey> es geht ja primaer um den read
23:46 <+Drezil> ?
23:46 <+Artrey> na sagen wir jeder Spieler hat von seiner Basis aus einen Sonarradius
23:46 <+Artrey> in dem er alle flotten sieht
23:46 <+Artrey> _auf ihrer aktuellen Position_
23:46 <+Artrey> dafuer muss ich die position kennen
23:46 <+Artrey> und genau darum geht es ;)

Und nach Query Diskussion: er hat quasi Variante 2. ohne forecast und in einem postgres view gekapselt bei sich im Einsatz.

wenn es eine php implementierung ist ohne echte persistente objekte auf dem server, dann kann man backendlogik zugriffstechnisch schlecht von der DB trennen, ein client ist dann in meinen augen der prozess beim benutzer auf dem browser, sprich am anderen ende der leitung

was ist der client nun in eurem spiel, daemon, php skript oder noch was drittes? wenn's daemon ist, wie oft pollt er selbst die DB überhaupt und wie oft wird er von den browsern gepollt, mir persönlich fehlt die vorstellung von der architektur auf der die ansätze verglichen werden sollen, so dass ein konsistenter vergleich IMHO unvernünftig ist

Ok, ich versuch es ein wenig deutlicher zu machen.

Der "Client" (ja doofes Wort in dem Kontext) kann hier verschiedene Dinge umfassen.

Im Endeffekt sieht meine Gesamtstruktur so aus:

Browser <-> Javascript <--JSON--> Perl Catalyst Controller (Web backend) <--ORM--> RDBMS (Persistente Speicherung)

gleichzeitig, wenn noetig: Perl Catalyst Controller <--Event via Socket--> Perl Daemon <--ORM--> RDBMS (Persistente Speicherung)

und: Perl Daemon <--Event oder Job der ansteht--> Berechnung <--ORM--> RDBMS (Persistente Speicherung)

Sowohl der Controller, also das Web Backend, als auch der Daemon, sei es bei einem eingehenden Event oder einem scheduled Event oder Job sollen in der Lage sein die aktuelle Position von Geschwadern auszulesen.

Die Frequenz des Ganzen ist ziemlich haeufig, ich bin mir noch nicht sicher ob es technologisch in Richtung Comet geht und ich mir fuer die frequenten Ajax geschichten nen simplen Webserver mit persistenten Verbindungen auf ne andere IP Adresse binde, aber ich denke mal Updates irgendwo zwischen 1 und 5 Minuten je User werden Standard sein. Jeder User kann dabei die Positionen von Geschwadern in einer gewissen Reichweite (wahrscheinlich so Scope von 25 Usern, die je 1-10 Flotten haben koennen) sehen.

Der Daemon wird wohl ca. minuetlich einmal den state pollen muessen fuer automatisiertes Abfangen. Das ist noch nicht fix, aber es wird auf etwas in der Richtung hinauslaufen.

Es ist nicht geplant das Ganze irgendwie von der DB zu trennen. Die ist zwangslaeufig involviert, ausser ich treibe die Comet Idee so weit, dass ich den State der Geschwader dort cache. Das ist aber momentan nicht geplant, also erstmal alles per RDBMS. Die einzige Frage ist wie, wann und wo ich update und rechne, wie der Titel schon sagt. ;)

hab mir schon so ähnlich vorgestellt, aber ohne die eigenarten des PCC und Comets (leider gehen die demos nicht) zu kennen  und da ich demnächst selbst vor einem wohl noch schlimmeren problem stehe (echtzeit iso-ansteuerung der spielfigur) , hätte ich vermutlich zunächst eine zwischenlösung  gefahren. Der Ansatz in Fabularis würde mich zb auch interessieren

man lässt die daten von der DB auf dem deamon/appserver und rechnet timer-/periodengesteuert in stücken, bei jedem tick schreibt man relevante daten zurück in die DB bzw synct nochmal mit ihr.  ist vorgang abgeschlossen dann sowieso nochmal sync.

der client (also FrontEnd) wird vermutlich sowieso eigene pollfrequenz haben. daher hat man weder 1 noch 2, ich hätte einfach einen ansatz (oder halt mischung) genommen und prototypen gebaut, echte vorteile und nachteile wirst du vermutlich erst feststellen wenn enstprechende benchmarks gefahren hast

Joa, tendiere auch dazu das mal zu prototypen und zu benchmarken.

Wobei eine eigene Pollfrequenz im Client (Browser) ja keiner der drei Loesungen wiederspricht, sofern man mit der Granularitaet von z.B. minuetlichen Updates leben kann, was ja bei minuetlicher oder groesserer Update Frequenz nicht ins Gewicht faellt.

Letztendlich ist die genaue Architektur relativ egal denke ich, es geht nur um das Verhaeltnis von Write und Read und das entscheidet darueber welcher Ansatz der effizientere ist. Dass die Architektur und das Gamedesign darauf einen direkten Einfluss haben ist klar, daher kann ich mir auch durchaus vorstellen, dass man wirklich im Einzelfall unterscheiden muss. Aber ein paar Richtwerte waeren schoen gewesen, kann nicht/kaum glauben, dass ich der erste bin, der sich die Frage stellt, da hier ja mindestens zwei andere interessiert sind. ;)

Es spielt allerdings auch das Userverhalten selbst eine grosse Rolle, was es schwer macht eine Vorhersage zu treffen. Irgendwie hat wirklich jede Methode ihre Vor- und Nachteile und wenn die Performance nicht sonderlich abweicht, wuerde ich mich wohl fuer 1. oder 3. entscheiden wollen, weil der Zugriff, der an verschiedener Stelle noetig ist, vereinfacht wird. Allerdings belastet das wieder das DBMS mehr... waehrend hingegen 2. schlechter skaliert und das DBMS umso mehr belastet je mehr Flotten da sind. ;) 

Und da ich grosser Freund von Skalierbarkeit bin, favorisiere ich gerade rein in der Theorie die Optionen 1. und 3., koennte mir aber gut vorstellen, dass 3. die effizienteste Variante ist. Ist auch das wozu mir mein Bekannter geraten hat. Laut seinen Infos werden aehnliche Verfahren oft/regelmaessig in der Gaming Industrie bei Multiplayer Applikationen eingesetzt und haben sich dort bewaehrt. Das ist natuerlich nur eine Aussage ohne Belege, aber es klingt plausibel. ;)

hätte vorhin fast geschrieben, dass auch zunächst voll auf 1 setze werden und  erstmal der DB-Perfomanz vertraue, der grosse Vorteil ist quasi die implizite Persisenz der Zustände. Erfahrung bei sowas habe ich null, wird sicher spass machen wenn's soweit ist, mit anderen worten: nicht rumreden-handeln

Naja das hab ich so nun seit 5.5 Jahren im Einsatz, nur weiss ich nicht wie gut es nach oben skaliert (vor allem weil sich das Spielkonzept ein wenig aendert) und ob es nicht eleganter geht. ;) Aber es ist auf jeden Fall die "einfachste" Loesung in der Implementation. Man koennte vor allem relativ einfach spaeter zu 3. wechseln, waehrend 2. sich doch recht stark von den andern beiden Ansaetzen unterscheidet.

Weniger Persistenz hast du ja mit 3. auch nicht, nur noch mehr Daten zur Verfuegung, die irgendwie ins System rein und spaeter wieder raus muessen, also ein wenig Verwaltungs- und mehr IO-Overhead. ;) Vor allem wenn Neuberechnungen faellig werden.

1. hat den grossen Vorteil, dass man relativ einfach viel Schindluder mit den Geschwadern treiben kann, wie z.B. mitten drin anhalten und pausieren oder die Geschwindigkeit aendern, etc.., ohne dass noch gross etwas zu tun waere. Das ist natuerlich schon relativ elegant.

Vor allem faellt mir grad auf, dass ich die Missionen sowieso von den Flotteninfos selbst abstrahieren sollte, um Wegpunkte effizienter und ohne Redundanzen zu implementieren, insofern waere auch das Locking ein wenig unproblematischer und entspraeche weitestgehend dem in 3....

Dann geht es primaer darum wie die Performance je nach read und write Verhaeltnis aussieht, vielleicht find ich am Wochenende Zeit das zu testen.

das problem bei 1 ist:

bei 100 usern funktionierd das noch super ..

bei 1000 usern anfangs auch ...

aber später im spiel steigt die zahr der flotten (je nach spiel) im schlimmsten falle exponentiell.

was passiert, wenn das zurückschreiben der daten (was ja in einer transaktion abläuft) länger dauert, als der "tick"?

programmiertechnisch ist dann das kind im brunnen und ohne viel aufwand, wird man dann auch nicht mehr viel optimieren können.

ich würde eher auf eine "live"-berechnung setzen mit ausreichenden caching-mechanismen um die konkrete ergebnismenge so weit runterzu kondensieren, dass nur noch wenige berechnungen übrigbleiben. die müssen dann zwar bei jedem read gemacht werden (vllt. noch ein cache?), aber die berechnungen würden bei einem tick ja ohnehin für die ganze liste anfallen.

wie ich das meine? konkret angenommen:

100.000 flotten unterwegs. mach bei minütlichem update 100000 berechnungen + write in die db (inkl. table-lock, io-problemen bei ner lahmen hdd, ...)

wenn aber pro anfrage z.b. nur 100 flotten angezeigt werden müssen (spielfeld ist groß, ein ausschnitt hätte nie alle flotten drin!) und as durch caches soweit optimiert ist, dass man nur noch 120 potentielle flotten hat, die man konkret berechnen muss, dann gibt das bei einer abfragefrequenz von 500/minute (was denke ich mal realistisch ist, da der client ja auch cachen soll etc.) insgesamt 60.000 berechnungen OHNE write in die db (und den resultierenden locks).

außerdem ist die granularität bliebig wählbar (ich würd z.b. sec nehmen - dann kann man aber ähnliche anfragen nicht mehr cachen; bei minuten könnte man noch einen cache einbauen für alle weiteren hereinkommenden anfragen den sektor betreffend - setzt aber vorraus, dass man requestübergreifend was machen kann).

14:45 wenn wir das universum rastern (wozu ich übrigens dringenst raten würde - das mach etliche sachen extrem einfach optimierbar!), dann haben wir quiasi noch sektoren.
14:45 der client fragt immer ganze sektoren an und bekommt dann eine liste von allem, was er sieht.
14:47 beim flottenstart werden in eine tmp-tabelle einfach alle sektoren eingetragen, die durchflogen werden.
14:48 stürzt etwas ab, kann man sich aus der bewegungsdaten-tabelle (start, vektor, zeit) die sektordurchquerungstabelle wieder generieren.
14:50 dann reicht ein 'select (konkrete berechnung) from flottensektortabelle s join flottenbewegung b where $sektor in s.durchflug and $sektor = sektor_von(konkrete position aus
               berechnung)' reichen.
14:51 da die tabelle s die ergebnismenge erheblich einschränken dürfte (vllt. auf nen paar 100 ergebnisse im dichten getümmel), werden auch nur noch wenige durch die  2. where-bedingung
               ausgesiebt.
14:53 in non-sql (bsp: c++) würd ich das konkret so umsetzen: ein tree mit [sektor] -> [ [flotteid, eintrittszeit, austrittszeit], nächste flotte, ... ] und dann nur ein 'select from
               flottenbewegung where flotteid in (...)' - das wäre mit abstand der minimalste aufwand.
den tree kann man aber auch als heap-db mit dem sektor als b-tree-index sehen macht ja keinen unterschied.

Original von Kallisti

Naja das hab ich so nun seit 5.5 Jahren im Einsatz, nur weiss ich nicht wie gut es nach oben skaliert (vor allem weil sich das Spielkonzept ein wenig aendert) und ob es nicht eleganter geht. ;) Aber es ist auf jeden Fall die "einfachste" Loesung in der Implementation. Man koennte vor allem relativ einfach spaeter zu 3. wechseln, waehrend 2. sich doch recht stark von den andern beiden Ansaetzen unterscheidet.

keiner sagt dass es schlecht seien muss, als reiner webentwickler hat man den ansatz 1 ja immer, indem die clientaufrufe mehr oder weniger direkt bis  zur DB durchgereicht werden. Eine gute DB wird das schon abkönnen, wenn genug CPUtime und Ram zur verfügung stellst. Das grösste nadelöhr ist doch das protokol an sich und die damit verbundenen "übel" wie apache und co (das beste beispiel: ein php chat) Abhängig von dem Spiel/Anforderungen wird man um eine alternative lösung nicht herumkommen (hab rtmp genommen), Comet ist sicher auch  interessante sache. Gut ich rede jetzt mehr projektbezogen, aber stimmen tuts trotzdem

Ich hab ein hartes Limit von 10-20 Missionen, das ist also kein Issue (exponentielle Steigerung). Ich rechne mit im Schnitt 5 Flotten je Spieler, die wirklich fahren. Wenn ueberhaupt. Tendenziell eher weniger, weil die Spieler ihre Flotten bei meinem Spielkonzept eher ruhen lassen werden, wenn sie nicht online sind.

Gehen wir also von 100.000 Flotten aus, sind das 20.000 aktive Spieler (schon ein ganz schoener Batzen, kenne kaum komplexe Spiele die das auf einer Kiste unterstuetzen). Egal!

Wenn von den 20.000 Spielern nur 20% gleichzeitig aktiv sind, habe ich 4.000 Views mit je ca. 125 Flotten in Sicht.

Das sind nicht 60.000, sondern 500.000 Berechnungen. Und das ohne Puffer fuer den Forecast, welche ueberhaupt potentiell in Frage kaemen (20-30% mehr).

Hinzu kaemen noch die weiteren Reads aus dem Daemon. Der Vorteil bei der Granularitaet existiert, das stimmt. ;)

Ab der Groesse wird dann wohl auch ein expliziter Caching Daemon nur fuer Flottenbewegungen in memory (also quasi ein Mix aus Variante 1 und 2) interessant, da dann bei allen drei Verfahren die Datenbank irgendwann zum Bottleneck wird.

Fuer Sektoren wie du sie beschreibst seh ich ehrlich gesagt keinerlei Vorteile gegenueber dynamischer Sektorenberechnung, die ich fuer meine Vorstellung einer zoombaren Karte sowieso brauche. Und gegenueber der Temp Tabelle keinen Unterschied gegenueber dem Speichern der Start und Endposition jeder Mission (ah ich seh grad, dass es da nur um den Puffer geht, ich glaub das geht um einiges einfacher indem man einfach die x und y koordinate um die maximal moegliche Bewegung je Tick erweitert).

Aber ich werd trotzdem alle drei Verfahren testen. ;) Grad der Unterschied zwischen read und write locking interessiert mich ja.

Ich sagte doch, dass Drezil der "Objekte die sich im Raum bewegen"-Experte ist. ;-)

Sehr interssantes Thema... deshalb versuche ich mich hiermit zu beteiligen, aber bitte nicht den Kopf abreißen falls es nicht dem bisher angeschnitten Niveau gerecht wird (hab halt noch relativ wenig Erfahrung, was Performance angeht).

Ich weiß auch nicht ob es dir mehr um das Anzeigen der aktuellen Flottenposition ging, oder auch im Kollisionen, ... 

Lösung 1 und 2 erlauben einem relativ einfach auch Abfangen oder dergleichen zu implementieren, was bei Lösung 3 wohl er schwerer wird. Entweder man geht dann zu 1 oder 2 über oder man hat eine rießige Liste von möglichen Kollisionen. 1000 Flotten könnten sich im Worst Case eben mit je 999 Flotten kreuzen, das wären also 999 Writes bei nur einer Kursänderung...im Vergleich dazu hast du bei Ticks auch nur 1000 Writes (pro min.). Es kommt also ganz darauf an wie weit die Flotten fliegen können/im Durchschnitt fliegen und ihren Kurs ändern.

Im Moment setzten wir 1. ein, aber werden wohl zu einer "sektorierten"-Variante von 3. kombiniert mit 2. übergehen:

Flotte A startet im Sektor 1 und will bis sagen wir Sektor 5 fliegen (irgendwo in den Sektoren). Dann werden die Zeitpunkte der Sektorenübergänge (1-->2, 2-->3, 3-->4, 4-->5) gespeichert (mit FlottenId). Bzw. nur der aktuelle Sektor und wann die Flotte im Nächsten ist, beim Sektorenübergang werden dann diese beiden Werte erneut berechnet und gespeichert. Man könnte bei einem solchen Übergang auch noch alle möglichen Kollisionen speichern (hätte dann den grundsätzlichen Vorteil von 3., jedoch ohne eine rießige Datenmenge zu erzeugen)

Wenn dann die aktuelle Positionen von Flotten (weswegen auch immer...Abfangen, Anzeigen auf der Karte) benötigt werden, brauch die nur von wenigen Flotten berechnet werden. Nämlich von denen, die sich gerade im relevanten Sektor(en) befinden. Ich denke das entspricht in etwa dem Verfahren von Drezil.

Anstatt von Sektoren könnte man wohl auch einfach das Neuberechnungsintervall vergrößern und Flotten dann mit einer bestimmten Toleranz die Flotten auswählen. Von diesen dann die genaue Position berechnen.

Aber auf deine Benchmarks bin ich schon sehr gespannt *grins*

Also das Abfangen steht in keiner Relation dazu, denn ich würde einfach bei Missionsstart des abfangenden Geschwaders den optimalen Abfangkurs errechnen (anhand von Start und Geschwindigkeit beider Geschwader und des Ziels des abzufangenden) und ein Event generieren, das dann zu dem jeweiligen Zeitpunkt einen Kampf berechnet. Das abfangende Geschwader wäre also einfach auf einer normalen "Abfangen" Mission mit dem optimalen Punkt zum Abfangen als Ziel.

Ändert das Ziel seine Mission oder Geschwindigkeit, muss das System natürlich den Abfangkurs neu berechnen.

Was ich als gewisse Form von K.I. gern hätte ist eine Mission "Guard" oder "Protect", in der ein Geschwader quasi still steht und alles in einem gewissen Umkreis beschießt. ;) Das ist mit allen drei Varianten relativ einfach möglich. - Selbst wenn das Spielkonzept selbst quasi in Echtzeit abläuft, braucht man ja eine Schussfrequenz, sofern man Interaktion in Kämpfen möchte und ein Kampf selbst nicht rein atomar ablaufen sollte. Die würde ich der Einfachheit halber mit einer Minute ansetzen, insofern wäre ein minütlicher Check fällig, ob entsprechende Ziele in der Nähe sind. Ist ein ziemlich simpler join bei 1. und 3. und ein paar Berechnungen mehr bei 2..

Komplizierter wäre eine Mission "Patrol", bei der das Geschwader einen vordefinierten Kurs aus Wegpunkten abfährt und dabei alles angreift, was ihm zu nahe kommt. Klappt mit Variante 1. und 3. ziemlich problemlos, wird mit Variante 2. aber wieder etwas eklig, wenngleich dennoch möglich.

Deine Kollisionsthematik kann ich daher nicht ganz nachvollziehen. Ich würde das nicht vorher, sondern "on demand" berechnen. ;) Ersteres ginge natürlich auch, kann aber ziemlich kompliziert werden, wenn viel interagiert (Torpedos, andere Flotten...). Dann macht das Aufräumen keinen Spaß mehr...

Den Hintergedanken bei den Sektoren kann ich nun ein wenig verstehen, wenn man 2. und 3. kombiniert. Nur irgendwie ist mir das zu unsauber... ich bin Freund von kompromisslosen Lösungen und die Mängel der einen (Begrezung der Auswahlmenge bei 2.) mit einer beschnittenen Methode der anderen zu beheben (Zwischenspeichern wie in 3. von wichtigen Punkten zum Rastern) ist irgendwie nicht die Art von Problemlösung, die mich glücklich macht. ;) - macht vor allem Wartbarkeit und Verständnis nicht einfacher, sondern das eigentliche Problem imho zu unnötig kompliziert. Aber das ist meine persönliche Meinung. ;) Vor allem ist mir das fast zu viel Aufwand, um es für einen Benchmark zu integrieren...

was ich mit Kollision entspricht eigentlich deinem Patroulieren:

Falls sich zwei Flotten (zufällig) im Weltall begegnen, fangen sie an zu kämpfen (ohne dass einer der beiden User direkt gesagt hat "Fange Flotte A/B ab").

Und das ist wie du bereits gesagt hast, nicht so einfach und sollte mMn am besten mit der Sektoren-Lösung performen.

Kollision muss ja nicht direkter Schnittpunkt heißen, wenn ich das richtig verstanden haben. Die Guards und Patrols haben einen gewissen Radius, ab dem sie aktiv werden?

Da ich stark annehme dass es hier um Aquaphobia 2 geht eine Frage: Wird es weiterhin die südliche Verlangsmung geben? Das würde ja auch noch ein riesen "Problem" werden..

Original von Fornax

Kollision muss ja nicht direkter Schnittpunkt heißen, wenn ich das richtig verstanden haben. Die Guards und Patrols haben einen gewissen Radius, ab dem sie aktiv werden?

Jau genau. Der Radius koennte sogar je nach Schiffstypen variieren (Artillerie, Nahkampf...). Deshalb wuerde ich so etwas wirklich nicht vorher berechnen.

Wenn man ein ungefaehres Verstaendnis von Einheiten haben moechte: Die Entfernung zwischen zwei Basen betraegt ca. 100 Einheiten, Schiffe werden wohl ca. 50-100 Einheiten/h schnell sein. Nahkampf heisst ca. 2-5 Einheiten Radius, Fernkampf ca. 10-30 - ca. weil noch nichts davon fest entschieden ist.

Da ich stark annehme dass es hier um Aquaphobia 2 geht eine Frage: Wird es weiterhin die südliche Verlangsmung geben? Das würde ja auch noch ein riesen "Problem" werden..

Jep, geht es. ;-) Momentan denke ich, dass die Verlangsamung nicht mehr noetig ist. Nichtsdestotrotz waere es kein "Riesenproblem" fuer das Bewegen selbst (zumindest mit Methode 1 und 3, Methode 2. wuerde wohl performance technisch gekillt). Sehr wohl natuerlich fuer Kollisionsvorausberechnung sowieso Abfangkursberechnung. Und genau letzteres waere ein Argument es nicht mehr einzubauen.^^

Die wichtigeren Argumente es nicht mehr einzubauen werden aber sein, dass die Spieler weit staerker starten und einfacher aufholen koennen, es sehr regelmaessig (alle zwei Wochen oder so) "bebt", also das gesamte Spielfeld neu aufgerollt wird, jeder Spieler 1/3 aller anderen als Zwangsverbuendete haette und territoriale Kontrolle in Umgebung der eigenen Basis so wichtig ist, dass nur wenige weitere Reisen aufnehmen werden.

Deshalb hat sich die Hauptproblematik mit der Verlangsamung (Noobschutz) mehr oder weniger erledigt und ich denke das Spiel wird ohne interessanter. ;)

Zur Info fuer alle, die das nicht kennen: Wir haben derzeit ein Feature, dass alle Flotten, die sich von ihrer Heimatbasis um eine gewisse Entfernung nach Sueden weit weg befinden (ab einem vordefinierten Punkt bis zu dem das nicht gilt) mit jeder Einheit nach Sueden um eine Einheit langsamer werden, bis sie irgendwann stehen bleiben. Umgekehrt beschleunigt die Flotte dann wieder langsam. So ist es alten Spielern nicht moeglich die ganz jungen zu bashen, weil sich immer eine Distanz dazwischen befindet, die dies verbietet. Die Spieler werden also quasi immer der Reihe nach von links nach rechts platziert (mit ein wenig Zufall), aber Reihe um Reihe kontinuierlich nach Sueden. 

Wir hatten naemlich vor ganz, ganz langer Zeit mal Probleme, dass einige, die seit Monaten spielten mit ihren Flotten in die Startgebiete gefahren sind und dort zwischen den ganz frischen Anmeldungen gewildert haben. Ich halte absolut nichts von "du darfst das nicht" Noobschutzsystemen, daher war dies eine Loesung mit der ich leben konnte.