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.
What's next? Here's a hint.
