Collision detection in HTML5 canvas. Optimization too

Question

I am making a platform game, but i have a problem with my collision detection. I've made a function that draws a tile on the screen/map. In that function is my collision detection, it works fine when only one tile is drawn, but when i created "stairs" with three tiles, the first tile doesnt work propertly. The player is just being "pushed" up on the tile. The side detection isn't working. And the other tiles are working just fine.

Here is the code for collision detection and tile drawing:

//Function that allows you to draw a tile
function drawTile(type, x, y, collision){
    var tileImg = new Image();
    tileImg.onload = function(){
        ctx.drawImage(tileImg, x, y)
    };
    tileImg.src = "images/" + type + ".png";

    if (collision){
        //Worst collision detection ever.
        if((player_x + player_width == x) && (player_y + player_height > y)){
            canMoveRight = false;
        }else if((player_x == x + 32) && (player_y + player_height > y)){
            canMoveLeft = false;
        }else if((player_y + player_height > y) && (player_x + player_width >= x) && (player_x + player_width <= x + 64)){
            player_y = y - player_height;
        }else{
            canMoveRight = true;
            canMoveLeft = true;
        }
    }
}

//Draw the map
function drawMap(){
    drawTile("block", 96, 208, true);
    drawTile("block", 128, 208, true);
    drawTile("block", 128, 176, true);
};

As you can see, the collision detection code kinda sucks. So it also would be good if you showed me better ways of making it.

Just say if you need to know something. :)

Answer 1

I know this will sound like horrible overhead to you, but you should consider using a Scene Graph to handle all your collision detection, drawing and even click events on the screen.

A Scene Graph is basicly a tree data structure representing 1-parent to n-child relation (note: the DOM of every HTML page is also a Scene Graph)

So to aproach this, you would have a basic interface or abstract class called "node" or whatever, representing the interface every node in your sceneGraph must implement. Again its just like Elements in the dom, they all have CSS properties, methods for event handling and position modifiers.

Node:

{
    children: [],

    update: function() {
        for(var i = 0; i < this.children.length; i++) {
            this.children[i].update();
        }
    },

    draw: function() {
        for(var i = 0; i < this.children.length; i++) {
            this.children[i].draw();
        }
    }
}

Now, as you might know, if you move one element in the DOM per maring, position or what so ever, all the child elements automaticly go to the new position with their parent, this behaviour is achieved via transformation inheritance, for simplicity i'm not gonna show a 3D transformation Matrix, rather just a translation (an x,y offset).

Node:

{
    children: [],
    translation: new Translation(),


    update: function(worldTranslation) {
        worldTranslation.addTranslation(this.translation);

        for(var i = 0; i < this.children.length; i++) {
            this.children[i].update(worldTranslation);
        }

        worldTranslation.removeTranslation(this.translation);
    },

    draw: function() {
        for(var i = 0; i < this.children.length; i++) {
            this.children[i].draw();
        }
    }
}

Transformation:

{
    x: 0,
    y: 0,

    addTranslation: function(translation) {
        this.x += translation.x;
        this.y += translation.y;
    },

    removeTranslation: function(translation) {
        this.x -= translation.x;
        this.y -= translation.y;
    }
}

(note that we dont instanciate new translation objects, because its cheaper to just add/remove values on a global translation)

Now your worldTranslation (or globalTranslation) features all offsets a node can inherit from its parents.

before i go into collision detection, i will show how to draw sprites with this techniqe. Basicly you will fill an array in your Draw-loop with position-image pairs

Node:

{
    children: [],
    translation: new Translation(),

    image: null, //assume this value is a valid htmlImage or htmlCanvas element, ready to be drawn onto a canvas
    screenPosition: null, //assume this is an object with x and y values like {x: 0, y: 0}

    update: function(worldTranslation) {
        worldTranslation.addTranslation(this.translation);

        this.screenPosition = {x: worldTranslation.x, y: worldTranslation.y};

        for(var i = 0; i < this.children.length; i++) {
            this.children[i].update(worldTranslation);
        }

        worldTranslation.removeTranslation(this.translation);
    },

    draw: function(spriteBatch) {

        spriteBatch.push({
            x: this.screenPosition.x,
            y: this.screenPosition.y,
        });

        for(var i = 0; i < this.children.length; i++) {
            this.children[i].draw(spriteBatch);
        }
    }
}

Render Function:

function drawScene(rootNode, context) {
    //clear context here

    var spriteBatch = [];
    rootNode.draw(spriteBatch);

    //if you have to, do sorting according to position.x, position.y or some z-value you can set in the draw function

    for(var i = 0; i < spriteBatch.length; i++) {
        var sprite = spriteBatch[i];

        context.drawImage(sprite.image, sprite.position.x, sprite.position.y);
    }
}

