Raycasting 2.5d on canvas

2015-03-01

One of the simpler ways of getting a cheap but good 3d experience is raycasting. This is sometimes referred to as "2.5d" instead of 3d because you only get a horizontal free look. That is, you look left and right and behind you but not up or down. One of the earliest big games that used this approach was Wolfenstein.

I've already published a post about raycasting yesterday so if you want to know how the ray casting itself works, go read that first. I'll wait here.

How do we get from having casted some rays to the actual rendering of a 2.5d environment? Well, a bit of math and a bit of straightforward thinking.

Ok first we need a texture. The walls of our environment need to be painted somehow and for this we need a texture. For now I'll just generate them randomly:

Code:
var canvas = document.querySelector('#e1');
var ctx = canvas.getContext('2d');

canvas.width = 800;
canvas.height = 100;

function rcolor() {
return '#'+(Math.floor(Math.random()*(0xffffff-0x100000)+0x100000).toString(16);
}

for (var i=0; i<8; ++i) {
var g = Math.random() > .5
? ctx.createRadialGradient(i*100+50, 50, 0, i*100+50, 50, 100)
: ctx.createLinearGradient(i*100, 0, i*100+100, 100);

g.addColorStop(0, rcolor());
g.addColorStop(1, rcolor());
ctx.fillStyle = g;
ctx.fillRect(i*100, 0, 100, 100);
}




Our map is (again) a single dimension array with indexes referring to these "textures". Zero is open so the indexes should subtract one to map to the texture index. We'll define the map with xes and spaces (okay Alexander? ;) and assign random texture indexes to the the xes.

Code:
var map = [
'xxxxxxxxxxxxxxx',
'x x x x',
'x xx xxx x x',
'x x x',
'xxxxxxxxxxxxxxx',
].join('').split('').map(function(s){
// spaces are open, xes are a random texture
if (s === ' ') return 0;
return 1+Math.floor(Math.random()*8);
});

var width = 15;
var height = 5;
var unit = 50;

var canvas = document.querySelector('#e2');
var ctx = canvas.getContext('2d');
canvas.width = width*unit;
canvas.height = height*unit;

for (var x=0; x for (var y=0; y if (map[y*width+x]) {
ctx.drawImage(textures, (map[y*width+x]-1)*100, 0, 100, 100, x*unit, y*unit, unit, unit);
}
}
}




Now that we have our map and know how to do raycasting, let's construct our field of view.

Each cast ray reflects a certain number of pixels of your viewport. How much really just depends on the size of your canvas and the number of rays. Two rays will make each ray fill 50% of the view and give you a terrible experience. The more rays the better the quality and the more computing time it'll need. Of course the upper limit is where a ray becomes smaller than the smallest unit you can paint.

Let's create a canvas of 500px wide. The height is irrelevant for this approach, it kinda only depends on your textures. We'll use a field of view (FOV) of 100 degrees. We'll display 100 "rays" on a 500 pixel canvas so each ray is 1 degree and covers 5 pixels.

Code:
var FOV = 100;
var width = 500;
var rays = 100;
var degRay = FOV / rays;
var pxRay = width / rays;

We'll use an optimized version of cast() compared to the function we defined before and cast rays from our current position in the specified angle left to right keeping our heading at the center of it, keep something like this in mind (fiddle):




Going from left (red to right (green) we take cast a ray at heading - (FOV / 2) + (i * degRay) degrees. Well we'll do it in radians but same difference.

Let's take a look at the middle ray and see what we get. We look at 30 degrees (offset east) and are in the middle of the <1,1> cell the ray. So x=1.5, y=1.5, h=30/180*Math.PI. If we cast on that using the above map the <3,2> cell is the first solid cell to be hit by the center ray (fiddle).




The next steps are to figure out which side of the cell was hit, which texture should be painted on that side (all sides of a cell have same texture in our model) and get the proper slice of texture.

To find out which side was hit we'll have to an intersection check. There are four sides to possibly hit, but you can only see two sides at the same time tops from any point so our rays can only hit one of those two sides. Our casting gives us a position where we know it's inside a solid cell for the first time. We can use this to determine whether it's to the left or right and higher or lower to our starting position. This allows us to determine whether it's the left or right and upper or lower side that may be hit by the ray at all.

Next we do one or two intersect checks to see whether the line of the ray cross the line of the cell side (fiddle).

Code:
function intersects(ax, ay, aax, aay, bx, by, bbx, bby, side){
var sax = aax - ax;
var say = aay - ay;
var sbx = bbx - bx;
var sby = bby - by;

var s = (-say * (ax - bx) + sax * (ay - by)) / (-sbx * say + sax * sby);
var t = ( sbx * (ay - by) - sby * (ax - bx)) / (-sbx * say + sax * sby);

if (s >= 0 && s <= 1 && t >= 0 && t <= 1) {
var x = ax + (t*sax);
var y = ay + (t*say);

return {x:x, y:y, side:side};
}

return null;
}
function collides(x1, y1, x2, y2, cx, cy) {
// which side may be hit
var rightward = x1 < x2;
var downward = y1 < y2;

// t will end up with the intersection coordinate, or null if there was no hit
var t = null;
if (downward) t = intersects(x1, y1, x2, y2, cx, cy, cx+1, cy, 'up');
if (rightward && !t) t = intersects(x1, y1, x2, y2, cx, cy, cx, cy+1, 'left');
if (!downward && !t) t = intersects(x1, y1, x2, y2, cx, cy+1, cx+1, cy+1, 'down');
if (!rightward && !t) t = intersects(x1, y1, x2, y2, cx+1, cy, cx+1, cy+1, 'right');

return t;
}

var width = 15;
var height = 5;
var unit = 50;

// position
var x = 1.5;
var y = 1.5;
var heading = 30 /180*Math.PI;

// end of ray if we ignore collisions
var ex = x + width * height * Math.cos(heading);
var ey = y + width * height * Math.sin(heading);

var cell = cast(x, y, heading);
var collision = collides(x, y, ex, ey, cell.x, cell.y);
// cell: 3, 2
// collision: 3, 2.37, left

Besides needing the cell face that was hit, we also need the exact collision coordinate to determine the length of the ray. The length determines how much we need to scale the ray because rays become smaller as they are further away from you.

Since we have the exact collision coordinate now and our start position we can get the length of the ray by the Pythagorean theorem: Math.sqrt(Math.pow(x-collision.x, 2) + Math.pow(y-collision.y, 2)) = 1.73. So we have to draw the center ray at 1.7 units away from us.

Another reason we need the exact collision point is because that's where we will be taking our ray sample from. We will take a small slice of the texture at this point. In the example it hits on the side at 2 x 2.37, which means it looks at the texture 37% from the left.

We have a number of rays that cover our viewport so each ray covers width/rays pixels. Again, the height is only relevant when scaling, we always take the full height of the texture.

Scaling is a bit tricky. We have to decide how the set unit relates to our viewport. Easiest is to say that the side of a cell spans the entire viewport exactly once at one unit distance. At two units distance two cells fit the viewport, etc. So at n units distance, n walls fit the screen. Height is actually the same except we'll never be painting more than one cell heigh and the cell is always vertically centered, which forms a horizon.

Code:
var rayLength = Math.sqrt(Math.pow(x-collision.x, 2) + Math.pow(y-collision.y, 2));
// how many texture pixels do we draw per screen pixel for this particular ray?
var texturePixelsPerScreenPixelX = (rayLength * unit) / viewport.width;
var texturePixelsPerScreenPixelY = viewport.height / unit / rayLength;
// get offset coord such that cell will be centered (we're painting middle ray)
var offsetX = width / 2;
var offsetY = (height / 2) - (texturePixelsPerScreenY * unit);
// which texture do we paint again?
var textureIndex = map[collision.x + collision.y * width];

// paint! we have all the details now
ctx.drawImage(
texture,
// read texture slice
Math.round(textureIndex*100), 0, RAYWIDTH * sourceWidthPerPixel, 100,
// write ray slice
offsetX, offsetY, RAYWIDTH, texturePixelsPerScreenPixelY * UNIT
);

Combining that together shows us this (fiddle):




That doens't look like much. First time I got this I was a bit skeptical on whether this was really going to work. I mean, something had to go wrong with these slices, right? Well... no. This is really what you're working with. And when you repeat this for all rays left to right, this is the result (fiddle):





That's already pretty cool! But there are three things wrong with this version. One is the so called "fish bowl effect", one is the fact that the textures are incorrectly sampled (you should see a radial gradient but you won't anywhere), and the third is that wide rays should have a slope as well (you can see jagged edges when walls are close by).

The fish bowl effect is best explained with the image below. The rays from the camera to the wall are longer as you move away from the center. That's correct. But since we're drawing it on a flat surface (your screen), we'll need to compensate for it.




To counter this effect we'll need to extend the length of the ray to take the additional distance into account. Luckily this is relatively simple to do, slightly more mathy to explain.

The fix is to do distance *= Math.cos(heading-angle);. The reason is that cos(heading-angle) = adjacent / hypotenuse (remember SOH CAH TOA?). We have the adjacent because it's the center distance from camera to the wall. We have the angle, of course. So to get the length of the hypotenuse (the actual length from camera to wall at given angle) is hypotenuse = adjacent * cos(heading-angle). So that's what we do :)

