Java Ein wenig Ünterstützung beim "Raycasten" benötigt

[CPU]

Hey Leute,

Herzlichen Glückwunsch, dass du das hinbekommen hast!

Danke! Auch wenn es erst nach dem dritten Ansatz funktioniert hat ...

Wenn du ein Tutorial dazu machst, werde ich mir das definitiv durchlesen. Mit Nacharbeiten wird es da bei mir schwerer; ich habe ein paar eigene Projekte in der Warteschlange. Meeh, der Tag hat zu wenig Stunden.

Ich muss selber mal sehen, dass ich dafür die Zeit finde, denke aber, dass es machbar sein sollte (wenn auch nicht heute oder morgen)!

Das mit den Linien hängt damit zusammen, dass du eine begrenzte Anzahl Strahlen losschickst. Es sind nicht genug, um jeden Winkel einer Fläche oder einer Wand beliebig genau abzutasten. Also entweder lässt du es so, oder du wirfst mehr Strahlen raus (zB in Halbgradschritten).

Ich denke, dass das Ergebnis relativ genau ist und genau genug für diesen Spieltypus.

In deinem Code hat sich wieder viel getan. Die ganzen kleinen Methoden hast du eliminiert und Codeabschnitte hast du mit einem Kommentar versehen. Es ist doch so gleich viel übersichtlicher.

Naja, übersichtlich ist der Code ja noch nicht, weil zu einem großen Teil noch viel Debug-Kram mit drin ist.

Was ich aber noch anmerken möchte:
- Es zählt als Best Practice, wenn man globale und lokale Variable an den Anfang der Klasse und Methode setzt. So hat man einen zentralen Ort. Bei dir sind sie im Moment noch gerne in der Gegend verteilt, weswegen andere Leute etwas länger nach der Deklaration suchen.
Ob man das so machen will, ist eine reine Stilfrage.

Oh, sorry. Ich sehe das ganze hier als eine "Demo" und nicht ein richtiges Spiel oder Programm. Ich habe jetzt den Algorithmus implementiert und er funktioniert und dann kann ich jetzt mich ransetzten und mir ein Klassengerüst erdenken, worein ich dann später den Algorithmus kopieren werde.

Ich habe aber festgestellt, dass es für mich einfacher ist bei der Entwicklung von solchen Algorithmen sich hauptsächlich um die Funktion zu kümmern, als um die Struktur des Quellcodes. Das und die Optimierung können dann später folgen ...

Daher ist auch z.B. die Tastaturgeschichte nur so rudimentär implementiert und ich mische auch heavyweight und lightweight Komponenten ...

- Da der Code nun funktioniert, und sich am Algorithmus nicht mehr wesentlich etwas verändern wird, wird es langsam Zeit für Doc Comments.

Klar!

- Die Sichtbarkeiten sind etwas komisch gesetzt. Es ist ein buntes Durcheinander von public, protected, private und package. Da solltest du noch einmal drüber gehen.

Siehe Grund oben!

Nun noch zwei Fragen, zu denen ich auch ein Paar Denkanstöße gebrauchen könnte:

* Ein "Stripe" zeichnet sich also durch eine Höhe und einer Position von oben aus und ist einen Pixel breit. Wenn man sich jetzt im Raum dreht und z.B. sich eine Wand (z.B. 6|3) anschaut hat die eine Dicke. Wo kann ich steuern, wie dick die Wand ist? Und wie bekomme ich jetzt meine Textur auf die Wand? D.h. technisch ist mir das schon klar, ich meine aber wie ich immer den richtigen Pixel-Streifen finde, sodass am Ende auch die ganze Textur lückenlos/sprunglos dargestellt wird? (War das verständlich?)

* Wie sorge ich für mehr "Differenzierung" in der Ansicht? D.h. die Wände und Co. werden ja korrekt gerendert. Aber das Auge vermischt eben die Ecken, wo zwei gleichfarbige Wände orthogonal aufeinander stehen. Wie kann ich z.B. alle südlichen oder nördlichen Wände dunkler einfärben. Also feststellen, ob es sich bei dem aktuellen Ray um ein nördliches oder südliches handelt?

Jetzt muss ich mich nur noch um das ordentliche Rendering kümmern und eine kleine Storyline entwickeln ... da bin ich ja FAST schon fertig!

