ZFX
ZFX Neu
Home
Community
Neueste Posts
Chat
FAQ
IOTW
Tutorials
Bücher
zfxCON
ZFXCE
Mathlib
ASSIMP
NES
Wir über uns
Impressum
Regeln
Suchen
Mitgliederliste
Membername:
Passwort:
Besucher:
4460784
Jetzt (Chat):
14 (0)
Mitglieder:
5239
Themen:
24223
Nachrichten:
234554
Neuestes Mitglied:
-insane-

ZFX
Coding-Foren
Algorithmen und Datenstrukturen
Re: Rendern in einer 2d-Engine: Vorgehensweise
Normal
AutorThema
Hundefutter Offline
ZFX'ler


Registriert seit:
03.10.2006

Nordrhein-Westfalen
Rendern in einer 2d-Engine: VorgehensweiseNach oben.
Hallo zusammen.

Ich habe eine kleine Sammlung von Funktionen für den 2d-Bereich, mit denen ich auch schon ein paar kleine Spielchen erstellt habe.
(Mehr auf www.groovy-goblins.com)
Nun möchte ich diese Funktionen in einer kleinen Engine kapseln, sodass ich daraufhin eine gute Grundlage für weitere Spiele habe.

Bin gerade dabei, mich mit dem Rendern zu beschäftigen. Wie ist sowas normalerweise realisiert? Habe schon mit ein paar Leuten gesprochen und von der Nutzung von Bäumen zur Kollisionsabfrage gehört, könnte man so auch das Rendern aufbauen? Also eine hirarchische Struktur, mit der man abhängig von der aktuellen Szene / dem akt Level eine bestimmte Zahl von Objekten auf dem Bildschirm anzeigt.

Da hier mehrere Leute mit großer Erfahrung in dem Bereich sind, würde ich einfach mal gerne wissen, wie man generell oder wie ihr das Rendern in einer 2d-Engine angeht.

MfG
Hundefutter
04.03.2009, 12:00:26 Uhr
Schrompf Offline
ZFX'ler


Registriert seit:
04.04.2006

Sachsen
Re: Rendern in einer 2d-Engine: VorgehensweiseNach oben.
Das ist aber eine sehr allgemein gefasste Frage. Und so wie ich das verstehe, ist das Rendern gar nicht die Frage, sondern die Auswahl der sichtbaren Objekte. Die ist für den 2D-Fall anfangs relativ schlicht beantwortbar:

a) Render einfach alles. Die Grafikkarte wendet sowieso ihre Clipping-Funktionen auf jedes Dreieck an und sortiert damit alle Elemente außerhalb des Schirms aus.

Vorteil: sehr einfach zu implementieren, reicht bei ein paar tausend Zeichenelementen völlig aus.

Nachteil: bei hoher Anzahl nicht sonderlich fix.

b) Iteriere (wie oben auch) lineare über alle zu zeichnenden Elemente und teste deren grafischen Bereich gegen den aktuellen Bildschirmausschnitt.

Vorteile: viele Elemente können bereits vor dem Rendern ausgeschlossen werden. Der Test Rechteck gegen Rechteck ist üblicherweise sehr fix.

Nachteile: Bei sehr hoher Anzahl macht sich selbst die Rechenzeit für das Drüberiterieren und den Sichtbarkeitstest bemerkbar. Außerdem spart man dadurch nicht wirklich viel, weil das Rendern von 2D-Sprites ja nicht mehr als das Verpacken zweier texturierten Dreiecke in einen dynamischen VertexBuffer ist. Das "Zeichnen" eines Elements kostet also vielleicht 10x so viel wie das Testen, mehr ist da nicht rauszuholen.

c) Benutze eine räumliche Beschleunigungsstruktor. Die kann im schlichtesten Fall erstmal ein regelmäßiges Raster ein. In jedes Rasterelement tragen sich die Zeichenelemente ein, die es z.B. berühren oder ihren Mittelpunkt darin haben. Dann brauchst Du nur noch die Zeichenelemente in den Rasterslots durchgehen, die der aktuelle Bildschirmausschnitt berührt.

