Background:

I programmed my own damn A* algorithm. It worked like a dream (well as much of a dream as A* is when it's hellishly greedy).

Now I'm trying to get it to use Jump Point Search instead of basic greedy-search.

(

Overview of JPS)

Problem is, it isn't greedy

*enough* and I can't figure out why.

I know it has to do with the JSP on the diagonal, as I've been able to walk through the nodes it selects manually from a failed search and on a diagonal it is incredibly prone to failure.

Here's the relevant section from the main loop:

`dx = jsx - current.parent.x;`

dy = jsy - current.parent.y;

if(Mathf.Abs(dx) == Mathf.Abs(dy)) {

//diagonal

var jpx1:int;

var jpy1:int;

var jpx2:int;

var jpy2:int;

var jumpPointA:boolean = false;

var jumpPointB:boolean = false;

var jumpPointC:boolean = false;

do {

jsx += dx;

jsy += dy;

jpx1 = jsx;

jpy1 = jsy;

jpx2 = jsx;

jpy2 = jsy;

if(map[jsx-dx][jsy].wall || map[jsx][jsy-dy].wall) {

jumpPointC = true;

}

interesting = false;

if(! map[jpx1+dx][jpy1].wall) {

while(!interesting) {

jpx1 += dx;

jpy1 += 0;

interesting = map[jpx1+dx][jpy1].wall || map[jpx1][jpy1+dx].wall || map[jpx1][jpy1-dx].wall;

} ;

if(map[jpx1][jpy1+dx].wall || map[jpx1][jpy1-dx].wall) {

jumpPointA = true;

}

Debug.Log("Quitting A because (" + (jpx1+_x) + "," + (jpy1+_y) + ")");

}

interesting = false;

if(!map[jpx2][jpy2+dy].wall) {

while(!interesting) {

jpx2 += 0;

jpy2 += dy;

interesting = map[jpx2][jpy2+dy].wall || map[jpx2+dy][jpy2].wall || map[jpx2-dy][jpy2].wall;

} ;

if(map[jpx2+dy][jpy2].wall || map[jpx2-dy][jpy2].wall) {

jumpPointB = true;

}

Debug.Log("Quitting B because (" + (jpx2+_x) + "," + (jpy2+_y) + ")");

}

} while(!jumpPointA && !jumpPointB && !jumpPointC);

neighbor = addPoint(jsx, jsy, current); //next jump point

if(jumpPointA)

addPoint(jpx1, jpy1, neighbor); //horizontal neighbor

if(jumpPointB)

addPoint(jpx2, jpy2, neighbor); //vertical neighbor

if(jumpPointC) { //Forced Neighbours

if(map[jsx-dx][jsy].wall) {

addPoint(jsx-dx, jsy+dy, neighbor);

}

if(map[jsx][jsy-dy].wall) {

addPoint(jsx+dx, jsy-dy, neighbor);

}

}

}

And ancillary function

`//stripped down, as I think this function is fine`

function addPoint(dx:int, dy:int, p:PathPoint):PathPoint {

//heuristic cost check

//**these functions may need to be checked for accuracy**

var cost:float = heuristic(current) + movementcost(current, neighbor);

//check if p exists in OPEN

//check if p exists in CLOSED

//add p to OPEN

}

And a double check that these are correct:

`const D = 1;`

const D2 = 1.4142135;

private function heuristic(node:PathPoint):float {

var dx = Mathf.Abs(node.x - goal.x);

var dy = Mathf.Abs(node.y - goal.y);

return D * (dx + dy) + (D2 - 2 * D) * Mathf.Min(dx, dy);

}

private function movementcost(c:PathPoint, n:PathPoint):float {

var dx = c.x - n.x;

var dy = c.y - n.y;

return Mathf.Sqrt(dx*dx + dy*dy);

}