Simple LOVE Raytracer Code (both untextured and textured)

[scutheotaku]

Here's my FPS
Nontextured
1. 640x480 : 79
2. 800x600 : 60
3. 1024x768 : 56
4. 1280x1024 : 45

Textured
1. 640x480 : 85
2. 800x600 : 72
3. 1024x768 : 58
4. 1280x1024 : 47


Strange, Textured is faster.. Here are my specs :

1280x1024 Monitor
No Graphics Card (derp)
Windows 7 Ultimate x64
(from memory) ASUS P5KPL-AM-SE Motherboard

Thanks for the stats, and for checking it out! Yeah, I think the untextured version is faster because of "drawline"'s relative inefficiency, though I'm not sure. It seems strange that drawing a line would be less efficient than a textured quad though...

Congratulations. Your raytracer should be probably the lightest engine of this kind in LOVE (Inny's one is also quite light).
It's hard to ran one without heat up my machine but your hardware fingerprint is almost null. Also solid vsynced 60fps in both versions.
Plus your code is so clean (and short) that even a math idiot like myself could learn it easily. Well done.
Don't worry about the stretch bug some quad/math LOVE wizard will certainly help you to solve it.

Thanks for the encouraging words!
I'm glad that my code is readable. That's something I always strive for as it was driven pretty hard into my heard when I first learned BASIC

Very nice! It makes much more sense to increment the X distance and the Y distance in the same loop rather than do all the X's and all the Y's separately, as in the earlier raycasting demos that Jasoco and others posted a while back. I've been using raycasting for the lighting in my game, and this should make it a bit quicker.

Thanks! I'm really glad it proved helpful for you. I'd love for you to message me a link to an example of your lighting, if you don't mind sharing it

The more raycasters the better. Let everyone create their own. I love it. Imagine if Ken Silverman decided not to create the Build engine because DOOM was just so awesome. We wouldn't have the superior (To the DOOM engine) Duke Nukem 3D/Blood/Shadow Warrior engine which was capable of things the DOOM engine could never do, and even Quake couldn't do in some ways.

Ken started by creating a Wolfenstein 3D style engine of his own when he was a teenager. Then graduated to the more DOOM-like Build engine later on. YouTube has a lot of really cool videos documenting the history of his engines.
http://www.youtube.com/watch?v=l8tDBg4pfYk


My engine eventually gained floor textures (Aided by Canvas) as well as buggy doors, annoying dumb NPC's that just constantly walk towards you, a map and sprite objects. When I get around to redoing it, it will get even more... eventually. At some point eventually.

Thanks for checking this out

Ah, I'm a big Ken Silverman fan, and of the Build engine. While I prefer Doom and its engine's aesthetic over the Build engine's (Doom based games just had a certain feel to them that I love), a lot of aspects of the Build engine were pretty genius.

Reading Ken's website a while back got me interested in a voxel engine. Perhaps I'll attempt something like that in LOVE, though that's probably a little over my head Oh, and speaking of which, anyone interested in Ken's work can get a lot of free downloads from his website (including his voxel engine(s), the Build engine source code [including updates to it and its tools as recent as 2009], and the aforementioned Wolf3D clone "Ken's Labyrinth"): http://advsys.net/ken/ There's a lot of great info there for people interested in this great and revolutionary era of computer games!

I'm interested in the canvas method of casting floors, though it does seem pretty limited. I experimented with the pixel-by-pixel approach to floor casting from Lode's tutorials, but in LOVE it ended up being a buggy mess that absolutely destroyed the framerate...

PS: I love the music on that video...relaxing in an AFX/Analord sort of way.

Very neat.

In addition to Lode's tutorial, you probably saw this in your searches as well: http://www.permadi.com/tutorial/raycast/index.html

There's a few good tidbits of info in there, like how to get looking up/down and changing the eyeline (to simulate jumping/ducking). In terms of how it applies to Lode's code, the center line you draw the scanlines from is for "Looking", meaning change that and you can look up and down. The eyeline was a bit more tricky. I have updated code that I probably should refresh my old thread with to demonstrate these features. I was taking my engine towards being an RPG engine though, and gave up when it came to floor/ceiling textures since I couldn't find a reasonable way to do it (even the mode7 style code looked to be way too painful toward the framerate).

What I'd also love to see eventually done is variable height floors/ceilings. Even if we can't quite get to textured surfaces, it'd be nice to see doom/hexen or even RiseoftheTriad style vertical movement. It might make a nice longterm goal for you if you want to take your code past the wolfenstein era.

Thanks for looking!

Yeah, I had seen the Permadi article too. There is a lot of good info there, though I hadn't really dug in enough to translate it to my current code. If I decide to further this little engine, what you wrote will definitely be helpful!

I don't think that RotT stlye movement would be that hard, but anything in the vein of the Doom engine would be quite a leap. I think we'd have to follow a similar line that id Software did and use a BSP-style system. Speaking of which, I think it might be worthwhile using lookup tables for the different formulas like almost all of these old engines (like the Wolf3D engine, the DOOM engine, and IIRC the Quake 1 engine did). I'm not really sure how to go about this though :/

DOOM would be very possible. Except that floor/ceiling would be very hard as far as I've seen so far. (I had to resort to canvases for floors in my Wolf clone and that's just one plane) Also you'd need to figure out collision with arbitrarily positioned lines.

