Diagonal movement and collision detection

[Yu]

I've tried to do collision detection with diagonal movement and
quickly realized why this wasn't in the Simple RPG tutorial :)

So, when we do four-way collision detection, everything is simple:
character collides with obstacle at 90 degrees, he is stopped,
everything looks fine. But when we do eight-way movement and collide
with the obstacle at 45 degrees, we can't just stop character where it
stands, because the player expects it to "slide" along the obstacle,
as in classical RPGs. And the problem is how to detect the direction
of this "sliding".

Diagonal movement is a sum of two vectors, on x and y axis. To negate
one of them we must know where the character was located before the
collision relative to the obstacle: to the north/south of it and so
on. To do that, I need to store character's position in the frame
previous to collision, and to calculate character's and obstacle's
geometrical sizes.

But that is a bit messy and I'm not sure if this is the best way. Any
suggestions? I've browsed through Collision docs and didn't find any
built-in methods about this.

[Matt Petrovic]

Try splitting the movement into the 2 vectors and handling them separately.

x += speed.x
if (testCollision()) x -= speed.x
y += speed.y
if (testCollision()) x -= speed.y

[Yu]

Well yeah, this part is obvious, and I wrote about it in my post. I am
asking about these testCollision()'s.

[Matt Petrovic]

is there something wrong with .hit() ?

http://craftyjs.com/api/Collision.html#-hit

Basically, your movement code would be:

this.x += speed.x

if (this.hit('wall')) this.x -= speed.x

this.y += speed.y

if (this.hit('wall')) this.y -= speed.y

Move it on the x, check to see if it collided, undo if it did. Then do the same with the y. Keep them completely independent of each other and you don't need to know where they were before.

[Yu]

I'll try to explain again.

Character is moving diagonally to the north-west. On its way it
encounters a wall, that goes from south to north, and collides with
it. I want my character not to completely stop, but to "slide" along
the wall, specifically to the north in this example. His diagonal
movement vector is a sum of two vectors, one pointing north, second
pointing west. The wall blocks character from moving to the west, but
it can move north.

And this:

this.x += speed.x
if (this.hit('wall')) this.x -= speed.x
this.y += speed.y
if (this.hit('wall')) this.y -= speed.y

will block both x and y movement at the same time when
this.hit('wall') is true.

[Yu]

Of course, all of that moving/sliding is going on while the player
keeps ARROW_LEFT and ARROW_UP pressed.

[Matt Petrovic]

I understood you fine, although I admit I may not understand the collision code correctly. 

The point is to test collision after moving on one vector, and if we're colliding after doing so, immediately back out so that we are no longer colliding with it. This would leave us in a not-colliding state to test the next vector on. 

If we collide on x, we undo it. then .hit('wall') returns false again, and we can check the y-axis. 

Whether the user is still pressing keys or not is irrelevant. The only thing those should be doing is setting speed.x and speed.y. 

[Søren Bramer Schmidt]

As long as your walls are not diagonal i believe this code should work fine.

If you create a minimal example game we can continue the discussion from there. http://jsfiddle.net/ is awesome for this.

[Yu]

Jsfiddle seems to be down for me, here is the example on the pastebin:
http://pastebin.com/EhJNHuyG

This is a slightly modified Simple RPG demo. The character is allowed
to move 8-way. Try to collide with the wall of bushes while moving
diagonally.

[Matt Petrovic]

Yeah, you won't get the sliding effect there because you reverse all movement when you hit something. You aren't handling your vectors separately so the game doesn't know which way you collided from.

If you want the sliding effect, you'll need to move keyboard detection into actual keyboard events. Store your speed on x and y separately, and then test each of them for collision in the enter frame. You wouldn't be using onHit in this case. 

I modified that code to show what I mean:

https://gist.github.com/966686

Look at the CustomControls constructor and the enterframe handler.

[Yu]

I am sorry, but your code isn't working. The guy does not move at all.

[Matt Petrovic]

yeah, I know. I tried fixing it earlier but couldn't figure out why. I came back to it just now and it works:

https://gist.github.com/966686

http://jsfiddle.net/pvKSY/

[Yu]

Try to get the wall to run horizontally (change i to j in line 34),
and everything breaks.

[Matt Petrovic]

Forget the fact that it breaks. Do you get what I'm saying? The method I'm proposing?

[Yu]

No, I don't. And I think that you don't get it as well, because all
the way down you are testing against "this.hit('wall')", which will be
"true" every time for every collision regardless of the direction of
movement, and the fact that your suggested "solution" does not work
proves it.

[Matt Petrovic]

http://jsfiddle.net/pvKSY/6/

Better? 

I understand the problem fine. The code didn't work not because of problems with the actual logic, but because of issues with the engine and small typos. I will be raising those issues when I get a test case up. 

It didn't work yesterday because Crafty was blowing away a handler it shouldn't have, and the keyboard events didn't follow conventions.

It didn't work with a horizontal wall today because I missed changing an 'x' to a 'y' when I copied that bit of code. 

There's a difference between 'broken due to faulty logic' and 'broken due to typos'. 

The fundamental fact you seem to be missing is this:

At the beginning of every enterframe, we assume we aren't colliding with the wall. .hit(wall) should never return true until we change the x or y. From that state, we can move on each vector, test for collision and then undo that vector's movement if we find our new position to be invalid. And then we leave enterframe with our entity not colliding with anything.

Under no circumstances should .hit() return true longer than the time it takes to undo the movement.

[Yu]

Under no circumstances should .hit() return true longer than the time
it
takes to undo the movement.

^^^^
You should have said this from the start!! I wasn't aware of that. Now
it makes perfect sense. Thank you, and sorry if I was rude.

[Søren Bramer Schmidt]

Thank you for your thorough and patient answers in this thread Matt.

I have a proposal for an update to the Fourway component that would make it very easy to implement this. Would you care to see if there is anything you don't like about it https://github.com/louisstow/Crafty/issues/84

This would make it possible to forgo CustomControls entirely and setup animations and collision detection like this: 

player = Crafty.e("2D, DOM, player, Keyboard, Fourway, SpriteAnimation, Collision")

            .attr({x: 160, y: 144, z: 1})

            .fourway(1)

            .animate("walk_left", 6, 3, 8)

            .animate("walk_right", 9, 3, 11)

            .animate("walk_up", 3, 3, 5)

            .animate("walk_down", 0, 3, 2)

            .bind('NewDirection', function(direction) {

                this.stop();

                if(direction.up) {

                    this.animate("walk_up", 10, -1);

                }

                if(direction.right) {

                    this.animate("walk_right", 10, -1);

                }

                if(direction.down) {

                    this.animate("walk_down", 10, -1);

                }

                if(direction.left) {

                    this.animate("walk_left", 10, -1);

                }

            })

            .bind('Moved', function(from) {

                if(this.hit('wall')){

                    this.attr({x: from.x, y:from.y});

                }

            })

            .collision();

[Matt Petrovic]

I don't think we should be promoting checking for keyboard status in an enterframe handler.

For starters, we need to keep the enterframe logic as light as humanly possible. If we can move anything out of there, we should. We have perfectly good events for catching when keys are pressed, we should use those, and avoid having to check for them on every frame. This has the added benefit of separating the interface from actual game logic. We'll be able to implement controls for other devices (touchscreen, gamepad, etc) more easily.

I like NewDirection, but again, that's the kind of thing that can go elsewhere. The direction doesn't change every frame, it changes when you tell it to. Trigger that event when you tell it to change direction. And then enterframe can take the _direction and _speed and figure out which way to go from there.

One of the things we need to be especially careful about is triggering ANY events in enterframe. It should be one of those things you do only when you really need to and there is no other way possible to do what you're trying to do. That's a very easy way to lag down a game.

[Søren Bramer Schmidt]

I agree. There are some things that makes it not so clear in this case though.

* when a key is pressed down for long periods (like when you want the character to walk in one direction), keydown is fired very rapidly in most browsers, perhaps more often than the enterframe event. There might be ways for crafty to provide another event, say KeyPressed that is only fired once, but from a little googleing it appears that there is no good way to do this cross browser.