Vorteile: Damit verschiebt sich der Testaufwand vom Zeichnen (jedes Frame) zur Update-Funktion des Elements, wo es sich evtl. bewegt. Für statische Objekte reicht also eine einmalige Zuordnung, danach versuchen weiter entfernte Elemente gar keine Rechenzeit mehr. Bei dynamischen Objekten spart man nichts: die Einordnung ins Raster kostet üblicherweise genausoviel Rechenzeit wie der Sichtbarkeitstest, und beide passieren jedes Frame.

Nachteile: Klappt nur bei in der Spielwelt halbswegs gleichmäßig verteilten Zeichenelementen. Z.B. bei einem Weltraum-Szenario knäulen sich üblicherweise viele Einheiten an gewissen Ballungszentren, während anderswo grooooße Raumbereiche komplett leer sind.

d) Benutze eine schlauere räumliche Beschleunigungsstruktur. Das wäre z.B. ein Quadtree, was Du wahrscheinlich mit "Bäumen" meinst.


Vorteile: Der Quadtree ist adaptiv unterteilt, da wo es nötig ist. Womit Du evtl. in sehr dünn besiedelten Bereichen Rechenzeit und Speicher sparst und dafür in dichten Gebieten noch mehr Elemente vorab vom Rendern ausschließen kannst.

Nachteile: Die Einordnung kostet mehr Rechenzeit und die Gewinne für's reine Rendern sind kaum noch messbar... man spart ja nur das an Rechenzeit, was man (gegenüber den vorherigen Methoden) zusätzlich noch an Elementen vorab ausschließen kann. Für 2D-Rendern halte ich das für Verschwendung.

So... nette Aufstellung, aber Du hast in Deiner Frage ja auch noch die Kollisionsprüfung reingemischt. Die ist insoweit ein anderes Thema, da bei der Kollisionsprüfung ja nicht ein gegebener Bildschirmbereich gegen jedes Element geprüft wird (lineare Komplexität), sondern potentiell jedes Element gegen jedes Element (quadratische Komplexität). Die Rechenzeit dafür wächst halt quadratisch, die kann Dir sehr schnell um die Ohren fliegen. Theoretisch kannst Du mit obigen Methoden auch bei der Kollisionsprüfung herangehen. Praktisch gesehen erfordert die Prüfung aber doch subtil andere Beschleunigungsstrukturen. Beim Zeichnen z.B. reicht ein regelmäßiges Raster, während man für die Kollisionsprüfung lieber einen etwas weiter unterteilten Baum nimmt.

Das ist übrigens im Kern auch die Aussage des gern zitierten Artikels "Say No To Scenegraphs" - ein einzelner Graph für alle Zwecke wird eher früher als später scheitern. Gegen mehrere Strukturen, um die Zugriffe für verschiedene Zwecke zu optimieren, wurde nie was gesagt.

Bye, Thomas

04.03.2009, 12:35:26 Uhr
Dreamworlds Development
Hundefutter Offline
ZFX'ler


Registriert seit:
03.10.2006

Nordrhein-Westfalen
Re: Rendern in einer 2d-Engine: VorgehensweiseNach oben.
Hallo.

Erstmal vielen Dank für die ausfürliche Darstellung, das hört sich schon alles sehr gut an.
Jedoch bist du glaube ich schon eine Ebene tiefer gegangen, als ich es bis jetzt war, wahrscheinlich wegen der von mir ins Spiel gebrachten Kollisionserkennung.
Hatte es bis jetzt erst etwas allgemeiner gehalten. Folgende Grafik zeigt die Überlegungen, die ich bis jetzt hatte:

http://www.sebastian-surmund.de/public/Objektbaum.png