I did do a lot of research into the histories of DOOM and Wolfenstein back then.

The source code for each is readily available even though it's C.

I've yet to look at the Wolf3D or DOOM source code yet, though I've wanted to. Knowing the era and Carmack, there's probably enough Assembly to make my head spin...

Like I mentioned before, you can also grab the Build engine source code from Ken's site ( http://advsys.net/ken/buildsrc/default.htm ). There's also JonoF's port/fork which ports the Build engine from DOS to Windows, MacOSX, and Linux, while also adding some enhancements like a full 3D renderer and 3D model support: http://www.jonof.id.au/jfbuild (though the original engine is probably more relevant to what we would want to/could do with LOVE). You can also get the source code to "Ken's Labyrinth": http://advsys.net/ken/klab.htm

RoTT seems like the next logical step, seeing as how it was just the floor on a flat plane, and they emulated staircases and platforms heights through sprites.

See: https://love2d.org/imgmirrur/uTlGG.jpg

Agreed! I don't think that this would be THAT hard, but then again I'm still having trouble with a lot of the basics

Jasoco, I remember all the awesome screens you posted of your double-layered raycasting with mouselook. We're still waiting for the final product

Yes!

[scutheotaku]

Using some excellent advice from Jasoco, I made a slight addition to the code that, as Jasoco puts it, gives the engine a more "authentic retro feel."

I added these two lines of code (well, a comment and a line of code) to the load callback function:

Code: Select all

--change default image filter to reduce bluriness when scaling images
	love.graphics.setDefaultImageFilter("nearest","nearest")

That sets the default image filter to nearest neighbour, getting rid of the antialiased look when images are scaled. This makes the wall textures look more pixelated and less blurry and smooth.

To illustrate this, here are before and after screenshots-

Before:


After:


If you prefer the original look, then just remove those two lines

You can download the updated version from the original post, or here:
https://dl.dropbox.com/u/17269775/scuth ... -0.55.love

---

As far as any more progress on this engine...if anyone has any code suggestions, I'd be more than happy to look at them and possibly add them. Aside from that, I probably won't add anymore features until I can figure out the whole "textures distort once their height fills the height of the window" problem...any help on that would be very, very, very appreciated!

[Jasoco]

DOOM would be very possible. Except that floor/ceiling would be very hard as far as I've seen so far. (I had to resort to canvases for floors in my Wolf clone and that's just one plane) Also you'd need to figure out collision with arbitrarily positioned lines.

I did do a lot of research into the histories of DOOM and Wolfenstein back then.

The source code for each is readily available even though it's C.

I've yet to look at the Wolf3D or DOOM source code yet, though I've wanted to. Knowing the era and Carmack, there's probably enough Assembly to make my head spin...

Wolfenstein has a little Assembly but is mostly C. DOOM is pretty much all C.

Jasoco, I remember all the awesome screens you posted of your double-layered raycasting with mouselook. We're still waiting for the final product

Yes!