* There will only ever be one entity using Fourway at a time.

I will try to whip up a more event driven approach in the weekend though. I still think it will be useful to have a Moved event triggered on enterframe.

[Matt Petrovic]

I see. I was under the impression that KeyDown would fire once for each key press, not continue firing as long as the key is down. Regardless, it's something we can filter. Crafty already keeps track of what keys are down, so if we detect a keydown that's already down, we simply don't fire Crafty's KeyDown event.

As for the multiple fourway issue, we can replace hard-coded keys with some variables, a constructor, and defaults for games that only have one fourway. We probably should anyway, since I at least will want to be able to allow users to customize that.

[Søren Bramer Schmidt]

Great suggestions. What about a Multiway component that will make it easy to create controlcomponents by binding a key to a direction in degrees:

Crafty.c("LeftControls", {

    init: function() {

        this.requires('Multiway');

    },

    

    leftControls: function(speed) {

        this.multiway(speed, {W: -90, S: 90, D: 0, A: 180})

        return this;

    }

    

});

Crafty.c("NumControls", {

    init: function() {

        this.requires('Multiway');

    },

    

    numControls: function(speed) {

        this.multiway(speed, { NUMPAD_8: -90, NUMPAD_2: 90, NUMPAD_6: 0, NUMPAD_4: 180,

                               NUMPAD_9: -45, NUMPAD_3: 45, NUMPAD_7: -135, NUMPAD_1: 135})

        return this;

    }

    

});

I have moved most stuff out of the enterframe event, so all that has to happen is calculate two sums and trigger the Moved event.

There is quite a bit of housekeeping to do in order to support keys that move on two axes, but performance vise it is ok as it is done on KeyDown (i fixed the KeyDown rapid fire).

Crafty.c("Multiway", {

_speed: 3,

        _keyDirection: {},

_keys: [],

        _movement: {x: 0, y: 0},

        

init: function() {

this.requires("Keyboard");

},

multiway: function(speed, keys) {

if(speed) this._speed = speed;

                

                this._keyDirection = keys;

                this.speed(this._speed);

                this.bind("KeyDown", function(e) {

                    if(this._keys[e.keyCode]) {

                        this._movement.x = Math.round((this._movement.x + this._keys[e.keyCode].x)*1000)/1000;

                        this._movement.y = Math.round((this._movement.y + this._keys[e.keyCode].y)*1000)/1000;

                        

                        this.trigger('NewDirection', this._movement);

                        console.log(this._movement.y + ' ' + this._movement.x);

                    }

                })

                .bind("KeyUp", function(e) {

                    if(this._keys[e.keyCode]) {

                        this._movement.x = Math.round((this._movement.x - this._keys[e.keyCode].x)*1000)/1000;

                        this._movement.y = Math.round((this._movement.y - this._keys[e.keyCode].y)*1000)/1000;

                        

                        this.trigger('NewDirection', this._movement);

                    }

                })

                

this.bind("enterframe",

                          function() {

                                if (this.disableControls) return;

                        

                                if(this._movement.x !== 0) {

                                    this.x += this._movement.x;

                                    this.trigger('Moved', {x: this.x - this._movement.x, y: this.y});

                                }

                                if(this._movement.y !== 0) {

                                    this.y += this._movement.y;

                                    this.trigger('Moved', {x: this.x, y: this.y - this._movement.y});

                                }

});

return this;

},

        

        speed: function(speed) {

                for(var k in this._keyDirection) {

                   var keyCode = Crafty.keys[k] || k;

                   this._keys[keyCode] = { x: Math.round(Math.cos(this._keyDirection[k]*(Math.PI/180))*1000 * speed)/1000,

                                           y: Math.round(Math.sin(this._keyDirection[k]*(Math.PI/180))*1000 * speed)/1000}

                }

                return this;

        }

});

I think that the Multiway component could exist along some easy to use components, say LeftControls, RightControls. 

WDYT?

[Matt Petrovic]

Looks good. And it opens the way for dealing with some alternate control schemes, like a game pad or with touch events.