Weird behaviour with diagonals enabled

[catigator]

EasyStar.js doesn't seem to take the cost for diagonals into account in my testing, so for paths that should be straight lines it will often go up and then down the diagonals for no reason. Below is some example code where I'm trying to go from point [0,0] to [7,0], which you'd assume would be a straight line, but for some reason easyStar makes a detour to [6,1] instead of going through [6,0].

Am I doing something wrong here?

Code:

zeroGrid = [];
for (i = 0; i < 10; i++) {
zeroGrid[i] = [];
for (j = 0; j < 10; j++) {
zeroGrid[i][j] = 0;
}
}

easystar = new EasyStar.js();
easystar.enableDiagonals();
easystar.setGrid(zeroGrid);
easystar.setAcceptableTiles([0]);

var mypath;
easystar.findPath(0, 0, 7, 0, function( path ) {
if (path === null) {
//alert("Path was not found.");
} else {
mypath = path;
//alert("Path was found. The first Point is " + path[0].x + " " + path[0].y);
}
});

easystar.calculate();

for (i = 0; i < mypath.length; i++) {
console.log("Node " + i + ", x = " + mypath[i].x + ", y = " + mypath[i].y);
} // when i = 6 this prints "Node 6, x = 6, y = 1", I don't know why it doesn't just go through x = 6, y = 0.

Thanks for any help!

[prettymuchbryce]

Hi Catigator. I'm thinking there may be a bug with the distance calculation in the latest version.

Could you try this version, and report back with your results ? I'm interested to know if it still causes issues for you.

https://s3.amazonaws.com/easystar/easystar-0.1.7-test.js

[catigator]

Thanks for the quick reply! That version did fix all the issues I was having.

On very much of a side note, have you thought of implementing any of the smoothing techniques described in http://www.gamasutra.com/view/feature/131505/toward_more_realistic_pathfinding.php ? (most importantly this kind of smoothing: http://www.gamasutra.com/features/20010314/pinter_02.jpg ). On my current project I might have to modify the code to do this stuff myself.

Cheers

[catigator]

Hmm actually it is still making some unnecessary detours sometimes, but much less often than before! I have not yet been able to determine exactly what triggers this behaviour.

[prettymuchbryce]

Hi catigator. If it's not too much trouble could you create an example which I can use to reproduce this detouring behavior ?

[catigator]

Hi again,

Sorry for the late reply, I haven't been by my computer since last time. The example in the code below has some weird detours to y = 12, where it should just stay at y = 13 until the final jump to y = 12.

One sideote is also that it's a bit confusing that setGrid uses the order [y,x] while findPath uses an [x,y] order, might be something worth changing or thinking about! (Though there may very well be a reason for this)

Code:

zeroGrid = [];
for (i = 0; i < 20; i++) {
zeroGrid[i] = [];
for (j = 0; j < 20; j++) {
zeroGrid[i][j] = 0;
}
}

for (var i = 5; i < 10; i++) {

//[y,x]
zeroGrid[12][i] = 1;

}

for (var i = 12; i < 17; i++) {

//[y,x]
zeroGrid[12][i] = 1;

}

easystar = new EasyStar.js();
easystar.enableDiagonals();
easystar.setGrid(zeroGrid);
easystar.setAcceptableTiles([0]);

easystar.setTileCost([0], 1);

var mypath;
// findPath = function(startX, startY ,endX, endY, callback) {
easystar.findPath(18,13,4,12, function( path ) {
if (path === null) {
//alert("Path was not found.");
} else {
mypath = path;
//console.log(path);
//alert("Path was found. The first Point is " + path[0].x + " " + path[0].y);
}
});

easystar.calculate();

for (i = 0; i < mypath.length; i++) {
console.log("Node " + i + ", x = " + mypath[i].x + ", y = " + mypath[i].y);
}

[prettymuchbryce]

catigator,

Your help is much appreciated. I have added both of your examples as unit tests which will help prevent future issues. I think I have resolved this problem. Here is a new file for you to test out.

https://s3.amazonaws.com/easystar/easystar-0.1.7-test2.js

Let me know if you run into further problems. I will be cutting a 0.1.7 release soon with this fix.