Geschwindigkeit bei heightmapähnlicher Karte

Janko

Okay ich habe ein Spiel programmiert, was aber ziemlich langsam ist.
Wie kann ich hier die Geschwindigkeit erhöhen?

man stelle sich eine Heightmap vor...
d.h. Die Landschaft besteht aus miteinander verbundenen Feldern/Vierecken, welche wiederum in jeweils 2 Dreiecken zerlegt sind.
Eine Ecke eines beliebigen Feldes hat demnach die
Koordinaten = int_nx, float_y, int_mz.
Die Felder können entweder 0% oder 100% transparent sein.

Diese sogenannte Heightmap/Landschaft/Ebene existiert jedoch nicht einmal sondern mehrmals und zwar übereinander!
d.h. man hat mehrere Ebenen(bis zu die sich jedoch nie überschneiden, sondern maximal berühren, so das die Spielfigur von einer Ebene auf eine andere gehen kann.
Zwischen 2 Ebenen sind (auf den der Feldergrenzen) Wände entlang der x und z Achse und einer Diagonalen möglich.

Ein einzelnes Feld einer Ebene sieht nun so aus

struct Sfeld
{
float hoehe; // linke obere Ecke des Feldes. Die anderen Ecken sind in der Nebenfeldern gespeichert
int typ1;    // Texturindex des ersten Dreiecks des Feldes. 0=unsichtbar
int typ2;
int Wand_x;  // Texturindex der Wand von 0/0 zu 1/0 
int Wand_z;  // Texturindex der Wand von 0/0 zu 0/1
int Wand_xz; // Texturindex der Wand von 0/0 zu 1/1
bool isVisible; // Ist das Feld(typ1/2,Wand_x/z/xz) von der Mitte des Feldes aus sichtbar?
};

gezeichnet wird dann ungefähr so.

loop durch alle Felder
  if (!Feld.typ1 bzw. typ2) // wenn das Dreieck des Feldes nicht vorhanden/unsichtbar ist.
   continue;
  if (Feld_innerhalb_des_Sichtpyramidenstumpfes(Feld))
   continue;
  if (/*Ist die Seite von Feld.typ1/typ2 zu sehen*/)    // backface culling durch die Eigenschaft Feld.isVisible bestimmbar
   continue;
  Zeichne();
//genau das gleiche wird dann mit den Wänden gemacht

Und jetzt frage mich wie man am besten die Spielgeschwindigkeit erhöhen kann.
Ich benutze OpenGL und habe eine Riva TNT2 und einen 400Mhz Prozessor.
Meine Verbesserungen waren bis jetzt
Mipmap, Sichtweitenbegrenzung auf 16 Felder, backfaceculling.

habt ihr noch Ideen?
Dadurch das eine sehr simple Strukturierung der Karte gewählt wurde, sollte es einfach sein z.B. einen besseren Zeichenvorgang zu wählen. Bei mir wird ja z.B. langwierig einfach jedes Feld einzeln überprüft. Was wäre hier das beste?

[Nachtrag]
Ich weiß übrigens nicht ob mein Rechner oder meine Grafikkarte das ist die sich langweilt, oder keine von beiden.
Wenn ich z.B. eine 32x*32z*8y Karte spiele und mich ganz an den Rand der Karte stelle, also so dass kein Polygon zu sehen ist, beträgt die Framezahl ungefähr 30 pro Sekunde.
Bei einer 8x*8z*8y sind es ungefähr 58.
Hierraus ist zu entnehmen, dass sich die Grafikkarte langweilt weil der Prozessor zu langsam ist.
Schaut man jedoch von der einen Ecke der Karte zur anderen beträgt die Framezahl
statt 30 nur noch 10
und statt 58 nur noch 50
wodurch man denken könnte das die Grafikkarte zu langsam ist.

[ Dieser Beitrag wurde am 26.01.2003 um 11:20 Uhr von Janko editiert. ]

Headhunter

Hi !

Normalerweise arbeitet man bei Landschaftsengines mit Quadtrees, so kann man schnell große Teile der Landschaft verwerfen, wenn sie nicht gezeichnet werden müssen.
Dann kannst du noch einen Level Of Detail Algorithmus implementieren. So werden weit entfernte Bereiche mit sehr wenigen Verticen gezeichnet, während die Gegend vor dir sehr detailliert ist. Besonders bei großen Landschaften wie sie bei dir wohl vorliegen kann man die Performance *enorm* steigern.

Jester

Noch ne Idee:

Dadurch, daß Deine Ebenen sich nicht schneiden genpgt es zu prüfen, ob die Eckpunkte einer Fläche sichtbar sind und nur dann zu zeichnen, wenn einer davon sichtbar ist. Vielleicht hilft das was.

Janko

arbeitet man bei Landschaftsengines
Hätte ich vielleicht sagen sollen.
Meine Karten sind selten simple Landschaften sondern eher Gebäude, Brücken, Klippen.

Jetzt lacht vielleicht jemand, weil ich Häuser, Kisten, Tunnel etc mit übereinandergelegt Heigtmaps mache, die die Eigenschaften haben an einigen Stellen unsichtbar zu sein und mit Wänden verbunden sein können, aber mit dem Karteneditor schafft man so sehr schnell gute Karten

Dann kannst du noch einen Level Of Detail Algorithmus implementieren.

Meine Karten haben normalerweise die Größe:Breite, Höhe=16,16 Felder
(Die Spielfigur ist 1/4 bis 1/2 Feld groß und überquert in 4-8 Sekunden die Karte.Das ist wirklich nicht viel.)
Wenn ich doch einen LOD Algorythmus einbauen sollte würde das bei der Größe nicht viel bringen.
Außerdem ist das bei Wänden nicht möglich

Quadtrees
War das die mehrmalige Zerlegung in jeweils 4 Teile der Karte
Falls ja schau ich mal was da zu machen ist.

Okay danke erstmal gibts noch andere Vorschläge.
Ich suche z.Z. einen Zeichenalgorythmus bei dem man von der Sichtpyramide aus die einzelnen Felder zeichnet, statt bei jedem einzelnen Feld zu überprüfen, ob es in der Sichtpyramide ist.

DasPinsch

Du kannst das Programm ja vielleicht mal uppen, dann können wir ja auch mal gucken wie langsam/schnell es ist...

DasPinsch

Janko

Du kannst das Programm ja vielleicht mal uppen, dann können wir ja auch mal gucken wie >langsam/schnell es ist...

Hmm das wäre nicht so ratsam, weil:
-Erstmal ist das kein kleines Programm, sondern bereits ein voll funktionierendes Spiel. Der Code könnte demnach etwas unübersichtlich sein.
-Die ersten Zeilen des Codes sind 1,5 Jahre alt. Der Code wurde dann in regelmäßiger Unregelmäßigkeit erweitert und verbessert. Damals hatte ich z.B. noch keine Ahnung von struct, class,... ein weiterer Grund warum nur ich den Code lesen kann, auch wenn er inzwischen lesbarer aussieht.
-Der letzte upload war am 20.11.02. Der Quellcode bezüglich des Zeichnens hat sich schon sehr geändert. Außerdem gibt es da noch keinen Framezähler. Oder um es in anderen Worten zu sagen: Das Spiel möchte ich euch so eigentlich nicht zeigen, weil meine noch nicht nichtupgedatete Version mir viel besser gefällt.

Aber damit ihr eine Vorstellung habt, wie ich das meine mit übereinanderliegenden Heightmaps, schaut euch mal die Screenshots dazu an.
vielleicht erkennt ihr es ungefähr. http://mitglied.lycos.de/jankosgames/Programme/UnrealShooter/screens.htm

So und falls tatsächlich doch jemand sich den Code anschauen will. http://mitglied.lycos.de/jankosgames/Programme/UnrealShooter/index.htm

Ich werde das nächste update nach den Winterferien herausbringen. Bis dahin hoffe ich das Programm netzwerkfähig gemacht zu haben.
Denn das Spiel ist ein Egoshooter, für zur Zeit max. 4 Spieler.
d.h. Splitscreen.
(Ja richtig gehört einen Egoshooter mit Splitscreen wo 4 Spieler an einer Tastatur kleben)
Bei einem Spieler stören 30 Fps nicht aber wenn man das zu 4 spielt sind es ungefähr 7.

[Nachtrag]
Mit dem Satz
"Die ersten Zeilen des Codes sind 1,5 Jahre alt"
will ich noch ergänzen, dass man, wenn man mit c++ anfängt, nicht mit etwas kleinem wie tetris anfangen muß, wie das einige meinen. Es geht auch anders, denn das war der Anfang meines aller ersten C++ Programms. (Ich habe danach immer als ich mal Lust hatte dann daran weitergearbeitet).

Janko

Is ja lol.
Je mehr man um das Problem herumredet, desto weniger Antworten erhält man.

Okay deshalb: werft mir halt meinetwegen irgendwelche Stichwörter oder OpenGL Befehle an den Kopf, unter denen ich mich informieren könnte um die Framezahl bei meinem Spiel zu erhöhen.

Ansonsten wäre es gut wenn einer eine Idee hat, wie man bei einer Heightmap (mehr oder weniger besteht ja mein Spiel aus so was) einen Schleifenalgorythmus aufschreiben könnte. Denn bei jedem heutigen guten Spiel mit Heightmap, werden von vornherein auch nicht alle Felder überprüft, die sich z.B. hinter einem befinden.

@ Jester:
Dein Vorschlag hört sich zwar zuerst gut und richtig an, würde aber zu lange dauern.
Weil 1. Meine Heightmaps ja Höhen und Tiefen haben, so dass ich wirklich alle Felder die diese Linie (Vom Spieler zum einem Eckpunkt des Feldes) kreuzen könnten überprüfen muß. und 2. weil, diese Linien auch durch Ebenen durchgehen könnten ohne von ihr verdeckt zu werden, da die Ebenen an einigen Stellen ja unsichtbar sind.

[ Dieser Beitrag wurde am 29.01.2003 um 17:15 Uhr von Janko editiert. ]

TGGC

Kenn dein Code nicht, aber du solltest erstmal:

Den Level in Teile zerlegen, bei denen alle Vertexe aus diesem Teil circa 16-64k benötigen.
Diese Vertexe in statische Buffer packen.
BoundigVolumes um diese Teile legen.
Diese in eine Tree einordnen.
Den Tree gegen das view frustrum cullen.
Alle sichtbaren Teile zeichnen und dabei möglichst wenig Renderstatewechsel haben.

Bye, TGGC