Raycaster und Prozessoptimierung

Übersicht BlitzMax, BlitzMax NG Beginners-Corner

Neue Antwort erstellen

Skabus

Betreff: Raycaster und Prozessoptimierung

BeitragMi, Dez 02, 2009 15:10
Antworten mit Zitat
Benutzer-Profile anzeigen
Hallo!

Ich habe mich, angeregt durch Noobody, einige Zeit
mit einem Raycaster beschäftigt, da ich in der Uni
gerade ähnliche Themen habe und ich schon seit
geraumer Zeit eine Idee für ein Spielremake im Kopf
habe, habe ich mich an die Aufgabe gesetzt einen
Raycaster zu schreiben.

Bissher bin ich bereits recht zufrieden mit meinen Ergebnissen, habe allerdings momentan ein Problem, an dem ich mir(inklusive
mehreren Info-Studenten und nem Mathestudent) die Zähne
ausbeiße...

Zunächst einmal könnt ihr die Release-Version hier laden:

https://www.blitzforum.de/upload/file.php?id=7535

Und hier noch ein unspektakulärer Screenie:

user posted image

Leider ist das Ganze extrem langsam, da ich eine höchst unoptimierte Art implementiert habe den Strahl zu konstruieren.
Ich nutze die einfache Beziehung zum Polarkoodinatensystem,
dass eine Linie des Winkels a mit dem sin a und dem cos a Steigungsdreiecke bildet.

Das resultierende Problem ist allerdings, dass ich dann für jedes
zu betrachtende Feld auf meiner 2D-Karte jeden einzelnen Punkt
auf dem Feld überprüfe.Bei einer Feldgröße von 64*64 Einheiten
würde er im besten Fall 64 Punkte prüfen, im Falle von Genauigkeitskorrekturen sogar noch mehr.
Was allerdings nicht notwendig ist, wie ich in diversen Quellen
gelesen habe.

Überall, sei es in meinem Raycasting-Buch, vertex Raycaster-Code,
oder sonstigen Internettutrorials steht überall dass ich die
Beziehung des tangens nutzen kann um meinen Code zu optimieren.

Leider habe ich in den letzten Wochen selbst mit Hilfe mehrerer Studenten keine Lösung gefunden, warum mein aktueller
Code mir nur Quark ausgibt.Wie mein aktuelles Ergebnis aussieht seht ihr hier:

user posted image

Mein Code sieht so aus:


Hier die Funktion die die Höheninformationen für den Rendering-Prozess ermittelt:

BlitzMax: [AUSKLAPPEN]


'ermittelt die Spalteninformationen die zum Zeichnen der Szenen benötigt werden
Method getSceneRows()

'lokale Variablen
Local x:Int
Local d:Int
Local addAngle:Float 'zeigt an wie viele zum Winkel hinzugefügt werden muss
Local curAngle:Float 'zeigt den aktuell zu betrachtenden Winkel an
Local curDis:Float
Local curHigh:Float
Local totalAngle:Float
Local tempX:Float = playerX
Local tempY:Float = playerY
Local diffX:Float = 0.0
Local diffY:Float = 0.0
Local dis:Float
Local dX:Float
Local dY:Float


'es wird ermittelt wie breit der Winkel eines Strahls ist
addAngle = Self.FOV / Self.screenX

'der Startwert Spaltenwinkel wird berechnet
curAngle = Self.POV + (Self.FOV/2)

'zur Erstellung der Szene müssen soviele Strahlen gesendet werden
'wie die Projektionsebene(Auflösung) Spalten(X-Wert) hat, Standard: 640
For x=0 To screenX-1

getDisDiagH(Self.playerX,Self.playerY,curAngle,x)

'der Spaltenwinkel des nächsten Strahls wird ermittelt
curAngle:-addAngle

Next

End Method


'Methode zur Berechnung des Pythagoras
Method pyth:Float(a:Int,b:Int)
Return Sqr(a*a+b*b)
End Method


'diese Methode wird aufgerufen wenn der Bildschirm aktualisiert werden muss
Method renderScenePerLines()

'lokale Variablen
Local x:Int = 0
Local y:Int = 0
Local y0:Int = 0
Local y1:Int = 0
Local curHigh:Int = 0
Local curDis:Int = 0
Local s:Int = 0
Local pixMapArray:Byte Ptr
Local red:Byte = 255
Local blue:Byte = 255
Local green:Byte = 255
Local alpha:Byte = 255