Eventually. One project at a time. My failing is taking on too many at once and getting bored or stuck too fast.

[Gravy]

Thanks! I'm really glad it proved helpful for you. I'd love for you to message me a link to an example of your lighting, if you don't mind sharing it

I don't mind sharing at all, but it might be a bit less than you were expecting This is a pared down version, but there is still some unnecessary stuff in there. I'm not entirely happy with how it looks, but as soon as I learn how shaders work, I'm hoping I can make the light appear a bit more natural.

I'm in the middle of implementing a spacial hash, using the tile grid as the buckets. This way I can use the same raycasting technique for shooting, just check all the bounding boxes of every object inside each tile to see if they intersect with the line before moving on to the tile.

[Inny]

What might make an interesting way to do the floor plane is to start with simulating solid colored polygons. Things like the Zombie Baseball demo show off how to do stuff like this. Having the polygon of the floor tile gives you the visual locations on the screen. With that, you can do the Mode7 techniques and get the scissor accurately to where the tile needs to be drawn, cutting down the number of blits per tile down from 240 to whatever the tilesize is (32?) or some small multiple of it.

[scutheotaku]

DOOM would be very possible. Except that floor/ceiling would be very hard as far as I've seen so far. (I had to resort to canvases for floors in my Wolf clone and that's just one plane) Also you'd need to figure out collision with arbitrarily positioned lines.

I did do a lot of research into the histories of DOOM and Wolfenstein back then.

The source code for each is readily available even though it's C.

I've yet to look at the Wolf3D or DOOM source code yet, though I've wanted to. Knowing the era and Carmack, there's probably enough Assembly to make my head spin...

Wolfenstein has a little Assembly but is mostly C. DOOM is pretty much all C.

Jasoco, I remember all the awesome screens you posted of your double-layered raycasting with mouselook. We're still waiting for the final product

Yes!

Eventually. One project at a time. My failing is taking on too many at once and getting bored or stuck too fast.

That's good to know on the Assembly. Though that is something I'd like to learn at some point...apparently Carmack used at least some assembly in his renderers as recently as id Tech 4 (Doom 3), though I think it's really used more for just basic optimizations nowadays (at least in games).

Yep, I get bored like that too :/

Thanks! I'm really glad it proved helpful for you. I'd love for you to message me a link to an example of your lighting, if you don't mind sharing it

I don't mind sharing at all, but it might be a bit less than you were expecting This is a pared down version, but there is still some unnecessary stuff in there. I'm not entirely happy with how it looks, but as soon as I learn how shaders work, I'm hoping I can make the light appear a bit more natural.

I'm in the middle of implementing a spacial hash, using the tile grid as the buckets. This way I can use the same raycasting technique for shooting, just check all the bounding boxes of every object inside each tile to see if they intersect with the line before moving on to the tile.

I only had a quick second to look at it, but from what I saw it looks really nice! The lighting may not be completely natural looking, but it has a really cool look in a stylized sort of way. Something like this would look really good in a detective noir game!

I had attempted something similar back in my Game Maker days, though both my programming/math skills at the time and Game Maker's speed (Game Maker 5.x, back when alpha blending could take the engine to a halt) resulted in a slow, inaccurate mess

What might make an interesting way to do the floor plane is to start with simulating solid colored polygons. Things like the Zombie Baseball demo show off how to do stuff like this. Having the polygon of the floor tile gives you the visual locations on the screen. With that, you can do the Mode7 techniques and get the scissor accurately to where the tile needs to be drawn, cutting down the number of blits per tile down from 240 to whatever the tilesize is (32?) or some small multiple of it.

That would be pretty interesting, though it would definitely only be applicable to single (vertical) level games. If I expand on this engine, I want to do it with the mindset of having support for at least stairs.

Speaking of which, I've recently been going through the Lode tutorials again, the Permadi tutorials, some analyses of the Wolf3D and Doom engines, and various other tutorials and docs, all with the goal of writing a new raycasting engine for LOVE. Don't expect too much, but it's something I'll be working on in the next couple of days (weeks?).

