Raycaster engine - Floors and Ceilings

We want to be able to pick a pixel on the screen and tell which pixel from a floor tile we should render there.

1
fig 1 The red square in the lower left side of the image represents a random pixel on the screen. Size has been exaggerated.

2
fig 2 This is the game world as seen from above, broken into a series of tiles. The player is the red circle and the blue line the direction he's looking in. How do we match up the pixel from fig 1 to a pixel on a tile that we can then put on the screen?

Lets start with what we know about this pixel:
1. First we recognize that each floor pixel has a twin ceiling pixel located above the wall segment that our floor pixel is part of. This is because the walls themselves are rendered with their centers right at the center line of the screen. The top and bottom half of the walls are then mirrored from each other and this mirroring affects in turn the floor and ceiling, making them too mirrors.

3
fig 3 Because the the wall extends the same amount above the middle center line of the screen as below that means that if we can find a floor pixel a certain distance below the lowest part of a wall segment - here labeled as a green X - we will always find a ceiling pixel the same distance above the highest part of the same wall segment. There can never be more floor pixels than ceiling pixels and vice versa, they're always paired two and two.

2. We know that the top and bottom pixel of a wall segment has the same position in 2D space because the wall is vertical. We also know that the farther away from the middle of the screen a pixel is the closer to the player in 2D that pixel is, since as walls get close their top and bottom pixel move away from the center of the screen. If two pixels are the same distance away from the middle of the screen like those in fig 3 is we know that they must be on the same coordinate in 2D space. So both the pixels on screen in fig 3 will represent the same pixel as seen from above in fig 2. Each tile of our map will have both a floor and ceiling texture associated with it and if we find out the 2D coordinates say our top ceiling pixel on the screen in fig 3 has we will also know the 2D position it's twin floor pixel has. We then only need to calculate a 2D position for one pixel and we'll get the position for another one for free.
3. Remember from the raycasting tutorial that a single ray is responsible for rendering one vertical segment on screen. By creating this virtual wall segment between a floor and ceiling pixel that's larger than the actual wall rendered in between them we can imagine the ray for that screen segment as being able to create that wall segment had it just stopped earlier. This means that whatever floor and ceiling pixels we end up placing on any Y positions in say X position 3 on screen we know that the third ray must have passed over them.

These three things taken together mean that we can treat any two floor and ceiling pixels as though they were the end points of an imaginary wall segment as long as they are the same distance from the center of the screen. Counting backwards we can then figure out how far a ray would have to travel in order to hit this wall. We also know which ray would have to have hit the wall because of it's X position on screen and therefore we would know it's angle and so direction in the world. If we know the distance and direction from the player we can find the 2D position that we would have to end up on for the floor and ceiling pixel.

When drawing a wall segment to the screen we first started our calculations with how far away the ray hitting the wall got and which X position on the screen that ray represented. Plugging those two things into some equations allowed us to get two mirrored pixels position on the screen and we fill in the space in between them with a wall texture.
By starting out with a floor and ceiling pixel on the screen and thinking of them as being the end points of a wall we can then reverse the equations and end up with a ray distance and angle. Starting from the player's position and moving that distance then puts us on the 2D coordinates that we need to read floor and ceiling data for those two pixels from.

Here's the equations from the raycasting tutorial where we have gotten the ray distance and are now calculating the two end points for a wall segment:

const double scale = scaleOneDist / rayFovDepth;
const int yScreenTop = screenHeight / 2.f - ( screenHeight / 2.f ) * scale;
const int yScreenBottom = screenHeight - yScreenTop - 1;

"yScreenTop" and "yScreenBottom" are the two pixels on screen that are now known to us and we need to calculate backwards to get the "rayFovDepth" which is how far down the field of view the ray managed to travel.

As stated before we only need to calculate the 2D coordinates for one pixel and so we can remove the last line that's calculating "yScreenBottom". We know "yScreenTop", it's the Y position for the ceiling pixel from fig 3 and we want to calculate a "scale" value for it. Reversing the equation is simple:

yScreenTop = screenHeight / 2 - ( screenHeight / 2 ) * scale

