### Author Topic: Warg Glargle Barg Fargle (aka My A* is Broked)  (Read 1350 times)

#### Draco18s ##### Warg Glargle Barg Fargle (aka My A* is Broked)
« on: March 11, 2014, 05:16:25 PM »
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 finefunction 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 ##### Re: Everything is Awesome (aka My A* works Now)
« Reply #1 on: March 11, 2014, 10:38:22 PM »
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.

@[email protected]

(It works now)