Astar Movement

[Rolf Veinø Sørensen]

Hi

I am trying to create a small RPG.

By using the astar from this example http://buildnewgames.com/astar/ i am able to get an array with the fastest non blocked path from the player to the clicked tile.
I am however not able to move the player on the correct way.

Lets say the player is located at [4,5]
Clicked tile is located at [7,8]
The astar returns this array
[4,5],
[5,5],
[6,5],
[6,6],
[6,7],
[7,7],
[7,8]

How should i move the player if i want the player to change direction, use walking animation like on the keys and respect player walking speed (velocity)?

myMouseUp: function () {
        var mouseX = me.game.viewport.pos.x + me.input.mouse.pos.x;
        var mouseY = me.game.viewport.pos.y + me.input.mouse.pos.y;
        var background = me.game.currentLevel.getLayerByName("background"); //Background always have a tile everywhere on the map
        var gameCollisionLayer = me.game.currentLevel.getLayerByName("collision");
        var gameCollisionMap = new Array();
       
        var player = me.game.getEntityByName("mainPlayer");
        var playerX = player[0].collisionBox.pos.x;
        var playerY = player[0].collisionBox.pos.y;
        var playerTile = background.getTile(playerX, playerY);
        var clickedTile = background.getTile(mouseX, mouseY);
       
        //Create an 2d array with all the tiles as 0 or 1 for collision
        for (var h = 0; h < gameCollisionLayer.rows; h++) {
            gameCollisionMap[h] = new Array();
            for (var i = 0; i < gameCollisionLayer.cols; i++) {
                if (jQuery.type(gameCollisionLayer.layerData[i][h]) != "null") {
                    gameCollisionMap[h].push(1);
                }
                else {
                    gameCollisionMap[h].push(0);
                }
            }
        }
        // start and end of path
        var pathStart = [playerTile.row, playerTile.col];
        var pathEnd = [clickedTile.row, clickedTile.col];
        // use pathfinding to get an array with the fasted non blocked route
        var currentPath = findPath(gameCollisionMap, pathStart, pathEnd);

        //Should move player to next tile by iterating over the tiles in the path array
        for (var im = 0; im < currentPath.length; im++) {
            var prevTile;
            if (im == 0) {
                prevTile = currentPath[im];
            }
            var currentTile = currentPath[im];
            var moveY = currentTile[1] - prevTile[1];
            var moveX = currentTile[0] - prevTile[0];
            if (moveX > 0) { //left
                player[0].renderable.setCurrentAnimation('left');
                player[0].direction = 'left';
                player[0].vel.x -= 32;
                player[0].updateMovement();
            } else
            if (moveX < 0) {
                player[0].vel.x += 32; //right
                player[0].renderable.setCurrentAnimation('right');
                player[0].direction = 'right';
                player[0].updateMovement();
            } else
            if (moveY < 0) { //down
                player[0].vel.y -= 32;
                player[0].renderable.setCurrentAnimation('down');
                player[0].direction = 'down';
                player[0].updateMovement();
            } else
            if (moveY > 0) { //up
                player[0].vel.y += 32;
                player[0].renderable.setCurrentAnimation('up');
                player[0].direction = 'up';
                player[0].updateMovement();
            }
            prevTile = currentPath[im];
        }
        player[0].vel.y = 0;
        player[0].vel.x = 0;
        player[0].renderable.setCurrentAnimation('down');
        player[0].direction = 'down';
        player[0].updateMovement();
    }

[Jay Oster]

You need to use a simple state machine to advance through the A* array. Your update method just implements a function that does the following:

1. Initialize state machine (start at index 1; index 0 has the current position, so ignore it)
2. Get current "destination" from A* array (using index)
3. Set animation direction based on difference between current location and destination
4. Set velocity based on difference between current location and destination)
5. Do nothing until object position >= destination
6. Increment index
7. If A* array hasn't been fully walked, go to step 2

This state machine really only has two states:

1. choose-next-direction state
2. walking state (the "do nothing" part)

The first step always advances immediately to the second step, and the second step does not advance until the object reaches its destination. I suppose you could also say there are two implied states; the initialization step, and the final step. But these can actually occur entirely outside of the state machine itself.

Here's some pseudo-code to get you started:

// Start state machine ... do this on click
this.step = 1;
this.index = 1;

 

// Initialize ... do this in the object.init() method
this.step = 0;
this.index = 0;

 