EDIT:
Hey, does anyone have a good source for learning/relearning math, particularly the trig and such that is useful for this type of graphics programming. I'm pretty good at math, but I didn't really apply myself in Trig or in college math courses (I just memorized stuff long enough to get good grades), something that I've really been regretting recently. There's a lot of math websites and books out there, but I'd love something that is more focused on the math behind games and graphics programming. Thanks!

[scutheotaku]

I mentioned before that I was going to start from scratch...well, I probably still will, but I was just looking over this code again and I fixed a MAJOR bug - the texture distortion bug.

It was really stupid on my part, actually...I was scaling the quads based on the "drawLineStart" and "drawLineEnd" variables, completely forgetting that those variables are "rounded off" in the rendering code if they exceed the window dimensions.

To better explain this, here's the old code from the raycasting loop (the lines that "round them off" are on the fifth and sixth lines):

Code: Select all

--Calculate height of line to draw on screen
		lineHeight = math.abs(math.floor(h / perpWallDist))
		
		drawStart = -lineHeight / 2 + h / 2
		if (drawStart < 0) then drawStart = 0 end
		drawEnd = lineHeight / 2 + h / 2
		if (drawEnd >= h) then drawEnd = h - 1 end

The drawStart and drawEnd values for the current x position were then set at the end of the loop:

Code: Select all

--set draw array variables
		drawScreenLineStart[x] = drawStart
		drawScreenLineEnd[x] = drawEnd	

I've now changed the code to this:

Code: Select all

--Calculate height of line to draw on screen
		lineHeight = math.abs(math.floor(h / perpWallDist))
		
		drawStart = -lineHeight + playerHeight / 2 + h / 2
		drawScreenLineOriginalStart[x] = drawStart
		if (drawStart < 0) then drawStart = 0 end
		drawEnd = lineHeight + playerHeight / 2 + h / 2
		drawScreenLineOriginalEnd[x] = drawEnd
		if (drawEnd >= h) then drawEnd = h - 1 end

Note: I'm now using "drawSceenLineOriginalStart" and "drawScreenLineOriginalEnd" in place of "drawScreenLineStart" and "drawScreenLineEnd". "drawScreenLineStart" and "drawScreenLineEnd" are still being set to the "rounded off" values at the end of the loop, but they aren't currently being used anywhere.

Now, there is no distortion close-up! Woohoo!



You probably noticed that something is a little off with that screenshot. Well, I also added a sort of "vertical looking" feature. Really, it just modifies the y coordinates of the quads, so it doesn't look quite right...but it looks pretty good, in a BUILD engine/ZDoom sort of way. Oh, and the variable the modifies this is erroneously named "playerHeight" - I'll probably rename this in the next version (as well as add comments for my additions), but I only have a minute so I just wanted to get these changes out

You control the vertical looking with the "u" and "i" keys.

Grab the new version here:
https://dl.dropbox.com/u/17269775/scuth ... d-0.6.love



---

EDIT:
Hey guys,

I have a little problem that I'd love some help with:

I'm currently working on adding "things" (borrowing some terminology from Doom...sprites in the level, e.g. in Wolfenstein 3D this might be an enemy, or a table, or a plate of food). All's going fairly well....I decided that (as of right now) the game would have two object types: "walls" and "things". Walls would be treated basically as they are now. Things are treated a little differently.

