Raycaster und Prozessoptimierung

Übersicht

BlitzMax, BlitzMax NG

Beginners-Corner

	Skabus Betreff: Raycaster und Prozessoptimierung	Mi, Dez 02, 2009 15:10 Antworten mit Zitat
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: 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 6464 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: Mein Code sieht so aus: Hier die Funktion die die Höheninformationen für den Rendering-Prozess ermittelt: BlitzMax:* [AUSKLAPPEN] [EINKLAPPEN] '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(aa+bb) 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] [EINKLAPPEN] '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

Skabus

Betreff: Raycaster und Prozessoptimierung

Mi, Dez 02, 2009 15:10
Antworten mit Zitat

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	Mi, Dez 02, 2009 16:27 Antworten mit Zitat
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

Casiopaya

Mi, Dez 02, 2009 16:27
Antworten mit Zitat

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	Mi, Dez 02, 2009 16:48 Antworten mit Zitat
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

Skabus

Mi, Dez 02, 2009 16:48
Antworten mit Zitat

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

	Casiopaya	Mi, Dez 02, 2009 17:54 Antworten mit Zitat
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 werd aber leider nicht schlau draus)

Casiopaya

Mi, Dez 02, 2009 17:54
Antworten mit Zitat

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	Mi, Dez 02, 2009 17:59 Antworten mit Zitat
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

Skabus

Mi, Dez 02, 2009 17:59
Antworten mit Zitat

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

	Casiopaya	Mi, Dez 02, 2009 18:11 Antworten mit Zitat
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.

Casiopaya

Mi, Dez 02, 2009 18:11
Antworten mit Zitat

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	Mi, Dez 02, 2009 18:34 Antworten mit Zitat
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 640480 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

Skabus

Mi, Dez 02, 2009 18:34
Antworten mit Zitat

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

	Noobody	Do, Dez 03, 2009 18:30 Antworten mit Zitat
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 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

Noobody

Do, Dez 03, 2009 18:30
Antworten mit Zitat

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	Do, Dez 03, 2009 18:43 Antworten mit Zitat
Hey Noobody, danke das du dir die zeit nimmst 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 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

Skabus

Do, Dez 03, 2009 18:43
Antworten mit Zitat

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...

	Noobody	Fr, Dez 04, 2009 19:47 Antworten mit Zitat
Ich habe das mal mit einem DDA-Algorithmus umgesetzt und das Programm läuft wie erwartet vergleichsweise schnell BlitzMax: [AUSKLAPPEN] [EINKLAPPEN] 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.1Cos( Angle ) Local NewY:Float = PositionY - ( KeyDown( KEY_UP ) - KeyDown( KEY_DOWN ) )0.1Sin( 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 = Width0.5/Tan( AOV0.5 ) Local AngleStep:Float = AOV/Width Local RayAngle:Float = Angle - AOV0.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/( DistanceCos( 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
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

Noobody

Fr, Dez 04, 2009 19:47
Antworten mit Zitat

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	Mo, Dez 28, 2009 1:39 Antworten mit Zitat
Vielen Dank Noobody für deine Mühe 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 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

Skabus

Mo, Dez 28, 2009 1:39
Antworten mit Zitat

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

	Noobody	Mo, Dez 28, 2009 2:15 Antworten mit Zitat
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

Noobody

Mo, Dez 28, 2009 2:15
Antworten mit Zitat

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	Mo, Dez 28, 2009 2:22 Antworten mit Zitat
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

Skabus

Mo, Dez 28, 2009 2:22
Antworten mit Zitat

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

Übersicht

BlitzMax, BlitzMax NG

Beginners-Corner

Nach Oben

BlitzBasic Portal

Raycaster und Prozessoptimierung

Betreff: Raycaster und Prozessoptimierung