Divide by screenHeight / 2:

yScreenTop / ( screenHeight / 2 ) = ( screenHeight / 2 ) / ( screenHeight / 2 ) - ( screenHeight / 2 ) * scale / ( screenHeight / 2 )
yScreenTop / ( screenHeight / 2 ) = 1 - scale
scale = -yScreenTop / ( screenHeight / 2 ) + 1

Knowing the Y position of our ceiling pixel on the screen and the screens vertical resolution we have now calculated a "scale" value. Reversing the last equation to get "rayFovDepth is simple:

rayFovDepth = scaleOneDist / scale

Now we've found out how far down the FOV this hypothetical ray must have moved however remember from the raycasting tutorial that this is not the same as the actual distance that the ray has traveled. We project all rays onto the median line and so several different ray lengths will all have the same "rayFovDepth" value. In order to find out the real distance traveled by the ray we need to know it's offset from the median line.
This offset angle is something we calculate at the start of each ray casting and so we can just keep that value and send it to the floor and ceiling drawing function. How this all works in code will be shown later. For now lets assume we now know the offset angle, what we have to work with then is:

4
fig 4 The values that are known to us. M is the "rayFovDepth" that we've just calculated and the angle "a" is something we've calculated at the start of each ray casting. What we want to find out is R which is the real distance traveled by our ray.

From fig 4 we can solve this with some trigonometry. R is our hypotenuse and cosine = adjacent cathetus / hypotenuse. To calculate the hypotenuse and therefore R we get:

R = M / cos( a )

In our code this becomes:

rayLength = rayFovDepth / cos( rayAngle );

So we now know how far from the player that the tile position we need to sample is but we still need a vector in order to know in which direction this sample lies. The ray angle can of course be used to figure out the direction of the ray and in fact at the start of every ray cast we calculate the unit vector for the ray which is still available to us. If we multiply that unit vector with the ray length or magnitude that we just calculated we get how far the hypothetical ray must have moved and and in which direction before striking our hypothetical wall. Couple that with with the player's position and we're able to get the absolute coordinates in the world where we need to sample our floor and ceiling pixels from:

const double xRayPos = xRayStart + xRayUnitVec * rayLength;
const double yRayPos = yRayStart + yRayUnitVec * rayLength;

Here "xRayStart" and "yRayStart" is the player's position where the ray emanates from. Multiply the ray's unit vector with it's length and we get a new relative position to which it's traveled. Add those two things together and we get an absolute 2D coordinate in the world where the ray ended up and we can sample the floor and ceiling texture from.

Finding the pixel on a tile

Now we need to turn these 2D coordinates into a pixel that we can put on screen and in order to do that we need to find out which tile we've landed on and where exactly on that tile our position is. Let's use an example:

5
fig 5 This is the game world as seen from above, a grid of tiles that are all 10x10 pixels wide. The blue numbers are the tile indices, so we have tile number 0 to 4 going from left to right and again tile number 0 to 4 running top to bottom. Blue numbers are used to specifying which tile the player is standing on.
Red numbers are pixel positions. For example tile ( 1, 0 ) covers the horizontal pixels from 10 to 19 and vertical pixels from 0 to 9, both spans of 10 pixels.
An example pixel with position X = 26 and Y = 12 has been marked.

If we now want to convert our pixel position in fig 5 into a tile position we just divide it's pixel position by the tile's size which is 10 pixels for both dimensions:

26 / 10 = 2.6
12 / 10 = 1.2

The integral part of these two numbers tell us which tile the pixel is in. So we have an X tile integral of 2 and an Y integral of 1 which is correct. We can see that the blue number above the tile that the pixel is in reads 2 and to the left of it we have a blue index number of 1.
The fraction tells us in percent where on this tile the pixel is located. Values of .6 and .2 translates to 60% from the left hand side of the tile and 20% from the top.

From knowing the pixel position in the world we can find out which tile we're on, pull a texture from that tile then by knowing the position on that tile in percent we can pull a pixel from the tile's texture.
In the example from fig 5 we would take the texture associated with tile index X: 2 and Y: 1 and find the pixel 60% from the left and 20% from the top on that texture.