Was meint ihr zu so einer Ordnung der Objekte? Ist eher eine Art Klassifizierung der verschiedenen Objekte, also eine erste Einteilung.
So würde dann wahrscheinlich ein Teilbaum (z.B. der Teilbaum "GUI" ) genommen werden und dieser dann mit einer der oben genannten Methoden verarbeitet und angezeigt werden.
Könnte man das so machen?

MfG
Hundefutter

1 Mal gendert, zuletzt am 04.03.2009, 14:25:54 Uhr von Hundefutter.
04.03.2009, 13:00:27 Uhr
Schrompf Offline
ZFX'ler


Registriert seit:
04.04.2006

Sachsen
Re: Rendern in einer 2d-Engine: VorgehensweiseNach oben.
Hmmm... dieses Ineinanderwürfeln grundverschiedener Themen setzt sich da irgendwie fort. Die GUI gehört nicht in den Szenegraphen, Debugausgaben auch nicht. Grafische Objekte nach Spielmechanik-Details (Freund oder Feind) zu unterscheiden ist ebenso albern. Fonts sind keine grafischen Elemente, sondern Resourcen. GUI gehört nicht ins Level. Usw.
04.03.2009, 13:47:56 Uhr
Dreamworlds Development
Hundefutter Offline
ZFX'ler


Registriert seit:
03.10.2006

Nordrhein-Westfalen
Re: Rendern in einer 2d-Engine: VorgehensweiseNach oben.
Also meinst du, dass ich das Ganze falsch angehe?
Wie sollte ich denn sonst unterscheiden auf dieser Ebene Objekte unterscheiden?
Wie werden die Objekte aufgeteilt, bevor sie wie in deinem ersten Post beschrieben nach bestimmten Kriterien gerendert werden?

MfG
Hundefutter
04.03.2009, 14:25:35 Uhr
Schrompf Offline
ZFX'ler


Registriert seit:
04.04.2006

Sachsen
Re: Rendern in einer 2d-Engine: VorgehensweiseNach oben.
Meine Liste bezog sich nur auf Spiel-Zeichenelemente. Also bei einem Space-Shooter z.B. Asteroiden, Sternenbasen, Schüsse, Raumschiffe, Rauchwolken, Trümmer, übriggebliebenes Klebeband. Bei einem RPG die Bodentiles (wobei die ja von Haus aus als Raster organisiert sind, das kann man ausnutzen), Monster, Bäume, Feuer, Feuerbälle, Charaktere, Items.

Die GUI ist ein separates Subsystem, die hat in der Szene gar nix zu suchen. Ebenso Konsole, Debugausgaben usw.

Ich glaube, Du vermischst grundsätzliche Aufgabengebiete. Ich würde in einer 2D-Engine ganz unten allgemeine Klassen unterbringen, die 2D-Grafiken auf den Bildschirm bringen können. Dazu gehört meiner Meinung nach das Gruppieren von Grafikteilen auf Sammeltexturen, das Erzeugen der texturierten Quadrate usw... auch Umfärben, Skalieren, Zeichenmodi und sowas gehören da rein. Dann gibt es andere, separate Teile, die diese Klassen benutzt, um andere Aufgaben zu erfüllen. Die GUI würde z.b. die Grafikfunktionen benutzen, um Fenster, Buttons und Text zu rendern. Und gleichzeitig von dem Submodul "Eingabe" Maus- und Tastaturereignisse abfragen und verarbeiten. Die Spielwelt würde eine endlose Liste Entities verwalten, die jeweils untereinander interagieren, sinnlos durch die Gegend schweben oder einfach nur rumstehen. Ein Submodul "Spieldarstellung" zeigt dann einen Ausschnitt der Spielwelt an und benutzt dabei die Grafikklassen von oben. Die Hauptschleife des Spiels besteht dann aus "Welt aktualisieren", "Spielwelt-Ausschnitt zeichnen", "GUI draufpinseln" und am Ende vielleicht ein paar Debugausgaben "Ich hab soundsoviele FPS gemessen".

