# 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);

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... 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] = thePath[i] * 64;
thePath[i] = thePath[i] * 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], game.data.getPath[this.counter]));
if (this.pos.x <= game.data.getPath[this.counter] && this.pos.y <= game.data.getPath[this.counter]) {
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?

## 1 Answer

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)