Code

First we look at the raycasting function from the original tutorial and how it calls the floor and ceiling drawing function:
1. This is the function for drawing the vertical wall segments to the screen. It returned the Y position on screen for the top and bottom of the wall segment it just drew. Using those two position we know to start drawing the floor 1 pixel below the bottom of the wall segment and the ceiling 1 pixels above the top of the wall segment.
2. Now we call the floor and ceiling function. Notice that we subtract 1 pixel from the "yScreenTop" value to place us 1 pixel above the top of the segment and add 1 pixel to the "yScreenBottom" value to place that 1 pixel below the bottom of the segment. Also note the values being passed to the function, in particular "rayAngleRel" and "xRayVec", "yRayVec".

	void ray_cast_ray( const int rayNbr, const double xPlayer, const double yPlayer, const int xTile, const int yTile,
			const double medianAngle, const double xVecMedian, const double yVecMedian, const double scaleOneDist,
			const int screenWidth, const int screenHeight, const int levelTileWidth, const int levelTileHeight,
			const int tileSize, const int tileHalfSize )
	{
		if( rayNbr == screenWidth ) return;

		const double rayAngleRel = atan( g_firstRayOffset + g_rayStep * rayNbr );
		const double rayAngleAbs = medianAngle - rayAngleRel;

		const double xRayVec = cos( rayAngleAbs );
		//because raylib has an inverted y axis for the screen we need to invert the y vector hence -sin
		const double yRayVec = -sin( rayAngleAbs );

1.		int yScreenTop, yScreenBottom;
1.		ray_trace_to_wall( rayNbr, xTile, yTile, xPlayer, yPlayer, xRayVec, yRayVec, xVecMedian, yVecMedian,
		scaleOneDist, screenWidth, screenHeight, levelTileWidth, levelTileHeight, tileSize, tileHalfSize, &yScreenTop, &yScreenBottom );

2.		ray_draw_floor_ceil( rayNbr, yScreenTop - 1, yScreenBottom + 1, rayAngleRel, xPlayer, yPlayer, xRayVec, yRayVec,
		scaleOneDist, screenWidth, screenHeight, tileSize );

		ray_cast_ray( rayNbr + 1, xPlayer, yPlayer, xTile, yTile, medianAngle, xVecMedian, yVecMedian, scaleOneDist,
				screenWidth, screenHeight, levelTileWidth, levelTileHeight, tileSize, tileHalfSize );
	}