'die benötigten Spalteninformationen werden ermittelt
getSceneRows()


'nun wird jede Spalte auf dem Bildschirm angezeigt
For x=0 To screenX-1

'die aktuelle Höhe wird übermittelt
curHigh = Int(sceneRows[x,0])

'die genaue Position der Spalte wird berechnet
y0 = (Self.playerViewPoint - curHigh) / 2
y1 = y0 + curHigh

'die Länge der Linie für das Bodensegment wird ermittelt
curDis = (screenY - y1)+5

'die Farbe der Wand wird ermittelt
If(sceneRows[x,1] = 1) Then

SetColor (255,0,0)

ElseIf(sceneRows[x,1] = 2) Then

SetColor (0,255,0)

ElseIf(sceneRows[x,1] = 3) Then

SetColor (0,0,255)

EndIf

'die Spalte wird angezeigt
DrawLine x,y0,x,y1

'sollte die Distanz kleiner sein als der Rest des Bildschirmauschnittes
'wird die Größe angepasst


'danach wird das Bodensegment gezeichnet
SetColor(255,255,0)
DrawLine x,y1,x,y1+curDis

Next

'die Farbeinstellung wird zurückgesetzt
SetColor(255,255,255)

End Method


Und hier jetzt die "optimierte" Unterfunktion, die den Fehler
verurrsacht:

BlitzMax: [AUSKLAPPEN]



'berechnet die Distanz zwischen Spielerposition und einer Wand
'unter Nutzung der horizontalen Schnittpunkte
Method getDisDiagH:Int(px:Int,py:Int,angle:Float,curRow:Int)

'lokale Variablen
Local dX:Float
Local dY:Float
Local curTan:Float
Local diffX:Int
Local diffY:Int
Local dis:Float=0
Local tempX:Float = px
Local tempY:Float = py
Local curHigh:Float

'als erstes müssen die Änderungen in X und Y-Richtung sowie der Tangens des Blickwinkels ermittelt werden
curTan = Tan(angle)
dY = GRID_SIZE
dX = dY/curTan

'die Richtung muss entsprechend des Blickwinkels angepasst werden
If(angle > 0 And angle < 90) Then

dY = -dY

ElseIf(angle > 90 And angle < 180) Then

dY = -dY

ElseIf(angle > 180 And angle < 270) Then

dX = -dX

ElseIf(angle > 270 And angle < 360) Then

dX = -dX

EndIf

'Nachdem dies passiert ist, wird nun der erste Schnittpunkt berechnet
diffX = Abs(playerX - (Int(playerX/GRID_SIZE)*GRID_SIZE))
tempX:+diffX
diffY = Abs(playerY - (Int(playerY/GRID_SIZE)*GRID_SIZE))
tempY:+diffY

'es wird geprüft ob wir uns bereits außerhalb der Karte befinden
If(tempX/GRID_SIZE > mapWidth-1) And (tempY/GRID_SIZE > mapHeight-1) Then Return -1 'keine Wand gefunden

'als nächstes Prüfen wir ob der Schnittpunkt bereits einer Wand entspricht
If(curMap[Int(tempX/GRID_SIZE),Int(tempY/GRID_SIZE)] <> 0) Then

'ist dies der Fall, wird die Distanz zurückgegeben
Return (pyth(tempX-px,tempY-py))

EndIf


'ist dem nicht so wird solange dX und dY zur temporären Position dazuaddiert bist
'eine Position gefunden wurde, oder das Ende der Karte erreicht wurde
While True

'die aktuelle Position wird berechnet
tempX:+ dX
tempY:- dY

If(Int(tempX/GRID_SIZE) > mapWidth-1 Or Int(tempY/GRID_SIZE) > mapHeight-1 Or tempX < 0 Or tempY < 0) Then

'der Strahl ist außerhalb der Karte, keine Wand gefunden
Return -1

EndIf

'nun wird geprüft ob der neu ermittelte Punkt eine Wand trifft
If(curMap[Int(tempX/GRID_SIZE),Int(tempY/GRID_SIZE)] <> 0) Then

'eine Wand wurde gefunden
'die Distanz wird berechnet
dis = pyth(tempX-px,tempY-py)
Exit

EndIf

Wend

'nachdem die Distanz berechnet wurde muss sie korregiert werden
'um den Fischaugeneffekt zu umgehen
dis= dis*(Cos((-angle) + Self.POV))

'anhand der Distanz wird die Höhe der Wand berechnet
curHigh = 40000/dis

'nun werden die benötigten Informationen in den SpaltenArray
'geschrieben
sceneRows[curRow,0] = curHigh
sceneRows[curRow,1] = curMap[Int(tempX/GRID_SIZE),Int(tempY/GRID_SIZE)]
sceneRows[curRow,2] = dis

End Method




Problem ist jetzt wie gesagt, das die Höheninformationen falsch in den sceneRows-Array geschrieben werden, ja manchmal sogar nicht gefunden wurden, obwohl die "Kamera" in einem
vollständig abgeschlossenen Raum steht.

Wir haben bereits mehrmals alle mathematischen Grundlagen durchgerechnet und kommen einfach nicht drauf,wo da
der Fehler liegt.Ich hab auch bereits Noobodys und vertex' Code
gewälzt und mir nen Wolf probiert, aber ich bekomme die absurdesten Farben und Formen raus, egal was ich probiere.

Der Fehler liegt warscheinlich an der Stelle wo deltaX und deltaY
berechnet werden.

Allerdings habe ich auch hier: http://www.permadi.com/tutorial/raycast/rayc7.html , die selbe Formel gefunden,
welche auch vollständig Sinn macht.Das Ergebnis sieht aber
wie gesagt aus wie...naja ihr seht es ja...

Meine Frage also, weiß jemand was ich falsch mache?
Weiß jemand ob ich einen grundsätzlichen Denkfehler habe,
oder nur im speziellen irgendwas falsch mache?

Ich hoffe jemand von euch kann mir sagen was nicht funktioniert.
Wäre ich euch wirklich sehr dankbar...

Danke im Vorraus!

MfG Ska


-
"In einer so verrückten Welt, kann man um in ihr zu überleben nur eines tun, nämlich eben jenes werden: Ein Verrückter!" -Selbstzitat

aktuelles Projekt: Aves Certim - Der Galgen ist nicht weit!
Ein SNES-RPG mit Handels- und Wirtschaftselemente.
Infos?Hier: http://www.blitzforum.de/worklogs/234/
Besucht meine Seite:
www.seelenfriedhof.de.vu

Casiopaya

BeitragMi, Dez 02, 2009 16:27
Antworten mit Zitat
Benutzer-Profile anzeigen
Hi!

mangels Zeit habe ich nun deinen Code nicht durchlesen können, aber aus meiner Erfahrung aus meinem VG Raytracer (kannst ja mal danach suchen):

Zum Performance-Problem:

Also, in einer unoptimierten Version schneidest du alle Objekte mit dem Strahl und berechnest jeweils den Schnittpunkt. Das sollte auch bei 100ten Wänden sehr schnell gehen. Bei noch mehr musst du ne Beschleunigungsstruktur einbauen. Durch den Schnittpunkt hast du gleichzeitig die Entfernung zum Objekt, das sichtbare Objekt ist das, mit der geringsten Entfernung, was uns zu 2. führt:

>> Hier die Funktion die die Höheninformationen für den Rendering-Prozess ermittelt:

Ich weis nun nicht genau was du mit "Höheninformationen " meinst, aber beim Raycasten hängt die Höhe einzig und alleine von der Entfernung ab. Da du die Entfernung zur Sichtbarkeitsberechnung ohnehin brauchst muss hier gar nichts mehr berechnet werden.

Also zusammengefasst:

- Du hast ein 2D-System, das mathematisch beschrieben wird.
- Du hast einen Kamerapunkt, (x1,y1)
- Pro Bildspalte hast du einen Sichtstrahl, die "Brennweite" deines Kameraobjektivs ergibt sich aus den Winkelgrenzen links und rechts. Nehmen wir an wenn du genau nach vorn schaust ist der Sichtstrahl um 0 Grad gekippt, dies wäre der Sichtstrahl für die Bildspalte in der Bildschirmmitte. Links ist der Strahl um vlt. -30 Grad gedreht, an der rechten Seite um +30Grad. Der Sichtstrahl selbst ist nichts anderes als eine (Halb-) Gerade in 2D, also ein (x1,y1) + lamda(x2,y2)
- Deine Wände sind ebenfalls Geraden, pro Bildzeile musst du die Sichtgerade mit allen geraden schneiden, den Schnittpunkt (g1,g2) berechnen, dessen Abstand zur Kamera (x1,y1), und dann enstprechend der Entfernung eine Linie zeichen.

Grüße

Skabus

