Warg Glargle Barg Fargle (aka My A* is Broked)

[Draco18s]

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:

Code: [Select]

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

Code: [Select]

//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:

Code: [Select]

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


[Draco18s]

Sometime all one needs is someone to talk to while trying things and show them what it's doing and what it should be doing.

@..@

(It works now)