Same example as above but with the correction:




This model will still have some artifacts, but they are less impeding.

The next problem was about texture sampling. I'm not even sure what I was thinking there but I worked out a much better version of it.

It works as follows. The rays being casted intersect with a cell on some side. We already know exactly where the ray intersects with that side and which side it is (this is what we get in the collision object). Next we have to figure out how much of the cell that ray actually sees. The ray has a fixed angle size so we cast another ray, but skip the collision detection. Yes, this potentially allows us to look around corners but that's not a big issue. We draw the line and only figure out where that second ray (ray prime?) intersects with the line of the cell of the side that was crossed in the first place. We then have a precise part of texture that the ray may see (neglecting potential solid blocks) so we can read that from the texture and write that to the screen. There's some annoying checks involved for negative dx or dy to prevent mirroring the texture.




The orange line is the second line casted. No collision detection is done for it. We only use it to determine how much of the texture the ray actually sees.

With the proper texture sampling and drawing, clipped and what not, this is what we end up with. I'll draw some text inside the texture to demonstrate they are painted properly.






Aint that a pretty picture? :) You can move the mouse on the world to change angle, and in the mini map to change position. It's a bit clumsy and you'll quickly uncover a bug, but that's not very relevant here. The point is that the textures are, for the most part, properly and completely painted. Nearly no seams even though we're literally painting slices of the texture.

So the last serious artifact are the top and bottom edges. They should be smooth but they are ... well, crap. The reason for this artifact is that the distance of a slice is determined by the distance of the ray. But as we already know and computed, the distance to the other side of the ray is probably different. So the ray / slice should be painted with some slope. To be precise the ray must be painted as a side way trapezoid. But... html5 canvas apparently can't transform an image like that. There are some hacks of course. And that's all you get. Either live with the artifact or hack it out best you can.

One other alternative is to use webgl. But that's kind of defeating the point I guess :)

I've chosen to use a hack where I paint strips of single pixels and extrapolate their height. You take the length of the ray and rayPrime, the width of a ray in world pixels, and for each world ray pixel wide read off the according number of pixels from the texture. This way you can vary the height of the strip in a linear line between the end points. This leads to very smooth slopes, which kind of surprised me. I really thought the pixel strips would lead to a bunch of worse artifacts.

Observe the final result. You can click it to get a pointer lock. Movement with arrows or wasd. Input is not "properly" handled, you'll have to live with it.





Clickity click to toggle pointer lock :) You can edit this in the last fiddle, although note that pointer lock won't work inside jsfiddle (due to iframe).

So there you have it. Building a raycasted Wolfenstein-esque demo. Soon I'll publish something related to this but this has been lying on the shelf for quite some time now and I wanted to do an extensive post on it. So I guess this is it.

Hope you enjoyed it. pointers are welcome :)