BeitragMi, Dez 02, 2009 16:48
Antworten mit Zitat
Benutzer-Profile anzeigen
Vielen Dank erstmal...

Das Raycasting-Prinzip habe ich, hoffentlich, soweit verstanden.

Mit "Höheninformationen" meine ich die korrespondierende Höhe zur jeweiligen Entfernung.Ich berechne ja schließlich für jeden Sehstrahl diejenige Entfernung die zwischen Kameraposition
und der ersten "anzutreffenden" Wandspalte besteht.

Entsprechend der errechneten Entfernung kann ich die Höhe meiner
Wand an der entsprechenden Bildspalte berechnen.

Nutze ich dabei die Beziehung:

aktuelleXPosition + cos Strahlenwinkel
aktuelleYPosition + sin Strahlenwinkel

Dabei gehe ich also davon aus, dass das Steigungsdreick
das der Strahl mit dem Winkel a eine Hypotenuse von der Länge 1, die Ankatete von 1*(cos a) und die Gegenkatete von 1*(sin a)
hat.

Was passiert nun wenn ich zur aktuellen Position deltaX und deltaY dazu addiere:

Ich kann jeden Punkt auf dem Strahl erreichen.Das brauche ich aber gar nicht.Denn wenn ich einmal einen Punkt der innerhalb
eines Feldes in meiner 2D-Karte als "keine Wand" gekennzeichnet
habe, so benötige ich nicht noch den nächste und übernächsten
Punkt dieses Feldes.

Und zur Lösung dieses Problem habe ich ja die beiden findDisDiagH und findDisDiagV geschrieben.Damit ich nur die Schnittpunkte
der Felder benötige und zwar die horizontalen Schnittpunkte
und die vertikalen Schnittpunkte.

Darum, und so finde ich es überall, dachte ich mir:

deltaX = GRID_SIZE (in meinem Fall 64 Einheiten)

und

deltaY = dX / tangens(Blickwinkel)

Ich gehe ja davon aus, dass der Tangens des Blickwinkel im Polarkoordinatensystem die Hypotenuse des Steigungsdreiecks ist
und ich somit die Einheiten die ich in Y-Richtung dazuaddieren
muss dadurch rausbekomme dass ich die Ankatete durch die Hypotenuse teile und so die Gegenkatete rausbekomme.

Nun müsste ja "eigentlich" der Prozess nicht nur korrekt sondern
sogar um ein vielfaches schneller sein.

Aber stattdessen bekomme ich halt abstrakte Formen raus
und weiß eben nicht warum...^^"

MfG Ska
"In einer so verrückten Welt, kann man um in ihr zu überleben nur eines tun, nämlich eben jenes werden: Ein Verrückter!" -Selbstzitat

aktuelles Projekt: Aves Certim - Der Galgen ist nicht weit!
Ein SNES-RPG mit Handels- und Wirtschaftselemente.
Infos?Hier: http://www.blitzforum.de/worklogs/234/
Besucht meine Seite:
www.seelenfriedhof.de.vu

Casiopaya

BeitragMi, Dez 02, 2009 17:54
Antworten mit Zitat
Benutzer-Profile anzeigen
Hi

Skabus hat Folgendes geschrieben:

Nutze ich dabei die Beziehung:

aktuelleXPosition + cos Strahlenwinkel
aktuelleYPosition + sin Strahlenwinkel


hmm, sorry aber ich muss zugeben, dass ich das nicht verstehe. Die Höhe der Wand hängt doch ausschließlich von der Entfernung ab, völlig unabhängig davon in welchem winkel du die Wand mit dem Sichtstrahl schneidest. Da alle Wände in der "Realität" gleich hoch sind, ist jedes Wandsegment (horizontal), das eine Entfernung A von der Kamera entfernt ist, genau gleich hoch. Wie das Verhältnis zwischen Abstand und Höhe nun ist, kannst du selbst festlegen. Da gibt es nichts korrektes oder inkorrektes, da je nach Verhältnis einfach eine andere Kamerabrennweite angenommen werden kann. Zunächst kannst du ja z.B. annehmen, dass alle Dinge, die 1 Meter entfernt sind 50% der Bildschirmgröße haben, alle die 2 entfernt sind 25 % etc (nur ein Vorschlag, hier kommt es darauf an, welches Einheitensystem du verwendest).

