5
\$\begingroup\$

For the past week, I've been making a raycaster in JS and if you want a live demo, you can try it here. It ran smoothly before I added variable height walls but now it is very slow (~15 FPS) so I want to know how to make it run faster.

I'd also like it if somebody would review the code normally so that I can improve it further.

var ctx = c.getContext("2d");
var mapCtx = minimap.getContext("2d");
var MINI_MAP_SCALE = 8;
var OUTSIDE_THE_MAP = -1;
var NO_HIT = 0;
var IS_HIT = 1;
var X_HIT = 0;
var Y_HIT = 1;
var UP = 1;
var DOWN = -1;
var LEFT = -1;
var RIGHT = 1;
var TEXTURED_WALL = 10;
var COLORED_WALL = 11;
var SPRITE = 12;
var SORT_BY_DISTANCE = (a, b) => {return b.distance - a.distance};
function drawMiniMap() {
    if (minimap.width !== player.map.width * MINI_MAP_SCALE || minimap.height !== player.map.height * MINI_MAP_SCALE) {
        minimap.width = player.map.width * MINI_MAP_SCALE;
        minimap.height = player.map.height * MINI_MAP_SCALE;
    }
    mapCtx.fillStyle = "white";
    mapCtx.fillRect(0, 0, minimap.width, minimap.height);
    for (var y = 0; y < player.map.height; y++)
        for (var x = 0; x < player.map.width; x++)
            if (player.map.get(x, y) > 0) {
                mapCtx.fillStyle = "rgb(200, 200, 200)";
                mapCtx.fillRect(
                    x * MINI_MAP_SCALE,
                    y * MINI_MAP_SCALE,
                    MINI_MAP_SCALE, MINI_MAP_SCALE
                );
            }
    updateMiniMap();
}
function updateMiniMap() {
    player.map.sprites.forEach(sprite => {
        mapCtx.fillStyle = "rgb(0, 200, 200)";
        mapCtx.fillRect(
            sprite.x * MINI_MAP_SCALE,
            sprite.z * MINI_MAP_SCALE,
            MINI_MAP_SCALE, MINI_MAP_SCALE
        );
        mapCtx.fillStyle = "black";
        mapCtx.fillRect(
            player.x * MINI_MAP_SCALE - 2,
            player.y * MINI_MAP_SCALE - 2,
            4, 4
        );
    });
    mapCtx.beginPath();
    mapCtx.moveTo(player.x * MINI_MAP_SCALE, player.y * MINI_MAP_SCALE);
    mapCtx.lineTo(
        (player.x + Math.cos(player.rot) * 4) * MINI_MAP_SCALE,
        (player.y + Math.sin(player.rot) * 4) * MINI_MAP_SCALE
    );
    mapCtx.stroke();
}
class Player {
    constructor() {
        this.x = 0;
        this.y = 0;
        this.dirX = 1
        this.dirY = 0; 
        this.planeX = 0;
        this.planeY = 0.66;
        this.dir = 0;
        this.rot = 0;
        this.speed = 0;
        this.moveSpeed = 0.4;
        this.rotSpeed = 6 * Math.PI / 180;
        this.map = null;
        return this;
    }
    move() {
        var moveStep = this.speed * this.moveSpeed;
        this.rot += this.dir * this.rotSpeed;
        var newX = this.x + Math.cos(player.rot) * moveStep;
        var newY = this.y + Math.sin(player.rot) * moveStep;
        var currentMapBlock = this.map.get(newX|0, newY|0);
        if (currentMapBlock === OUTSIDE_THE_MAP || currentMapBlock > 0) {
            this.stopMoving();
            return;
        };
        this.x = newX;
        this.y = newY;
        this.rotateDirectionAndPlane(this.dir * this.rotSpeed);
        return this;
    }
    rotateDirectionAndPlane(angle) {
        var oldDirX = this.dirX;
        this.dirX = this.dirX * Math.cos(angle) - this.dirY * Math.sin(angle);
        this.dirY = oldDirX * Math.sin(angle) + this.dirY * Math.cos(angle);
        var oldPlaneX = this.planeX;
        this.planeX = this.planeX * Math.cos(angle) - this.planeY * Math.sin(angle);
        this.planeY = oldPlaneX * Math.sin(angle) + this.planeY * Math.cos(angle);
        this.stopMoving();
    }
    setXY(x, y) {
        this.x = x;
        this.y = y;
        return this;
    }
    setRot(angle) {
        var difference = angle - this.rot;
        this.rot = angle;
        this.rotateDirectionAndPlane(difference);
        return this;
    }
    startMoving(direction) {
        switch (direction) {
            case "up":
                this.speed = UP; break;
            case "down":
                this.speed = DOWN; break;
            case "left":
                this.dir = LEFT; break;
            case "right":
                this.dir = RIGHT; break;
        }
        return this;
    }
    stopMoving() {
        this.speed = 0;
        this.dir = 0;
        return this;
    }
    castRays() {
        this.move();
        var visibleSprites = [];
        var zBuffer = [];
        Object.keys(this.map.wallTypes).forEach(typeID => {
            this.castRaysToSpecifiedWallType(this.map.wallTypes[typeID], zBuffer);
        });
        this.map.sprites.forEach(sprite => {
            var spriteX = sprite.x - this.x;
            var spriteY = sprite.z - this.y;
            var invDet = 1 / (this.planeX * this.dirY - this.dirX * this.planeY);
            var transformX = invDet * (this.dirY * spriteX - this.dirX * spriteY);
            var transformY = invDet * (-this.planeY * spriteX + this.planeX * spriteY);
            if (transformY > 0) {
                var spriteScreenX = (c.width / 2) * (1 + transformX / transformY);
                var spriteHeight = Math.abs(c.height / transformY);
                var imaginedHeight = sprite.y * spriteHeight;
                var drawStartY = -imaginedHeight / 2 + c.height / 2 - imaginedHeight;
                var drawEndY = imaginedHeight / 2 + c.height / 2 - imaginedHeight;
                var spriteWidth = Math.abs(c.height / transformY);
                var drawStartX = -spriteWidth / 2 + spriteScreenX;
                var drawEndX = spriteWidth / 2 + spriteScreenX;
                var spriteImage = sprite.texture;
                var texHeight = spriteImage.image.height;
                var texWidth = spriteImage.image.width;
                zBuffer.push({
                    type: SPRITE,
                    drawX: drawStartX,
                    drawY: drawStartY,
                    texture: spriteImage,
                    width: spriteWidth,
                    height: spriteHeight,
                    distance: transformY
                });
            }
        });
        return zBuffer.sort(SORT_BY_DISTANCE);
    }
    castRaysToSpecifiedWallType(wallType, zBuffer) {
        for (var x = 0; x < c.width; x++) {
            var cameraX = 2 * x / c.width - 1;
            var rayPosX = this.x;
            var rayPosY = this.y;
            var rayDirX = this.dirX + this.planeX * cameraX;
            var rayDirY = this.dirY + this.planeY * cameraX;
            var mapX = rayPosX | 0;
            var mapY = rayPosY | 0;
            var deltaDistX = Math.sqrt(1 + (rayDirY * rayDirY) / (rayDirX * rayDirX));
            var deltaDistY = Math.sqrt(1 + (rayDirX * rayDirX) / (rayDirY * rayDirY));
            var stepX = 0;
            var stepY = 0;
            var sideDistX = 0;
            var sideDistY = 0;
            var wallDistance = 0;
            var giveUp = false;
            if (rayDirX < 0) {
                stepX = -1;
                sideDistX = (rayPosX - mapX) * deltaDistX;
            } else {
                stepX = 1;
                sideDistX = (mapX + 1 - rayPosX) * deltaDistX;
            }
            if (rayDirY < 0) {
                stepY = -1;
                sideDistY = (rayPosY - mapY) * deltaDistY;
            } else {
                stepY = 1;
                sideDistY = (mapY + 1 - rayPosY) * deltaDistY;
            }
            var hit = NO_HIT;
            var side = X_HIT;
            while (hit === NO_HIT) {
                if (sideDistX < sideDistY) {
                    sideDistX += deltaDistX;
                    mapX += stepX;
                    side = X_HIT;
                } else {
                    sideDistY += deltaDistY;
                    mapY += stepY;
                    side = Y_HIT;   
                }
                var currentMapBlock = this.map.get(mapX, mapY);
                if (currentMapBlock === OUTSIDE_THE_MAP || this.map.wallTypes[currentMapBlock] === wallType) {
                    hit = IS_HIT;
                    if (currentMapBlock === OUTSIDE_THE_MAP) {
                        giveUp = true;
                    }
                }
            }
            if (giveUp) {continue;}
            if (side === X_HIT) {
                wallDistance = (mapX - rayPosX + (1 - stepX) / 2) / rayDirX;
            } else {
                wallDistance = (mapY - rayPosY + (1 - stepY) / 2) / rayDirY;
            }
            var color = wallType.color;
            var wallHeight = wallType.height;
            var lineHeight = c.height / wallDistance;
            var drawEnd = lineHeight / 2 + c.height / 2;
            lineHeight *= wallHeight < 0 ? 0 : wallHeight;
            var drawStart = drawEnd - lineHeight;
            var exactHitPositionX = rayPosY + wallDistance * rayDirY;
            var exactHitPositionY = rayPosX + wallDistance * rayDirX;
            if (side === X_HIT) {
                var wallX = exactHitPositionX;
            } else {
                var wallX = exactHitPositionY;
            }
            var currentBuffer = {};
            zBuffer.push(currentBuffer);
            currentBuffer.side = side;
            currentBuffer.start = drawStart;
            currentBuffer.end = drawEnd;
            currentBuffer.x = x; 
            currentBuffer.distance = wallDistance;
            if (color instanceof Texture) {
                currentBuffer.type = TEXTURED_WALL;
                var texture = color;
                currentBuffer.texture = texture;
                wallX -= wallX | 0;
                var textureX = wallX * texture.image.width;
                if ((side === X_HIT && rayDirX > 0) || (side === Y_HIT && rayDirY < 0)) {
                    textureX = texture.image.width - textureX - 1;
                }
                currentBuffer.textureX = textureX;
            } else {
                currentBuffer.type = COLORED_WALL;
                currentBuffer.color = color;
            }
        }

    }
    render(zBuffer) {
        zBuffer.forEach(currentBuffer => {
            var side = currentBuffer.side;
            var drawStart = currentBuffer.start;
            var drawEnd = currentBuffer.end;
            var {
                side,
                texture,
                textureX,
                color,
                x,
                drawX,
                drawY,
                width,
                height,
                start: drawStart,
                end: drawEnd
            } = currentBuffer;
            var lineHeight = drawEnd - drawStart;
            if (currentBuffer.type === TEXTURED_WALL) {
                ctx.globalAlpha = 1;
                ctx.fillStyle = "black";
                ctx.fillRect(x, drawStart, 1, lineHeight);
                if (side === Y_HIT) {
                    ctx.globalAlpha = .7;
                } else {
                    ctx.globalAlpha = 1;
                }
                ctx.drawImage(texture.image, textureX, 0, 1, texture.image.height, x, drawStart, 1, lineHeight);
            } else if (currentBuffer.type === COLORED_WALL) {
                ctx.globalAlpha = 1;
                ctx.fillStyle = "black";
                ctx.fillRect(x, drawStart, 1, lineHeight);
                if (side === Y_HIT) {
                    ctx.globalAlpha = .7;
                } else {
                    ctx.globalAlpha = 1;
                }
                ctx.fillStyle = "rgb("+color[0]+", "+color[1]+", "+color[2]+")";
                ctx.fillRect(x, drawStart, 1, lineHeight);
            } else if (currentBuffer.type === SPRITE) {
                ctx.globalAlpha = 1;
                ctx.drawImage(texture.image, 0, 0, texture.image.width, texture.image.height, drawX, drawY, width, height);
            }
        });

    }
}
class Grid {
    constructor(wallGrid, wallTextures, sprites) {
        this.wallGrid = wallGrid;
        this.height = wallGrid.length;
        this.width = this.height === 0 ? 0 : wallGrid[0].length;
        this.wallTypes = wallTextures || {};
        this.sprites = sprites || [];
        return this;
    }
    get(x, y) {
        x = x | 0;
        y = y | 0;
        var currentMapBlock = this.wallGrid[y];
        if (currentMapBlock === undefined) return OUTSIDE_THE_MAP;
        currentMapBlock = currentMapBlock[x];
        if (currentMapBlock === undefined) return OUTSIDE_THE_MAP;
        return currentMapBlock;
    }

}
class Texture {
    constructor(src, width, height) {
        this.image = new Image();
        this.image.src = src;
        width ? this.image.width = width : 0;
        height ? this.image.height = height : 0;
    }
}
class Sprite {
    constructor(texture, x, y, z){
        this.texture = texture;
        this.x = x;
        this.y = y;
        this.z = z;
    }
}

