Cacomania: Canvas Raycaster

Cacomania

Canvas Raycaster

Guido Krömer - 27. December 2012 - Tags: , ,

When I was young I loved Games like Wolfenstein 3D, Nitemare 3D, Corridor 7: Alien Invasion and of course Doom or Duke Nukem 3D. Since Doom and Duke Nukem 3D using complex raycaster engines with a BSP for storing the map and evaluating which parts has to be drawn I'm going to try a Wolfenstein 3D like raycaster, which is very simple and can be implemented very easy in JavaScript using the canvas element for drawing. Raycaster with default settings on Opera

Raycasting gray theory

Raycasting is a technique for faking the impression of 3D, but it's 2D indeed. The map is a grid of squares/tile based map which can be stored into a two dimensional array. For each pixel in the width a ray gets cast from the player's position until it is hitting a wall, the length of the ray determines how large a vertical line will be drawn at the given width.

Raycasting gray theory part 1
The green object is the player's position and the blue area is the view of field by the given direction the player is looking at.

Raycasting gray theory part 2, casing rays
Now a ray is cast for each pixel in the width, at a resolution of 320x240 pixel 320 rays would be cast and 1920 if we would render the scene in Full HD. For casting a ray we need the angle the player is looking at and the VOF, the VOF is set to 60° by default, but it could be set to 90° or even 360° which looks really funny. The VOF is stored as radiant. With the VOF we can calculate the angle for a single ray, which is RAY_ANGLE = VOF / SCR_W;, SCR_W is the width of the screen. Through those precalculations the single ray angles can be calculated by simple additions: for (var rayAngle = -VOF_HALF; rayAngle < VOF_HALF; rayAngle += RAY_ANGLE), VOF_HALF is just the precalculated half VOF. With the rayAngle a point far away from the player's position with the given angle can be calculated:

var dx = this.player.x + Math.cos(this.player.angle + rayAngle) * 100;
var dy = this.player.y + Math.sin(this.player.angle + rayAngle) * 100;

Casting a ray

The point (dx, dy) is used for casting a ray from the player's position in the given angle and get passed to the this.getLine(this.player.x, this.player.y, dx, dy, lineElement); method. The lineElement is passed by reference which prevents continuous instantiating of this object which contains the point where the ray hits a wall, the color of the wall tile and an inexact distance (which is the number of iterations until the ray hits the wall). The getLine() method if a modified version of Bresenham's line algorithm which breaks if a wall was hit and returns some other information off course.

Raycasting, casting a single ray.
The ray does not get cast above the tiles.

Raycasting, casting a single ray in detail.
The ray get cast with the resolution defined in TILE (This should be 64 by default).

This is the ray casting method in detail:

this.getLine = function(x1, y1, x2, y2, lineElement) {
  var dx = Math.abs(x2 - x1);
  var dy = Math.abs(y2 - y1);
  var sx = (x1 < x2) ? 1 : -1;
  var sy = (y1 < y2) ? 1 : -1;
  var err = dx - dy;
  var e2;
  var perviousTileX = 0;
  var perviousTileY = 0;
  var distance = 0;

  while (!((x1 == x2) && (y1 == y2))) {
    e2 = err << 1;
    if (e2 > -dy) {
      err -= dy;
      x1 += sx;
      distance++;
    }
    else if (e2 < dx) {
      err += dx;
      y1 += sy;
      distance++;
    }

    var mapX = Math.floor(x1 / TILE);
    var mapY = Math.floor(y1 / TILE);

    if (this.map[mapY][mapX]) {
      lineElement.y = y1;
      lineElement.x = x1;
      lineElement.color = this.map[mapY][mapX];
      lineElement.north = perviousTileX == mapX;
      lineElement.dist = distance;

      return;
    }
    perviousTileX = mapX;
    perviousTileY = mapY;
  }
}

The map is stored into the two dimensional array map, determining on which tile the ray actually is can be done by dividing the point through the tile factor TILE and flooring it. The distance is as mentioned before just an approximated value of the distance. The north field determines the side of the wall which was hit by the ray, this value can be used later for displaying the sides with a different brightness values for improving the look and feel of the 3D effect.

Drawing the walls

Drawing a line element is really simple, the variable i determines the pixel in the width and wallFactor is the half height of the wall to draw on the screen. SCR_H_HALF is a precalculated "constant" containing the half height of the screen in pixel.

var wallFactor = SCR_H_HALF / lineElement.dist * TILE_QUATER
ctx.strokeStyle = this.getColor(lineElement);
ctx.beginPath();
ctx.moveTo(i, SCR_H_HALF - wallFactor);
ctx.lineTo(i, SCR_H_HALF + wallFactor);
ctx.closePath();
ctx.stroke();

Raycaster without depth correction.
The result might look a little odd, that is because the distance has not be calculated correctly, it is just the distance approximated by the getLine() method. The correct distance can be calculated by taking the magnitude of the vector (player - lineElement) multiplied by the cosine of the rayAngle, without the cosine multiplication we would have a fish eye effect.
Raycaster Fisheye Effect
The graphic above show why the fish eye effect occurs, the player is looking towards the wall, the ray (A) calculated for the screen center is shorter than the ray (B) which angle would be 330° at a 60° VOF. Parts of the wall which are far away are drawn smaller so the part of the wall hit by ray B gets drawn smaller than the element which was hit by ray A.

Raycaster with default settings on Opera

The depth shading is achieved by using the getColor() method if depthShading is set to true. Using the lineElement.north field makes walls which side is north a little bit lighter than the others, the higher the distance is the darker the wall gets drawn.

this.getColor = function(lineElement) {
  if (!this.depthShading) {
    return COLORS[lineElement.color];
  }

  var dist = lineElement.dist / (TILE_QUATER / 16);
  var factor = Math.ceil(lineElement.north ? 255 - dist * 1.3 : 255 - dist * 1.5);
  return COLORS[lineElement.color].replace('255', factor).replace('255', factor);
}

With disabled depth shading the result will look like this:
Raycaster without depthshading.

Game management

The game management is based upon the GameManager that I had already used in this article: Speeding up canvas drawing by scaling it with CSS3, the raycaster itself is just a simple GameObject. This keeps timing and drawing logic out of the RayCaster class itself.

The raycaster in 4 different resolutions/scale factors.
Scaling up to archive a better performance can be done, too.

If you want to test the ray caster go to this demo page.

Finally here is the whole code of the RayCaster class, the rest of the code is in the gist.

Some fun with the VOF

As mentioned before a larger VOF than 60-90° will look really funny, the screen shot below shows the scene with a VOF of 180°:
The Raycaster at a 180° VOF

If you want to look at all directions try a VOF of 360° :D
The Raycaster at a 360° VOD

Conclusion

I hope you liked my article about basic raycasting, in the next one I am going to add textured walls and maybe sprites to the raycaster and turn this little demo into a real game :) .