Könntst du mal ganz kurz und knapp in Worten erklären, was dein Algor. genau macht? (ICh hab das Posting schon komplett durchgelesen Smile werd aber leider nicht schlau draus)
  • Zuletzt bearbeitet von Casiopaya am Mi, Dez 02, 2009 18:00, insgesamt einmal bearbeitet

Skabus

BeitragMi, Dez 02, 2009 17:59
Antworten mit Zitat
Benutzer-Profile anzeigen
Nein die Beziehung

aktuelleXPosition + cos Strahlenwinkel
aktuelleYPosition + sin Strahlenwinkel

benutze ich nicht zur Berechnung der Höhe, sondern zur Konstruktion meines Sehstrahls.Ich muss doch in Abhängikeit
des Winkels des aktuellen Strahls einen imaginären Sehstrahl zwischen Kameraposition und der nächsten Wand berechnen.

Die Höhenverhältnisse sind wie du ja sagst vollkommen egal.
Da teile ich einfach irgendeinen Wert durch die Entfernung,
damit es passt.

Mein Problem liegt wie gesagt bei der Konstruktion der Strahlen
und die ist, bei Nutzung von sin a cos a extrem langsam, da
ich wie gesagt jedesmal nur sin a und cos a zur aktuellen Position
hinzuaddiere(bzw. subtrahiere)...

Ich hoffe das es jetzt etwas klarer gewordne ist^^

MfG Ska
"In einer so verrückten Welt, kann man um in ihr zu überleben nur eines tun, nämlich eben jenes werden: Ein Verrückter!" -Selbstzitat

aktuelles Projekt: Aves Certim - Der Galgen ist nicht weit!
Ein SNES-RPG mit Handels- und Wirtschaftselemente.
Infos?Hier: http://www.blitzforum.de/worklogs/234/
Besucht meine Seite:
www.seelenfriedhof.de.vu

Casiopaya

BeitragMi, Dez 02, 2009 18:11
Antworten mit Zitat
Benutzer-Profile anzeigen
Skabus hat Folgendes geschrieben:


Mein Problem liegt wie gesagt bei der Konstruktion der Strahlen
und die ist, bei Nutzung von sin a cos a extrem langsam, da
ich wie gesagt jedesmal nur sin a und cos a zur aktuellen Position
hinzuaddiere(bzw. subtrahiere)...