Wohin genau Du welchen Aspekt der Gesamtfunktionalität schiebst, ist in gewissem Maße auch Geschmackssache. Aus langjähriger (teilweise schmerzhafter) Erfahrung kann ich Dir aber sagen, dass Du in den meisten Fällen besser kommst, wenn Du einzelne Aufgaben identifizierst und die tatsächlich so unabhängig wie möglich implementiert bekommst. Also so dass die Schnittstelle zu und vom Submodul möglichst dünn ist. Das kann man zwar auch übertreiben, aber bis dahin ist es ein weiter Weg.

Ich hoffe, das hilft Dir. Und ich hoffe, Du verstehst jetzt auch, was ich mit "Themen vermischen" meine und warum ich das für eine schlechte Idee halte

Bye, Thomas
04.03.2009, 15:04:58 Uhr
Dreamworlds Development
Hundefutter Offline
ZFX'ler


Registriert seit:
03.10.2006

Nordrhein-Westfalen
Re: Rendern in einer 2d-Engine: VorgehensweiseNach oben.
Hui, da wird ja schon einiges klarer...

Danke für die ausführlichen Beschreibungen!

Ich denke, ich habe verstanden, was du mit "Themen vermischen" meinst und wie ich die Sachen anzuordnen und vor allem zu trennen habe. Die Beispiele in deinen Erklärungen verdeutlichen sehr gut das Vorgehen.

Ich glaube, ich fange jetzt erstmal an, alles neu zu strukturieren und mich dann nochmal melden.

MfG
Hundefutter
04.03.2009, 15:43:21 Uhr
Hundefutter Offline
ZFX'ler


Registriert seit:
03.10.2006

Nordrhein-Westfalen
Re: Rendern in einer 2d-Engine: VorgehensweiseNach oben.
Hallo. Ich hätte nochmal eine Frage zu dem Begriff "Submodul". Zum Beispiel sagst du
Zitat:
Ein Submodul "Spieldarstellung" zeigt dann einen Ausschnitt der Spielwelt an und benutzt dabei die Grafikklassen von oben.

Zitat:
von dem Submodul "Eingabe" Maus- und Tastaturereignisse abfragen und verarbeiten

Wie ist so ein "Submodul" abzubilden?




-------------------------------------------------
Update:
-------------------------------------------------

Hier mal ein erster Entwurf des Designs:
http://www.sebastian-surmund.de/public/Engine-Design.png

Was meint ihr dazu?

MfG
Hundefutter

2 Mal gendert, zuletzt am 04.03.2009, 23:29:49 Uhr von Hundefutter.
04.03.2009, 18:14:56 Uhr
Schrompf Offline
ZFX'ler


Registriert seit:
04.04.2006

Sachsen
Re: Rendern in einer 2d-Engine: VorgehensweiseNach oben.
Zitat von Hundefutter:
Ha
Wie ist so ein "Submodul" abzubilden?


Mit "Submodul" meine ich einfach ein Konstrukt, das einen bestimmen Zweck erfüllt. Das ist meist eine einzelne Klasse, gelegentlich ein Set aus Klassen.



Zitat:

Hier mal ein erster Entwurf des Designs:
http://www.sebastian-surmund.de/public/Engine-Design.png


Hmm... was ist die Aussage dieses Designs? Jeder redet mit jedem? Eher nicht. Jedes Modul hat seine eigene Schnittstelle. Und das Design kommt an der Stelle zum Tragen, wo Du als Programmierer bestimmst, welchen Job jedes Modul hat und auf welche anderen Module sie dafür zurückgreifen müssen. Dein Bild ist in der Hinsicht zu schlicht, um wirklich eine diesbezügliche Aussage zu enthalten. Außer vielleicht dass die Debugausgaben wohl kaum Sound brauchen. Und dass die GUI wahrscheinlich Informationen aus der Spielwelt ziehen wollen wird. Wobei das schon wieder eine Abhängigkeit ist, die man evtl. nicht durch ein Rudel Getter regeln sollte, sondern vielleicht in ein GameState-Objekt verpacken sollte. Das ist dann Detailarbeit, das siehst Du dann beim Schreiben.