class Wall {
    constructor(height, color) {
        this.height = height;
        this.color = color;
    }
}
var player = new Player();
player.x = player.y = 3;
player.map = new Grid([
    [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,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,0,1],
    [1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
    [1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
    [1,0,0,0,0,0,1,1,1,1,1,0,0,0,0,1,0,1,0,1,0,0,0,1],
    [1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1],
    [1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,1,0,0,0,1,0,0,0,1],
    [1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1],
    [1,0,0,0,0,0,1,1,2,1,1,0,0,0,0,1,0,1,0,1,0,0,0,1],
    [1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
    [1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
    [1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
    [1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
    [1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
    [1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
    [1,0,0,0,0,0,0,0,0,0,0,0,0,0,2,1,0,0,0,0,0,0,0,1],
    [1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
    [1,1,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
    [1,1,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
    [1,1,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
    [1,1,0,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
    [1,1,0,0,0,0,0,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,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,1,1,1,1,1,1,1,1,1,1,1]
], {'1': new Wall(2, new Texture('walls.png')), '2': new Wall(4, [255, 0, 0]) }, [new Sprite(new Texture('walls.png'), 4, 1, 4)]);
var keyCodes = {
    "38": "up",
    "40": "down",
    "37": "left",
    "39": "right"
}
document.addEventListener("keydown", function(e) {
    player.startMoving(keyCodes[e.keyCode]);
});
document.addEventListener("keyup", function(e) {
    player.stopMoving(keyCodes[e.keyCode]);
});
var isDragging = false;
c.addEventListener("mousedown", startDragging);
window.addEventListener("mouseup", endDragging);
c.addEventListener("touchstart", startDragging);
c.addEventListener("touchend", endDragging);
c.addEventListener("mousemove", whileDragging);
c.addEventListener("touchmove", whileDragging);
var mouseX = 0;
var pmouseX = 0;
var mouseY = 0;
var pmouseY = 0;
function whileDragging(e) {
    var event;
    e.preventDefault();
    if (e.touches) {
        event = e.touches[0];
    } else {
        event = e;
    }
    pmouseX = mouseX;
    pmouseY = mouseY;
    mouseX = event.pageX - c.offsetLeft;
    mouseY = event.pageY - c.offsetTop;
    if (isDragging) {
        player.setRot(player.rot + (mouseX - pmouseX) / c.width * 2);
        player.speed = -(mouseY - pmouseY) / c.height * 15;
    }
}
function startDragging(e) {
    var event;
    e.preventDefault();
    if (e.touches) {
        event = e.touches[0];
    } else {
        event = e;
    }
    mouseX = event.pageX - c.offsetLeft;
    mouseY = event.pageY - c.offsetTop;
    isDragging = true;
}
function endDragging(e) {
    e.preventDefault();
    isDragging = false;
}
function renderLoop() {
    ctx.clearRect(0, 0, c.width, c.height);
    player.render(player.castRays());
}
requestAnimationFrame(function animate() {
    if (c.clientWidth !== c.width || c.clientHeight !== c.height) {
        c.width = c.clientWidth;
        c.height = c.clientHeight;
    }
    renderLoop();
    drawMiniMap();
    requestAnimationFrame(animate);
});
\$\endgroup\$
  • \$\begingroup\$ Instead of zBuffer.sort() you might want to precompute a BSP Binary Space Partitioning) tree of your geometry which allows efficient retrieval of the sorted elements during runtime. Great for software rendering and easy to implement. You need to split intersecting geometry though, if any. \$\endgroup\$ – le_m Apr 11 '17 at 17:46
1
+50
\$\begingroup\$

This answer is probably not worth much, but I'd like to add my 5 cents. Who knows, maybe it will have some noticeable impact on performance:

  • Compressing your walls.png can save you over 25% of bytes. This image is drawn and transformed many times and as such this compression may be significant.
  • There are two isntances of zBuffer.push() in your code, both in loops performing a lot of operations for many iterations. The one in castRaysToSpecifiedWallType() can be replaced with zBuffer[x] = currentBuffer. The other one with zBuffer[zBuffer.length], but the first replacement is way more important. Why? Well, there is a huge performance difference between the two, here is the benchmark: Array push vs array addition
  • This line is performance heavy:
    ctx.drawImage(texture.image, textureX, 0, 1, texture.image.height, x, drawStart, 1, lineHeight);
    I don't have much experience with canvases, but from what I know it's better to use integers in this case, while textureX, drawStart and lineHeight are float values. As such, it may be a good idea to round them. Math.round() is sometimes a bit slower, so you could use this hackery method: (0.5 + value) << 0.
  • Other thing, you are using zBuffer.forEach(). forEach() is way slower than good ol' for. It's even more important since zBuffer is an array of more than a thousand objects. In a simple benchmark I performed, it was 82.3% slower:
    JS for loops benchmark

Other than that, I must say that your code is really neat. I'm absolutely positively impressed.

\$\endgroup\$
  • \$\begingroup\$ Hey, what debugger are you using? \$\endgroup\$ – user123460 Apr 10 '17 at 3:28
  • \$\begingroup\$ @LearnHowToBeTransparent: Usually just the Chrome built-in one. But I like to just read the code block-by-block too. I will add more tips on Tuesday or Wednesday, as I can't really do it right now comfortably. Probably nothing game-changing, but hey it'll be something, especially since no one else seem to will to provide their answer to this question. \$\endgroup\$ – Przemek Apr 10 '17 at 15:49
  • \$\begingroup\$ @LearnHowToBeTransparent: I've added two more points as promised. \$\endgroup\$ – Przemek Apr 11 '17 at 17:40
  • \$\begingroup\$ Thanks a lot for helping. <<0 is cast to integer, right? So I'll change it to |0, for the sake of consistency. \$\endgroup\$ – user123460 Apr 12 '17 at 2:55
  • \$\begingroup\$ @LearnHowToBeTransparent: That is absolutely right. I'll gladly hear about results of your efforts, once they will conclude ;). \$\endgroup\$ – Przemek Apr 12 '17 at 10:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy