Raycaster Competition
BlitzMax Forums/BlitzMax Programming/Raycaster Competition
| ||
| Who wants to have a raycaster competition? I've never written one before and would like to. This could be a great excuse to write an old school game. What should the requirements be? -Walls -Floor & Ceiling -? |
| ||
| nazis? |
| ||
| LOL! |
| ||
| question: what's a raycaster competition? |
| ||
| could be: smallest raycast code (only walking/walls, no enemies) |
| ||
| @z80jim : http://en.wikipedia.org/wiki/Ray_casting |
| ||
Raycasting is an old way of drawing 3D scenes, which was used by pseudo-3D games on older computers. Like this: Back then, the game drew the world by casting one ray per vertical line of the screen, to find out how far it was to the nearest wall, which were aligned to a grid in the case of Wolf3D in order to make it fast enough. Then it drew a scaled vertical segment of the appropriate texture, which could be done fast because no divisions needed to be done per pixel to adjust for perspective, because all pixels in that vertical segment were the same distance from the camera. Nowadays, computers are fast enough that you don't have to reprent the level with a grid or a 2D map of line segments. You can use polygons. And you can cast one ray per pixel on the screen. But nowadays 3D cards can draw a polygon much faster than it could be calculated by the CPU, so you might be limited in the resolution, and unless you support mipmaps you're gonna see a lot of aliasing. |
| ||
| OH MAN I have just had an amazing idea. |
| ||
| Do tell! |
| ||
| So what'll it be? Smallest code? Best looking? |
| ||
| I already have a working raycaster test in Blitzmax so I would surely participate depending on the competition goal. sSwift: Nowadays, computers are fast enough that you don't have to reprent the level with a grid or a 2D map of line segments. You can use polygons. And you can cast one ray per pixel on the screen. This would actually be 'Ray tracing' no? Although this would be an interesting idea for the competition. I am very unsure about the performance of a realtime raytracer even on today's machine. Intriguing.. |
| ||
| I did one in C years ago, just never got rid of the fish-eye-lens problem :) |
| ||
| Funny you should say that, I was going to say earlier today that I think I'll just sit back and wait for the first people to start asking how to get rid of the fish eye. :-) Since I remember how frustrating that problem was, I offer this hint to those who might try to implement one of these: The back of your eye is curved. To remove the fish eye effect, you must adjust the distance you calculate for each wall by taking this curvature into account. In other words you'll need to incorporate some sort of multiplication of the distance by sin or cos to cancel out the curvature that you would see if your retina were flat like the sensor of a camera. |
| ||
| Remz: Realtime raytracing is possible, and I saw demos years and years ago which did it at low resolution. But those were with simple environments. Obviously the more detailed the environment the more costly it will be to raytrace, and I don't know what the state of the art in that area is right now. |
| ||
| Hey you need some sort of fish-eye powrup it would look quite cool. |
| ||
| sswift http://www.openrt.de/ I saw this a while back, havent checked it out in a while. |
| ||
| http://blogs.intel.com/research/2007/10/real_time_raytracing_the_end_o.php nice article on the benefits of raytracing in case anyone was actually interested. |
| ||
| I can explain how to remove the fish eye effect. In fact, the Fish-eye effect is caused when your raycasting algorithm is not correct: In a tradionnal fish-eye raycaster, you basically setup a field-of-view (FOV), say 90 degrees, and you then cast one ray per screen column, say 320, with a calculated delta degree, 90 / 320 = 0.28125 degree per column. That's not the right way: it will always give a 'fish eye' effect, more visible if the FOV is large. You can try to do a 'fish eye correction' with some acos() stuff but it doesn't work. I might sketch up something to demonstrate the right way I'm talking about.. |
| ||
| There we go, I wiped up some pics, hope that helps! This is the traditional 'fish eye' raytracing:  and here's the correct way to do it:  |
| ||
I'm not entering the competition, but this is a snippet I came up with a while ago. It uses 'cheating math' because I was too bored to actually read a tutorial, so I came up with my own ways. It is a 3d raycaster not a 2.5d.SuperStrict; AppTitle = "Raytracer" Const GfxWidth:Int = 200,GfxHeight:Int = 200,PlanetCount:Int = 3,CameraSize:Float=10 Const CameraWidth:Float = Float(GfxWidth)/Float(GfxHeight)*CameraSize; Const CameraHeight:Float = CameraSize Const CameraMax:Float = 5.0,RayStep:Float=0.25; Const Spheres:Int=5 Graphics GfxWidth,GfxHeight,0 Type Point Field X:Float,Y:Float,Z:Float End Type Type Sphere Extends Point Field Radius:Float Field R:Int,G:Int,B:Int Global List:TList Method New() ListAddLast(List,Self) End Method End Type Sphere.List = CreateList() Local Buffer:TPixmap = CreatePixmap(GfxWidth,GfxHeight,PF_RGBA8888); Buffer.ClearPixels(0) Local DrawFPS:Int,FPSCounter:Int,FPSTimer:Int,Camera:Point = New Point; Camera.Z = -10 For Local t:Int = 1 To Spheres Local S:Sphere = New Sphere S.X = Rnd(-10,10); S.Y = Rnd(-10,10); S.Z = Rnd(-10,10); S.Radius = Rnd(1,5); S.R = Rand(0,255); S.G = Rand(0,255); S.B = Rand(0,255) Next Repeat If KeyDown(KEY_LEFT) Then Camera.X:-3 If KeyDown(KEY_RIGHT) Then Camera.X:+3 If KeyDown(KEY_UP) Then Camera.Z:+1 If KeyDown(KEY_DOWN) Then Camera.Z:-1 Buffer.ClearPixels(0) For Local y:Int = 0 To GfxHeight-1 For Local x:Int = 0 To GfxWidth-1 Local Ray:Point = New Point Ray.X = Camera.X+((x-GfxWidth*0.5)/GfxWidth)*CameraWidth Ray.Y = Camera.Y+((y-GfxHeight*0.5)/GfxHeight)*CameraHeight Ray.Z = Camera.Z Local S:Sphere Local StepX:Float = ((x-GfxWidth*0.5)/GfxWidth)*CameraWidth*0.05 Local StepY:Float = ((y-GfxHeight*0.5)/GfxHeight)*CameraHeight*0.05 Local X1:Float,Y1:Float,Z1:Float,FoundS:Sphere,StartZ:Float=Ray.Z S = Null Repeat Ray.X:+StepX Ray.Y:+StepY Ray.Z = Ray.Z+RayStep For Local FS:Sphere = EachIn Sphere.List X1 = Ray.X-FS.X; Y1 = Ray.Y-FS.Y; Z1 = Ray.Z-FS.Z If Sqr(X1*X1+Y1*Y1+Z1*Z1) <= FS.Radius Then S = FS Exit EndIf Next Until S<>Null Or Ray.Z>CameraMax Local R:Int = S.R-10*(Ray.Z-StartZ); If R<0 Then R=0 Local G:Int = S.G-10*(Ray.Z-StartZ); If G<0 Then G=0 Local B:Int = S.B-10*(Ray.Z-StartZ); If B<0 Then B=0 If S<>Null Then Buffer.WritePixel(x,y,(R Shl 16) | (G Shl 8) | B) Next Next DrawPixmap Buffer,0,0; FPSCounter:+1 If MilliSecs()>FPSTimer+999 Then FPSTimer = MilliSecs(); DrawFPS = FPSCounter; FPSCounter = 0 EndIf DrawText "FPS: "+DrawFPS,0,0 Flip 'Cls Until KeyHit(KEY_ESCAPE) |
| ||
| Nawi, I get a whopping 2 FPS on my 4-year-old 1.5 GHz laptop :) And for some reason I get a runtime error for accessing a null object when compiling in debug mode. |
| ||
| Allow me to restate what Remz said in an easier to grasp manner: If your screen is 640 pixels wide, and your FOV is 90, instead of casting one ray every 0.140625 degrees, what you need to do is imagine that the screen is suspended in front of the player, and cast the rays through the individual pixels in that screen. If you do that, then the change in angle from one ray to the next will be greatest near the middle of the screen, and less towards the edges. ---- Now that you understand that... Calculating the correct angle for each pixel is fairly simple if you know the rules dealing with how the lengths of the sides of a right triangle (a triangle with one corner that is 90 degrees) relates to the angles. And those rules are: SohCahToa or Sine = Opposite/Hypoteneuse Cosine = Adjacent/Hypotenuse Tangent = Opposite/Adjacent Let's use the first equation as an example: Sine = Opposite/Hypoteneuse This means that the Sine of an angle (Which is a number you can convert into an angle) equals the length of the side across from it, divided by the hypoteneuse, which is the side across from the 90 degree corner. (The adjacent side in the other equations is the side touching the corner you're trying to find the angle of.) In other words: |\ |_\ The side at an angle is the hypoteneuse. The side on the left and the side on the bottom could either be the opposite or the adjacent, depending on which corner you're trying to find the angle of. Now let's flip that triangle over and get to calculating our angle: ``/ |/ P P is our player. That corner there is the one we're trying to find the angle of. H is the length of our hypoteneuse on the right. We don't know H. A is the length of our adjacent side. For this example, that would be the left side. It is the side which is not the hypoteneuese which is touching the angle that we want to find. We do know the length of this side. Here, it is 1. O is the length of our opposite side. This is the length of the top side, which is opposite the corner at the bottom of the triangle. We also know the length of this. Here it is 2, but this length will vary. It will be 0.5 for the centers of the first two columns of the screen to the left and right of the center of the screen which is between two pixels. And it will increase by 1 each pixel away from the center two pixels. So, which of the three euqations will let us compute our angle with opposite and adjacent? This one! Tangent = Opposite/Adjacent So we could just plug in our values into this and get the tangent of our angle, but we want an actual angle. To get that, you pass that value into a function called ArcTan. So: Angle = ArcTan(Opposite/Adjacent) You can also use the ArcTan2 function, like so: Angle = ArcTan2(Opposite, Adjacent) ArcTan2 exists beccause adjacent approaches 0 as the angle approaches 90 degrees, and ArcTan2 can use the two values it is passed to compensate for this. (An adjacent approaching 0 causes the value passed to the ArcTan function to approach infinity if you just do the division method.) You won't be going more than 45 degrees in either direction from center, and your adjacent length will always be 1, so this won't be an issue for you, but if you ever need to calculate the angle an object is at in relation to another object, ArcTan2 is your function. I don't know which is faster, but I personally always use ArcTan2. And so that's it. Now you have your angle, and you can use that to cast your ray. Now, you might think "I don't need to do any of that angle stuff! I've gone as far as calculating the opposite and adjacent for a specific pixel, and I therefore know the X and Y of that pixel. And that means I know the endpoint of a very short vector that travels in exactly the same direction that I want my ray to go in. And that's all I need for my infinite ray!" But that will only work if you can't turn in place at all. So you do need the angles. You need to calculate the angle for each column, and store that in an array at the start of your program for quick access. Then at runtime, you add the current view angle to the angle for each column, and calculate your vector for your ray like so: X = Radius * Cos(Angle) Y = Radius * Sin(Angle) You can just assume a radius of 1 and exclude that from the equations. And that gives you your ray vectors, with no fisheye effect. Ta da! |
| ||
| found this article on tinternet http://student.kuleuven.be/~m0216922/CG/raycasting.html and to help me make sense of it I blitzified it.. and added a topdown map view. Its quite messy code still and I have only taken the first part where the walls are just plain colors but it works. Now I need to mess around to get my head around exactly what it does ! Anyway. some might find it useful. Not really all my code so I cant really enter it into the Keys: cursor to move,q to quit Edit : This version calcs the xpos (0-1) on the cell that the ray has hit. The 2d view draws all the rays now. |
| ||
| @QuietBloke - Good find. That's a pretty fast raycaster. If it had textured walls with floor and ceiling it would stellar. It would be impressive to add HDR lighting and depth of field to a raycaster. We'll seeeee :) |
   |