I decided against trying to detect things (which should be allowed to move and be of various sizes, as well as not be fixed to any grid) with raycasting. Instead I decided that in the main "things loop", each "thing" would see if it falls inside the player's cone of vision. If it does, then it would be added to the Draw Table (I'll get to that in a second). The downside to this method is that there is bound to be overdraw since many of the things that fall into the player's cone of vision probably won't be seen. The upside is two-fold: 1. I believe that a little overdraw in this case would be faster than trying to detect the things with raycasting (maybe I'm wrong though?), and 2. this allows for things to be seen through partially transparent walls and, as I hope to add soon, walls of different heights. I realize there are other ways to do this, but, at this point, I feel that the simplicity of this method outweighs the potential slight performance hit.

Now, to allow things to be in front of or behind walls, I implemented a Draw Table. Each row in the Draw Table includes an "id" (for a wall, this is its x position, for a thing this is its thing id), its type ("wall" or "thing"), and its distance to the player. At the beginning of every frame, the Draw Table is cleared. Then we check for things, and any things without the player's cone of sight are added to the Draw Table. Then we check for walls, and each 1 pixel wide vertical strip is individually added to the Draw Table. As each thing or vertical wall strip is added to the Draw Table, its distance to the player is also calculated and added along with it (remember, drawTable = {id, drawType, distanceToPlayer}).

Now we move to drawing...
Right before we start drawing, we sort the table by "distanceToPlayer":

Code: Select all

--sort table
table.sort(drawTable, function(a,b) return a.distanceToPlayer < b.distanceToPlayer end)

Next, we start the draw loop. If all is working correctly, this should draw everything in the Draw Table in descending order of its distance to the player (I might be saying that wrong, but basically the things closest to the player will be drawn last):

Code: Select all

--draw loop
	for i=0, #drawTable do
		if (drawTable[i].drawType == "wall") then
			--draw wall
			DrawWall(drawTable[i].id)
		elseif (drawTable[i].drawType == "thing") then
			--draw thing
			DrawThing(drawTable[i].id)
		end
	end	

For good measure, here are the two functions referenced there (I know that both of these work):

Code: Select all

--draw wall function
function DrawWall(x)
	love.graphics.setColor(drawScreenLineColor[x])
	drawScreenQuad[x] = love.graphics.newQuad(drawScreenLineX[x], 0, 1, texHeight, texWidth, texHeight)
	local texYScale = (drawScreenLineOriginalEnd[x] - drawScreenLineOriginalStart[x]) / texHeight
	local texXScale = 1
	love.graphics.drawq(texture[drawScreenTexture[x]], drawScreenQuad[x], x, drawScreenLineOriginalStart[x] + playerVLook, 0, texXScale, texYScale)
end

--draw thing function
function DrawThing(id)
	thingQuad[id] = love.graphics.newQuad( 0, 0, 64, 64, 64, 64 )
	love.graphics.drawq(thingTexture[id], thingQuad[id], 320, 240, 0, 1, 1)
end

NOTE: The "DrawThing" function is only partially implemented at this point. It only draws the "thing" in the center of the screen, with no scaling.

The result?

Here:


You'll notice that the "thing" (which is temporarily represented by the 64x64 eagle wall texture) is being drawn behind walls that are much farther away. As you'll see by the numbers along the top, the player is positioned at 22,12 (the number all the way to the right), and the thing is position at 22,10 (the bottom two numbers in the middle), and the thing's distanceToPlayer is exactly 2 (the top number in the middle). Despite all of that, the thing is drawn before the walls that are much farther away - or at least I assume that it is drawn before them since it is behind them.

I'm very, very new to Lua, so I think that this probably has to do with how I'm using tables, particularly how I'm sorting them. I based how I'm sorting the table and such on, among other things I've read tonight, this article: https://love2d.org/wiki/Tutorial:Drawing_Order . Unless I'm missing something, which I most definitely am, my sorting code should work just as well as the sorting code in that article...but it doesn't :/

Any help with this (tips, code examples, complete changes, etc...) would be very, very, very appreciated!

Here is my current code:
https://dl.dropbox.com/u/17269775/scuth ... 07DEV.love

Thanks!

[Jasoco]

You need to have all drawables in one single "draw pool" as I call it in my engine. This includes all wall slices (i.e. all the "rays"), all "things", all enemies, anything that will be drawn should be in this single table. Then you sort the entire "pool" and draw everything. It seems you're only adding wall slices and not "things" as well.

Anything that will be drawn should be sorted. You create (or subsequently replace) the pool table (lol) at the start of the Update loop. Then add each drawable one at a time. Its image and quad, its screen position, its X and Y scale values and any other metadata that should be attached to it for use when drawing like maybe colorization or darkness (If you want to add "fog" or "darkness" for distant places.) values. Anything. Also, when adding to the pool, make sure to give each one a "type" so you can handle it later when doing your draw pass.

Do you know how to calculate the screen location of "things" in your view? It will be important for when you want to have other stuff like enemies. Some Pseudocode:

Code: Select all

local dx = THING.x - player.x
local dy = THING.y - player.y

local dist = math.sqrt(dx*dx + dy*dy)

local spriteAngle = math.atan2(dy, dx) - player.rotation_angle

local size = viewDist / (math.cos(spriteAngle) * dist)

local x = math.tan(spriteAngle) * viewDist
local left = (screenWidth/2 + x)
local top = ((screenHeight-size)*player.eyeHeight)

local dbx = THING.x - player.x
local dby = THING.y - player.y

local blockDist = dbx*dbx + dby*dby
local z = -math.floor((dist-.5)*10000)

Might not be completely useful. I had a lot of custom stuff in my project. But it should show you the correct math.

In my engine I had implemented darkness values so far off objects and wall slices would be darker than closer ones. I also made it so any object could be illuminated which would make it show up 100% brightness no matter what. Before I got stuck I had plans for adding pre-calculated lighting effects and other cool things. I can't wait to go back to it really. But not until I am done with my current project. One at a time, Jason.

[scutheotaku]

You need to have all drawables in one single "draw pool" as I call it in my engine. This includes all wall slices (i.e. all the "rays"), all "things", all enemies, anything that will be drawn should be in this single table. Then you sort the entire "pool" and draw everything. It seems you're only adding wall slices and not "things" as well.

Anything that will be drawn should be sorted. You create (or subsequently replace) the pool table (lol) at the start of the Update loop. Then add each drawable one at a time. Its image and quad, its screen position, its X and Y scale values and any other metadata that should be attached to it for use when drawing like maybe colorization or darkness (If you want to add "fog" or "darkness" for distant places.) values. Anything. Also, when adding to the pool, make sure to give each one a "type" so you can handle it later when doing your draw pass.

Do you know how to calculate the screen location of "things" in your view? It will be important for when you want to have other stuff like enemies. Some Pseudocode:

Code: Select all

local dx = THING.x - player.x
local dy = THING.y - player.y

local dist = math.sqrt(dx*dx + dy*dy)

local spriteAngle = math.atan2(dy, dx) - player.rotation_angle

local size = viewDist / (math.cos(spriteAngle) * dist)

local x = math.tan(spriteAngle) * viewDist
local left = (screenWidth/2 + x)
local top = ((screenHeight-size)*player.eyeHeight)

local dbx = THING.x - player.x
local dby = THING.y - player.y

local blockDist = dbx*dbx + dby*dby
local z = -math.floor((dist-.5)*10000)

Might not be completely useful. I had a lot of custom stuff in my project. But it should show you the correct math.

In my engine I had implemented darkness values so far off objects and wall slices would be darker than closer ones. I also made it so any object could be illuminated which would make it show up 100% brightness no matter what. Before I got stuck I had plans for adding pre-calculated lighting effects and other cool things. I can't wait to go back to it really. But not until I am done with my current project. One at a time, Jason.

Thanks, I appreciate all of the information. Though, I am adding the "things" to the same table. I've also confirmed that they are in that same table. And, actually, the "thing" that is being drawn behind the walls wouldn't draw at all unless it was in that same table. You also wouldn't see most of those stats at the top of the screen (they're grabbed straight from drawTable).

Here's the "thing loop":

Code: Select all

--"thing" loop
	for x = 0, thingCounter, 1 do
		--convert x,y position to polar coordinates
		local myAngle = math.atan2(thingY[x], thingX[x])
		
		--if I'm inside player's vision cone
		if ((myAngle >= angle1) and (myAngle <= angle2)) then
			--calculate distance to player
			local dX = posX - thingX[x]
			local dY = posY - thingY[x]
			local dist = math.sqrt((dX * dX) + (dY * dY))
			
			--add self to draw table
			drawTable[currentDrawTableID] = {id = x, drawType = "thing", distanceToPlayer = dist}
			currentDrawTableID = currentDrawTableID + 1
		end
	end

I think my problem is definitely in the table sorting...maybe

I had a pretty good idea on how to calculate the screen location of "things" (I hadn't gotten there quite yet), but that code will be very helpful. Thanks!

[IndieKid]

How do you create a floor based on another matrix table (like map {{1,1,1...0,1}})?

I got the idea that I need to know how far is the bottom of the wall is, but how do I get the height of the wall on the opposite side from player?