Optimizing a raycaster

Question

I have finished a raycaster, and I want to optimize it before I add other features, such as variable height walls, texture mapping and lighting. I'd like someone to review the code so I can improve it further.

Pastebin

#include <stdio.h>
#include <SDL2/SDL.h>
#include <sys/time.h>
const int RESX = 960;
const int RESY = 540;
const float ROTSPEED = 0.03;
const float MOVESPEED = 0.08;
const float STRAFEMOVESPEED = 0.05657;
char placeDist = 3;
char MAP[32][32] = {
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,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,0,0,0,0,0,0,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,0,0,0,0,0,0,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,0,0,0,0,0,0,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,0,0,0,0,0,0,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,0,0,0,0,0,0,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,0,0,0,0,0,0,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,0,0,0,0,0,0,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,0,0,0,0,0,0,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,0,0,0,0,0,0,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,0,0,0,0,0,0,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,0,0,0,0,0,0,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,0,0,0,0,0,0,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,0,0,0,0,0,0,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,0,0,0,0,0,0,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,0,0,0,0,0,0,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,0,0,0,0,0,0,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,0,0,0,0,0,0,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,0,0,0,0,0,0,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,0,0,0,0,0,0,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,0,0,0,0,0,0,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,0,0,0,0,0,0,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,0,0,0,0,0,0,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,0,0,0,0,0,0,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,0,0,0,0,0,0,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,0,0,0,0,0,0,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,0,0,0,0,0,0,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,0,0,0,0,0,0,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,0,0,0,0,0,0,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,0,0,0,0,0,0,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,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}};
int main() {
 float posX = 3, posY = 4;
 float dirX = 1, dirY = 0; //direction vector
 float planeX = 0, planeY = 0.66; //camera plane
 float time = 0;
 float oldtime = 0; //for FPS calculations
 SDL_Window* window = NULL; //init SDL
 SDL_Renderer* renderer = NULL;
 SDL_Surface* surface = NULL;
 if( SDL_Init( SDL_INIT_VIDEO ) < 0 ) {
 printf( "SDL could not initialize! SDL_Error: %s\n", SDL_GetError() );
 }
 window = SDL_CreateWindow("SDL Window", SDL_WINDOWPOS_UNDEFINED, SDL_WINDOWPOS_UNDEFINED, RESX, RESY, SDL_WINDOW_SHOWN );
 if( window==NULL) {
 printf( "SDL_Error: %s\n", SDL_GetError() );
 }
 surface = SDL_GetWindowSurface( window );
 renderer = SDL_CreateRenderer( window, -1, SDL_RENDERER_ACCELERATED);
 if(renderer==NULL) {
 printf("Renderer error: %s\n", SDL_GetError() );
 }
 char running = 1;
 const Uint8* keystate = SDL_GetKeyboardState( NULL );
 clock_t t1, t2;
 while( running == 1 ) {
 t1 = clock();
 SDL_Rect rect;
 rect.w = 1;
 SDL_Event e;
 SDL_SetRenderDrawColor( renderer, 0x11, 0x11, 0x11, 0xFF);
 SDL_RenderClear( renderer );
 if( SDL_PollEvent( &e ) > 0) {
 if( e.type == SDL_QUIT) running = 0;
 }
 float oldPlaneX, oldDirX;
 if(keystate[SDL_SCANCODE_RIGHT]) {
 oldDirX = dirX;
 dirX = dirX * cos(ROTSPEED) - dirY * sin(ROTSPEED);
 dirY = oldDirX * sin(ROTSPEED) + dirY * cos(ROTSPEED);
 oldPlaneX = planeX;
 planeX = planeX * cos(ROTSPEED) - planeY * sin(ROTSPEED);
 planeY = oldPlaneX * sin(ROTSPEED) + planeY * cos(ROTSPEED);
 }
 if(keystate[SDL_SCANCODE_LEFT]) {
 oldDirX = dirX;
 dirX = dirX * cos(-ROTSPEED) - dirY * sin(-ROTSPEED);
 dirY = oldDirX * sin(-ROTSPEED) + dirY * cos(-ROTSPEED);
 oldPlaneX = planeX;
 planeX = planeX * cos(-ROTSPEED) - planeY * sin(-ROTSPEED);
 planeY = oldPlaneX * sin(-ROTSPEED) + planeY * cos(-ROTSPEED);
 }
 if(keystate[SDL_SCANCODE_D]) {
 if(keystate[SDL_SCANCODE_W] ^ keystate[SDL_SCANCODE_S]) {
 if(!MAP[(char)(posX-dirY*STRAFEMOVESPEED)][(char)posY]) posX-=dirY*STRAFEMOVESPEED;
 if(!MAP[(char)posX][(char)(posY-dirX*STRAFEMOVESPEED)]) posY+=dirX*STRAFEMOVESPEED;
 }
 else {
 if(!MAP[(char)(posX-dirY*MOVESPEED)][(char)posY]) posX-=dirY*MOVESPEED;
 if(!MAP[(char)posX][(char)(posY-dirX*MOVESPEED)]) posY+=dirX*MOVESPEED; 
 }
 }
 if(keystate[SDL_SCANCODE_A]) {
 if(keystate[SDL_SCANCODE_W] ^ keystate[SDL_SCANCODE_S]) {
 if(!MAP[(char)(posX+dirY*STRAFEMOVESPEED)][(char)posY]) posX+=dirY*STRAFEMOVESPEED;
 if(!MAP[(char)posX][(char)(posY-dirX*STRAFEMOVESPEED)]) posY-=dirX*STRAFEMOVESPEED;
 }
 else {
 if(!MAP[(char)(posX+dirY*MOVESPEED)][(char)posY]) posX+=dirY*MOVESPEED;
 if(!MAP[(char)posX][(char)(posY-dirX*MOVESPEED)]) posY-=dirX*MOVESPEED; 
 }
 }
 if(keystate[SDL_SCANCODE_W]) {
 if(keystate[SDL_SCANCODE_D] ^ keystate[SDL_SCANCODE_A]) {
 if(!MAP[(char)(posX+dirX*STRAFEMOVESPEED)][(char)posY]) posX+=dirX*STRAFEMOVESPEED;
 if(!MAP[(char)posX][(char)(posY+dirY*STRAFEMOVESPEED)]) posY+=dirY*STRAFEMOVESPEED;
 }
 else {
 if(!MAP[(char)(posX+dirX*MOVESPEED)][(char)posY]) posX+=dirX*MOVESPEED;
 if(!MAP[(char)posX][(char)(posY+dirY*MOVESPEED)]) posY+=dirY*MOVESPEED;
 }
 }
 if(keystate[SDL_SCANCODE_S]) {
 if(keystate[SDL_SCANCODE_D] ^ keystate[SDL_SCANCODE_A]) {
 if(!MAP[(char)(posX-dirX*STRAFEMOVESPEED)][(char)posY]) posX-=dirX*STRAFEMOVESPEED;
 if(!MAP[(char)posX][(char)(posY-dirY*STRAFEMOVESPEED)]) posY-=dirY*STRAFEMOVESPEED;
 }
 else {
 if(!MAP[(char)(posX-dirX*MOVESPEED)][(char)posY]) posX-=dirX*MOVESPEED;
 if(!MAP[(char)posX][(char)(posY-dirY*MOVESPEED)]) posY-=dirY*MOVESPEED;
 }
 }
 if(keystate[SDL_SCANCODE_SPACE]) {
 MAP[(char)(posX+dirX*placeDist)][(char)(posY+dirY*placeDist)] = 1;
 }
 if(keystate[SDL_SCANCODE_LCTRL]) {
 MAP[(char)(posX+dirX*placeDist)][(char)(posY+dirY*placeDist)] = 0;
 }
 if(keystate[SDL_SCANCODE_LSHIFT]) {
 MAP[(char)posX][(char)posY] = 0;
 }
 for(int z = 0; z < RESX; z += 1 ) { //raycasting code 
 rect.x = z;
 float cameraX = 2 * z/(float)RESX -1; // cam vector, -1 to 1
 float raydX = dirX + planeX * cameraX; // frustum thingy
 float raydY = dirY + planeY * cameraX;
 unsigned char mapX = (char)posX;
 unsigned char mapY = (char)posY;
 float sdistX;
 float sdistY;
 float deltaX = fabsf(1/raydX);
 float deltaY = fabsf(1/raydY);
 float pWallDist;
 char stepX;
 char stepY;
 char side; //either 0 (NS), or 1 (EW)
 if(raydX < 0) {
 stepX = -1;
 sdistX = (posX - mapX) * deltaX; // one side
 }
 else {
 stepX = 1;
 sdistX = (mapX + 1.0 - posX) * deltaX; // have to round the other way for this side.
 }
 if(raydY < 0) {
 stepY = -1;
 sdistY = (posY - mapY) * deltaY; // one side
 }
 else {
 stepY = 1;
 sdistY = (mapY + 1.0 - posY) * deltaY; // have to round the other way for this side.
 }
 for( unsigned char step = 0; step < 26; step +=1 ) {
 if(sdistX<sdistY){
 sdistX += deltaX;
 mapX += stepX;
 side = 0;
 }
 else {
 sdistY += deltaY;
 mapY += stepY;
 side = 1;
 }
 if(MAP[mapX][mapY] !=0) step = 27;
 }
 if(side == 0) pWallDist = (mapX - posX + (1-stepX) / 2) / raydX;
 else pWallDist = (mapY - posY + (1-stepY) / 2) / raydY;
 int lineHeight = (int)( RESY / pWallDist);
 signed int drawColour = 255-pWallDist*15;
 if(drawColour < 0x11) drawColour = 0x11;
 SDL_SetRenderDrawColor( renderer, drawColour, drawColour, drawColour, 0xFF);
 rect.h = lineHeight*2;
 rect.y = (RESY/2 - lineHeight);
 SDL_RenderDrawRect( renderer, &rect);
 }
 SDL_RenderPresent( renderer );
 t2 = clock();
 float ms = (float)(t2-t1)/1000.0;
 printf("%f\n", ms );
 if(ms < 16) SDL_Delay(16.0 - ms);
 }
 SDL_DestroyWindow( window );
 SDL_Quit();
}
```

• Mast: Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers .

Answer 1

Code:

#include <sys/time.h>

Note that this isn't cross-platform. We can use SDL_GetTicks() instead.

---

const int RESX = 960;
const int RESY = 540;
const float ROTSPEED = 0.03;
const float MOVESPEED = 0.08;
const float STRAFEMOVESPEED = 0.05657;
char placeDist = 3;
char MAP[32][32] = {

I don't think any of these need to be globals. We could declare them in main instead. It might be worth grouping some of them into a settings struct.

---

char MAP[32][32]

We should use named variables, instead of magic numbers.

---

 float posX = 3, posY = 4;
 float dirX = 1, dirY = 0; //direction vector
 float planeX = 0, planeY = 0.66; //camera plane

These aren't used until after we've initialized SDL, so we can (and should) declare them later.

---

 if( SDL_Init( SDL_INIT_VIDEO ) < 0 ) {
 printf( "SDL could not initialize! SDL_Error: %s\n", SDL_GetError() );
 }

If we fail to initialize sdl, we probably shouldn't continue running the program! We could add a return EXIT_FAILURE; in there. The same problem exists with the window and renderer.

It would be neater to move the SDL initialization into a separate function.

---

 char running = 1;

We could use <stdbool.h> for this.

---

 SDL_Rect rect;
 rect.w = 1;

This isn't used in the input handling, so it can be declared later.

---

 float oldPlaneX, oldDirX;
 if(keystate[SDL_SCANCODE_RIGHT]) {
 oldDirX = dirX;
 dirX = dirX * cos(ROTSPEED) - dirY * sin(ROTSPEED);
 dirY = oldDirX * sin(ROTSPEED) + dirY * cos(ROTSPEED);
 oldPlaneX = planeX;
 planeX = planeX * cos(ROTSPEED) - planeY * sin(ROTSPEED);
 planeY = oldPlaneX * sin(ROTSPEED) + planeY * cos(ROTSPEED);
 }
 if(keystate[SDL_SCANCODE_LEFT]) {
 oldDirX = dirX;
 dirX = dirX * cos(-ROTSPEED) - dirY * sin(-ROTSPEED);
 dirY = oldDirX * sin(-ROTSPEED) + dirY * cos(-ROTSPEED);
 oldPlaneX = planeX;
 planeX = planeX * cos(-ROTSPEED) - planeY * sin(-ROTSPEED);
 planeY = oldPlaneX * sin(-ROTSPEED) + planeY * cos(-ROTSPEED);
 }

Yikes. We could really do with a vec2 struct, and some math functions (vec2_rotate, vec2_add, vec2_sub etc.)

It would be neater (and less repetitious) to apply the camera movement as a separate stage after getting the input. We just need to set a variable to +1.f when the right key is pressed, and -1.f when the left key is pressed. Then we multiply the ROTSPEED by this variable. e.g.:

struct vec2 {
 float x, y;
};
struct vec2 vec2_rotate(struct vec2 v, float angle) {
 struct vec2 out;
 out.x = v.x * cos(angle) - v.y * sin(angle);
 out.y = v.x * sin(angle) + v.y * cos(angle);
 return out;
}
...
 float rotation = 0.f;
 if (keystate[SDL_SCANCODE_RIGHT]) rotation += +1.f;
 if (keystate[SDL_SCANCODE_LEFT]) rotation += -1.f;
 if (rotation != 0.f) {
 float angle = rotation * ROTSPEED;
 dir = vec2_rotate(dir, angle);
 plane = vec2_rotate(plane, angle);
 }

We can do a similar thing for the other movement inputs.

---

Note that we need to take into account the frame-rate when applying the movement in order to be completely consistent with the speed at which the camera moves. We might need to use an accumulator or something similar.

---

 for (unsigned char step = 0; step < 26; step += 1) {
 ...
 if (MAP[mapX][mapY] != 0) step = 27;
 }

26 deserves a variable name. We should also use break; to escape the loop instead of changing the loop variable (it won't stop working if we change the number of steps, or the loop condition).

---

The raycasting code should really be moved into a separate function returning the distance.

It would be a good idea to handle maps that aren't bounded by walls (we'd need to check that we don't step out of bounds).

---

Performance:

The ray-casting code is already very fast. Drawing to the screen and calling SDL_RenderPresent takes the most time, and there's probably not a lot we can do about that.

Note that SDL_RenderDrawRect is actually for outlining rectangles, so it draws multiple lines internally. So technically we should be using SDL_RenderFillRect instead, though it doesn't seem to make much of a difference in performance.

Answer 2

In all, this code is not bad, but there are some ways I think it might be improved.

Fix the bug

If the user hits the space key, it fills in a block and a left cntl removes it. Unfortunately, although the arena is fenced when the program starts, the user is not prevented from removing the fence blocks and wandering outside the allocated memory. This, of course, is a serious bug that should be addressed.

Decompose your program into functions

All of the logic here is in main in one rather long and dense chunk of code. It would be better to decompose this into separate functions.

Use <stdbool.h> for boolean types

The running variable is used as a boolean value, but is declared as a char. It would be clearer to readers of the code if instead of this:

char running = 1;
while( running == 1 ) {

write this:

for (bool running = true; running; ) {

Prefer logical evaluation to if

The code contains these lines:

if( SDL_PollEvent( &e ) > 0) {
 if( e.type == SDL_QUIT) running = 0;
}

Especially in combination with the suggestion above, I think this would be more clearly expressed like this:

running = !( SDL_PollEvent( &e ) > 0 && e.type == SDL_QUIT);

Write portable code where practical

The code uses #include <sys/time.h> and has these lines:

t2 = clock();
float ms = (float)(t2-t1)/1000.0;
printf("%f\n", ms );
if(ms < 16) SDL_Delay(16.0 - ms);

This is not portable code. First, the standard location is <time.h> (no sys). Second, this assumes that clock() is measuring in seconds, but that's not actually required by the C standard. Instead, to get milliseconds, one could write this:

t2 = clock();
float ms = (float)(t2-t1)/CLOCKS_PER_SEC*1000.0;
printf("%f\n", ms );
if(ms < 16) SDL_Delay(16.0 - ms);

Note, however, SDL_Delay is not that fine-grained and may not be doing what you intend. See this game-dev answer for details.

Be careful with signed vs. unsigned

In C, array access via subscripting is done with unsigned integer subscripts, but this code casts the subscript to char in many places. That's a potential problem because char is signed for some compilers. Better would be to use a size_t type.

Eliminate "magic numbers"

There are a few numbers in the code, such as 0x11 and 16 and 27 that have a specific meaning in their particular context. By using named constants such as wall_color or ms_per_loop, the program becomes easier to read, understand and maintain.

Use an appropriate data structure

The code is full of separate lines that separately update an \$x\$ and \$y\$ coordinate. What would make the code simpler to read, understand and maintain, would be to create and use a structure for both like this:

typedef struct {
 float x;
 float y;
} Point2D;
void rotate(Point2D* p, float rotangle) {
 float oldX = p->x;
 p->x = p->x * cos(rotangle) - p->y * sin(rotangle);
 p->y = oldX * sin(rotangle) + p->y * cos(rotangle);
}

This enables changing this:

 if(keystate[SDL_SCANCODE_RIGHT]) {
 oldDirX = dirX;
 dirX = dirX * cos(ROTSPEED) - dirY * sin(ROTSPEED);
 dirY = oldDirX * sin(ROTSPEED) + dirY * cos(ROTSPEED);
 oldPlaneX = planeX;
 planeX = planeX * cos(ROTSPEED) - planeY * sin(ROTSPEED);
 planeY = oldPlaneX * sin(ROTSPEED) + planeY * cos(ROTSPEED);
 }

To this:

 if(keystate[SDL_SCANCODE_RIGHT]) {
 rotate(&dir, ROTSPEED);
 rotate(&plane, ROTSPEED);
 }

Eliminate unused variables

Unused variables are a sign of poor code quality, so eliminating them should be a priority. In this code, surface, oldtime and time are unused. My compiler also tells me that. Your compiler is probably also smart enough to tell you that, if you ask it to do so.

Eliminate global variables where practical

The code declares and uses a number of global variables. Global variables obfuscate the actual dependencies within code and make maintainance and understanding of the code that much more difficult. It also makes the code harder to reuse. For all of these reasons, it's generally far preferable to eliminate global variables and to instead pass pointers to them. That way the linkage is explicit and may be altered more easily if needed. It may also be handy to collect such variables into structures.

Don't Repeat Yourself (DRY)

The movement operations all include a lot of very similar repeated code. Instead of repeating code, it's generally better to make common code into a function. In this case, I'd replace the lengthy and repetitive code that handles the D, A, W and S keys with this:

float velocity = ((keystate[SDL_SCANCODE_D] ^ keystate[SDL_SCANCODE_A]) &&
 (keystate[SDL_SCANCODE_W] ^ keystate[SDL_SCANCODE_S])) ? STRAFEMOVESPEED : MOVESPEED;
Point2D oldpos = pos;
if(keystate[SDL_SCANCODE_D]) {
 pos.x -= dir.y * velocity;
 pos.y += dir.x * velocity;
}
if(keystate[SDL_SCANCODE_A]) {
 pos.x += dir.y * velocity;
 pos.y -= dir.x * velocity;
}
if(keystate[SDL_SCANCODE_W]) {
 pos.x += dir.x * velocity;
 pos.y += dir.y * velocity;
} 
if(keystate[SDL_SCANCODE_S]) {
 pos.x -= dir.x * velocity;
 pos.y -= dir.y * velocity;
} 
adjustCollision(&pos, &oldpos, map);

This assumes that pos and dir are Point2D structures as mentioned above and that the adjustCollision function will prevent moving in a direction that is blocked by a wall.

Answer 3

Math related review.

Rather than use double functions, float functions make more sense for speed.

// dir.x = dir.x * cos(rotspeed) - dir.y * sin(rotspeed);
dir.x = dir.x * cosf(rotspeed) - dir.y * sinf(rotspeed);
// same for the remaining function.

or if precision is important, consider changing all float objects to double.

---

Likewise, rather than use double constants (which cause the computation to occur as double), use float constants. Many locations.

// sdistX = (map.x + 1.0 - pos.x) * deltaX
sdistX = (map.x + 1.0f - pos.x) * deltaX

---

char is a poor type to use for variables/casts involved in math computation here. It incurs twice the testing needed to see if it works as an unsigned char or signed char. Use signed char or unsigned char. Save char for text processing, not math.