// State machine logic ... do this in the object.update() method
switch (this.step) {
    case 1:
        // Get destination from A*
        // Expects an object with `x` and `y` properties expressed in pixels
        this.dest = this.astar[this.index++];

        // Determine direction and set velocity
        if (this.dest.x != this.pos.x) {
            // Direction is left or right
            this.velocity = {
                x : (this.dest.x - this.pos.x).clamp(-1, 1) * this.accel.x,
                y : 0
            };
            this.dir = this.velocity.x < 0 ? "left" : "right";
        }
        else {
            // Direction is up or down
            this.velocity = {
                x : 0,
                y : (this.dest.y - this.pos.y).clamp(-1, 1) * this.accel.y
            };
            this.dir = this.velocity.y < 0 ? "up" : "down";
        }

        // Set animation
        this.renderable.setCurrentAnimation("walk_" + this.dir);

        // Advance to next state
        this.step++;

        // FALL THROUGH!

    case 2:
        // Set actual velocity
        this.vel.copy(this.velocity);
        this.vel.scale(new me.Vector2d(me.timer.tick, me.timer.tick));

        this.updateMovement();

        // Advance to next step in state machine
        function nextStep() {
            // To state 0 if there is more A*, else state 0 (do nothing)
            this.step = (this.index < this.astar.length) ? 1 : 0;

            // Force position to destination
            this.pos.copy(this.dest);
        }

        // Determine if object has reached its destination
        switch (this.dir) {
            case "up": if (this.pos.y <= this.dest.y) nextStep(); break;
            case "down": if (this.pos.y >= this.dest.y) nextStep(); break;
            case "left": if (this.pos.x <= this.dest.x) nextStep(); break;
            case "right": if (this.pos.x >= this.dest.x) nextStep(); break;
        }

        break;
}

[Rolf Veinø Sørensen]

thank you for the awsome reply.

I have created a small RPG based on your example. If I walk around for a while or change level is seems like the screenupdating is broken and only when i alt-tab between windows the game movement is beeing updated.

I have placed the mouseup on main game and the other stuff on the mainplayer.

any suggestions on how to fix the broken screenupdating?

Testsite: http://easymodules.net/Games/Ragnarok

Planned to be an open source MMORPG using Microsoft MVC, Webapi, knockout.js, jquery and melonJS ;-)

Global vars:

var stateMachineStep = 0;

var stateMachineIndex = 0;

var stateMachinePath = new Array();

var stateMachineCurrentMoveTile = new Array();

game.PlayerEntity = me.ObjectEntity.extend({

 

    init: function (x, y, settings) {

        stateMachineStep = 0;

        stateMachineIndex = 0;

        stateMachinePath = new Array();

        stateMachineCurrentMoveTile = new Array();

        // call the constructor

        this.parent(x, y, settings);

        // set the walking speed

        this.setVelocity(5, 5);

        // disable gravity

        this.gravity = 0;

        

        // set the display to follow our position on both axis

        me.game.viewport.follow(this.pos, me.game.viewport.AXIS.BOTH);

        // Set animations

        this.renderable.addAnimation("down", [0]);

        this.renderable.addAnimation("left", [4]);

        this.renderable.addAnimation("up", [12]);

        this.renderable.addAnimation("right", [8]);

        this.renderable.addAnimation("walk_down", [0, 1, 2, 3]);

        this.renderable.addAnimation("walk_left", [4, 5, 6, 7]);

        this.renderable.addAnimation("walk_up", [12, 13, 14, 15]);

        this.renderable.addAnimation("walk_right", [8, 9, 10, 11]);

    },

    update: function() {

        //if (me.input.isKeyPressed('touch')) {

            // Set the player variable

            var player = me.game.getEntityByName("mainPlayer")[0];

            switch (stateMachineStep) {

            case 1:

                // Get destination from A*

                    // Expects an object with `x` and `y` properties expressed in pixels

                stateMachineCurrentMoveTile = stateMachinePath[stateMachineIndex++];

                if (typeof stateMachineCurrentMoveTile === 'undefined') {

                    stateMachineStep = 0;

                    stateMachineIndex = 0;

                }

                else {

                // Determine direction and set velocity

                if (stateMachineCurrentMoveTile.x != player.pos.x) {

                    // Direction is left or right

                    player.velocity = {

                        x: (stateMachineCurrentMoveTile.x - player.pos.x).clamp(-1, 1) * player.accel.x,

                        y: 0

                    };

                    player.dir = player.velocity.x < 0 ? "left" : "right";

                } else {

                    // Direction is up or down

                    player.velocity = {

                        x: 0,

                        y: (stateMachineCurrentMoveTile.y - player.pos.y).clamp(-1, 1) * player.accel.y

                    };

                    this.dir = this.velocity.y < 0 ? "up" : "down";

                }

                // Set animation

                player.renderable.setCurrentAnimation("walk_" + player.dir);

                

                

                // Advance to next state

                stateMachineStep++;

                }

            // FALL THROUGH!

            case 2:

                // Set actual velocity

                player.vel.copy(player.velocity);

                player.vel.scale(new me.Vector2d(me.timer.tick, me.timer.tick));

                player.updateMovement();

                // Advance to next step in state machine

                function nextStep() {

                    // To state 1 if there is more A*, else state 0 (do nothing)

                    stateMachineStep = (stateMachinePath != null && stateMachineIndex < stateMachinePath.length) ? 1 : 0;

                    // Force position to destination

                    player.pos.copy(stateMachineCurrentMoveTile);

                }

                // Determine if object has reached its destination

                switch (player.dir) {

                case "up":

                    if (player.pos.y <= stateMachineCurrentMoveTile.y) nextStep();

                    break;

                case "down":

                    if (player.pos.y >= stateMachineCurrentMoveTile.y) nextStep();

                    break;

                case "left":

                    if (player.pos.x <= stateMachineCurrentMoveTile.x) nextStep();

                    break;

                case "right":

                    if (player.pos.x >= stateMachineCurrentMoveTile.x) nextStep();

                    break;

                }

                break;

            }

            // check for collision

            me.game.collide(player);

    }

    

});