Beste Grüße & Danke für die Unterstützung,
Gruß,
CPU

 

[PanzerHase]

Mmmm ... warum komme ich nicht umhin, in

Zitat von qwertzuio
Du bist ein ganz schlauer Fuchs Herr CPU.

Ironie zu sehen?

Fräulein CPU?

 

[CPU]

Fräulein CPU?

Wie habe ich das denn zu verstehen?

 

[PanzerHase]

Weil es doch die Central Processing Unit heißt, das meintest du doch mit Ironie zu sehen oder?

 

[CPU]

Hallo,

für alle, die es zukünfig noch interessiert: ich habe ein bisschen Performance-Tunig gemacht und bin von 7 Milisekunden für 320 Rays auf rund 0,7 Milisekunden für 320 Rays gekommen. Und das ist ja nur ein Zehntel der Zeit!

Was habe ich gemacht? Ich habe:
* eine Abbruchbedingung in die Schleife gefügt: Abbruch sobald horizontal und vertikal ein Treffer gefunden wurde
* Komplet auf das Bogenmaß umgestiegen - auch wenn das etwas ungenauer ist
* Multiples Math.sqrt() und Math.pow() entfernt und am Ende nur einmal durchgeführt

Achso: auch wenn ich von Tabellen für Sinus und Cosinus gesprochen habe, waren die doch nur "kontraproduktiv" und der Math.sin()-Aufruf ist außerdem bei mir auch sehr schnell (ca. 250 ns und aus dem Array lesen 150 ns).

Vielleicht interessiert es ja noch jemanden

Gruß,
CPU

 

[Krik]

Inwiefern waren die Tabellen kontraproduktiv? Zum umständlich zu handhaben?
Ich mein', der Arrayzugriff ist laut deiner Messung 66% schneller als Math.sin().

Fang nicht auf halben Wege, die Optimierung fallen zu lassen. ^^

 

[CPU]

Hallo,

Inwiefern waren die Tabellen kontraproduktiv? Zum umständlich zu handhaben?
Ich mein', der Arrayzugriff ist laut deiner Messung 66% schneller als Math.sin().

genau, es ist sehr umständlich handzuhaben - zumindest empfinde ich das so. Natürlich kann man das irgendwie hinbekommen und ist dann sogar noch etwas schneller.

Wenn ich aber "Math.sin()" verwenden kann und insgesamt noch ein sehr akzeptables Ergebnis erziele (und das sind doch 0.7 Sekunden für 320 Rays, oder?), warum soll ich dann noch solche Umstände machen. Das ist doch so in Ordnung.

Fang nicht auf halben Wege, die Optimierung fallen zu lassen. ^^

Das ist immer die Frage: wo fängt man an, wo hört man auf. Ich versuche immer so zu optimieren, dass der Code trotzdem noch gut lesbar bleibt (d.h. dass man später sich wieder einfach einlesen kann).

Gruß,
CPU

 

[Krik]

Nachvollziehen kann ich es nicht so wirklich.
Ich mein, man lässt ein Array generieren, dass zB beim diesem Aufruf Sinus[90] halt den Sinuswert zurück gibt. So besonders aufwändig ist das eigentlich nicht.


Es stimmt, die Frage ist, wie weit man die Optimierung treiben will. Ich glaube, ich hätte es versucht noch weiter zu optimieren, weil ich so was einfach interessant finde. Siehe zB meinen Thread hier.


Ob 0,7 Millisekunden für 320 Rays gut oder schlecht sind, kann ich nicht so direkt beantworten. Ich glaube, es ist eher ein schlechter Wert, der vor allem durch die Verwendung von Java kommt. Aber das verfügbare Potential hast du, denke ich, ganz gut ausgeschöpft.


Bitte lass uns später wissen, wie du das Programm weiterentwickelt hast.

 

[CPU]

Hallo,

Nachvollziehen kann ich es nicht so wirklich.
Ich mein, man lässt ein Array generieren, dass zB beim diesem Aufruf Sinus[90] halt den Sinuswert zurück gibt. So besonders aufwändig ist das eigentlich nicht.

das stimmt. Aber was ist mit dem Winkel 39,9375°, der durchaus vorkommen kann (denn man hat ja 60/320 "Winkelstückchen")? Und außerdem arbeitet ja alles im Bogenmaß. Da ist das ja dann eine Nachkommastellenschlacht!