auch auf die Gefahr hin dass ich dich nun wieder falsch verstanden habe, aber den Sichtstrahl selbst kannst du auch ganz ohne Sin und Cos berechnen, einfach indem du eine "Projektstionslinie" vor die Kamera "stellst". Diese Linie liegt horizontal auf Kamerahöhe und hat eine linke und eine rechte ecke. Du fängst mit der linken Ecke an (Ex,Ey), nun hast du 2 Punkte (die Kamera Cx,Cy und (Ex,Ey), daraus kannst du dir deine Gerade in Form a * yb bauen. Für die nächste Bildspalte zählst du ein ExDiff und EyDiff auf Ex bzw Ey drauf, sodass du nach genau 1000 Schritten (falls die Auflösung eine Breite von 1000 Pixel hat) am andere Ende der Linie angelangt bist. Du läufst die Linie also entlang, baust dir jedesmal den Sichtstrahl aus 2 Punkten (Feste Kamera und wandernder Punkt) ganz ohne Trigonometrie. (Beim Bewegen musst du nur die beiden Eckpunkte der Linie bewegen)

Aber mal anders: Mehrere 1000 Sinusse oder Cosinusse pro Sekunde sollten dich performancemäßig kein Problem sein?

EDIT: Etwas missverständlich ist hier vlt das Ex und Ey: Das ist so gemeint, dass du von oben auf die Szenerie schaust, dann hat die Kamera eine xy Position, und jeder Punkt der Linie ebenfalls.

Skabus

BeitragMi, Dez 02, 2009 18:34
Antworten mit Zitat
Benutzer-Profile anzeigen
Hm, du hast mich schon richtig verstanden.

Das Problem ist nur, dass ich das eben nicht ohne Berücksichtigung des Blickwinkels machen kann.

Mein Field of View habe ich mit 64 festgelegt.Vom aktuellen Blickwinkel der Kamera will ich die Hälfte davon subtrahieren
und die Hälfte addieren.

Angenommen mein Blickwinkel ist 0° so geht meine Abtastreichweite
von -32° und +32°

Was bedeutet 328° bis 32°.Da ich eine Auflösung von 640*480 habe muss ich den FOV / 640 teilen.Denn ich brauche jeweils
0.2 * 640 um jede Bildschirmspalte zu erreichen.

Das System basiert meiner Ansicht nach auf der Nutzung dieser
Angaben.

Ich versteh nicht wirklich warum ich das jetzt ohne Trigonometrie und Winkel machen soll^^"

Hast du dir meinen Code mal angesehen?

MfG Ska
"In einer so verrückten Welt, kann man um in ihr zu überleben nur eines tun, nämlich eben jenes werden: Ein Verrückter!" -Selbstzitat

aktuelles Projekt: Aves Certim - Der Galgen ist nicht weit!
Ein SNES-RPG mit Handels- und Wirtschaftselemente.
Infos?Hier: http://www.blitzforum.de/worklogs/234/
Besucht meine Seite:
www.seelenfriedhof.de.vu

Noobody

BeitragDo, Dez 03, 2009 18:30
Antworten mit Zitat
Benutzer-Profile anzeigen
Ich habe mir deinen Code mal durchgesehen und ich denke, ich sehe das Problem. Da du schon auf diese Seite hier verlinkt hast, würde ich empfehlen, sie nochmals durchzulesen Wink

In deinem Code prüfst du nur auf Schnittpunkte mit horizontalen Wänden. Damit du ein korrektes Resultat erhältst, musst du aber sowohl horizontale wie auch vertikale Schnittpunkte berechnen und zum Schluss die Wand zeichnen, deren Schnittpunkt näher an der Kamera liegt. Prüfst du nur auf eine Sorte von Schnittpunkten, so erscheinen die Wände je nach Blickwinkel solide, zerstückelt oder ganz durchlässig.

Allerdings kommt mir der Algorithmus ein wenig ineffizient vor, wie er auf der Seite vorgeschlagen wird; ich schätze, ein DDA-Algorithmus wäre um einiges schneller, da vertikale und horizontale Schnittpunke gleichzeitig und nicht nacheinander errechnet werden. Falls ich Zeit finde, probiere ich mal aus, was schneller ist.
Man is the best computer we can put aboard a spacecraft ... and the only one that can be mass produced with unskilled labor. -- Wernher von Braun

Skabus

BeitragDo, Dez 03, 2009 18:43
Antworten mit Zitat
Benutzer-Profile anzeigen
Hey Noobody,

danke das du dir die zeit nimmst Smile

Ich hab nur zur Übersicht die vertikale Berechnung weggelassen,
im Orginalcode ist die vertikale Berechnung mit enthalten.

Ich prüfe im Anschluss beider Funktionsaufrufe ob die Distanz der vertikalen Berehcnung kleiner als die der horizonatlen Berechnung ist.

Leider ist kein Unterschied zu erkennen, das Ergebnis sieht letzlich genauso aus Sad

Ich bin mir sicher, dass irgendwas an meinem Algorithmus nicht stimmt....

Ich kann gerne den gesamten Code nochmal hochladen, aber ich
hab da massenweise Testcode und überflüssige Funktionen drin
und wollte niemanden verwirren...

Wäre wirklich nett wenn du mir da helfen könntest^^"


MfG Ska

Wie genau funktioniert ein DDA-Algorithmus?Kann ich mich dazu irgendwo belesen?Hab diesbezüglich bissher nix gefunden...
"In einer so verrückten Welt, kann man um in ihr zu überleben nur eines tun, nämlich eben jenes werden: Ein Verrückter!" -Selbstzitat

aktuelles Projekt: Aves Certim - Der Galgen ist nicht weit!
Ein SNES-RPG mit Handels- und Wirtschaftselemente.
Infos?Hier: http://www.blitzforum.de/worklogs/234/
Besucht meine Seite:
www.seelenfriedhof.de.vu

Noobody

BeitragFr, Dez 04, 2009 19:47
Antworten mit Zitat
Benutzer-Profile anzeigen
Ich habe das mal mit einem DDA-Algorithmus umgesetzt und das Programm läuft wie erwartet vergleichsweise schnell BlitzMax: [AUSKLAPPEN]
SuperStrict

Const GWIDTH:Int = 800
Const GHEIGHT:Int = 600

SetGraphicsDriver GLMax2DDriver()

Graphics GWIDTH, GHEIGHT

Global FPSTimer:Int = MilliSecs(), FPSCounter:Int, FPS:Int

Local Cam:TCamera = New TCamera
Local Pixmap:TPixmap = CreatePixmap( GWIDTH, GHEIGHT, PF_BGRA8888 )

Local Timer:TTimer = CreateTimer( 60 )

While Not ( KeyHit( KEY_ESCAPE ) Or AppTerminate() )
Cls

Cam.Update()
Cam.Render( Pixmap )

DrawPixmap Pixmap, 0, 0

DrawText "FPS: " + GetFPS(), 0, 0

Flip 0
WaitTimer Timer
Wend
End

Function GetFPS:Int()
FPSCounter :+ 1

If MilliSecs() - FPSTimer > 1000 Then
FPS = FPSCounter
FPSCounter = 0

FPSTimer = MilliSecs()
EndIf

Return FPS
End Function

Type TCamera
Field AOV:Float

Field PositionX:Float
Field PositionY:Float

Field Angle:Float

Field Map:Int[][]
Field ColorTable:Int[]

Method New()
AOV = 60.0

Angle = 90.0

PositionX = 5.0
PositionY = 8.0

Map = [ [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ], ..
[ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 1 ], ..
[ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 ], ..
[ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 1 ], ..
[ 1, 4, 4, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 ], ..
[ 1, 5, 0, 3, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 1 ], ..
[ 1, 5, 0, 3, 0, 0, 2, 2, 0, 0, 0, 0, 0, 0, 0, 1 ], ..
[ 1, 5, 0, 3, 0, 0, 2, 2, 0, 0, 0, 6, 0, 0, 0, 1 ], ..
[ 1, 5, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 ], ..
[ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 1 ], ..
[ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 ], ..
[ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 1 ], ..
[ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 ], ..
[ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 1 ], ..
[ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 ], ..
[ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ] ]

ColorTable = [ $FFFFFF, $FF0000, $00FF00, $FFFF00, $CCCCFF, $FFCC22 ]
End Method

Method Update()
Local NewX:Float = PositionX + ( KeyDown( KEY_UP ) - KeyDown( KEY_DOWN ) )*0.1*Cos( Angle )
Local NewY:Float = PositionY - ( KeyDown( KEY_UP ) - KeyDown( KEY_DOWN ) )*0.1*Sin( Angle )

If Not Map[ Int( PositionY ) ][ Int( NewX ) ] Then PositionX = NewX
If Not Map[ Int( NewY ) ][ Int( PositionX ) ] Then PositionY = NewY

Angle :+ KeyDown( KEY_RIGHT ) - KeyDown( KEY_LEFT )
End Method

Method Render( Pixmap:TPixmap )
Pixmap.ClearPixels( 0 )

Local Width:Int = Pixmap.Width
Local Height:Int = Pixmap.Height

Local MapWidth:Int = Map[ 0 ].Length
Local MapHeight:Int = Map.Length

Local TileX:Int = Floor( PositionX )
Local TileY:Int = Floor( PositionY )

Local PlaneDistance:Float = Width*0.5/Tan( AOV*0.5 )

Local AngleStep:Float = AOV/Width

Local RayAngle:Float = Angle - AOV*0.5

Local PixelPointer:Int Ptr = Int Ptr Pixmap.PixelPtr( 0, 0 )

For Local I:Int = 0 Until Width
Local DirX:Float = Cos( RayAngle )
Local DirY:Float = -Sin( RayAngle )

Local StepX:Int = Sgn( DirX )
Local StepY:Int = Sgn( DirY )

Local dTX:Float = Abs( 1.0/DirX )
Local dTY:Float = Abs( 1.0/DirY )

Local MinTX:Float, MinTY:Float
If StepX = -1 Then MinTX = ( PositionX - TileX )*dTX Else MinTX = ( TileX + 1.0 - PositionX )*dTX
If StepY = -1 Then MinTY = ( PositionY - TileY )*dTY Else MinTY = ( TileY + 1.0 - PositionY )*dTY

Local RayX:Int = TileX
Local RayY:Int = TileY

Local Distance:Float
While RayX >= 0 And RayY >= 0 And RayX < MapWidth And RayY < MapHeight
If Map[ RayY ][ RayX ] Then
Local WallHeight:Float = PlaneDistance/( Distance*Cos( RayAngle - Angle ) )

Local Color:Int = ColorTable[ Map[ RayY ][ RayX ] - 1 ]

Local Pixel:Int Ptr = PixelPointer + Max( Int( ( Height - WallHeight )*0.5 ), 0 )*Width

For Local Y:Int = 0 Until Min( WallHeight, Height )
Pixel[ I ] = Color

Pixel :+ Width
Next

Exit
EndIf

If MinTX < MinTY Then
RayX :+ StepX

Distance = MinTX

MinTX :+ dTX
Else
RayY :+ StepY

Distance = MinTY

MinTY :+ dTY
EndIf
Wend

RayAngle :+ AngleStep
Next
End Method
End Type

Die Beschreibung des Algos an sich findest du in diesem Artikel. Den brauchte ich mal für ein Raytracer-Projekt Razz
Man is the best computer we can put aboard a spacecraft ... and the only one that can be mass produced with unskilled labor. -- Wernher von Braun

Skabus

BeitragMo, Dez 28, 2009 1:39
Antworten mit Zitat
Benutzer-Profile anzeigen
Vielen Dank Noobody für deine Mühe Very Happy

ich hab mich jetzt eine ganze Weile mit diesen Thema(vor allem DDA) beschäftigt, allerdings
scheint auch diese Methode auf schwachen PC´s nicht optimal genug zu sein...Leider...

Auf meinem eePC mit 800 Mhz läuft es gerade mal mit 5 FPS(maximal), was für ein vernünftiges Spiel viel zu wenig
ist.Gibt es Mittel und Wege das Ganze mit BMax noch zu optimieren?

Ich versuch gerade, einen Raycaster mit DDA-Algorithmus mit C++ und ner Grafikbibilothek zu realisieren,
hab da aktuell aber noch arge Verständnisprobleme, allerdings siehts da bissher auch nicht sonderlich
rosig aus...

Ein Bekannter hat mir empfohlen die zeitkritischen Passagen mit Assembler zu realisieren, hab allerdings
noch nicht ausprobiert in wie weit das funktionieren würde.

Wäre schön wenn du, bzw. auch gerne jeder andere, mir da noch nen Tip geben könntest,
wie ich da noch mehr Geschwindigkeit rausholen kann...

Mein Dank sei dir gewiss Smile

MfG Ska
"In einer so verrückten Welt, kann man um in ihr zu überleben nur eines tun, nämlich eben jenes werden: Ein Verrückter!" -Selbstzitat

aktuelles Projekt: Aves Certim - Der Galgen ist nicht weit!
Ein SNES-RPG mit Handels- und Wirtschaftselemente.
Infos?Hier: http://www.blitzforum.de/worklogs/234/
Besucht meine Seite:
www.seelenfriedhof.de.vu

Noobody

BeitragMo, Dez 28, 2009 2:15
Antworten mit Zitat
Benutzer-Profile anzeigen
Der Bottleneck liegt hier aber nicht beim DDA bzw. Raycasting-Algo - bei Messungen hier verbraucht der Algo gerade mal 0-4ms, je nach Position auf der Karte.

Der wahre Übeltäter ist die Pixmap, die bei mir immer so um die 15ms zum Zeichnen benötigt. Das liegt daran, dass das 3D-Fenster, das durch Max2D geöffnet wird, einfach nicht auf Pixelmanipulation ausgelegt ist und DrawPixmap daher sehr, sehr langsam ist. Es steht ja auch bei der Doku des Befehls bei: "This function is intended for debugging purposes only - performance is unlikely to be stellar."

Die einzige Möglichkeit ist nun, dir eine andere Grafiklib zu schnappen (z.B. SDL), die direkte Buffermanipulation erlaubt oder aber die Fenstererstellung selber vorzunehmen.
Man is the best computer we can put aboard a spacecraft ... and the only one that can be mass produced with unskilled labor. -- Wernher von Braun

Skabus

BeitragMo, Dez 28, 2009 2:22
Antworten mit Zitat
Benutzer-Profile anzeigen
Aso, na wunderbar, dann werd ich mich mal daran machen, mit der SDL oder irgendeiner anderen geeigneten Lib
die Sache mal umzusetzen.

Vielen Dank erstmal^^


MfG Ska
"In einer so verrückten Welt, kann man um in ihr zu überleben nur eines tun, nämlich eben jenes werden: Ein Verrückter!" -Selbstzitat

aktuelles Projekt: Aves Certim - Der Galgen ist nicht weit!
Ein SNES-RPG mit Handels- und Wirtschaftselemente.
Infos?Hier: http://www.blitzforum.de/worklogs/234/
Besucht meine Seite:
www.seelenfriedhof.de.vu

Neue Antwort erstellen


Übersicht BlitzMax, BlitzMax NG Beginners-Corner

Gehe zu:

Powered by phpBB © 2001 - 2006, phpBB Group