The basics of infinite terrain generation for a horizontal endless runner – discretizing the terrain with Simplify.js library and adding Matter physics

Talking about Horizontal Endless Runner game, Game development, HTML5, Javascript and Phaser.

If you enjoyed the post about infinite terrain generation for a horizontal endless runner, and tried to build a physics terrain out of the example I published, you probably faced these issues:

1 – With a 750 pixels wide game, you absolutely can’t build 750 bodies to turn a cosine-generated terrain into a physics terrain.

2 – 750 points are too many even to draw the terrain using grahpics objects.

So we have to find a way to keep our terrain smooth while dramatically reduce the points needed to draw it. Less points mean less bodies.

Here comes into play the Ramer–Douglas–Peucker algorithm: the purpose of the algorithm is, given a curve composed of line segments, to find a similar curve with fewer points. The algorithm defines “dissimilar” based on the maximum distance between the original curve and the simplified curve. The simplified curve consists of a subset of the points that defined the original curve.

Coding the Ramer-Douglas-Peucker algorithm is quite easy, but why should we reinvent the wheel when we can use Simplify.js library by Vladimir “mourner” Agafonkin?

In this example, we have a randomly generated terrain made of more than 1300 points usually reduced – but perfectly working – to less than 50 physics bodies.

There is no interactivity: a terrain is generated, then 60 random polygons fall down, then a new terrain is generated, and so on.

It’s amazing how you can have a perfectly working terrain using less of 4% the original points.

Look at the source code:

var game;

var gameOptions = {
    startTerrainHeight: 0.5,
    amplitude: 300,
    slopeLength: [100, 350],
}
window.onload = function() {
    let gameConfig = {
        type: Phaser.AUTO,
        backgroundColor: 0x75d5e3,
        scale: {
            mode: Phaser.Scale.FIT,
            autoCenter: Phaser.Scale.CENTER_BOTH,
            parent: "thegame",
            width: 1334,
            height: 750
        },
        physics: {
            default: "matter",
            matter: {
                debug: true,
                debugBodyColor: 0x000000
            }
        },
        scene: playGame
    }
    game = new Phaser.Game(gameConfig);
    window.focus();
}
class playGame extends Phaser.Scene{
    constructor(){
        super("PlayGame");
    }
    create(){
        this.slopeGraphics = this.add.graphics();
        this.sliceStart = new Phaser.Math.Vector2(0, Math.random());
        this.drawTerrain(this.slopeGraphics, this.sliceStart);
    }
    drawTerrain(graphics, sliceStart){
        let slopePoints = [];
        let slopes = 0;
        let slopeStart = 0;
        let slopeStartHeight = sliceStart.y;
        let currentSlopeLength = Phaser.Math.Between(gameOptions.slopeLength[0], gameOptions.slopeLength[1]);
        let slopeEnd = slopeStart + currentSlopeLength;
        let slopeEndHeight = Math.random();
        let currentPoint = 0;
        while(currentPoint < game.config.width){
            if(currentPoint == slopeEnd){
                slopes ++;
                slopeStartHeight = slopeEndHeight;
                slopeEndHeight = Math.random();
                var y = game.config.height * gameOptions.startTerrainHeight + slopeStartHeight * gameOptions.amplitude;
                slopeStart = currentPoint;
                currentSlopeLength = Phaser.Math.Between(gameOptions.slopeLength[0], gameOptions.slopeLength[1]);
                slopeEnd += currentSlopeLength;
            }
            else{
                var y = (game.config.height * gameOptions.startTerrainHeight) + this.interpolate(slopeStartHeight, slopeEndHeight, (currentPoint - slopeStart) / (slopeEnd - slopeStart)) * gameOptions.amplitude;
            }
            slopePoints.push(new Phaser.Math.Vector2(currentPoint, y))
            currentPoint ++ ;
        }
        let simpleSlope = simplify(slopePoints, 1, true);
        graphics.x = sliceStart.x;
        graphics.clear();
        graphics.moveTo(0, game.config.height);
        graphics.fillStyle(0x654b35);
        graphics.beginPath();
        simpleSlope.forEach(function(point){
            graphics.lineTo(point.x, point.y);
        }.bind(this))
        graphics.lineTo(currentPoint, game.config.height);
        graphics.lineTo(0, game.config.height);
        graphics.closePath();
        graphics.fillPath();
        graphics.lineStyle(16, 0x6b9b1e);
        graphics.beginPath();
        simpleSlope.forEach(function(point){
            graphics.lineTo(point.x, point.y);
        })
        graphics.strokePath();
        for(let i = 1; i < simpleSlope.length; i++){
            let line = new Phaser.Geom.Line(simpleSlope[i - 1].x, simpleSlope[i - 1].y, simpleSlope[i].x, simpleSlope[i].y);
            let distance = Phaser.Geom.Line.Length(line);
            let center = Phaser.Geom.Line.GetPoint(line, 0.5);
            let angle = Phaser.Geom.Line.Angle(line)
            this.matter.add.rectangle(center.x, center.y, distance, 10, {
                isStatic: true,
                angle: angle
            })
        }
        this.add.text(0, game.config.height - 60, "Bodies to generate terrain: " + simpleSlope.length, {
            fontFamily: "Arial",
            fontSize: 64,
            color: "#00ff00"
        });
        this.polygons = 0;
        this.time.addEvent({
            delay: 500,
            callbackScope: this,
            callback: function(){
                this.matter.add.polygon(Phaser.Math.Between(0, game.config.width), -50, Phaser.Math.Between(3, 10), Phaser.Math.Between(10, 40));
                this.polygons ++;
                if(this.polygons > 60){
                    this.scene.start("PlayGame");
                }
            },
            loop: true
        });
    }
    interpolate(vFrom, vTo, delta){
        let interpolation = (1 - Math.cos(delta * Math.PI)) * 0.5;
        return vFrom * (1 - interpolation) + vTo * interpolation;
    }
}

What about re-introducing the scrolling and adding a car? Wait for next tutorial to see a complete game prototype, meanwhile download the source code and enjoy.