A few months ago I started experimenting with raycasting. It's basically the concept of drawing an imaginary line between two points and checking if it hits anything solid on the way. In computer graphics it's one way to create a 3d-esque environment. In this blog post I'll only cover how this ray casting principle works. Later we'll work our way up to a Wolfenstein-esque environment. That means horizontal 360 degrees first person movement only. So no looking up or down. But we start with top-down raycasting like in a mini map.
First the demo. It's not super clean, this was an early development phase so just take it for what it's worth.
Here's a fiddle for it. Use A and S to change the angle. Arrow keys to move around. The white "ray" helps you to confirm which cells were cut through and which weren't. The red lines make up your field of view (FOV) and are cut off when they collide. Their distance is not yet properly computed which is why they bleed into cells when colliding at angles. We'll fix that :) The green dots on the "green" cells indicate which side the ray collided which is important to determine which image to draw for it.
I'm not going to give you a full rundown of the code but let's quickly go through it.
We setup a fixed unit size and only work with values in terms of this unit internally. This makes the app cleaner and easier to work with and coordinates map 1:1 to cells. On top of that you'll only have to adjust the unit size in order to scale the view up or down. In this app we use a square unit, so width is equal to height. This simplifies a few things and at least prevents us from juggling both a width and height unit.
The map is declared in a super trivial format which is visualized with whitespace:
var map = [
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,
0,1,1,1,0,0,0,0,1,0,0,0,0,0,0,
0,1,1,1,1,0,1,1,1,0,0,0,0,0,0,
0,1,1,0,0,0,1,0,1,0,0,0,0,0,0,
0,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,
];
Look at that and the canvas above. Look similar? In this map zero means solid and one means open. But you probably figured that out already ;) Painting the tiles is done in a simple loop. Nothing weird here. Nearly no math involved.
The rays are different. Lot's of math involved here. We set a FOV (somewhere between 60 and 120) and cast a ray for each of them.
var DEGRAD = (1/180)*PI; // "radians per degree", go with it
var PI2 = Math.PI * 2; // full circle in radians
var heading = 0.25 * Math.PI; // radians. note: when you look to the RIGHT this is 0
var FOV = 60; // degrees, 30 left and right of heading
FOV = (FOV/180)*PI; // to radians
var FOV_2 = FOV / 2; // how wide left and right of center
var start = (heading - FOV_2) % PI2;
var stop = (heading + FOV_2) % PI2;
for (var ang = start; ang < stop; ang += DEGRAD) {
cast(px, py, ang);
}
cast(px, py, ph);
The math basically involves converting degrees (a circle is 360 degrees) to radians (a circle is
2 pi or
6.28 radian) because that's what the angle functions work with in JavaScript (and many other languages). We determine how many degrees or radians are covered by a single ray and we cast those rays such that they cover the entire FOV. You can see in the example above that the rays sort of create an angle of 60 degrees and that they rays are evenly spread between. The further the rays get, the wider spread out they become.
Casting here means "brute forcing" the check for a collision. It will start at the current position and follow the line checking in every cell it passes through whether it is solid, open, or out of bounds (OOB). While it'd be easy to do this for straight horizontal and vertical lines (every cell intervals at step
1) and even vertical in a square unit environment, it's slightly more tricky for any other angle. In a slope you may pass up to three cells in a single unit distance. You must check all of them because otherwise you may just be cutting corners.
We can get all the cells by computing the
slope of the ray. More precisely, we'll get the exact horizontal and vertical increment of the position we need to move exactly one unit further on the ray. Using the heading this is what
Math.cos and
Math.sin gives us:
var dx = Math.cos(angle);
var dy = Math.sin(angle);
Like I said we may cut through up to three cells so for every unit moved on the ray we need to do up to three checks:
[x+dx, y], [x, y+dy], [x+dx, y+dy]. We floor each of these coordinates and check the cell that corresponds to these ints (unit size really helps here) in the array we declared above.
Once we know the ray collided with something solid we can get the exact distance from your origin to the side of the cell that was hit to draw a better line. This involves some more math but even without it, with just collision detection and painting the rays as we have them you can already get the clear impression of environmental solid detection. As you can see above :)
Next time we'll use this technique to create a "3d" Wolfenstein environment, so horizontally looking 360 degrees around you but not up or down.