Irgendwie sind meine zwei wichtigen Fragen von oben verloren gegangen:

Ein "Stripe" zeichnet sich also durch eine Höhe und einer Position von oben aus und ist einen Pixel breit. Wenn man sich jetzt im Raum dreht und z.B. sich eine Wand (z.B. 6|3) anschaut hat die eine Dicke. Wo kann ich steuern, wie dick die Wand ist? Und wie bekomme ich jetzt meine Textur auf die Wand? D.h. technisch ist mir das schon klar, ich meine aber wie ich immer den richtigen Pixel-Streifen finde, sodass am Ende auch die ganze Textur lückenlos/sprunglos dargestellt wird? (War das verständlich?)

Gruß,
CPU

EDIT: Eigentlich geht es bei den Texturen ja nur darum, die Position des richtigen Pixelstreifens in der Textur zu finden, oder?

EDIT II: Nun ich habe mal schnell etwas gestrickt (siehe Bild im Anhang). Auf den ersten Blick sieht es ganz passabel aus, ist es aber nicht. Denn ich habe einfach eineb globalen Counter eingeführt, der immer hochzählt und dessen Wert dann modulo Texturbreite genommen wird. Aber das ist ja Schrott, denn so wandern beim drehen die Texturen mit!

 

[Krik]

Beim Winkel würde ich eiskalt die Nachkommastellen abschneiden, ohne noch extra zu runden. Ein Cast zu Int reicht dazu schon. Oder eben das Array vergrößern, dass zB 39,375° Sinus[393] entspricht. Also Winkel mal 10 und dann ein Int-Cast.
Dabei geht natürlich einiges an Genauigkeit verloren. Man müsste schauen, wie viele Werte in dem Array Sinn ergeben.


Zu den anderen Fragen:
Die Dicke der Wand hängt davon ab, aus wie vielen Klötzen du sie zusammensetzt. Im Moment hast du eigentlich eine mikroskopische Welt, die um den Faktor 15 vergrößert dargestellt wird. Wenn du den Faktor auf 1 setzt, dann muss die Wand 15 Einheiten lang sein, damit sie der Länge der alten Wand entspricht.

Das mit der Textur wird ein klein wenig kompliziert. Du brauchst die Eckkoordinaten der Würfel. Damit spannst du ein Trapez auf. Und jetzt hast du zwei Möglichkeiten:
1) Du nimmst eine quadratische Textur und verzerrst sie so, dass sie dem Trapez entspricht und pappst sie auf die sichtbare Anzeige. Ich weiß jetzt aber nicht, ob Java dafür passende Methoden mitbringt.
2) Wenn 1) nicht geht, bastelst du dir die Transformation selber. Du nimmst von der 3D-Ansicht die Höhe der senkrechten Linien und teilst die Textur ebenfalls in senkrechte Linien auf. Anschließend passt du die Länge der Texturlinien auf die Linien der 3D-Abbildung an und kannst sie dann anzeigen lassen.*

Das wird allerdings alles ziemlich rechenintensiv, insbesondere wenn die Textur eine größere Auflösung hat.


*Pseudo Code
Für alle senkrechten Linien in der Textur
- Speichere die Linie in einem Array

Für alle sichtbaren Wände
- Ermittle die Koordinaten der Ecken und damit das Trapez
- Für alle senkrechten und (teilweise) sichtbaren Linien im Trapez
- - Ermittle die Koordinaten und Länge der Linien
- - Passe die dazugehörende Linie aus dem Bildarray darauf an
- - und stelle sie dar


So in etwa. Da sollte es aber auch andere Ansatzpunkte geben, die eventuell schneller sind.

 

[CPU]

Hallo,

Die Dicke der Wand hängt davon ab, aus wie vielen Klötzen du sie zusammensetzt. Im Moment hast du eigentlich eine mikroskopische Welt, die um den Faktor 15 vergrößert dargestellt wird. Wenn du den Faktor auf 1 setzt, dann muss die Wand 15 Einheiten lang sein, damit sie der Länge der alten Wand entspricht.

Du meinst, "15" wegen dem Skalierungsfaktor? Wenn ich den herunter setze bleibt die absolute "Dicke" einer Wand in der Pseudo-3D-Ansicht gleich. Es gibt ja noch ein Wikibook zu Raycasting und eben jenes Tutorial von Permadi [1], wo immer von ominösen 64 Pixeln für die Breite x Höhe x Tiefe eines Quaders gesprochen wird. Aber die tauchen nirgendwo auf.

2) Wenn 1) nicht geht, bastelst du dir die Transformation selber. Du nimmst von der 3D-Ansicht die Höhe der senkrechten Linien und teilst die Textur ebenfalls in senkrechte Linien auf. Anschließend passt du die Länge der Texturlinien auf die Linien der 3D-Abbildung an und kannst sie dann anzeigen lassen.*

Das ist entsprechender Ansatz. Aber ich glaube, Du hast mich noch nicht ganz verstanden: ich habe eine Textur z.B. 64x64 Pixel. Daraus ergeben sich 64 Texturstreifen für diese Textur. Nun soll ein Quader eben die Breite & Tiefe 64 Pixel haben, so dass also die Textur genau einmal drauf passt. Und jetzt muss ich ja für jeden Strahl bestimmen, an welcher Position er auftrifft, damit ich den n-ten Streifen für diesen Strahl auswählen kann!

Und ich habe im Moment keine Idee, wie ich auf diesen n-ten Streifen komme, weil ich auch noch nicht weiß, wo die Dicke der Felder festgelegt ist.

Gruß,
CPU

Ergänzung (23. August 2012)

Hallo Leute,

und wieder: wenn man sich mal ruhig hin setzt und überlegt kommt man auf die Lösung! Ich habe meine beiden Probleme gelöst.

Nun, ein solcher Block hat die "Dicke" 1 und die Berechnung mit diesen Blöcken findet dann in dem Intervall ]0,1[ statt. Nun kann man abstrakt hin gehen und sagen, dass 1 kongruent 64 ist und man an nimmt (***), dass ein Block eben 64 Pixel breit, dick und hoch ist. Und dann macht man nur noch folgendes: man prüft, ob ein Strahl eine vertikale oder horizontale Seite getroffen hat und bestimmt dann den Offset auf diesem Block. Also für x (horizontal) beispielsweise:

double offset = x-Math.floor(x); // mit x der orginalen double-Koordinate des Treffers

Und diesen Offset multipliziert man also mit 64 - der angenommenen Breite. Da der Offset nun zwischen ]0,1[ liegt ist das also ein prozentualer Wert, der genau angibt wie viel "Prozent weit" (sehr unschöne Formulierung) man den Block vom Beginn an mit dem Strahl getroffen hat. Und mit 64 multipliziert und dann noch gerundet bekommt man eine Pixel-Anfgabe im Bereich [0,64[, die dann genau den Wert angibt, welchen Pixelstreifen wir aus der Textur nehmen müssen.

Und mit:

Image img = texturen[(stripe[i].wandIndex-1)*64+stripe[i].wandOrt];
g.drawImage(img, xo+i, yo+stripe[i].top, 1, stripe[i].height, null);

kann aus den vorbereiteten Streifen-Texturen der Streifen äußerst Performant - im Gegensatz zu

g.drawImage(img.getScaledInstance(1, stripe[i].height, Image.SCALE_FAST), ...);

- auf die Bildfläche gezeichnet werden! Zwar ist diese Methode etwas ungenau, da z.B. niemals der 64. Streifen erwischt wird - aber genau genug für diesen Zweck. Und wo bliebe sonst das 80er-Feeling?

Super!

Da wäre nur noch eine kleine Ungereimtheit: an der Stelle (***) habe ich ja - wie ich finde einen ganz plausiblen Grund dargelegt. Aber: die eigentliche Breite in der Pseudo-3D-Ansicht wird ja doch von den Rays bestimmt, oder? Angenommen ich sende 320 über den gesamten Bildbereich aus und stehe vor einer Wand, die 50% einnimmt. Dann müsste doch die Wand zumindest 160 Pixel breit gezeichnet werden - weil ja 50% der Stahlen (320 Stück) auf die Wand treffen und jeder Streifen 1 Pixel breit ist. Aber müssten dann nicht Texturstreifen ausgelassen werden? Und dann müsste doch das Muster unterbrochen sein, oder? Aber ich bemerke das garnicht ... egal ... es funktioniert!

Gruß,
CPU

 

[Krik]

Schön, dass es jetzt geklappt hat.
Bekommen wir einen weiteren Screenshot zu sehen?


Dein Ungereimtheit kommt mMn dadurch, dass du die einzelnen Längeneinheiten gedanklich durcheinander wirfst.
Du hast eine Textur, die ist 64 Pixel breit. Diese wird auf eine Wand mit der Längeneinheit 1 abgebildet. Und das wird dann auf bspw. 160 Pixel auf dem Bildschirm abgebildet.
Im Grunde rechnest du also mit drei verschiedenen Koordinatensystemen und bildest sie vollständig aufeinander ab, wobei sich die Umrechnung zwischen einerseits dem Bildschirm und andererseits dem Block und der Textur laufend verändert. Die die Abbildung aufeinander entstehen keine Lücken, wenn du nicht gerade falsch rechnest.

Eigentlich ist das ein Fall für Vektorrechnung, die ist genau dafür da. ^^

 

[Airbag]

Ob 0,7 Millisekunden für 320 Rays gut oder schlecht sind, kann ich nicht so direkt beantworten. Ich glaube, es ist eher ein schlechter Wert, der vor allem durch die Verwendung von Java kommt. Aber das verfügbare Potential hast du, denke ich, ganz gut ausgeschöpft.

Ja, tendentiell ein eher schlechterer Wert. Musste für die Uni mal einen Raycaster (ging aber eher um die Paralellisierung) schreiben. Gab dazu auch einen Wettbewerb(waren aber auch komplexere Szenen, dafür hatte man aber Zugriff auf den GRIS - Cluster vom Grafikinstitut) von Nvidia gesponserten Wettbewerb , wer den schnellsten Caster schreiben kann, wo man bis zu 3 GTX480 gewinnen konnte. Man sollte aber auch sagen, dass es nicht in Java, sondern C++ geschrieben wurde und auch Inline-ASM-Code enthielt um es performanter zu machen.

 

[CPU]

Hallo,

Schön, dass es jetzt geklappt hat.
Bekommen wir einen weiteren Screenshot zu sehen?

anbei der gewünschte Screenshot - sogar in 640x400 Pixeln Auflösung ... WOW ... Außerdem werden jetzt nördliche und östliche Wände dunkler dargestellt als südliche und westliche Wände heller!

Das Holz (links) wird noch nicht ganz sauber gerendert. Wenn ich aber eine andere Textur wähle, wird es korrekt dargestellt. Scheint wohl ein Textur-Fehler zu sein. Außerdem habe ich bei den Texturen noch Rechenfehler drin (wird nicht ganz sauber ausgewählt). Aber das ist ja schnell beoben

Ich finde den Performance-Wert ganz in Ordnung und für meine Zwecke ausreichend!

Gruß,
CPU

 

[Krik]

Um die Immersion zu erhöhen, könntest du die Wände je nach Distanz dunkler einfärben. Damit gibst du dem Betrachter eine optische Referenz über die Tiefe.
Die Distanz hast du ja vorher schon bestimmt. Dazu machst du dir einfach noch zB 64 "Alpha"-Stripes, die passend über Textur-Stripe gelegt werden. Boden und Decke muss an die Abdunklung ebenfalls angepasst werden. Das sollte eigentlich noch recht einfach zu machen sein.

Ich denke, dass es dann noch besser aussieht. Je nach Stärke der Abdunklung könnte es dann aber auch wie Unterwasser aussehen. Auf diesem Bild erkennt man gut, wie der Boden in der Ferne immer dunkler wird. Es kann aber auch wie eine Taschenlampenbeleuchtung aussehen.

 

[CPU]

Hallo,

Um die Immersion zu erhöhen, könntest du die Wände je nach Distanz dunkler einfärben. Damit gibst du dem Betrachter eine optische Referenz über die Tiefe.

das ist sogar noch einfacher als der Nord/Ost-Trick und wahrscheinlich auch noch wirkungsvoller. Aber ab welcher Entfernung soll abgedunkelt werden?

Ich habe noch eine Frage, wozu ich einen kleinen Denkanstoß gebrauchen könnte: Decke und Boden mit Texturen versehen. Ist das arg schwierig oder kann man das relativ schnell/einfach realisieren? Die Erklärung im Tutorial [1] finde ich nicht so aufschlussreich ...

Gruß,
CPU

 

[Krik]

Ab wann? Hm, gute Frage. Da wirst du wohl experimentieren müssen. Wie wäre es für den Anfang mit 1 Längeneinheit pro Abdunklungsstufe? Falls da der Effekt nicht gut herauskommt (auf deinem Screenshot oben würde man dann nur 5-6 Stufen sehen), wäre eine kleinere Zahl besser. Bei 64 Stufen und ein 0.2 Längeneinheiten pro Stufe, kannst du eine Distanz von knapp 13 Längeneinheiten verschieden stark abdunkeln. Das klingt auch nach keinem schlechten Wert.



Decke/Boden

* Start from the bottom of the wall slice.
1. Take the pixel.
2. Draw a line (a ray) from the pixel to the viewers eye.
3. Extends the line so that it intersect the floor.
4. The point where the line "intersect" the floor is the point on the texture map that is being hit by the ray.
5. Take the pixel value of that point on the texture map (see the next figure to see how this can be done) and draw it on the screen.
* Repeat 1-5 until the bottom of the screen is reached.

Das wäre die Variante mit Rays aus dem Tutorial.

Im Grunde ist das doch auch nicht anders als stünde der Spieler in einem 1 Block breiten und x Blöcke langen Gang - nur eben um 90° gedreht.

 

[CPU]

Hallo,

@Schatten: Danke für den "Anstoß", das werde ich sicherlich so machen.

@Boden: So wie im angehangenen Bild ist das ja falsch: ich habe einfach von der unteren Ecke jedes Streifens eine Linie zum unteren Ende der Projektionsfläche gezogen (gestreift s/w, damit man es besser erkennen kann).

Irgendwie habe ich da noch nicht Verstanden, wie das realisiert werden soll. Könntest Du (oder jemand anderes) kurz nochmal die Idee umreißen?

Viele Grüße,
CPU

EDIT: Mit dem Fluchtpunkt kommt man auch nicht vorwärts ...

 

[Krik]

Das Bild ist richtig. Das ist ein Fächer von Strahlen, die einen gemeinsamen(!) Ursprung haben (den Spieler) und durch die Darstellung auf dem Bildschirm parallel abgebildet werden. Das ist ja auch logisch, weil die Darstellung einen 90° (?) Blickwinkel in der Breite darstellt. Der untere Rand markiert die Position des Spielers auf dem Boden. Im Grunde hast du eine verzerrte Geometrie, weswegen auch kein Fischaugeneffekt zustande kommt. Edit: Dein zweiter Screenshot zeigt den umgekehrten Fischaugeneffekt.

Genauso ist es aber auch mit der Senkrechten. Du hast einen 90° (?) Blinkwinkel in der Höhe. Du musst nur deinen vorhandenen Code nehmen und ihn so ändern, dass er die Höhe und Distanz zum Objekt statt Länge und Breite verarbeitet.

Ich habe das mal fix in eine kleinen Grafik aufgezeichnet. Das Rechenprinzip bleibt das gleiche, nur dass du den Strahlenfächer nun senkrecht statt waagerecht werfen musst.

 

[CPU]

Hallo,

Danke für Deine Antwort, e-Laurin!

Das Bild ist richtig. Das ist ein Fächer von Strahlen, die einen gemeinsamen(!) Ursprung haben (den Spieler) und durch die Darstellung auf dem Bildschirm parallel abgebildet werden. Das ist ja auch logisch, weil die Darstellung einen 90° (?) Blickwinkel in der Breite darstellt.

Also das Blickfeld des Spielers beträgt 60° (von Blickwinkel-30° bis Blickwinkel+30°).

Sorry. Aber ich habe das immer noch nicht ganz verstanden.

Aber müsste nicht so gehen: in der 2D-Kartenansicht stellt jedes Quadrat - das keine Wand ist - eine Bodenfliese dar. Nun wenn man einem Strahl folgt, kann man aus jeder Fliese dann entsprechendes Bodenstück ausschneiden und einfach auf der Zeichenfläche darunter malen. Ginge das nicht so. Siehe auch Bild im Anhang?

Gruß,
CPU