game.PlayScreen = me.ScreenObject.extend(

{

    init: function () {

    },

    onResetEvent: function () {

        // stuff to reset on state change

        // bind keys

        //me.input.bindKey(me.input.KEY.ENTER, "action");

        //me.input.bindKey(me.input.KEY.SPACE, "action");

        me.input.bindKey(me.input.KEY.Q, "touch");

        me.input.bindMouse(me.input.mouse.LEFT, me.input.KEY.Q);

        // bind mouse

        me.input.registerMouseEvent('mouseup', me.game.viewport, this.onMouseUpEvent.bind(this));

        // add music

        me.audio.playTrack("Aaron_Krogh_162_Pre_Boss_Battle_Tension");

        me.levelDirector.loadLevel("area_001");

        // add a default HUD to the game mngr

        me.game.addHUD(0, 500, 960, 100, '#000000');

        // add a new HUD item 

        me.game.HUD.addItem("gold", new game.GoldObject(100, 10));

        // make sure everyhting is in the right order

        me.game.sort();

    },

    onDestroyEvent: function () {

        me.input.unbindKey(me.input.KEY.ENTER);

        me.input.unbindKey(me.input.KEY.SPACE);

        me.input.unbindKey(me.input.KEY.Q);

        me.input.unbindMouse(me.input.mouse.LEFT);

        me.input.releaseMouseEvent('mouseup', me.game.viewport);

        // remove the HUD

        me.game.disableHUD();

    },

    onMouseUpEvent: function () {

        var mouseX = me.game.viewport.pos.x + me.input.mouse.pos.x;

        var mouseY = me.game.viewport.pos.y + me.input.mouse.pos.y;

        var background = me.game.currentLevel.getLayerByName("background"); //Background always have a tile everywhere on the map

        var gameCollisionLayer = me.game.currentLevel.getLayerByName("collision");

        var gameCollisionMap = new Array();

        var player = me.game.getEntityByName("mainPlayer");

        var playerX = player[0].collisionBox.pos.x;

        var playerY = player[0].collisionBox.pos.y;

        var playerTile = background.getTile(playerX, playerY);

        var clickedTile = background.getTile(mouseX, mouseY);

        function convertToPixel(a, d) {

            var b = Math.floor(a * 32);

            var c = Math.floor(d * 32);

            return {

                x: b,

                y: c

            };

        }

        //Create an 2d array with all the tiles as 0 or 1 for collision

        for (var h = 0; h < gameCollisionLayer.rows; h++) {

            gameCollisionMap[h] = new Array();

            for (var i = 0; i < gameCollisionLayer.cols; i++) {

                if (jQuery.type(gameCollisionLayer.layerData[i][h]) != "null") {

                    gameCollisionMap[h].push(1);

                }

                else {

                    gameCollisionMap[h].push(0);

                }

            }

        }

        // start and end of path

        var pathStart = [playerTile.row, playerTile.col];

        var pathEnd = [clickedTile.row, clickedTile.col];

        // use pathfinding to get an array with the fasted non blocked route

        var currentPath = findPath(gameCollisionMap, pathStart, pathEnd);

        var currentPathInPixels = new Array();

        

        for (var ix = 0; ix < currentPath.length; ix++) {

            var curTile = currentPath[ix];

            // Debug

            //background.setTile(curTile[1], curTile[0], 7);

            var currentPix = convertToPixel(curTile[1], curTile[0]);

            

            currentPathInPixels.push(currentPix);

        }

        if (typeof currentPathInPixels === "undefined" || currentPathInPixels.length === 0) {

            stateMachinePath = null;

            stateMachineIndex = 0;

            stateMachineStep = 0;

        } else {

            stateMachinePath = currentPathInPixels;

            stateMachineIndex = 1;

            stateMachineStep = 1;

        }

    }

});

[melonJS]

You need to return true from your entity update function.

That's a feature of melonjs, as If no object are returning true, the engine wil, consider that there is nothing to update and won't redraw the screen (that helps sometimes in saving a few fps here and there),

[Rolf Veinø Sørensen]

Thank you this seems to work for me. Just for others to reference this is the playerEntity that have changed with a few animations and the return true or false on the player.

game.PlayerEntity = me.ObjectEntity.extend({

    init: function (x, y, settings) {

        stateMachineStep = 0;

        stateMachineIndex = 0;

        stateMachinePath = new Array();

        stateMachineCurrentMoveTile = new Array();

        // call the constructor

        this.parent(x, y, settings);

        // set the walking speed

        this.setVelocity(5, 5);

        // disable gravity

        this.gravity = 0;

        this.firstUpdates = 2;

        this.direction = 'down';

        

        // set the display to follow our position on both axis

        me.game.viewport.follow(this.pos, me.game.viewport.AXIS.BOTH);

        // Set animations

        this.renderable.addAnimation("down", [0]);

        this.renderable.addAnimation("left", [4]);

        this.renderable.addAnimation("up", [12]);

        this.renderable.addAnimation("right", [8]);

        this.renderable.addAnimation("walk_down", [0, 1, 2, 3]);

        this.renderable.addAnimation("walk_left", [4, 5, 6, 7]);

        this.renderable.addAnimation("walk_up", [12, 13, 14, 15]);

        this.renderable.addAnimation("walk_right", [8, 9, 10, 11]);

    },

    update: function() {

            // Set the player variable

        var player = me.game.getEntityByName("mainPlayer")[0];

        switch (stateMachineStep) {

            case 0:

                if (typeof player.dir === 'undefined') {

                    player.renderable.setCurrentAnimation("down");

                } else {

                    player.renderable.setCurrentAnimation(player.dir);

                }

                break;

        // update animation if necessary

        if (player.vel.x != 0 || player.vel.y != 0) {

            // update object animation

            player.parent();

            return true;

        }

        // Set animation

        if (typeof player.dir === 'undefined') {

            player.renderable.setCurrentAnimation("down");

            player.direction = 'down';

        } else {

            player.renderable.setCurrentAnimation(player.dir);

            player.direction = player.dir;

        }

        player.updateMovement();

        return false;

    }

});

I hope others will find this simple and working astar example useful for making games...

[Rolf Veinø Sørensen]

Funny it seems to be working for about a minute or two then just stops working no error

Am I using the return statement wrong?

                return false;

        return false;

    }

});

[Jason Oster]

You need to use the 'this' keyword on all your state machine variables. Without that, you are modifying the same global variables from multiple objects. Not good. I don't know if that will fix the specific problem (it might) but it will definitely fix a big problem in the code.

--
You received this message because you are subscribed to a topic in the Google Groups "melonJS - A lightweight HTML5 game engine" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/melonjs/5BbT7QhVtKI/unsubscribe?hl=en.
To unsubscribe from this group and all its topics, send an email to melonjs+u...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Rolf Veinø Sørensen]

Do I need to move the mouseUp code from the playScreen object to the mainplayer object?

If the mouseUp should stay on the playScreen then how to reference the variables that are in this scope on mainplayer?

[Jason Oster]

Your update method has a 'player' variable which should also be 'this'. And every member of the player object is globally accessible using the same code that you currently have for setting up that 'player' variable.

[Jay Oster]

I can't actually debug the "it stops working after x minutes" problem, because the code on your server is minified. :( And actually I can't get it to stop working entirely.

I did, however, find that on the second screen, there's a point that when crossed, means you cannot get back to the right side of the map. Here's a screenshot that illustrates:

The pink region on the right side is where I walked immediately to the left (going for the cave). Now I cannot get back to the right side... You can see I've traversed every accessible piece of land on the left side; as long as I click within this region, it works as expected. If I click on the right side ... nothing. It looks like the coordinate system is offset, or there is some code preventing me from initiating the pathfinding to the right side.

[Rolf Veinø Sørensen]

Thank you for the bugtest, I will try and create two maps with same size this evening and see if that fixes the movement on map 2 problem. Also I will try to adjust boundingbox on mainplayer so its less than tile size.

I will put the code on github tonight or tomorrow.

[Rolf Veinø Sørensen]

Fixed part of the problem with the pathfinding not always finding the route (read below)
However I suspect the problem with map2 is happening because the melonjs teleport transfers the player to a different location on the map than the mouseup/pathfinding method expects because it when the trigger is fired still have the player location from map 1.
To test I think ill add key move support so I can "manually" walk back from map2 to map1 and see if the pathfinding now gets screwed on map1.

The pathfinding method from the tutorial i mentioned was only handling equal square levels correctly. didnt read the comments like I SHOULD have done ;-)

    // keep track of the world dimensions
    // Note that this A-star implementation expects the world array to be square:
    // it must have equal height and width. If your game world is rectangular,
    // just fill the array with dummy values to pad the empty space.
    var worldWidth = world[0].length;
    var worldHeight = world.length;
    var worldSize =    worldWidth * worldHeight;

I changed it to this instead:

    // keep track of the world dimensions
    // Note that this A-star implementation expects the world array to be square:
    // it must have equal height and width. If your game world is rectangular,
   
    var worldWidth = world[0].length;
    var worldHeight = world.length;
    // just fill the array with dummy values to pad the empty space.
    if (worldHeight != worldWidth) {
        if(worldWidth < worldHeight) {
            //Create blocked cols foreach row that is missing to create same width as height
            for (var wh = 0; wh <= worldHeight; wh++)
            {
                for (var whc = 0; whc < worldHeight - worldWidth; whc++) {
                    world[wh].push(1);
                }
            }
        } else {
            //Create blocked rows that are missing to make the array equal square in h and w
            for (var ww = worldHeight++; ww > worldWidth; ww++) {
                world.push(ww);
                for(var wwc = 0; wwc < worldWidth;wwc++) {
                    world[ww].push(1);
                }
            }
        }
    }

[Rolf Veinø Sørensen]

Still got the bug but I have now created a simple html page and wrapped it so it can run for anyone who feels like playing with it.
 (I am running it normally using MS MVC with Razor and Web.Optimizations so it minifies auto but debugs in full js. The MVC will be released at a later and more stabile time)

Download

[Jay Oster]

The problem isn't in the touch code at all. The code that tries to turn the map data into a square is just not working correctly. Specifically, this:

            //Create blocked rows that are missing to make the array equal square in h and w
            for (var ww = worldHeight++; ww > worldWidth; ww++) {
                world.push(ww);
                for(var wwc = 0; wwc < worldWidth;wwc++) {
                    world[ww].push(1);
                }
            }

At this point, worldHeight is always < worldWidth, so the for-loop body never executes. And the body doesn't look quite right, either...

for (var ww = worldHeight; ww < worldWidth; ww++) {

    world.push(new Array());

    for (var wwc = 0; wwc < worldWidth; wwc++) {

        world[ww].push(1);

    }

}

Changing those two lines fixes the clickable area in map 2.

[Rolf Veinø Sørensen]

Awsome in my attempt to fix the strange error i created a new one :-p

TY for the help it looks to me like everything concerning Astar is now working. 

Hope others can make use of this example 

I have added a few minor things to help beeing a dev.

the melonjs debugger module

path icons to be drawn when path has been calculated for cool effect or debugging

Example on download link have been updated!