Now that we have the basic understanding of drawing images from a sceneGraph, we go to collision detection:

First we need our Nodes to have BoundryBoxes:

Box:

{
    x: 0,
    y: 0,

    width: 0,
    height: 0,

    collides: function(box) {
        return !(
                ((this.y + this.height) < (box.y)) ||
                (this.y > (box.y + box.height)) ||
                ((this.x + this.width) < box.x) ||
                (this.x > (box.x + box.width))
            );
    }
}

in 2D Games i prefer having boundry boxes not in the coordinate system of the node its in, rather having it to know its Absolute values. Explanation via CSS: in css you can set margin and padding, those values do not depend on the page, rather they only exist in the "coordinate system" of the element who has those values set. so its like having position: absolute and left: 10px vs margin-left: 10px; the benifit in 2D is we dont need to bubble the sceneGraph all along to find detections AND we dont have to compute the box out of its current coordinate system -> into the world coordinate system -> back into each node for collision detection.

Node:

{
    children: [],
    translation: new Translation(),

    image: null,
    screenPosition: null,

    box: null, //the boundry box

    update: function(worldTranslation) {
        worldTranslation.addTranslation(this.translation);

        this.screenPosition = {x: worldTranslation.x, y: worldTranslation.y};

        this.box.x = worldTranslation.x;
        this.box.y = worldTranslation.y;
        this.box.width = this.image.width;
        this.box.height = this.image.height;

        for(var i = 0; i < this.children.length; i++) {
            this.children[i].update(worldTranslation);
        }

        worldTranslation.removeTranslation(this.translation);
    },

    collide: function(box, collisions) {
        if(this.box.collides(box)) {
            collisions.push(this);
        }

        //we will optimize this later, in normal sceneGraphs a boundry box asures that it contains ALL children
        //so we only will go further down the tree if this node collides with the box
        for(var i = 0; i < this.children.length; i++) {
            this.children[i].collide(box, collisions);
        }
    },

    draw: function(spriteBatch) {

        spriteBatch.push({
            x: this.screenPosition.x,
            y: this.screenPosition.y,
            image: this.image,
        });

        for(var i = 0; i < this.children.length; i++) {
            this.children[i].draw(spriteBatch);
        }
    }
}

Collision Function:

function collideScene(rootNode, box) {
    var hits = [];

    rootNode.collide(box, hits);

    for(var i = 0; i < hits.length; i++) {
        var hit = hits[i];

        //your code for every hit
    }
}

Note: Not every node has to represent an Image, you can create Nodes to just add a Translation to its children, like making a DIV container with no visuals to arrange a bunch of objects while only have to edit the position of one. A Character could consist of:

CharacterRoot (Translation Only)
    CharacterSprite (Image)
    Weapon (Image)
    Shield (Image)

Now those are just some basics arround Scene Management used in Games, you can google on many therms i used here, make some further optimizations and feel free to ask any question.

Answer 2

With box collision detection, it's important to compare the x and y separately. Here's the pseudo code for how I've done something similar the past:

var o1 = {x:100, y:229, w:30, h:30};
var o2 = {x:100, y:200, w:30, h:30};

//Amount of overlap
leftDist    = (o2.x - o2.w/2) - (o1.x + o1.w/2);
rightDist   = (o1.x - o1.w/2) - (o2.x + o2.w/2);
topDist     = (o2.y - o2.h/2) - (o1.y + o1.h/2);
bottomDist  = (o1.y - o1.h/2) - (o2.y + o2.h/2);


if( leftDist    < 0 &&
    rightDist   < 0 &&
    topDist     < 0 &&
    bottomDist  < 0 ){

    //Get the closest collision
    var closest;
    var direction; //0 = left, 1 = right, 2 = top, 3 = bottom


    var xDist = o1.x - o2.x;
    var yDist = o1.y - o2.y;

    if(xDist < 0) {
        closest = leftDist;
        direction = 0;
    } else {
        closest = rightDist;
        direction = 1;
    }


    if(yDist < 0) {
        if(closest < yDist) {
            closest = topDist;
            direction = 2;
        }
    } else {
        if(closest < yDist) {
            closest = bottomDist;
            direction = 3;
        }
    }



    //Last, jump to the contact position
    switch(direction) {

        case 0:
            o1.x += closest;
            break;
        case 1:
            o1.x -= closest;
            break;
        case 2:
            o1.y += closest;
            break;
        case 3:
            o1.y -= closest;
            break;

    }


}

Let me know if you have any questions about it.