# A* Pathfinding math for 2D, oblique style game

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;
/*
*/
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?

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)