Das ist übrigens auch meine Empfehlung an Dich: fang an, den Kram zu implementieren. Du siehst dann ganz automatisch, wo es hakt, wer auf wen eigentlich Zugriff bräuchte und warum es eine miese Idee ist, jedem dieser Zugriffswünsche nachzugeben. Im Fachjargon nennt man das "Iterative Entwicklung" und hat es zu allen möglichen Modellen wie "Extreme Programming" oder "Scrum" weiterentwickelt, aber im Kern ist die Aussage jedesmal die selbe: "Wir wissen noch nicht so genau, was am Ende rauskommen soll und wie es aufgebaut sein soll... aber vom reinen Draufstarren wird's nicht besser. Also lass uns mal anfangen."

Bye, Thomas
05.03.2009, 13:08:30 Uhr
Dreamworlds Development
Hundefutter Offline
ZFX'ler


Registriert seit:
03.10.2006

Nordrhein-Westfalen
Re: Rendern in einer 2d-Engine: VorgehensweiseNach oben.
Zitat von Schrompf:
"Wir wissen noch nicht so genau, was am Ende rauskommen soll und wie es aufgebaut sein soll... aber vom reinen Draufstarren wird's nicht besser. Also lass uns mal anfangen."


Alles klar, stürze mich mal einfach rein .

Ich denke, ich habe durch deine Rückmeldungen schon eine ungefähre Vorstellung, wie es auszusehen hat und werde jetzt einfach mal versuche, es so umzusetzen. Bei Problemen kann ich mich ja dann einfach wieder melden.

MfG
Hundefutter
05.03.2009, 13:26:33 Uhr
Schrompf Offline
ZFX'ler


Registriert seit:
04.04.2006

Sachsen
Re: Rendern in einer 2d-Engine: VorgehensweiseNach oben.
Falls das als Ironie angekommen sein sollte: ich hab das durchaus ernstgemeint. Auch die Professionellen in einer Firma wissen vorher nicht zwangsweise genau, was am Ende alles drin sein soll. Die ganzen "agilen" Entwicklungsprozesse sind aus dieser Erkenntnis entstanden. Es gibt zwar gelegentlich noch in Foren Leute, die die große Planung vorab predigen, aber ich halte das für Zeitverschwendung. Wenn man keine Vorstellung davon hat, welche Funktionalität man braucht und wie man sie aufteilen sollte, ist die ganze Planung sowieso für den Arsch.
05.03.2009, 16:04:28 Uhr
Dreamworlds Development
Hundefutter Offline
ZFX'ler


Registriert seit:
03.10.2006

Nordrhein-Westfalen
Re: Rendern in einer 2d-Engine: VorgehensweiseNach oben.
Zitat von Schrompf:
Falls das als Ironie angekommen sein sollte: ich hab das durchaus ernstgemeint.


Das hatte ich auch als ernst gemeinte Aussage verstanden. Habe eben schon angefangen zu implementieren...

Zitat von Schrompf:

Auch die Professionellen in einer Firma wissen vorher nicht zwangsweise genau, was am Ende alles drin sein soll. Die ganzen "agilen" Entwicklungsprozesse sind aus dieser Erkenntnis entstanden. Es gibt zwar gelegentlich noch in Foren Leute, die die große Planung vorab predigen, aber ich halte das für Zeitverschwendung. Wenn man keine Vorstellung davon hat, welche Funktionalität man braucht und wie man sie aufteilen sollte, ist die ganze Planung sowieso für den Arsch.


Jo, denke aber, dass ein gewisses Maß an Planung da sein sollte, wie eben hier diese Diskussion im Forum. Man kann es natürlich auch an Planung übertreiben.

Naja, bin wie gesagt jetzt erstmal am implementieren.

MfG
Hundefutter
05.03.2009, 16:21:05 Uhr
Normal


ZFX Community Software, Version 0.9.1
Copyright 2002-2003 by Steffen Engel