This page chronicles the development of my javascript raycaster. Each version is built upon the previous versions, adding optimizations and new features to make it faster and better. Some of the commentary here was written well after the fact, so they may have inaccuracies and omissions.
I started with a basic rendering engine.
There's not a lot to say about how it works. Rays are cast from the camera and traced along the grid-based map until a wall is found.
For each ray cast, a div is created and sized based on the distance to the wall. Each div is 10px wide, and 80 rays are cast, for a 800px wide rendering area.
For each frame it clears the "frame buffer" by clearing it's innerHTML, and starts over. The blue "sky" is actually the top border and the grey walls are the background. The green floor is the container's background.
For this version the rendering has been completely rewritten. Instead of using fixed-width columns, it finds the edges between grid cells and tries to use a single div for each cell. So if you're close to a wall, only a few divs need to be used. If you're using Firebug or IE Dev Toolbar, you can see the sizes of the different columns.
Grid cell edges are found using binary search and are placed in a list:
function Split(ray1, ray2) {
// if the rays hit the same wall, there's no border between them
if (ray1.target == ray2.target) return;
// if the rays are right next to each other, there's an edge between them
if (ray1.x + 1 == ray2.x) {
edges.push(ray2);
edges.push(ray1);
} else {
// otherwise, they're far apart with at least 1 edge in between
newEdge = (ray1 + ray2) / 2;
Split(newEdge, ray2);
Split(ray1, newEdge);
}
}
function Render() {
edges = [];
edges.push(lastRay);
Split(firstRay, lastRay);
edges.push(firstRay);
while (edge1 = edges.pop()) {
edge2 = edges.pop();
AddColumn(edge1, edge2);
}
}
Far fewer divs are needed this way.
The other big step for this version is the higher-quality walls. By using a JavaScript border trick, we can get pixel-perfect angled walls. The walls you see are no longer the background of the divs, but the borders. The actual interior of the divs have a width of 0px. For example, walls that slant away to the left (like on the very right of the screenshot) use the right border. The top border is the blue sky, and the bottom border is the green ground. By adjusting the border sizes, we can get a slope of any angle.
Massive speed-up from simplifying the way HTML was being built. Previously, each column would be inserted into the frame independantly, then its style would be modified. It looked like this:
frameobj.innerHTML += "<div id=\"column " + id + "\"></div>";
var columnobj = document.getElementById("column" + id);
columnobj.style.borderTop = ...;
columnobj.style.borderBottom = ...;
etc.
Now, it builds the entire HTML string and then throws it into the frame object.
frameHTML +="<div id=\"column " + id + "\"" style=\"" frameHTML += "border-top: ...; "; frameHTML += "border-bottom: ...; "; frameHTML += "\"></div>";
This is much faster because the browser only has to handle re-rendering once each frame. Plus, it eliminates the flicker in Firefox.
I also added basic collision detection so you can't walk through walls anymore.
Holy crap it's a Cyber Demon.
Two things are appearant in the screenshot - sprites and a skymap - but much more has been added.
Sprites are just regular imgs that are absolutely positioned and scaled with a lot of boring math. To make them clip against the walls I had to make a few changes to the wall rendering and add z-indexing. You can't tell from the screenshot, but they're animated. Plus, the sargeant can actually face different directions (I haven't taken the time to prepare all the cyberdemon or imp sprites yet).
Sprites done using imagemaps, or sprite sheets, so a single image holds many sprites. Each sprite is rendered using a scaled img placed in a wrapper div that hides the overflow.
When I first uploaded this version, there was a problem with image caching that I didn't have locally. The issue was that browsers (at least Firefox and IE) don't use cached images if the only reference to the images is replaced. For example, all sprites are children of a single "frame" element. The entirety of the "frame" innerHTML is replaced each frame, so the image references are lost for a split second. This was solved by precaching the images in a hidden, static div.
The skymap is just an image that is positioned left or right when you turn. It's actually two instances of an image next to each other, to make the entire sky is covered.
I've thought about floormapping, but I haven't been able to find any way to do it. Floormapping can't be done by just sliding an image across the screen like skymapping. The floor image would need to change from frame to frame.
One thing you can't tell from the screenshot is that there's new controls: WASD + mouse, allowing multiple keypresses. So you can circle-strafe. It's Wii compatible, but you can't turn while moving.
I don't have a new screenshot, because it looks almost same as Version 3, but there are some significant changes. First, a few cosmetic updates:
A quick note about view-bobbing. It works by just sliding the walls up or down a little, based on their distance. The actual calculations using are only slightly more complex than the old ones. Instead of:
positionTop = parseInt((FRAMEHEIGHT - wallHeight) / 2);
it does:
positionTop = parseInt(FRAMEHEIGHT / 2.0 - wallHeight * (1 - cameraHeight));
If cameraHeight is 0.5, meaning half-way up the wall, you can see that the calculations are the same.
Also changed in this version is the string concatenation. As explained by Dennis Forbes, string concatenation can be slow. Previously, I was building the frame HTML using something like this:
frameHTML += newHTML1; frameHTML += newHTML2; ... frame.innerHMTL = frameHTML
It's faster to use an array:
frameHTML.push(newHTML1);
frameHTML.push(newHTML2);
...
frame.innerHTML = frameHTML.join("");
String handling doesn't take a lot of time here though, so this doesn't give much of a speed increase.
Something that did help the speed a lot was splitting each sprite into it's own file. The previous version used large sprite maps, so there were a bunch of 500x500 images being scaled and moved around, even though only a small portion of each would be shown. Putting each sprite in it's own image is much easier for the browser, even though it takes more image requests when loading.
Another speed increase came from changing the skymapping. I did a test with IE8 beta and noticed, among other things, that the sky wouldn't clip to the render area. My first attempt at fixing the overflow problem was to put the sky in with the rest of the frame, but dynamically creating and destroying two 2400x400 images each frame was hard on the browser. So I replaced the 2 imgs with a single div using a background image and background-offset to move it.
Well, the Cyber Demons are gone, but don't worry. To make up for it I've added ... stairs. Okay, maybe stairs - or, more accurately, variable-height walls - aren't as exciting as Cyber Demons, but it's a big step forward for the engine.
I tried a few different methods of raycasting and rendering (including replacing the raycasting with traditional projection and rasterising), but in the end a (relatively) simple extension of the previous version worked best. Instead of just casting a ray until the first wall is hit, the ray is continued until a full-height wall is hit, keeping a list of all the intersections in the process. The basic algorithm looks like this:
cast left-most ray case right-most ray compare lists of intersections if both rays hit the same wall, prepare the wall and the previous floor to be rendered if they hit different walls cast a new ray in the middle recurse the left half of the split recurse the right half of the split break
There are a few more details that caused a ton of rendering errors along the way (like when the left and right rays are adjacent, or keeping track of matching intersections between the lists, or keeping track of the bottom-most pixel that needs to be drawn). The most important thing is that line about preparing the wall and the floor to be rendered.
One thing the really slows down this version is that all the floors are now drawn, which needs to be done to cover up overdraw. Since the walls are no longer always full height - always extending both above and below the camera - the projected shape of a wall can no longer be drawn with a single div (that first stair, for example, would need to be split a few times). So, I simplified the rendering, making it so all rendered objects extend downward until the bottom is flat (so they're rectangles with slanted tops).
Floors were more complicated at first, before I settled on this algorithm. (I was trying to render the floors as tiles, as in RenderFloorTile(x, y), instead of rendering the area between walls.) But in the end, they're treated exactly the same as walls.
One more thing is the "prepare" part of that line. Nothing is rendered yet, not until all the rays are cast and all the walls and floors are ready. If the rendering happened right away, each wall and floor would be split into many pieces, because the rays would rarely fall exactly on their edges, and we would end up with hundreds of small divs (which is very, very slow). So the wall and floor slices are combined and each is rendered as a single piece:
PrepareWall(wallIdx, left, right) {
if (walls[wallIdx]) {
if (left is to the left of wall[wallIdx].left) wall[wallIdx].left = left;
if (right is to the right of wall[wallIdx].right) wall[wallIdx].right = right;
} else {
wall[wallIdx].left = left;
wall[wallIdx].right = right;
}
}
Each wall (and by "wall" I really mean the edge between floor tiles) and floor tile has an index number based on its position in the map. This way walls and floor can be referenced as numbers, which make the comparison between intersections easy (if the indices are the same, the intersections match).
This all results in far fewer objects. Unlike this screenshot showing a "debug" mode before I inmplemented the "prepare" step. Compare that "630 walls and 2709 floors" to about 300 total now. You can see a similar view by hitting "B" in the raycaster, and you'll see that while there's a lot more overdraw and overlapping, there are a lot fewer rectangles.
Even after all the optimizations I've been able to find, it's still really slow. I strongly recommend using Google Chrome, which is not only the fastest browser I've tried, but is also the only browser that antialiases the edges of the divs (which was a pain when I was trying to debug). Opera is next fastest, then IE8, then Firefox 3. Yes, in my tests IE is about twice as fast as Firefox.
A few other things you can do (this is listed in the controls when the raycaster starts): "R" to disable the display (to see how fast it is with all the raycasting but without rendering anything), "T" to show where the splits occurred (slow), "I" to show stats like the frame rate and number of rays cast.
Here are a few things I'd like to add at some time:
And some things I won't be implementing: