Part 2: Naive raycasting
Raycasting is a efficient rendering technique to create an illusion of a 3D world from a 2D playing field. The most well known example is id Software's Wolfenstein 3D from 1992, considered the first 3D shooter ever.
These were the days before graphics cards - everything was software rendered, blitting pixel by pixel without much parallelism. True software 3D rendering is very slow, but raycasting could work on computers slower than our STM32.
The idea is to cast a ray for every vertical slice of the screen until it hits a solid object. Based on the distance from player's eyes to collision, we can calculate object height to create an illusion of perspective, in which objects further away appear smaller.
The player cannot look up or down. (In some games that was possible only in limited angles with shearing distortion.)
We define the map as an array, which we can imagine as a 2D grid. In our example, the map grid is size 16x16. It can be whatever integer size, but we make an assumption that grid will be square.
Preview (we will create such minimap later):
Warning: The outer edge of the map must be surrounded by walls, otherwise ray will never collide and you will have to define some upper bound manually.
// uint8_t[]
08 08 E1 E1 08 08 75 08 08 08 75 75 08 08 E1 08
03 .. .. .. .. .. .. .. .. .. .. .. .. .. .. 24
02 .. 11 11 01 .. .. .. .. .. .. .. .. .. .. 24
03 .. 21 .. .. .. .. .. 13 13 18 13 .. .. .. 24
12 .. 23 .. .. .. .. .. 77 .. .. .. .. .. .. 24
13 33 .. .. .. .. .. 78 .. .. .. .. .. .. .. 24
22 12 .. .. .. .. .. 02 .. 34 .. 08 09 08 .. 24
21 .. .. .. 05 05 05 03 .. .. .. .. .. .. .. 24
03 .. .. .. 05 .. .. 45 17 17 E1 A1 .. .. C3 24
02 .. .. .. 05 .. .. 17 .. .. .. .. .. B3 .. 24
03 .. .. .. 3C .. .. 17 .. .. .. .. 93 .. .. 24
02 .. .. .. .. .. 15 15 .. .. .. A3 26 26 .. 24
03 33 2D 3E .. 15 .. .. .. .. D3 .. 26 .. .. 24
02 66 .. .. .. .. .. .. .. 82 .. .. 26 .. .. 3C
03 34 .. .. .. .. .. .. .. .. .. .. .. .. .. 24
15 15 15 75 15 15 15 15 75 75 75 15 15 15 75 75Values '..' are transformed into '00' at reading and represent empty space. (This is just for easier editing, because it's easier to see where the empty spaces lie that way.)
Values from '01'-'FF' represent walls. Different values mean different textures applied to the wall.
Texture mapping floor and ceiling is quite complicated and more performance intensive, so I've decided to simply draw horizontal lines with linearly interpolating starting and ending color, which still gives a nice visual result. On top of these walls will be drawn later.
void Raycaster::drawHLines(uint16_t* fb, uint16_t x, uint16_t y, uint16_t width, uint16_t height, uint16_t fromColor, uint16_t toColor)
{
// Assert arguments are valid...
// Assuming RGB565 format
uint8_t fromR = (fromColor >> 11) & 0x1F;
uint8_t fromG = (fromColor >> 5) & 0x3F;
uint8_t fromB = fromColor & 0x1F;
uint8_t toR = (toColor >> 11) & 0x1F;
uint8_t toG = (toColor >> 5) & 0x3F;
uint8_t toB = toColor & 0x1F;
for (uint16_t i = 0; i < height; i++) {
float t = static_cast<float>(i) / (height - 1);
uint8_t r = static_cast<int>(fromR + t * (toR - fromR));
uint8_t g = static_cast<int>(fromG + t * (toG - fromG));
uint8_t b = static_cast<int>(fromB + t * (toB - fromB));
uint16_t interpolatedColor = (r << 11) | (g << 5) | b;
for (uint16_t j = 0; j < width; j++) {
fb[SCREEN_WIDTH * (y + i) + x + j] = interpolatedColor;
}
}
}
For every vertical stripe of the screen, we cast a ray (vector) starting at player location (float within bounds of the map) in the direction of the player's looking direction. We move the ray forward in small increments until we hit a wall. Calculate the distance of the vector to determine height of wall on the screen (how many pixels). The closer the wall, the bigger it's on screen, the further, the smaller.
However, there are two problems with this simple approach.
By starting the ray vector from player position, side rays will be more distant than the middle rays and we get fisheye effect.
(image by vinibiavatti1)
We could apply correction to distorted distance by multiplying it by cos(ray_angle - player_angle), but I've chosen another approach.
Instead of casting rays from player position, we create a camera plane vector that is perpendicular to player direction vector. If they would be of equal length, we would have FOV 90. 2/3 means FOV 60, which is what we want.
Vec2f Raycaster::playerPos = {2, 11};
Vec2f Raycaster::dir = {0, -1};
Vec2f Raycaster::cameraPlane = {0.66f, 0};
I find this approach more mathematically intuitive and we get rid of having to use trigonometric functions, which can prove faster.
The problem with adding a constant value to the ray each step until we hit a wall is that takes a lot of calculations - tens or hundreds for every screen column. We could try lowering constant value, but that quickly induces visual artifacts and even worse - we can end up missing a wall altogether!
In Part 3, we will use DDA algorithm, which moves by a whole tile at a time, making it orders of magnitude faster. Not only that, it is always correct and never misses a wall.
In-depth explanation of efficient DDA raycasting algorithm. (Explanation images of grid taken from there)