A* Pathfinding math for 2D, oblique style game

Question

I'm making a 2D, oblique-styled RPG game and am implementing A* pathfinding for NPCs. The game is on canvas, using melonJS engine and sprites not confined to a 'grid'. I'm having a hard time converting my path (array of x,y coordinates) to my game world x,y coordinates for the sprite.

My game world is a 100 x 100 Tiled tilemap of 64x64px tiles.

I'm using Qiao's A*, which has me create a grid of 0's (walkable) and 1's (unwalkable):

var matrix = [
    [0, 0, 0, 1, 0],
    [1, 0, 0, 0, 1],
    [0, 0, 1, 0, 0],
];
var grid = new PF.Grid(matrix);

Then create the path based on a starting position of 1, 2 (x,y) and ending position of 4, 2 (x,y):

var finder = new PF.AStarFinder();
var path = finder.findPath(1, 2, 4, 2, grid);

Which returns an array of coordinates:

[ [ 1, 2 ], [ 1, 1 ], [ 2, 1 ], [ 3, 1 ], [ 3, 2 ], [ 4, 2 ] ]

Obviously, since my game world consists of 100x100 64x64px tiles, the NPC's coordinates might be something like (1000, 1500). So my thought was to

• get the start world coordinates of the NPC (let's say 1000, 1500),
• divide by 64 to account for px width of grid,
• choose a end location (startX+500, startY+200), divide those by 64 too

• when the path is generated for the 100x100 grid, convert the paths back to world coordinates by multiplying each path coordinate x,y by 64

  A_Star : function () {
      var api = {};
  
      api.init = function () {
  
          this.grids = this.createGrid();
  
          this.grid = new PF.Grid(this.grids[0]);
  
          var finder = new PF.AStarFinder();
  
          var converted_start_x = Math.floor(game.data.NPCX/64);
          var converted_start_y = Math.floor(game.data.NPCY/64);
  
          //arbitrary end location at x+500, y+200
          var converted_end_x = Math.floor(500/64);
          var converted_end_y = Math.floor(200/64);
  
          /*
              thePath returns array of x,y coordinates
              Passing in grid coordinates for x, y (so grid[1][2]... etc
              Need to translate the NPC's x,y world coordinates (2000, 1700) to grid coordinates
  
           */
  
          var thePath = finder.findPath(converted_start_x, converted_start_y, (converted_start_x+converted_end_y), (converted_start_y+converted_end_y), this.grid);
  
          /*
              Convert pathing back to actual world coordinates (*64)
           */
  
          for (var i = 0; i < thePath.length; i++) {
              thePath[i][0] = thePath[i][0] * 64;
              thePath[i][1] = thePath[i][1] * 64;
          }
          game.data.getPath = thePath;
  
          game.data.STARTPATH = true;
      };
  

Create the grid:

        api.createGrid = function () {
            var grid = [];
            var xLoc = 50;
            var yLoc = 50;

            for (var y = 0; y < 100; y++) {
                grid[y] = [];
                nodeGrid[y] = [];
                for (var x = 0; x < 100; x++) {
                    var type = 'walkable';
                    var val = 0;

                    //Set an arbitrary wall of unwalkable tiles in grid
                    if (x === 4 && (y === 3 || y === 4 || y === 5 || y === 6)) {
                        val = 1; //1 means unwalkable
                    }
                    grid[y][x] = val;
                    xLoc+=64;
                }
                xLoc = 50;
                yLoc += 64;
            }

            return [
                grid,
                nodeGrid
            ];
        };

NPC update method: Then, in my NPC class,

• set a counter to keep track of each path coordinate...
• once that path coordinate is reached by the NPC, increment counter so the player will start heading to the next path coordinate in the array

...

NPC class {
...
  update: function(delta) {
    var angle = 0;
    /*
        Keep loading next set of path coordinates to angle
     */
    if (game.data.STARTPATH) {
        if (this.counter < game.data.getPath.length) {
            angle = this.angleToPoint(new me.Vector2d(game.data.getPath[this.counter][0], game.data.getPath[this.counter][1]));
            if (this.pos.x <= game.data.getPath[this.counter][0] && this.pos.y <= game.data.getPath[this.counter][1]) {
                this.counter++;
            }
        } else {
            console.log('NPC has reached destination...');
        }
        this.body.vel.set(Math.cos(-angle) * .9, -Math.sin(-angle) * .9);

        this.body.update(delta);

        return (this._super(me.Entity, 'update', [delta]) || this.body.vel.x !== 0 || this.body.vel.y !== 0);
    }
},

My questions: The pathing seems quite wonky... so I'm obviously doing something wrong.

• Am I correct in dividing by 64px to convert to possible grid coordinates in the 100x100 matrix, getting path of coordinates, then multiplying back by 64px?
• What other recommendations would you have to convert path coordinates then set the path for the player?

Answer 1

To make it easier for you to switch between world coordinates and grid coordinates, you should make two functions, projectToWorld and projectToGrid.

pseudo code:

/**
* returns the topleft position of a given grid coordinate. 
*/
function projectToWorld(gridX, gridY) {    
    return new Vector2(TILE_WIDTH * gridY, TILE_HEIGHT * gridY);    
}


/**
* returns a grid coordinate by a given world position
*/
function projectToGrid(worldPosX, worldPosY) {    
    int x = Math.Floor(worldPosX / TILE_WIDTH);
    int y = Math.Floor(worldPosY / TILE_HEIGHT);
    return new Vector2(x, y)
}

Now you can translate forth and back when generating the path, for example:

pseudo code:

var endPos = new Vector2(1440, 2020); // world end position to walk to
Vector2 endPosGrid = projectToGrid(endPos.X, endPos.Y);
Vector2 startPosGrid = projectToGrid(NPC.Pos.X, NPC.Pos.Y);

List<Vector2> nodes = finder.findPath(
    startPosGrid.x, startPosGrid.y, endPosGrid.x, endPosGrid.y, grid
);

// since we floored values, the projection gives us a corner but we want the npc to walk to the center :   
float offsetX = TILE_WIDTH / 2f;
float offsetY = TILE_HEIGHT / 2f;

foreach(Vector2 node in nodes) {
    Vector2 worldPos = projectToWorld(node.x, node.y);
    NPC.WalkToPos(worldPos.x + offsetX, worldPos.y + offsetY);
}

Additional info: this is pseudo code (actually a mix of at least three different languages)