Moving on to the new floor and ceiling function it should be noted that it draws the ceiling pixels going up from the top of the wall's top most pixel and it draws the floor downward from the wall's bottom most pixel. The screen position for the ceiling pixel we're currently drawing is "yScreenTop" and for the floor pixel it's "yScreenBottom":
1. Check if the ceiling pixel we're trying to draw is above the top of the screen. If so we're done drawing. Note that we could just as well have checked if "yScreenBottom" was below the bottom of the screen but because the top and bottom pixels are mirrored they will both go outside the screen at the same time so we need only check one of them.
2. Using the ceiling pixel calculate how far a ray hitting a hypothetical wall segment with it as it's top would have to travel. As described above.
3. Using the length of the ray from step 2 and the unit vector received from the calling function in combination with the player's position we calculate a 2D position in the world that we need to sample floor and ceiling pixels from.
4. Calculate which tile that pixel is on.
5. Strip the integral part from the tile we calculated in step 4 by passing the float value to an int value. The results in the tile index.
6. Strip the fraction part from the tile in step 4 by subtracting the integer part from it. This results in a percentage of where on the tile the pixel is.
7. Here we should call a function that finds the texture that's on the tile we're interested in. Something like "level_get_tile_texture( xTileIntegral, yTileIntegral )". But I haven't implemented storing textures on tiles so I just use the two global textures that are loaded...
8. Multiplying the percentage position with the width and height of the textures gives us the pixel position on them we should sample from.
9. Pull a pixel from the ceiling texture and one from the floor texture from the position in step 8.
10. Put these pixels on the screen using the "yScreenTop" and "yScreenBottom" pixels that we're on.
11. Move "yScreenTop" and "yScreenBottom" one pixel away from the middle of the screen and do the whole thing again.

	void ray_draw_floor_ceil( const int xScreen, const int yScreenTop, const int yScreenBottom, const double rayAngleRel,
		const double xRayStart, const double yRayStart, const double xRayUnitVec, const double yRayUnitVec,
		const double scaleOneDist, const int screenWidth, const int screenHeight, const int tileSize )
	{
1.		if( yScreenTop < 0 ) return;

2.		const double scale = -yScreenTop / ( screenHeight / 2.f ) + 1;
2.		const double fovDepth = scaleOneDist / scale;
2.		const double rayLength = fovDepth / cos( rayAngleRel );

3.		const double xRayPos = xRayStart + xRayUnitVec * rayLength;
3.		const double yRayPos = yRayStart + yRayUnitVec * rayLength;

4.		const double xTile = xRayPos / tileSize;
4.		const double yTile = yRayPos / tileSize;
5.		const int xTileIntegral = xTile;
5.		const int yTileIntegral = yTile;
6.		const double xTileFraction = xTile - xTileIntegral;
6.		const double yTileFraction = yTile - yTileIntegral;

7.		const Image ceil = g_texCeil;
7.		const Image floor = g_texFloor;

8.		const int xPixelCeil = xTileFraction * ceil.width;
8.		const int yPixelCeil = yTileFraction * ceil.height;
8.		const int xPixelFloor = xTileFraction * floor.width;
8.		const int yPixelFloor = yTileFraction * floor.height;

9.		const Color pixelCeil = *( ( Color* ) ceil.data + xPixelCeil + yPixelCeil * ceil.width );
9.		const Color pixelFloor = *( ( Color* ) floor.data + xPixelFloor + yPixelFloor * floor.width );

10.		*( (Color*) screenImage.data + xScreen + yScreenTop * screenWidth ) = pixelCeil;
10.		*( (Color*) screenImage.data + xScreen + yScreenBottom * screenWidth ) = pixelFloor;

11.		ray_draw_floor_ceil( xScreen, yScreenTop - 1, yScreenBottom + 1, rayAngleRel, xRayStart, yRayStart,
		xRayUnitVec, yRayUnitVec, scaleOneDist, screenWidth, screenHeight, tileSize );
	}

Possible optimization

Looking at the first three lines of code in the floor drawing function we notice something:

const double scale = -yScreenTop / ( screenHeight / 2.f ) + 1;
const double fovDepth = scaleOneDist / scale;
const double rayLength = fovDepth / cos( rayAngle );

The variables used here have a very limited range. "screenHeight" is the vertical screen resolution and wont change at all unless the user goes into the settings and so it can almost be considered a constant. "scaleOneDist" is just half the player's size which isn't expected to change during the game either.
Then we have "yScreenTop" which does change but has a very limited range, it can only go from 0 which is the top of the screen down to the middle of the screen which would be half the vertical screen resolution.
Likewise if we look at the last variable "rayAngleRel" we can see where is being calculated that it really only depends on the ray number which equates to the horizontal position on the screen:

const double rayAngleRel = atan( g_firstRayOffset + g_rayStep * rayNbr );

Here the only thing that changes every time the function is run is "rayNbr" which is the same as the X position on screen we're currently at.

The value of "rayLength" which is what we're after only really depends on the X and Y position of the screen pixel that we're currently processing and there's a finite amount of those X and Y position that are possible. So we could easily precalculate those "rayLength" values for each pixel above the middle of the screen and put them into a look-up table. Instead of calculating those three lines for each pixel we could just read the value from memory like this:
const double rayLength = g_rayLengthTable[ X ][ Y ];

Now that I think of it the calculation for getting the relative ray angle offset from the median - "rayAngleRel" - should ideally also be put in a lookup table since it only depends on a constant range of ray numbers.
I haven't written any code for this though since it's less code and easier to explain if you redo the calculations each time. So I'll leave it as an exercise for the reader d:^)